数独ソルバーをPython3で実装

先日ネットサーフィン中に次のような記事を見つけました: [「数学のエキスパートが3ヶ月かけて作成した「世界一難しい数独」」](http://gigazine.net/news/20100822_hardest_sudoku/)。事実かどうかはともかく、Python3でこれを解いてみました。なお実装としてはバックトラック法を利用しています。要するに力任せに解いているということですね(´・ω・`)

```py3

import itertools

class Sudoku(object):
    def __init__(self):
        self.matrix = [[0 for _ in range(9)] for _ in range(9)] # 空白の場合は0
    
    # 与えられた数独パズルを解く
    # 空白のマスを次々と埋めていき、すべての空白マスを埋めた場合はTrueを返す(埋められなかった場合はFalse)
    def solve(self):
        # 消去法: ただひとつに決まるマスを埋めていく
        while True:
            ls = []
            for i, j in itertools.product(range(9), repeat=2):
                if self.matrix[i][j] != 0: continue

                numbers = self.__find_numbers(i, j)
                if len(numbers) == 1: ls.append((i, j, numbers[0]))

            if len(ls) == 0: break
            for i, j, number in ls: self.matrix[i][j] = number


        blanks = [(i, j) for i, j in itertools.product(range(9), repeat=2) if self.matrix[i][j] == 0]
        if len(blanks) == 0: return True # すでにすべてのマスが埋められている場合

        first_i, first_j = blanks[0]
        stack = [(0, first_number) for first_number in self.__find_numbers(first_i, first_j)]

        # バックトラック法:
        #     1. 空白のマスに数字を入れる
        #     2. 次の空白のマスに数字が入るかどうかを調べる
        #     3. 2.において、入らない場合はバックトラック
        while stack:
            idx, number = stack.pop()
            i, j = blanks[idx]
            self.matrix[i][j] = number

            if idx == len(blanks) - 1: return True

            next_i, next_j = blanks[idx + 1]
            next_numbers = self.__find_numbers(next_i, next_j)

            # バックトラック
            if len(next_numbers) == 0:
                stack_top_idx = stack[-1][0]
                for temp_idx in range(stack_top_idx, idx + 1):
                    temp_i, temp_j = blanks[temp_idx]
                    self.matrix[temp_i][temp_j] = 0

            stack.extend((idx + 1, next_number) for next_number in next_numbers)

        return False

    # とあるマスに入れることができる数字をsetに格納する
    def __find_numbers(self, i, j):
        used_numbers = set()
        # 同じ行と同じ列を調べる
        for x in range(9): used_numbers |= {self.matrix[x][j], self.matrix[i][x]}

        # 同じブロックを調べる
        box_i_min, box_j_min = (i // 3) * 3, (j // 3) * 3
        for box_i, box_j in itertools.product(range(box_i_min, box_i_min + 3), \
                                              range(box_j_min, box_j_min + 3)):
            used_numbers.add(self.matrix[box_i][box_j])

        return set(range(1, 10)) - used_numbers

    def __str__(self):
        return "\n".join("".join(map(str, row)) for row in self.matrix)

if __name__ == "__main__":
    matrix = '''
        ..53.....
        8......2.
        .7..1.5..
        4....53..
        .1..7...6
        ..32....8.
        .6.5....9
        ..4....3.
        .....97..
    '''.split()

    sudoku = Sudoku()
    for i, j in itertools.product(range(9), repeat=2):
        if matrix[i][j] == ".": continue
        sudoku.matrix[i][j] = int(matrix[i][j])
    
    print(sudoku)
    sudoku.solve()
    print("========")
    print(sudoku)


# 005300000
# 800000020
# 070010500
# 400005300
# 010070006
# 003200080
# 060500009
# 004000030
# 000009700
# =========
# 145327698
# 839654127
# 672918543
# 496185372
# 218473956
# 753296481
# 367542819
# 984761235
# 521839764
```

GIGAZINEと同じ答えになったので、大丈夫でしょう(｀・ω・´)ｼｬｷｰﾝ