numpyを使って数独を爆速で解いてみる

数独とは

数独（すうどく）は、3×3のブロックに区切られた 9×9の正方形の枠内に1〜9までの数字を入れるペンシルパズルの一つである。「ナンバープレース（ナンプレ）」とも呼ばれる。(Wikipediaより)

らしいです。

もちろん、何も考えずに数字を埋めるわけではなく、以下のような制約が付きます。

• １つの列に同じ数字が存在してはいけない
• １つの行に同じ数字が存在してはいけない
• １つのブロックに同じ数字が存在してはいけない

(数学の面白いこと・役に立つことをまとめたサイト様より拝借させていただきました)

これをプログラミング初心者の後輩向けに問題にしようと思ったのですが、意外と書いてある記事が少なかったので書いておきます。

方針

まぁ単純に人間と同じことをやります。
以下のような数独を考えます。

例えば1について調べるとすると、各列、各行、各ブロックについて、1だけが入りうる場所を探すという作業になります。

各マスについて各数字が存在するフラグを立て、そのフラグ数の合計が1となる列、行、ブロックを発見する作業をコードにしていきます。

各マスについて、特定の数字が

• 存在する可能性があるマス　… 1
• 存在する可能性がないマス　… 0

と表すと、先ほどの数独において、"1"については以下のように存在フラグを立てることができます。（以降でこのような規則に従う2次元配列をレイヤ(layer)と呼びます）
以下はイメージです。(赤と数字マス…0、緑…1)

そして、各行、各列、各ブロックについて合計を計算します。
これで合計が１になったら数字が確定します。

この例ではちょうどそれぞれ３つ、更新すべき場所が発見できます。

このように、存在フラグを導入するだけでなんとも楽に解けそうです。

さて、次は実際にコードを書いていきましょう。

各行のチェック

def check_row(layer):
    rows = np.where(np.sum(layer, axis=1)==1)[0]
    w = np.where(layer[rows] == 1)
    cols = w[1][np.argsort(w[0])]
    return rows, cols

このように、基本的にはnp.sumとnp.whereを使用して、条件に合ったマスを抽出していきます。

各列のチェック

列についても同様です。

def check_col(layer):
    cols = np.where(np.sum(layer, axis=0)==1)[0]
    w = np.where(layer[:,cols] == 1)
    rows = w[0][np.argsort(w[1])]
    return rows, cols

各グリッドのチェック

def check_grid(layer):
    rows, cols = list(), list()
    for row in range(3):
        for col in range(3):
            grid = self.layer[row*3:(row+1)*3, col*3:(col+1)*3 ]
            if np.sum(grid) == 1:
                point = np.where(grid==1)
                rows.append(point[0][0]+row*3)
                cols.append(point[1][0]+col*3)
    return rows, cols

動作確認

さて、先ほどまでの関数を試してみましょう。

layer = np.array([[0, 0, 0, 0, 0, 0, 0, 0, 0],
                  [0, 1, 0, 0, 1, 1, 0, 0, 0],
                  [1, 0, 0, 0, 1, 1, 0, 0, 0],
                  [0, 0, 0, 0, 0, 1, 0, 0, 0],
                  [0, 0, 0, 0, 1, 1, 0, 0, 1],
                  [0, 0, 0, 0, 0, 0, 0, 0, 0],
                  [0, 1, 0, 0, 0, 0, 0, 0, 1],
                  [0, 0, 0, 0, 0, 0, 0, 0, 0],
                  [1, 1, 0, 0, 0, 0, 1, 0, 1]])
print(check_row(layer))
#(array([3], dtype=int64), array([5], dtype=int64))

print(check_col(layer))
#(array([8], dtype=int64), array([6], dtype=int64))

print(check_grid(layer))
#([4], [8])

上手く動いていますね。

各レイヤのチェック

さて、実はもう動くんですが、せっかくですのでもう一つ関数を追加します。

今までは一つのレイヤのみに注目していました。
しかし、数独は1～9の、9つの数字で構成されていますので、レイヤ同士を比べることも考えなければなりません。
つまり任意のセルにおいて、各レイヤを横断的に見渡し存在フラグが１レイヤでのみ立っていた場合、その場所は確定できるということです。

def check_all_layer(layers):
    nums = list()
    sum_map = np.sum(layers, axis=0)
    if np.any(sum_map==1):
        rows, cols = np.where(sum_map==1)
        for row, col in zip(rows, cols):
            idx = np.where(layers[:,row,col])[0][0]
            nums.append(idx+1)
    return rows, cols, nums

layers = np.zeros((9,9,9))
layers[3,5,7] = 1

print(check_all_layer(layers))
#(array([5], dtype=int64), array([7], dtype=int64), [4])

数字が代入された際の更新

数字が確定した際、レイヤも更新しなければなりません。
9×9×9の3次元配列レイヤを考えると、レイヤを更新する関数は以下のように書くことができます。

def update(layers, idx, row, col):
    layers[idx,row, : ] = 0 #行方向
    layers[idx, : ,col] = 0 #列方向
    layers[ : ,row,col] = 0 #層方向
    row, col = row//3*3, col//3*3
    layers[idx, row:row+3, col:col+3] = 0 #範囲

最後に

先輩と数独の話で盛り上がったときにちょちょっと書いただけのコードですので、正直まったく検証をしていません()
誤りなどあれば連絡いただければと思います。

最後まで読んでくださりありがとうございました。

実際のコード

クラスで実装したため若干上記のコードとは異なりますが、これで0.01秒くらいで数独が解けます。

ノリで書いたので全く動作確認してないんですが、たぶんちゃんと動きます。

sudoku.py

class sudoku_solver(object):
    def __init__(self, question):
        self.p = np.array(problem)
        self.layer = np.ones((9,9,9))
        self.__init_layer()
        self.update_list = list()

    def solve(self):
        count=0
        while np.sum(self.layer)!=0 or count<100:
            for i in range(9):
                self.check_row(i)
                self.check_col(i)
                self.check_grid(i)
            self.check_all_layer()
            self.__update()
            count+=1

    #更新関数
    def __update(self):
        for idx, row, col in self.update_points:
            self.__update_point(idx, row, col)
        self.update_points=list()

    def __update_point(self, idx, row, col):
        #回答更新
        self.p[row, col] = idx+1
        #レイヤ更新
        self.layer[idx,row, : ] = 0 #行方向
        self.layer[idx, : ,col] = 0 #列方向
        self.layer[ : ,row,col] = 0 #層方向
        row, col = row//3*3, col//3*3
        self.layer[idx, row:row+3, col:col+3] = 0 #範囲

    #レイヤ初期化関数
    def __init_layer(self):
        for idx in range(9):
            (rows, cols) = np.where(self.p==idx+1)
            for row, col in zip(rows, cols):
                self.__update_point(idx, row, col)

    #行確認関数
    def check_row(self, idx):
        rows = np.where(np.sum(self.layer[idx], axis=1)==1)[0]
        w = np.where(self.layer[idx][rows] == 1)
        cols = w[1][np.argsort(w[0])]

        for row, col in zip(rows, cols):
            self.update_list.append((idx, row, col))

    #列確認関数
    def check_col(self, idx):
        cols = np.where(np.sum(self.layer[idx], axis=0)==1)[0]
        w = np.where(self.layer[idx][:,cols] == 1)
        rows = w[0][np.argsort(w[1])]

        for row, col in zip(rows, cols):
            self.update_list.append((idx, row, col))

    #範囲確認関数
    def check_grid(self, idx):
        for row in range(3):
            for col in range(3):
                grid = self.layer[idx, row*3:(row+1)*3, col*3:(col+1)*3 ]
                if np.sum(grid) == 1:
                    point = np.where(grid==1)
                    row = point[0][0]+row*3
                    col = point[1][0]+col*3
                    self.update_list.append((idx,row,col))

    #層方向確認関数
    def check_all_layer(self):
        sum_map = np.sum(self.layer, axis=0)
        if np.any(sum_map==1):
            rows, cols = np.where(sum_map==1)
            for row, col in zip(rows, cols):
                idx = np.where(self.layer[:,row,col])[0][0]
                self.update_list.append((idx,row,col))