はじめに
はるか昔にc#を使って数独を解きました。今回はPythonを使ってみます。touch-sp.hatenablog.com
バックトラック法というアルゴリズムを使用しています。
名前は難しいですが単に順番に空欄に数字を入れていくだけです。その際に再起処理が必要となります。
Pythonスクリプト
たったこれだけですか？そう言いたくなる程短くまとめることができました。import textwrap def position_define(x): row, col = divmod(x, 9) return row, col, row//3 * 27 + col//3 * 3 def Try(question_list): if 0 in question_list: blank = question_list.index(0) for i in range(1, 10): if isOK(blank, i, question_list): question_list[blank] = i Try(question_list) question_list[blank] = 0 else: print(textwrap.fill(''.join([str(x) for x in question_list]), 9)) def isOK(blank, number, question_list): row, col, box_start = position_define(blank) row_list = question_list[row * 9:row * 9 + 9] col_list = question_list[col::9] box_list = question_list[box_start:box_start+3] + question_list[box_start+9:box_start+12] + question_list[box_start+18:box_start+21] if number in row_list: return False if number in col_list: return False if number in box_list: return False return True if __name__ == '__main__': q = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 8, 0, 3, 7, 6, 4, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 3, 0, 0, 0, 0, 6, 0, 1, 0, 0, 2, 8, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3 ] Try(q)
トータルで50行未満です。これだけで数独が解けてしまいます。
スクリプトの解説
textwrapのインポート
textwrapは81文字の文字列を9文字ずつ改行して表示するために使用しました。数独を解くことには直接関係ありません。
position_defineの定義
空欄がどの行、どの列、どのBOXに属するかを決定するための関数です。listに対してindex(0)で空欄を見つけます。その空欄に対してこの関数を適応するとどの行、どの列、どのBOXに属するかが返ってきます。
isOKの定義
この部分が今回のキモです。まずは空欄が属する行、列、BOXのリストをそれぞれ作ります。それぞれのリストは9個の要素を含んでいます。
次に空欄に入れる数字（1～9）がそれらのリストにすでに存在するかどうかを調べます。
すでに存在すればFalse, 存在しなければTrueを返します。
Tryの定義
空欄を見つけてそこに1～9の数字を順に入れていく関数です。最終的には空欄の数だけ再起的に自身の関数を呼び出すことになります。
途中で代入する数字がなくなればもちろんその後は打ち止めとなります。
if __name__ == '__main__'以下
数独の問題を入力してTry関数を実行するのみです。数独の問題は空欄を「0」として81個の数字のリストとして入力します。
最後に
空欄の多い難しい問題を解かせるとそれなりに時間がかかります。今回は簡潔に書くことに重点を置きましたが、時間があれば今度は速度に重点を置いてやってみようと思います。
2021年8月12日追記
isOKでの判定の際にFalseを返すタイミングを変更するとだいぶ速くなりました。変更前
def isOK(blank, number, question_list): row, col, box_start = position_define(blank) row_list = question_list[row * 9:row * 9 + 9] col_list = question_list[col::9] box_list = question_list[box_start:box_start+3] + question_list[box_start+9:box_start+12] + question_list[box_start+18:box_start+21] if number in row_list: return False if number in col_list: return False if number in box_list: return False return True
変更後
def isOK(blank, number, question_list): row, col, box_start = position_define(blank) row_list = question_list[row * 9:row * 9 + 9] if number in row_list: return False col_list = question_list[col::9] if number in col_list: return False box_list = question_list[box_start:box_start+3] + question_list[box_start+9:box_start+12] + question_list[box_start+18:box_start+21] if number in box_list: return False return True
スクリプトの行を変更しただけです。余計なリスト作成をしなくてすむので速くなります。
変更前結果
elapsed_time:296.0033047199249[sec]
変更後結果
elapsed_time:166.9490511417389[sec]
2021年8月13日追記
この記事の後に書いた記事です。良かったらこちらも見て下さい。touch-sp.hatenablog.com
touch-sp.hatenablog.com
