サンプルコード：数独ソルバー

Image from Wikipedia

数独パズルを解くソルバーを Python で実装してみたので、考え方も含めてご紹介します。

きっかけは Awesome Python Newsletter で紹介されていた次の動画です。

• Elegant sudoku solver. The algorithm is only about 10 lines of code.

Python の基本的な道具だけを使って数独を解く方法を順序立ててとてもわかりやすく説明しています。 programatically に数独を解いた経験のある方にとってはなんてことのないことかもしれませんが、やったことの無い方にはとても elegant でおもしろい動画だと思います。

ちなみに、今回説明する方法は上の動画の方法をきっかけ・参考にしていますが、コードの書き方・解き方は若干異なります。

数独をプログラムで解くときのポイント

おそらくここまで読み進めている方は数独がどんなものかはある程度ご存知だと思うので、数独とは何ぞやという説明は割愛します。

数独を解くアルゴリズムに関係するルールだけまとめると以下のとおりです。

• R1. 縦横 9 x 9 のマス（以下「グリッド」）のそれぞれに 1 から 9 の数字を入れられる
• R2. すべてのマスを埋めたら完成
• R3. 同じ行、同じ列、 3 x 3 のブロックに同じ数字を入れることはできない
• R4. 初期状態として、いくつかのマスに数字が入ったグリッドが与えられる

ということで、これをプログラムで解く方法を考えます。

データ構造

まずはデータ構造から。 9 x 9 のマスが必要なので、その状態を表せるデータタイプを用意します。

いちばんかんたんなのは、次のように要素が 1 - 9 の整数からなる 2 次元リスト（入れ子のリスト）を使うことです。空のセルは 0 で表します。

grid1 = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]

シンプルでわかりやすいですね。

ただ、これをそのまま使うよりは、ラップするデータクラスを作っておいた方が後が楽そうなので、今回はそれを用意することにします。

ROWS = COLS = 9
NUMBERS = [x for x in range(1, 9 + 1)]


class Grid:
    """数独のクイズを表すグリッド"""

    _values: List[List[int]]

    def __init__(self, values: List[List[int]]):
        assert isinstance(values, list)
        assert len(values) == ROWS
        for row in values:
            assert isinstance(row, list)
            assert len(row) == COLS

        self._values = values

アサーションをいくつか入れておくとケアレスミスで悩むのを防げそうです。

これは次のような形で使います。

grid1 = Grid([
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
])

これで上の R1 ・ R2 のふたつを実現できそうです。続いてアルゴリズムを考えます。

アルゴリズム

アルゴリズムの全体的な流れは次のとおりです。

• S0. パズルの状態を表すグリッドを渡される
• S1. グリッドのすべての空のセルに対して、現時点で入りうる数字をすべて洗い出す
• S2. 空のセルのうち、入りうる数字が最も少ないセルに仮に数字を入れる
• S3. S2 のグリッドを使って 1 に戻る
• S4. 空のセルがなくなったらパズルが解けたとみなす
• S5. 入りうる数字が無い空のセルが残った場合はそのルートは間違っているので終了

これを実装することで R2 ・ R3 を満たせるはずです。

S3 の部分は再帰を使って書くとよさそうです。

S1 と S2 では、空のセルの抽出、そして入りうる数字のリストアップが必要です。ここをきちんと書かないとうまく再帰が回らずに無限ループに陥ったりします。

再帰の停止条件は S4 と S5 です。

続いてこれをコードで書いていきます。

実装

まずは全体の半擬似コードを書きます。

from typing import List, Set


def main():
    # グリッドを定義してから解く
    grid1 = [...]
    grid = Grid(grid1)
    results = solve_all(grid)
    for r in results:
        print(r)


class Grid:
    """数独のクイズを表すグリッド"""

    _values: List[List[int]]

    def __init__(self, values: List[List[int]]):
        assert isinstance(values, list)
        assert len(values) == ROWS
        for row in values:
            assert isinstance(row, list)
            assert len(row) == COLS

        self._values = values


def solve_all(grid: Grid) -> Set:
    """指定された数独に対する解を全件返す"""
    solutions = set()

    def _solve(grid: Grid):
        # S4. 空のセルがなくなったら正解として追加

        # S1. すべてのセルに対して入りうる数字をリストアップする

        # S2 + S3. 入りうち数字が最も少ないセルに仮に数字を入れて再帰

        # S5. 入りうる数字がひとつも無い空のセルがある場合はそのルートは間違いなので終了

    _solve(grid)

    return solutions


if __name__ == '__main__':
    main()

これでよさそうなので実際のコードを入れていきます。

from __future__ import annotations
from pprint import pformat
from typing import List, Set, Tuple

ROWS = COLS = 9
NUMBERS = [x for x in range(1, 9 + 1)]

def main():
    # グリッドを定義してから解く
    grid1 = [
        [5, 3, 0, 0, 7, 0, 0, 0, 0],
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
        [0, 9, 8, 0, 0, 0, 0, 6, 0],
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
        [0, 0, 0, 0, 8, 0, 0, 7, 9],
    ]

    grid = Grid(grid1)
    results = solve_all(grid)
    for r in results:
        print(r)


class Grid:
    """数独のクイズを表すグリッド"""

    _values: List[List[int]]

    def __init__(self, values: List[List[int]]):
        assert isinstance(values, list)
        assert len(values) == ROWS
        for row in values:
            assert isinstance(row, list)
            assert len(row) == COLS

        self._values = values

    def __hash__(self):
        """hashable 化するための __hash__ 定義

        - set() で利用するため
        """
        return hash(''.join(str(x) for row in self._values for x in row))

    def __str__(self):
        """`print()` で出力されたときの表現を定義する"""
        return '{}(\n{}\n)'.format(type(self).__name__, pformat(self._values))

    def solved(self) -> bool:
        """空セルがなくなったかどうかを判定する"""
        all_values = [x for row in self._values for x in row]
        return 0 not in all_values

    def possible_numbers(self) -> List[Tuple[int, int, List[int]]]:
        """すべての空セルと入りうる数字の組み合わせを全件洗い出す"""
        return [
            (row, col, self._possible_numbers_for_cell(row, col))
            for row, values in enumerate(self._values)
            for col, x in enumerate(values)
            if x == 0
        ]

    def clone_filled(self, row, col, number) -> Grid:
        """特定のセルに指定された値が入った新しい grid を返す"""
        values = [[x for x in row] for row in self._values]
        values[row][col] = number
        return type(self)(values)

    def _possible_numbers_for_cell(self, row, col) -> List[int]:
        row_numbers = [x for x in self._values[row]]
        col_numbers = [row[col] for row in self._values]
        block_numbers = self._block_numbers(row, col)

        return [
            x
            for x in NUMBERS
            if (x not in row_numbers)
            and (x not in col_numbers)
            and (x not in block_numbers)
        ]

    def _block_numbers(self, row, col) -> List[int]:
        row_start = (row // 3) * 3
        col_start = (col // 3) * 3
        return [
            x
            for row in self._values[row_start : row_start + 3]
            for x in row[col_start : col_start + 3]
        ]


def solve_all(grid: Grid) -> Set[Grid]:
    """指定された数独に対する解を全件返す"""
    solutions = set()

    def _solve(grid: Grid):
        # S4. 空のセルがなくなったら正解として追加
        if grid.solved():
            solutions.add(grid)
            return

        # S1. すべてのセルに対して入りうる数字をリストアップする
        possible_numbers = grid.possible_numbers()

        # S2 + S3. 入りうち数字が最も少ないセルに仮に数字を入れて再帰
        row, col, numbers = min(possible_numbers, key=lambda x: len(x[-1]))

        # S5. 入りうる数字がひとつも無い空のセルがある場合はそのルートは間違いなので終了
        if not numbers:
            return

        for number in numbers:
            next_grid = grid.clone_filled(row, col, number)
            _solve(next_grid)

    _solve(grid)

    return solutions


if __name__ == '__main__':
    main()

最大のポイントは _solve() 内の再帰の部分です。

for number in numbers:
    next_grid = grid.clone_filled(row, col, number)
    _solve(next_grid)

clone_filled() の中身は次のとおりにしています。

def clone_filled(self, row, col, number) -> Grid:
    values = [[x for x in row] for row in self._values]
    values[row][col] = number
    return type(self)(values)

Python のリストは再代入のときに参照渡しをするので、 _values を新しい Grid インスタンスと共用すると思わぬ挙動を招きかねません。そのためここでは意図して 2 次元リストを展開して別のリストを作成しています。


ちなみにここは標準ライブラリの deepcopy.deepcopy() を使うとよりシンプルに書けます。

他にも Grid クラスに特殊メソッド __hash__() や __str__() を定義する等細かなポイントはいろいろありますが、興味のある方は読んでみてください。

上のコードを Python 3.7 で実行すると次のような出力が得られます。

Grid(
[[5, 3, 4, 6, 7, 8, 9, 1, 2],
 [6, 7, 2, 1, 9, 5, 3, 4, 8],
 [1, 9, 8, 3, 4, 2, 5, 6, 7],
 [8, 5, 9, 7, 6, 1, 4, 2, 3],
 [4, 2, 6, 8, 5, 3, 7, 9, 1],
 [7, 1, 3, 9, 2, 4, 8, 5, 6],
 [9, 6, 1, 5, 3, 7, 2, 8, 4],
 [2, 8, 7, 4, 1, 9, 6, 3, 5],
 [3, 4, 5, 2, 8, 6, 1, 7, 9]]
)

このパズルの場合は解はただひとつだけですが、例えば次のような空セルが多いパズルだと複数の解があるため、それが全件返されます。

grid2 = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]

出力結果:

Grid(
[[5, 3, 4, 6, 7, 8, 9, 1, 2],
 [6, 7, 2, 1, 9, 5, 3, 4, 8],
 [1, 9, 8, 3, 4, 2, 5, 6, 7],
 [8, 5, 9, 7, 6, 1, 4, 2, 3],
 [4, 2, 6, 8, 5, 3, 7, 9, 1],
 [7, 1, 3, 9, 2, 4, 8, 5, 6],
 [9, 6, 1, 5, 3, 7, 2, 8, 4],
 [2, 8, 7, 4, 1, 9, 6, 3, 5],
 [3, 4, 5, 2, 8, 6, 1, 7, 9]]
)
Grid(
[[3, 4, 5, 6, 7, 8, 9, 1, 2],
 [6, 7, 2, 1, 9, 5, 3, 4, 8],
 [1, 9, 8, 3, 4, 2, 5, 6, 7],
 [8, 5, 9, 7, 6, 1, 4, 2, 3],
 [4, 2, 6, 8, 5, 3, 7, 9, 1],
 [7, 1, 3, 9, 2, 4, 8, 5, 6],
 [9, 6, 1, 5, 3, 7, 2, 8, 4],
 [2, 8, 7, 4, 1, 9, 6, 3, 5],
 [5, 3, 4, 2, 8, 6, 1, 7, 9]]
)

以上です。ということで Python で数独を解くサンプルでした。

冒頭に紹介した動画が非常におもしろいので興味のある方はそちらも見てみてください。

参考

• Python Sudoku Solver - Computerphile - YouTube

Python Tips： Poetry の tips あれこれ

あけましておめでとうございます。

ここで言う Poetry とは Python のパッケージ管理ツールのことです。

• ライブラリ： Poetry

Poetry はアプリケーション開発とパッケージ開発のどちらでも利用できるものですが、私は現状アプリケーション開発のみで Poetry を使っています。そのため、以下にあげるのはすべてアプリケーション開発で Poetry を利用するときの tips です。

この記事では Poetry のバージョン 1.0.0 が対象です。 Poetry はわりと安定している（＝使い方がコロコロと変わりづらい）ツールですが、バージョンが上がるとやり方が変わる可能性があるので参考にされる際はご注意ください。

• venv のファイルをプロジェクトディレクトリの下に置きたい
• venv を作らずグローバルにパッケージをインストールしたい
• アップデート可能なパッケージをチェックしたい
• Poetry 自体をアップデートしたい
• Docker コンテナでインストールしたい
• どんなサブコマンドがあるのか忘れた
• サブコマンドのオプションにどんなものがあるか忘れた
• サブコマンドをタブ補完してほしい

venv のファイルをプロジェクトディレクトリの下に置きたい

→ 設定値 virtualenvs.in-project の値を true に変更します。

すべてのプロジェクトに適用する場合は次のとおりにします。

poetry config virtualenvs.in-project true

カレントプロジェクトにのみ適用する場合は --local オプションを付けます。

poetry config --local virtualenvs.in-project true

設定した値を初期状態にリセットしたいときは poetry config コマンドの --unset オプションを利用します。

グローバルな設定を削除:

poetry config --unset virtualenvs.in-project

プロジェクトローカルな設定を削除:

poetry config --local --unset virtualenvs.in-project

ちなみに、デフォルトでは Poetry は venv のファイルをホームディレクトリ以下の特定のディレクトリに集約して置くようになっています（私の手元の macOS 上で確認すると /Users/USERNAME/Library/Caches/pypoetry/virtualenvs でした）。

参考:

virtualenvs.in-project: boolean

Create the virtualenv inside the project's root directory. Defaults to false.

• virtualenvs.in-project: boolean | Configuration | Documentation | Poetry - Python dependency management and packaging made easy.

venv を作らずグローバルにパッケージをインストールしたい

→ 設定値 virtualenvs.create の値を false にします。

poetry config virtualenvs.create false

この設定が有用な場面はかぎられますが、このオプションの存在を覚えておくといざというときに便利です。

参考:

virtualenvs.create: boolean

Create a new virtual environment if one doesn't already exist. Defaults to true.

• virtualenvs.create: boolean | Configuration | Documentation | Poetry - Python dependency management and packaging made easy.

アップデート可能なパッケージをチェックしたい

→ poetry show コマンドの --outdated オプションを使用します。

poetry show --outdated

実際のアップデート処理を仮実行して確認したい場合は poetry update コマンドの --dry-run オプションが使えます。

poetry update --dry-run

参考:

• show | Commands | Documentation | Poetry - Python dependency management and packaging made easy.

• update | Commands | Documentation | Poetry - Python dependency management and packaging made easy.

Poetry 自体をアップデートしたい

→ poetry self update サブコマンドを使用します。

poetry self update

Poetry のバージョン 1.0.0 未満の頃は self:update というサブコマンドでしたが、変更されたようです。

万が一うまく行かない場合は公式の手順に従っていったんアンインストールしてからインストールし直すと解決する可能性があります。

Docker コンテナでインストールしたい

→ 単純に公式の手順に従ってインストールします。

公式の python:3.8 イメージの上にインストールする場合のサンプルは次のとおりです。

Dockerfile:

どんなサブコマンドがあるのか忘れた

→ サブコマンド無しで単に poetry と打つか help サブコマンドを使用します。

poetry

poetry help

サブコマンドのオプションにどんなものがあるか忘れた

→ poetry help コマンドにサブコマンド名を引数として渡します。

poetry help self

次のような内容が見やすい色付きで出力されます。

USAGE
      poetry self
  or: poetry self update [--preview] []

COMMANDS
  update
    Updates Poetry to the latest version.

                The version to update to.

    --preview            Install prereleases.

GLOBAL OPTIONS
  -h (--help)            Display this help message
  -q (--quiet)           Do not output any message
  -v (--verbose)         Increase the verbosity of messages: "-v" for normal output, "-vv" for more verbose output and "-vvv" for debug
  -V (--version)         Display this application version
  --ansi                 Force ANSI output
  --no-ansi              Disable ANSI output
  -n (--no-interaction)  Do not ask any interactive question

これを読んでもわからないことがあれば公式のドキュメントを読みます:

• Commands | Documentation | Poetry - Python dependency management and packaging made easy.

サブコマンドをタブ補完してほしい

→ poetry completions コマンドの出力を起動時のスクリプトに追加します。

公式で紹介されている macOS + Homebrew を使用している場合のサンプルは次のとおりです。

# Bash (macOS/Homebrew)
poetry completions bash > $(brew --prefix)/etc/bash_completion.d/poetry.bash-completion

参考:

• Enable tab completion for Bash, Fish, or Zsh
  | Introduction | Documentation | Poetry - Python dependency management and packaging made easy.

古い設定値を削除したい

→ Poetry のバージョンアップによって使われなくなった設定値を削除するには、設定値が格納されたファイルを直接編集して該当行を削除します。これは poetry config --unset が効かない場合のみ使用します。

私が確認した環境（ macOS / CentOS 7 ）ではそのファイルは ~/.config/pypoetry/config.toml にありました。拡張子が示すとおり中身は TOML フォーマットです。

vi ~/.config/pypoetry/config.toml

以上 Poetry の tips 集でした。

Python Tips： Python で FTP のアップロードを自動化したい

Python で FTP のファイルアップロード処理を行う方法についてです。

これは SSH/SCP が使えない古風なレンタルサーバーへのファイルアップロードや CMS のデプロイ等を自動化したいときに便利かと思います。

早速結論ですが、 Python で FTP を行うには ftplib という標準ライブラリを使うのがかんたんです。

• ftplib FTP protocol client — Python documentation

ただし ftplib はじゃっかんインタフェースがあまり人間向けでないというか直感的ではありません（ FTP の技術に疎い者の感想です）。

（ちなみにここでご紹介するのは ftplib の使い方のごく一部なので、以下で取り上げる使い方が各操作に対する唯一の方法というわけではありません）

早速サンプルを見てみましょう。

FTP 接続する

FTP 接続するには ftplib ライブラリのクラス FTP FTP_TLS のどちらかを使います。クラス名が示すとおり FTP は通常の FTP 用、 FTP_TLS は FTP over TLS/SSL （いわゆる FTPS ）用です。

いまどき通常の FTP を使うのはナニなので、ここからは FTPS を中心に説明していきます。

FTPS 接続をするには FTP_TLS クラスにホスト名・ユーザー・パスワードを渡して使用します。 FTP_TLS は組み込み関数の open() と同じような形で、コンテキストマネージャとして使用することもできます。

FTP_TLS のインスタンスの retrlines() メソッドに特定の引数を渡して実行すると、サーバーのファイル一覧を取得することができます。

# ファイル一覧をメタ情報付きで取得する
with FTP_TLS(host='example.com', user='username', passwd='password') as ftp:
    ftp.retrlines('LIST')

# ファイル一覧をファイル名だけ取得する
with FTP_TLS(host='example.com', user='username', passwd='password') as ftp:
    ftp.retrlines('NLST')
# 標準出力に次のような出力が出る:
# home
# cgi-bin
# cgi-def
# app-def
# data
# .well-known
# log

FTP でファイルをアップロードする

ファイルをアップロードするには FTP_TLS インスタンスの storbinary() メソッドを使用します。

from ftplib import FTP_TLS


def push(remote_path: str, local_path: str) -> None:
    """FTPS でファイルを 1 件アップロードする"""
    with FTP_TLS(host='example.com', user='username', passwd='password') as ftp:
        ftp.storbinary('STOR {}'.format(remote_path), open(local_path, 'rb'))


# ローカルの `.env.production` ファイルを `.env` という名前でアップロードする
push(remote_path='.env', local_path='.env.production')

storbinary() の第 1 引数は 'STOR アップロード先のファイルパス' というフォーマットの文字列で、第 2 引数はバイナリモードで開かれた読み込み可能なファイルオブジェクトです。

ちなみに、指定されたリモートパスの親ディレクトリが存在しない場合はエラーとなります。そのため、親ディレクトリが存在するかどうかわからない深い階層にファイルをアップロードしたい場合は、事前に親ディレクトリを作成する必要があります。

ディレクトリの作成には FTP_TLS インスタンスの mkd() メソッドが使えるので、たとえば次のような関数を書くと、深い階層の場所にファイルをアップロードすることができます。

from ftplib import FTP_TLS, error_perm


def push(remote_path: str, local_path: str, create_parents: bool=False) -> None:
    """FTPS でファイルを 1 件アップロードする（親ディレクトリ作成のオプション付き）"""
    with FTP_TLS(host='example.com', user='username', passwd='password') as ftp:
        if create_parents:
            parts = remote_path.split('/')
            chain = ['/'.join(parts[:n]) for n in range(len(parts))][1:]

            for part in chain:
                try:
                    ftp.mkd('{}'.format(part))
                # ディレクトリがすでに存在する場合はエラーがあがるのでキャッチしてスルー
                except error_perm as e:
                    pass

        ftp.storbinary('STOR {}'.format(remote_path), open(local_path, 'rb'))


# ローカルの `settings/prod.py` ファイルを `data/config/settings/prod.py` というパスにアップロードする
push(remote_path='data/config/settings/prod.py', local_path='settings/prod.py')

FTP でディレクトリをまるごとアップロードする

それひとつで特定のディレクトリ以下のファイルをまるごとアップロードできるようなメソッドは（私が知るかぎり） ftplib にはありません。そのため、特定のディレクトリをまるごとアップロードしたいような場合は、事前に対象ディレクトリ以下のファイルをリストアップして、それらを 1 件ずつアップロードする、という処理が必要になります。

具体的には、次のような感じでローカルのファイルを集めてその結果を上の push() 関数に渡す、といった形になるでしょうか。

from pathlib import Path
from typing import Generator, List


def get_local_files(target: str) -> Generator[Path, None, None]:
    """特定のディレクトリ以下のファイルをすべて取得する

    - リストアップの順番は DFS （深さ優先探索）
    """
    root = Path(target)
    if not root.is_dir():
        raise Exception('Only directories can be passed.')

    edges = [root]
    while edges:
        item = edges.pop()
        children = [x for x in item.iterdir()]
        dirs = [x for x in children if x.is_dir()]
        files = [x for x in children if x.is_file()]
        edges.extend(dirs)
        yield from files


for file in get_local_files(target='.'):
    push(remote_path=str(file), local_path=str(file))

今回ご紹介したのはあくまでもイメージを伝えるためのサンプルです。 FTP は操作に誤るとクリティカルな事故につながることもあるので、くれぐれもそのまま使用しないよういしてください。参考にされる際は自己責任でお願いします。

以上です。

私はとりあえず以上のことができればやりたいこととしては十分だったのでこれ以上は調べませんでしたが、冒頭に述べたとおり、ここでご説明したのは ftplib のごく一部なので、興味がある方は公式のドキュメントをご覧になってみてください。

• ftplib FTP protocol client — Python documentation

Python で FTP を行う方法についてでした。