Python3でArto Inkala氏の「世界一難しい数独」を解きます
世界一速いPeter Norvig氏のPython3プログラムが実際に動作します
「世界一難しい数独」の難易度は，25，31，36（2006, 2010, 2012年版）
Python3(3.10)で動くソースコード（.pyファイル .ipynbファイル）あります
「anaconda3」on .py「PyCharm」.ipynb「Jupyter Notebook」
数独の難易度とは，絞り込みの結果残る候補の個数を掛け合わせた数字；残りの探索回数の指数部
外部ファイルの問題を解くプログラム，問題を作りながら解くプログラム
Peter Norvig氏のオリジナル問題，このプログラムが作った1000問の問題
すべて左上隅よりダウンロードできます
Peter Norvig氏のオリジナルはPython2.7，しかも動作時間しか表示しない
そこでPython3.6に改造して問題の解答を表示できるようにして，さらに，問題をランダムに作ることができるように改造しました。
問題の解答を表示するプログラム，問題をランダムにつくるプログラムは左上隅からダウンロードできます。プログラムの動作はこのWebページで解説します。プログラムの使い方はこのWebサイトの別記事で解説します。
https://yamakatsusan.web.fc2.com/python16.html
『Arto Inkala氏の「世界一難しい数独」より難しい数独問題を無制限につくる』
ここでは，オリジナルプログラムをPython3.6に改造して，その動作を巧みなデバッグで解説します。Python3プログラムは巻末に掲載してあり，左上隅からダウンロードできます。ダウンロードファイルの解説は巻末にあります。
（2023-11-14）Python3.10で動作確認済み，コードを追加「time.clock = time.time」，旧いモジュールが使えなくなったので新しいモジュールを変換して旧いプログラムと互換とする。
「Pycharm」では，def test()が存在するだけでエラーになるのでコメントアウトしました。「Jupyter Notebook」では，正常に動作します。巻末のソースコードと左上隅からダウンロードできる「.py」ファイルは修正してあります（動作確認済）。
（2023-12-12）「世界一難しい数独」（2006, 2010, 2012年版）とプログラムにハードコードされている「hard1」の解答時間を測定しました（「hard1」を9x9に書き直したものは本記事と関連別記事の中にあります）。
解答時間は，
0.004, 0.006, 0.030, 52.950 秒
難易度は，（意味はあとで説明します）
25，31，36, 46（これが本当の「世界一難しい数独」かも。人では解けないおそれがあります）
左上隅からダウンロードできる「sudoku3X_txt.py」を使用。
自己テストの 203, 207行を run すると問題，解答，動作時間が表示されます。表示桁数は 162行の書式を替えます。難易度は「sudoku3X_parse.py」で表示されます（関連別記事参照）。
Arto Inkala氏「世界一難しい数独」の問題と解答。2006版, 2010版, 2012版
次図の左は2010年版，右は2012年版です。2006版も含めて，問題と解答は次図の下の表にあります。数独の難易度が解説が下にあります。理論的に納得できる定義です。
8 5 . |. . 2 |4 . .
7 2 . |. . . |. . 9
. . 4 |. . . |. . .
------+------+------
. . . |1 . 7 |. . 2
3 . 5 |. . . |9 . .
. 4 . |. . . |. . .
------+------+------
. . . |. 8 . |. 7 .
. 1 7 |. . . |. . .
. . . |. 3 6 |. 4 .
squares = 22
level = 1.7e+25
8 5 1369 | 36 1679 2 | 4 36 1367
7 2 136 | 34568 156 345 | 13568 3568 9
169 369 4 | 3568 15679 359 | 135678 2 135678
---------------------+---------------------+---------------------
69 689 689 | 1 4 7 | 3568 3568 2
3 7 5 | 26 26 8 | 9 1 4
1269 4 12689 | 2356 2569 359 | 35678 3568 35678
---------------------+---------------------+---------------------
4 36 236 | 9 8 1 | 2356 7 356
256 1 7 | 245 25 45 | 23568 9 3568
259 89 289 | 7 3 6 | 1258 4 158
8 5 9 |6 1 2 |4 3 7
7 2 3 |8 5 4 |1 6 9
1 6 4 |3 7 9 |5 2 8
------+------+------
9 8 6 |1 4 7 |3 5 2
3 7 5 |2 6 8 |9 1 4
2 4 1 |5 9 3 |7 8 6
------+------+------
4 3 2 |9 8 1 |6 7 5
6 1 7 |4 2 5 |8 9 3
5 9 8 |7 3 6 |2 4 1
========
. . 5 |3 . . |. . .
8 . . |. . . |. 2 .
. 7 . |. 1 . |5 . .
------+------+------
4 . . |. . 5 |3 . .
. 1 . |. 7 . |. . 6
. . 3 |2 . . |. 8 .
------+------+------
. 6 . |5 . . |. . 9
. . 4 |. . . |. 3 .
. . . |. . 9 |7 . .
squares = 23
level = 2.9e+31
1269 249 5 | 3 24689 24678 |14689 14679 1478
8 349 169 | 4679 5 467 | 1469 2 1347
2369 7 269 | 4689 1 2468 | 5 469 348
------------------+------------------+------------------
4 289 26789 | 1689 689 5 | 3 179 127
259 1 289 | 489 7 3 | 249 459 6
5679 59 3 | 2 469 146 | 149 8 1457
------------------+------------------+------------------
1237 6 1278 | 5 2348 12478 | 1248 14 9
12579 2589 4 | 1678 268 12678 | 1268 3 1258
1235 2358 128 | 1468 23468 9 | 7 1456 12458
1 4 5 |3 2 7 |6 9 8
8 3 9 |6 5 4 |1 2 7
6 7 2 |9 1 8 |5 4 3
------+------+------
4 9 6 |1 8 5 |3 7 2
2 1 8 |4 7 3 |9 5 6
7 5 3 |2 9 6 |4 8 1
------+------+------
3 6 7 |5 4 2 |8 1 9
9 8 4 |7 6 1 |2 3 5
5 2 1 |8 3 9 |7 6 4
========
8 . . |. . . |. . .
. . 3 |6 . . |. . .
. 7 . |. 9 . |2 . .
------+------+------
. 5 . |. . 7 |. . .
. . . |. 4 5 |7 . .
. . . |1 . . |. 3 .
------+------+------
. . 1 |. . . |. 6 8
. . 8 |5 . . |. 1 .
. 9 . |. . . |4 . .
squares = 21
level = 9.6e+36
8 1246 24569 | 2347 12357 1234 | 13569 4579 1345679
12459 124 3 | 6 12578 1248 | 1589 45789 14579
1456 7 456 | 348 9 1348 | 2 458 13456
------------------------+------------------------+------------------------
123469 5 2469 | 2389 2368 7 | 1689 2489 12469
12369 12368 269 | 2389 4 5 | 7 289 1269
24679 2468 24679 | 1 268 2689 | 5689 3 24569
------------------------+------------------------+------------------------
23457 234 1 | 23479 237 2349 | 359 6 8
23467 2346 8 | 5 2367 23469 | 39 1 2379
23567 9 2567 | 2378 123678 12368 | 4 257 2357
8 1 2 |7 5 3 |6 4 9
9 4 3 |6 8 2 |1 7 5
6 7 5 |4 9 1 |2 8 3
------+------+------
1 5 4 |2 3 7 |8 9 6
3 6 9 |8 4 5 |7 2 1
2 8 7 |1 6 9 |5 3 4
------+------+------
5 2 1 |9 7 4 |3 6 8
4 3 8 |5 2 6 |9 1 7
7 9 6 |3 1 8 |4 5 2
========
. . . |. . 6 |. . .
. 5 9 |. . . |. . 8
2 . . |. . 8 |. . .
------+------+------
. 4 5 |. . . |. . .
. . 3 |. . . |. . .
. . 6 |. . 3 |. 5 4
------+------+------
. . . |3 2 5 |. . 6
. . . |. . . |. . .
. . . |. . . |. . .
squares = 17
level = 4.4e+46
13478 1378 1478 | 124579 134579 6 | 1234579 123479 123579
13467 5 9 | 1247 1347 1247 | 123467 123467 8
2 1367 147 | 14579 134579 8 | 1345679 134679 13579
---------------------------+---------------------------+---------------------------
1789 4 5 | 126789 16789 1279 | 1236789 1236789 12379
1789 12789 3 | 12456789 1456789 12479 | 126789 126789 1279
1789 12789 6 | 12789 1789 3 | 12789 5 4
---------------------------+---------------------------+---------------------------
14789 1789 1478 | 3 2 5 | 14789 14789 6
13456789 1236789 12478 | 146789 146789 1479 | 12345789 1234789 123579
13456789 1236789 12478 | 146789 146789 1479 | 12345789 1234789 123579
4 3 8 |7 9 6 |2 1 5
6 5 9 |1 3 2 |4 7 8
2 7 1 |4 5 8 |6 9 3
------+------+------
8 4 5 |2 1 9 |3 6 7
7 1 3 |5 6 4 |8 2 9
9 2 6 |8 7 3 |1 5 4
------+------+------
1 9 4 |3 2 5 |7 8 6
3 6 2 |9 8 7 |5 4 1
5 8 7 |6 4 1 |9 3 2
世界一難しい数独の難易度は，25，31，36（2006, 2010, 2012年版）
ソースコードの自己テスト直前の'hard1'の難易度は，46（人は解けないかも）
上の表はそれらの数独を解いた結果です（添付のソースで）。数独の問題を解くとき最初に機械的な絞り込みをやります。確定するマスといくつかの候補が残るマスがあります。それを問題の後に表示しています。
この候補の個数を掛け合わせた数字は'level'であり，意味は残りの探索回数です。大きな数字なのでその指数部分に注目します。それが難易度なのです。10の何乗とかと言う累乗の部分です。
それが，25，31，36，46 なのです。
'level'の上の'squares'は問題の埋められている数字の個数です。これは難易度と弱い逆相関があります。当然，少ない方が難易度が高いです。
◆◆Peter Norvig氏のPython3プログラムは解も絞り込み結果も表示する◆◆
Peter Norvig氏は，やさしい数独から難しい数独まで150問ほど用意してくれました。問題の書式は何種類かあります。1つだけ1分ほどかかった問題がありましたが難易度が46でした。残りの探索回数が10の46乗ということです。
Arto Inkala氏の世界一難しい数独は中間くらいの難易度でした。2012年版でも難易度は，36です。前述の難易度46は，人間では解けないと思います。
最もやさしい問題は絞り込みの結果で各マスが確定し，候補の個数を掛け合わせた数字は1，難易度は0になります。
Peter Norvig氏は，ランダムに問題を作成するので，それから絞り込みの結果と難易度を表示させると，難易度ごとに分けられます。
問題を解くのはこのWebページ，問題を作成するのはこのWebサイトの別記事を参照してください。左上隅からすべてダウンロードできます。
・外部ファイルの問題を解くソースコードは，sudoku3X_txt.ipynb
・問題をつくりながら解くソースコードは，sudoku3X_parse.ipynb
◆◆Arto Inkala氏の「世界一難しい数独」を解くPeter Norvig氏のPythonプログラム◆◆
世界一難しい数独を世界一速く解くこのプログラムを巧みなデバッグでその動作を詳細に解説します。
数独を解くプログラムは，配列のオバケになりがちです。ですが，Peter Norvig氏のプログラムは，ハッシュ（辞書）を使い，配列の操作がほとんどありません。また，数独は探索回数が膨大になりますが，このアルゴリズムはそれを回避しています。
巧みなデバッグでそれらの秘密をお見せします。
ソースコードと問題は，左上隅からダウンロードできます。ソースコードはこのWebページの巻末に掲載してあります。次のWebからダウンロードしたオリジナルのコードは，python2用であり，かつ，動作時間しか出力しません。python3のJupiter Notebook用に数独の解を出力するように改造しました。
python3用に変換したのは巻末に紹介したWebを参照しました。数独の解を出力するのは200行目以降のコマンドのパラメータを書換えただけです。書換えの詳細は後述します。
◆◆Peter Norvig氏のPythonプログラムをオリジナルから丁寧に紹介する◆◆
次のWebは有名なPeter Norvig氏の「数独」の解法プログラムである。
http://norvig.com/sudoku.html
『Solving Every Sudoku Puzzle』
ソースファイルはここ（左上隅からもダウンロードできる）。
http://norvig.com/sudopy.shtml
『sudoku.py』
オリジナルのソースコードは巻末に掲載されています。
日本語訳もある。
http://www.aoky.net/articles/peter_norvig/sudoku.htm
『あらゆる数独パズルを解く』
著作権の問題があるかもしれないので日本語訳の方からは一切コピペしていません。
上のプログラムを参考にワンライナーをつくった方がいる。本当に１行494文字でできている。問題は世界一難しい数独2010年版である。動作することは確認したが詳細の検証はしてない。
http://handasse.blogspot.com/2010/08/python.html
『良いもの。悪いもの。 Pythonワンライナーで数独を解いてみた』
◆◆とにかく run させる：外部ファイルの問題の解を出力させる◆◆
問題ファイル「easy50.txt」「top95.txt」「hardest.txt」をプログラム「sudoku3X.ipynb」と同じディレクトリに置いてください。すべて上のWebサイトからダウンロードできます（左上隅からもダウンロードできる）。オリジナルのままrunさせた結果は次のようになります。
All tests pass. Solved 50 of 50 easy puzzles (avg 0.01 secs (193 Hz), max 0.01 secs). Solved 95 of 95 hard puzzles (avg 0.02 secs (53 Hz), max 0.09 secs). Solved 11 of 11 hardest puzzles (avg 0.01 secs (141 Hz), max 0.01 secs). Solved 99 of 99 random puzzles (avg 0.01 secs (178 Hz), max 0.01 secs).
オリジナルのソースコードでは上のように解く速度しか表示されません。そこで巻頭でやったように200行目からの解を出力するコマンドのパラメータNoneを削除するか時間を 0.0 にすれば，すべての問題と解を出力します。200行目の問題ファイルeasy50.txtの問題フォーマットは他の２つと違って区切り記号を使っています。
sudoku3X_txt.ipynb（sudoku3X.ipynbとの違いはここだけです）
198 199 200 201 202 203 204 205 206 207
if __name__ == '__main__':
# test()
solve_all(from_file("easy50.txt", '========'), "easy", 0.0)
solve_all(from_file("top95.txt"), "hard", 0.0)
solve_all(from_file("hardest.txt"), "hardest", 0.0)
solve_all(from_file("Arto Inkala.txt", '========'), "Arto Inkala", 0.0)
solve_all([random_puzzle() for _ in range(99)], "random", 100.0)
solve_all([grid1]) # 191行目
solve_all([grid2])
solve_all([hard1]) # 1分ほどかかる
外部ファイルの問題の一部だけを対象とする書き方は次である。2番目の問題は「世界一難しい数独」2010年版であるが，1番目の問題は同じく2006年版だそうだ。
201
solve_all(from_file("hardest.txt")[0:2], 'Inkala')
8 5 . |. . 2 |4 . .
7 2 . |. . . |. . 9
. . 4 |. . . |. . .
------+------+------
. . . |1 . 7 |. . 2
3 . 5 |. . . |9 . .
. 4 . |. . . |. . .
------+------+------
. . . |. 8 . |. 7 .
. 1 7 |. . . |. . .
. . . |. 3 6 |. 4 .
8 5 9 |6 1 2 |4 3 7
7 2 3 |8 5 4 |1 6 9
1 6 4 |3 7 9 |5 2 8
------+------+------
9 8 6 |1 4 7 |3 5 2
3 7 5 |2 6 8 |9 1 4
2 4 1 |5 9 3 |7 8 6
------+------+------
4 3 2 |9 8 1 |6 7 5
6 1 7 |4 2 5 |8 9 3
5 9 8 |7 3 6 |2 4 1
(0.01 seconds)
. . 5 |3 . . |. . .
8 . . |. . . |. 2 .
. 7 . |. 1 . |5 . .
------+------+------
4 . . |. . 5 |3 . .
. 1 . |. 7 . |. . 6
. . 3 |2 . . |. 8 .
------+------+------
. 6 . |5 . . |. . 9
. . 4 |. . . |. 3 .
. . . |. . 9 |7 . .
1 4 5 |3 2 7 |6 9 8
8 3 9 |6 5 4 |1 2 7
6 7 2 |9 1 8 |5 4 3
------+------+------
4 9 6 |1 8 5 |3 7 2
2 1 8 |4 7 3 |9 5 6
7 5 3 |2 9 6 |4 8 1
------+------+------
3 6 7 |5 4 2 |8 1 9
9 8 4 |7 6 1 |2 3 5
5 2 1 |8 3 9 |7 6 4
(0.01 seconds)
◆◆プログラムの中の問題の解を出力する◆◆
191行目以降のハードコードに問題があります。
191 grid1 = \ # \；バックスラッシュは行が続いていることを意味する
192 '003020600900305001001806400008102900700000008006708200002609500800203009005010300'
193 grid2 = \
194 '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
195 hard1 = \
196 '.....6....59.....82....8....45........3........6..3.54...325..6..................'
解を出力するには次の2通りの方法があります。200行目以降を次のように書換えます。前者は問題と解く時間も出力します。
195行目の問題 hard1 は1分以上かかりますので注意してください（世界一難しい数独はこれかも！？）。別記事に書きましたが，探索の順序がたまたま悪くて時間がかかることもあるので，難易度と直接関係ないこともあります。
200 201 202
solve_all([grid1])
solve_all([grid2])
solve_all([hard1])
All tests pass.
0 0 3 |0 2 0 |6 0 0
9 0 0 |3 0 5 |0 0 1
0 0 1 |8 0 6 |4 0 0
------+------+------
0 0 8 |1 0 2 |9 0 0
7 0 0 |0 0 0 |0 0 8
0 0 6 |7 0 8 |2 0 0
------+------+------
0 0 2 |6 0 9 |5 0 0
8 0 0 |2 0 3 |0 0 9
0 0 5 |0 1 0 |3 0 0
4 8 3 |9 2 1 |6 5 7
9 6 7 |3 4 5 |8 2 1
2 5 1 |8 7 6 |4 9 3
------+------+------
5 4 8 |1 3 2 |9 7 6
7 2 9 |5 6 4 |1 3 8
1 3 6 |7 9 8 |2 4 5
------+------+------
3 7 2 |6 8 9 |5 1 4
8 1 4 |2 5 3 |7 6 9
6 9 5 |4 1 7 |3 8 2
(0.00 seconds)
4 . . |. . . |8 . 5
. 3 . |. . . |. . .
. . . |7 . . |. . .
------+------+------
. 2 . |. . . |. 6 .
. . . |. 8 . |4 . .
. . . |. 1 . |. . .
------+------+------
. . . |6 . 3 |. 7 .
5 . . |2 . . |. . .
1 . 4 |. . . |. . .
4 1 7 |3 6 9 |8 2 5
6 3 2 |1 5 8 |9 4 7
9 5 8 |7 2 4 |3 1 6
------+------+------
8 2 5 |4 3 7 |1 6 9
7 9 1 |5 8 6 |4 3 2
3 4 6 |9 1 2 |7 5 8
------+------+------
2 8 9 |6 4 3 |5 7 1
5 7 3 |2 9 1 |6 8 4
1 6 4 |8 7 5 |2 9 3
(0.01 seconds)
. . . |. . 6 |. . .
. 5 9 |. . . |. . 8
2 . . |. . 8 |. . .
------+------+------
. 4 5 |. . . |. . .
. . 3 |. . . |. . .
. . 6 |. . 3 |. 5 4
------+------+------
. . . |3 2 5 |. . 6
. . . |. . . |. . .
. . . |. . . |. . .
4 3 8 |7 9 6 |2 1 5
6 5 9 |1 3 2 |4 7 8
2 7 1 |4 5 8 |6 9 3
------+------+------
8 4 5 |2 1 9 |3 6 7
7 1 3 |5 6 4 |8 2 9
9 2 6 |8 7 3 |1 5 4
------+------+------
1 9 4 |3 2 5 |7 8 6
3 6 2 |9 8 7 |5 4 1
5 8 7 |6 4 1 |9 3 2
(68.47 seconds)
200 201 202
display(solve(grid1))
display(solve(grid2))
display(solve(hard1))
（問題は出力されません）
◆◆プログラムのツリー図◆◆
def により定義された関数は引数として呼ばれても下位に属するとした
| main | solve_all | time_solve | solve | search | parse_grid | assign | eliminate |
| grid_values | |||||||
| assign | eliminate | ||||||
| display | |||||||
| solved | unitsolved | ||||||
| from_file | |||||||
| random_puzzle | assign | eliminate | |||||
| display | solve | search | parse_grid | grid_values | |||
| assign | eliminate | ||||||
| assign | eliminate | ||||||
| test |
◆◆プログラム内部の数独の表記法◆◆
◆◆数独のルール◆◆は，9×9の square に1から9の数字をある規則に準じて埋めていくことです。
まず座標は下図の1番目の図のようにします。行列やXY座標を使わない理由は内部データにリストを使わずハッシュ（辞書）を使うからだそうです。
下図の4, 5, 6番目の図は C2 に係る3つの unit を表しています。左から基準とした C2 を含む縦の列の unit，横の行の unit，3×3ブロックの unit を表しています。
1つの unit に1から9の数字を1回ずつ重複しないで埋めるのが規則です。C2に係る3つの unit には21の square があり（重複が6ある），C2の peer が20あることになります（3つのunit内の'C2'じしんを除いたsquareの数）。
A1 A2 A3| A4 A5 A6| A7 A8 A9 4 . . |. . . |8 . 5 4 1 7 |3 6 9 |8 2 5
B1 B2 B3| B4 B5 B6| B7 B8 B9 . 3 . |. . . |. . . 6 3 2 |1 5 8 |9 4 7
C1 C2 C3| C4 C5 C6| C7 C8 C9 . . . |7 . . |. . . 9 5 8 |7 2 4 |3 1 6
---------+---------+--------- ------+------+------ ------+------+------
D1 D2 D3| D4 D5 D6| D7 D8 D9 . 2 . |. . . |. 6 . 8 2 5 |4 3 7 |1 6 9
E1 E2 E3| E4 E5 E6| E7 E8 E9 . . . |. 8 . |4 . . 7 9 1 |5 8 6 |4 3 2
F1 F2 F3| F4 F5 F6| F7 F8 F9 . . . |. 1 . |. . . 3 4 6 |9 1 2 |7 5 8
---------+---------+--------- ------+------+------ ------+------+------
G1 G2 G3| G4 G5 G6| G7 G8 G9 . . . |6 . 3 |. 7 . 2 8 9 |6 4 3 |5 7 1
H1 H2 H3| H4 H5 H6| H7 H8 H9 5 . . |2 . . |. . . 5 7 3 |2 9 1 |6 8 4
I1 I2 I3| I4 I5 I6| I7 I8 I9 1 . 4 |. . . |. . . 1 6 4 |8 7 5 |2 9 3
A2 | | | | A1 A2 A3| |
B2 | | | | B1 B2 B3| |
C2 | | C1 C2 C3| C4 C5 C6| C7 C8 C9 C1 C2 C3| |
---------+---------+--------- ---------+---------+--------- ---------+---------+---------
D2 | | | | | |
E2 | | | | | |
F2 | | | | | |
---------+---------+--------- ---------+---------+--------- ---------+---------+---------
G2 | | | | | |
H2 | | | | | |
I2 | | | | | |
◆◆内部データ構造◆◆
14行目以降で内部データをつくっています。32行目以降でそれを test しています。
14行目以降で何をつくったのかを確認するには次のように200行目以降に debug 用プログラムを書きます。
squares は square の名称がリストの要素として81コ並んでいます。34行目の test は通るはずです。
unitlist は縦の列の unit，横の行の unit，3×3ブロックの unit が9コずつ計27コの unit 毎の square の名称がリストの要素として9コ並んだ2次元リストです。 35行目の test は通るはずです。
units は81コの square をハッシュ（辞書）の key としてそれに係る3つの unit を2次元リストの value としてしている。38行目の test はその1つの要素を表している。
peers は81コの square をハッシュ（辞書）の key としてそれに係る20コの peer を set にして value としてしている。41行目の test はその1つの要素を表している。
それにしても14行目～28行目の短いプログラムでここまでつくることができるのは素晴らしいです。
200 201 202 203
print squares
print unitlist
print units
print peers
['A1', 'A2', 'A3', 'A4', 'A5', 'A6', 'A7', 'A8', 'A9', 'B1', 'B2', 省略, 'I9']
[['A1', 'B1', 省略 'H1', 'I1'], ['A2', 'B2', 省略 'H2', 'I2'], 省略 'I8', 'I9']]
{'I6': [['A6', 省略 , 'I6'], ['I1', 省略, 'I9'], ['G4',省略 'I6']], 'H9': [[省略
{'I6': set(['I9', 'G6', 'G5', 'G4', 'F6', 'I8', 'I1', 'H6',省略]), 'H9': set([省略
◆◆問題のデータ構造◆◆
問題の与え方としては下図のようにいくつかの種類がある。規則として空の square として「.」ピリオドと「0」を使う。これらと1-9の数字以外はすべて無視する（段落も）。
したがって下図以外の書き方も許されているのである。区切りは巻末のソースの200行目を参照してください。実際に使っている記号をパラメータに書きます。解を出力することは検証した。
"4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......" === 400000805 030000000 000700000 020000060 000080400 000010000 000603070 500200000 104000000 === 4 . . |. . . |8 . 5 . 3 . |. . . |. . . . . . |7 . . |. . . ------+------+------ . 2 . |. . . |. 6 . . . . |. 8 . |4 . . . . . |. 1 . |. . . ------+------+------ . . . |6 . 3 |. 7 . 5 . . |2 . . |. . . 1 . 4 |. . . |. . .
◆◆盤面のデータ構造◆◆
問題 grid2 を読み込んだあと内部ではどのようなデータ構造となるのか。200行目に次のような文を書くと得られる。58行目の関数 grid_values()が問題文を内部データ構造に変換する。
その構造は81コの square をハッシュ（辞書）の key としてその square に入っている数字を value としてしている。
60 chars = [c for c in grid if c in digits or c in '0.']
問題文の中から数字と「.」ピリオドだけを選択する。
62 return dict(zip(squares, chars))
すべての square と上の問題文のリストを関数 zip で合体すればハッシュ（辞書）ができる。
その内部データを再び普通の盤面にするには202行目に次のような文を書けばよい。この出力はそのまま問題文とすることができる。
この print 文の関数 display() は101行目にあります。引数は上の盤面の内部データです。関数の中でやっていることは出力の図とコードを見比べれば判ります。
関数 display()の引数は盤面の内部データです。関数 grid_values()や関数 parse_grid()などでつくったものです。
103 width = 1+max(len(values[s]) for s in squares)
で square に入っている字数の最大値を見つけ，
104 line = '+'.join(['-'*(width*3)]*3)
で区切りをつくります。例として次のようなものです（width = 8）。
------------------------+------------------------+------------------------
105行目以降で実際に盤面を描きます。
105 for r in rows:
106 print(''.join(values[r+c].center(width)+('|' if c in '36' else '') for c in) cols)
108 if r in 'CF': print(line)
200 201
print grid_values(grid2)
display(grid_values(grid2))
{'I6': '.',省略 'I3': '4', 'E5': '8', 'I5': 省略'B8': '.', 'B9': '.', 'D1': '.'}
4 . . |. . . |8 . 5
. 3 . |. . . |. . .
. . . |7 . . |. . .
------+------+------
. 2 . |. . . |. 6 .
. . . |. 8 . |4 . .
. . . |. 1 . |. . .
------+------+------
. . . |6 . 3 |. 7 .
5 . . |2 . . |. . .
1 . 4 |. . . |. . .
◆◆解法の戦略◆◆
この種のパズルでは最適解というものが必要ないので普通は 深さ優先探索かバックトラック・アルゴリズムを採用する。
しかし，数独では探索回数が膨大になりメモリ不足のエラーになってしまうので解法の戦略を考える必要がある。
Peter Norvig氏の戦略は，まず最初に数独の規則を使って各 square はいる数字を絞り込み，そのあとに探索を使うようだ。このあいだずっと Constraint Propagation 制約伝播が使えるそうだ。
◆◆候補の絞り込み◆◆
絞り込んだ結果から見てみよう。
grid1 は絞り込んだだけで解が得られた。数独の中で最もやさしい部類になる。
grid2 では問題で与えられた square の他に一意に決まってしまったものがいくつか見られる。
hard1 はあまり絞り込みが進んでいないようである。
200 201 202
display(parse_grid(grid1))
display(parse_grid(grid2))
display(parse_grid(hard1))
4 8 3 |9 2 1 |6 5 7
9 6 7 |3 4 5 |8 2 1
2 5 1 |8 7 6 |4 9 3
------+------+------
5 4 8 |1 3 2 |9 7 6
7 2 9 |5 6 4 |1 3 8
1 3 6 |7 9 8 |2 4 5
------+------+------
3 7 2 |6 8 9 |5 1 4
8 1 4 |2 5 3 |7 6 9
6 9 5 |4 1 7 |3 8 2
4 1679 12679 | 139 2369 269 | 8 1239 5
26789 3 1256789 | 14589 24569 245689 | 12679 1249 124679
2689 15689 125689 | 7 234569 245689 | 12369 12349 123469
------------------------+------------------------+------------------------
3789 2 15789 | 3459 34579 4579 | 13579 6 13789
3679 15679 15679 | 359 8 25679 | 4 12359 12379
36789 4 56789 | 359 1 25679 | 23579 23589 23789
------------------------+------------------------+------------------------
289 89 289 | 6 459 3 | 1259 7 12489
5 6789 3 | 2 479 1 | 69 489 4689
1 6789 4 | 589 579 5789 | 23569 23589 23689
13478 1378 1478 | 124579 134579 6 | 1234579 123479 123579
13467 5 9 | 1247 1347 1247 | 123467 123467 8
2 1367 147 | 14579 134579 8 | 1345679 134679 13579
---------------------------+---------------------------+---------------------------
1789 4 5 | 126789 16789 1279 | 1236789 1236789 12379
1789 12789 3 | 12456789 1456789 12479 | 126789 126789 1279
1789 12789 6 | 12789 1789 3 | 12789 5 4
---------------------------+---------------------------+---------------------------
14789 1789 1478 | 3 2 5 | 14789 14789 6
13456789 1236789 12478 | 146789 146789 1479 | 12345789 1234789 123579
13456789 1236789 12478 | 146789 146789 1479 | 12345789 1234789 123579
48行目の関数 parse_grid() で上の絞り込みを実施している。
52 values = dict((s, digits) for s in squares)
は盤面の内部データである。52行目の後ろに print文を入れて確認するとハッシュ（辞書）の value にはすべて1-9の数字が入っている。
{'I6': '123456789', 'H9': '123456789', 'I2': '123456789', 'E8': '123456789',省略
これから数独の規則を使って候補を減らす。
53行目以降は関数 assign()に上のデータと問題の各 square を渡しているだけである。関数 items()はハッシュ（辞書）の key と value をすべて抽出する。
66行目の関数 assign()の動作を確認する。
200 201 202
values = dict((s, digits) for s in squares) s, d = 'G6', '3' display(assign(values, s, d)) 123456789 123456789 123456789 |123456789 123456789 12456789 |123456789 省略 123456789 123456789 123456789 |123456789 123456789 12456789 |123456789 省略 123456789 123456789 123456789 |123456789 123456789 12456789 |123456789 省略 ------------------------------+------------------------------+-------------- 123456789 123456789 123456789 |123456789 123456789 12456789 |123456789 省略 123456789 123456789 123456789 |123456789 123456789 12456789 |123456789 省略 123456789 123456789 123456789 |123456789 123456789 12456789 |123456789 省略 ------------------------------+------------------------------+-------------- 12456789 12456789 12456789 | 12456789 12456789 3 | 12456789 省略 123456789 123456789 123456789 | 12456789 12456789 12456789 |123456789 省略 123456789 123456789 123456789 | 12456789 12456789 12456789 |123456789 省略
結果から判るように square 'G6' の peer から '3' を消去しているのである。
57 58 201 元の
print s,d
display(values)
display(parse_grid(grid2))
省略
F8 .
4 123679 123679 | 1239 2369 1269 | 8 1239 5
2356789 12356789 12356789| 1234589 234569 1245689 | 123679 12349 1234679
235689 1235689 1235689 | 7 234569 1245689 | 12369 12349 123469
---------------------------+---------------------------+---------------------------
235789 12345789 1235789 | 23459 234579 24579 | 123579 6 123789
235679 1235679 1235679 | 2359 8 25679 | 4 12359 12379
2356789 23456789 2356789 | 23459 1 245679 | 23579 23589 23789
---------------------------+---------------------------+---------------------------
2589 2589 2589 | 6 2459 3 | 1259 7 12489
2356789 2356789 2356789 | 124589 24579 1245789 | 123569 1234589 1234689
1 2356789 4 | 2589 2579 25789 | 23569 23589 23689
D2 2（上段の途中経過に'D2'に2を入れて進めたのが下段）
4 13679 123679 | 1239 2369 1269 | 8 1239 5
2356789 1356789 12356789| 1234589 234569 1245689 | 123679 12349 1234679
235689 135689 1235689 | 7 234569 1245689 | 12369 12349 123469
---------------------------+---------------------------+---------------------------
35789 2 135789 | 3459 34579 4579 | 13579 6 13789
35679 135679 135679 | 2359 8 25679 | 4 12359 12379
356789 4 356789 | 2359 1 25679 | 23579 23589 23789
---------------------------+---------------------------+---------------------------
2589 589 2589 | 6 2459 3 | 1259 7 12489
2356789 356789 2356789 | 124589 24579 1245789 | 123569 1234589 1234689
1 356789 4 | 2589 2579 25789 | 23569 23589 23689
省略
これは途中経過であるが上の図の上段を見ると2列目で '4' が入る可能性があったのが 'D2' と 'F2' であったが 'D2' に問題の '2' が入ったとき 'F2' が '4' に確定するのである。同時に 'D2','F2' の peer からその数字を消去している。
上の図の例では，関数 eliminate()は引数で渡された'G6'や'D2'の数字を確定する以外にそれの peer の数字を消去したり確定したりしている。これらは形式的な再帰呼び出しのようになっている。
動作を詳細に見てみると，関数 assign()に例として'G6', '3'が渡されると（2つ前の図），関数 eliminate()に'G6'と '3'以外の数字が渡されて機械的に'G6'から'3'以外の数字が消去されて'3'が残る。
次に86行目で自分自身を呼び出し'G6'の peer と '3'を渡すと'G6'の peer から '3'が消去される。
関数 assign()に例として'D2', '2'が渡されると（1つ前の図），'D2'には '2'が残り，'D2'の peer から '2'が消去されるのは前の例と同じである。
さらに95行目で，関数 assign()が呼び出され，'F2', '4'が渡される。それで図のように'F2'の '4'が確定する。
このようにして数独のルールだけを使って絞り込みが進められるのである。前に出てきたが，grid1のように絞り込みだけで解が得られる問題もあるし，hard1ようにあまり絞り込めない問題もある。
◆◆次は探索◆◆
上の絞り込みまでは機械的に解けるそうだ。この先の戦略は何十も考えられるそうだ。しかし，それを実装するにはアルゴリズムが複雑すぎて何百ものコードを書くことになるそうだ。そこで人が解く場合は普通やらないが探索を採用するしかなくなる。探索は再帰呼び出しなどでコードが短くできる可能性がある。
Peter Norvig氏によれば上の絞り込みを実施した結果でもそのあとに探索をすると膨大な探索回数になりメモリ不足のエラーまたは時間オーバーになるそうです。
115行目の関数 search()によって探索します。123行目で values のコピーをつくりながら再帰呼び出しをしています。解が得られるまで再帰呼び出しをしているので深さ優先探索なのですが，関数 assign()によって制約伝播しています。
Peter Norvig氏によれば探索回数は劇的に少なくなっているそうです。実際に解を出す時間は驚異的に短いです。
193行目の問題 grid2 の絞り込み結果を渡して113行目の関数 solve()を呼びこれが115行目の関数 search()を呼んだときの詳細を見てみよう。
117行目のエラー検知，119行目の解発見は説明不要だろう。言うまでもなくすべての square の数字が1つになったものが解である。
次のように print文を入れて動作を確認する。
123 print(n,s,values[s])
124 print(values)
前項の最初の図の下段を見ながら説明をみてほしい。
122行目で候補数字の少ない square を探す。結果は'G2'の'89'である。これに対して深さ優先探索するため return文で再帰呼び出しをしている。
次に探索するのは'G1'の'29'であるが，実は最初の探索で候補が'289'から制約伝播（関数 assign()と関数 eliminate()で実現している）により'29'に減っているのである。
実際に探索したものを123行目に入れた print文で確認してみると次のようになる。偶然かもしれないが？候補数字はすべて2つに減っている。探索回数は 2**15 になる。
このサイトの別記事にある 8パズルと同程度の探索回数である。15パズルよりは２桁ほど探索回数が少ない。
Peter Norvig氏が採用したアルゴリズムの制約伝播が素晴らしいものであることが判る。
2 G2 89 2 G1 29 2 G5 45 2 H2 67 2 A2 19 2 A4 39 2 A8 29 2 A5 69 2 A5 26 2 A6 26 2 A4 13 2 A6 26 2 A5 26 2 A2 19 2 A4 39
◆◆解が複数ないか？◆◆
Peter Norvig氏によれば，問題の段階で確定しているsquareの数が17個未満か，確定している数字が8種未満だと，解が複数になるそうだ。
この条件が必要十分であるかは判らないが，スーパーコンピュータで膨大な問題を解いてみて得られた結論だそうだ。
◆◆問題を無制限につくる◆◆
このプログラムでは外部ファイルで問題を与えるのと別にプログラム内でランダムに問題をつくる仕組みを持っている。
これを改造して難易度を表示できるようにした。また，直接ではないが難易度も設定できる。
問題を無制限につくるプログラムの詳細な解説は同じサイトの次のWebページにあります。
https://yamakatsusan.web.fc2.com/hp_software/python16.html
『Arto Inkala氏の「世界一難しい数独」を瞬間解答するPeter Norvig氏のPythonプログラムで問題を無制限につくる』
◆◆ソースコード◆◆
このWebの左上隅からダウンロードできます。
7つのソースファイルと9つの問題のテキストファイルがあります。
python2用（.pyファイル）
・sudoku.py；オリジナルのプログラム（このままでは演算速度を表示するだけです）
python3用（.ipynbファイル，.pyファイル）
・sudoku3X.ipynb；sudoku.pyから変換，このままでは演算速度を表示するだけです
・sudoku3X.py
・sudoku3X_txt.ipynb；外部ファイルの問題を解くプログラム
・sudoku3X_txt.py
・sudoku3X_parse.ipynb；絞り込み結果と難易度を表示するプログラム，問題も作れる
・sudoku3X_parse.py
数独問題（オリジナル）
・Arto Inkala.txt；Arto Inkala氏の問題（世界一難しい数独）
・hardest.txt；オリジナルの問題（一番難しい）
・easy50.txt；オリジナルの問題（易しい）
・top95.txt；オリジナルの問題（かなり難しい）
このプログラムで作った数独問題（計1000問）
・NumberPlace20.txt；問題のマスに数字を埋めた個数が20（難易度40ほど）
・NumberPlace25.txt；問題のマスに数字を埋めた個数が25
・NumberPlace30.txt；問題のマスに数字を埋めた個数が30
・NumberPlace35.txt；問題のマスに数字を埋めた個数が35
・NumberPlace40.txt；問題のマスに数字を埋めた個数が40（難易度20ほど）
以上
【sudoku3X.ipynb】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212
## Solve Every Sudoku Puzzle
## See http://norvig.com/sudoku.html
## Throughout this program we have:
## r is a row, e.g. 'A'
## c is a column, e.g. '3'
## s is a square, e.g. 'A3'
## d is a digit, e.g. '9'
## u is a unit, e.g. ['A1','B1','C1','D1','E1','F1','G1','H1','I1']
## grid is a grid,e.g. 81 non-blank chars, e.g. starting with '.18...7...
## values is a dict of possible values, e.g. {'A1':'12349', 'A2':'8', ...}
def cross(A, B):
"Cross product of elements in A and elements in B."
return [a+b for a in A for b in B]
digits = '123456789'
rows = 'ABCDEFGHI'
cols = digits
squares = cross(rows, cols)
unitlist = ([cross(rows, c) for c in cols] +
[cross(r, cols) for r in rows] +
[cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
units = dict((s, [u for u in unitlist if s in u])
for s in squares)
peers = dict((s, set(sum(units[s],[]))-set([s]))
for s in squares)
################ Unit Tests ################
'''
def test():
"A set of tests that must pass."
assert len(squares) == 81
assert len(unitlist) == 27
assert all(len(units[s]) == 3 for s in squares)
assert all(len(peers[s]) == 20 for s in squares)
assert units['C2'] == [['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'],
['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'],
['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3']]
assert peers['C2'] == set(['A2', 'B2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2',
'C1', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9',
'A1', 'A3', 'B1', 'B3'])
print('All tests pass.')
'''
################ Parse a Grid ################
def parse_grid(grid):
"""Convert grid to a dict of possible values, {square: digits}, or
return False if a contradiction is detected."""
## To start, every square can be any digit; then assign values from the grid.
values = dict((s, digits) for s in squares)
for s,d in grid_values(grid).items():
if d in digits and not assign(values, s, d):
return False ## (Fail if we can't assign d to square s.)
return values
def grid_values(grid):
"Convert grid into a dict of {square: char} with '0' or '.' for empties."
chars = [c for c in grid if c in digits or c in '0.']
assert len(chars) == 81
return dict(zip(squares, chars))
################ Constraint Propagation ################
def assign(values, s, d):
"""Eliminate all the other values (except d) from values[s] and propagate.
Return values, except return False if a contradiction is detected."""
other_values = values[s].replace(d, '')
if all(eliminate(values, s, d2) for d2 in other_values):
return values
else:
return False
def eliminate(values, s, d):
"""Eliminate d from values[s]; propagate when values or places <= 2.
Return values, except return False if a contradiction is detected."""
if d not in values[s]:
return values ## Already eliminated
values[s] = values[s].replace(d,'')
## (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
if len(values[s]) == 0:
return False ## Contradiction: removed last value
elif len(values[s]) == 1:
d2 = values[s]
if not all(eliminate(values, s2, d2) for s2 in peers[s]):
return False
## (2) If a unit u is reduced to only one place for a value d, then put it there.
for u in units[s]:
dplaces = [s for s in u if d in values[s]]
if len(dplaces) == 0:
return False ## Contradiction: no place for this value
elif len(dplaces) == 1:
# d can only be in one place in unit; assign it there
if not assign(values, dplaces[0], d):
return False
return values
################ Display as 2-D grid ################
def display(values):
"Display these values as a 2-D grid."
width = 1+max(len(values[s]) for s in squares)
line = '+'.join(['-'*(width*3)]*3)
for r in rows:
print(''.join(values[r+c].center(width)+('|' if c in '36' else '')
for c in cols))
if r in 'CF': print(line)
print()
################ Search ################
def solve(grid): return search(parse_grid(grid))
def search(values):
"Using depth-first search and propagation, try all possible values."
if values is False:
return False ## Failed earlier
if all(len(values[s]) == 1 for s in squares):
return values ## Solved!
## Chose the unfilled square s with the fewest possibilities
n,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
return some(search(assign(values.copy(), s, d))
for d in values[s])
################ Utilities ################
def some(seq):
"Return some element of seq that is true."
for e in seq:
if e: return e
return False
def from_file(filename, sep='\n'):
"Parse a file into a list of strings, separated by sep."
# return file(filename).read().strip().split(sep)
with open(filename, mode='r', encoding="utf-8") as f:
return f.read().strip().split(sep)
def shuffled(seq):
"Return a randomly shuffled copy of the input sequence."
seq = list(seq)
random.shuffle(seq)
return seq
################ System test ################
import time, random
time.clock = time.time # 追加
def solve_all(grids, name='', showif=0.0):
"""Attempt to solve a sequence of grids. Report results.
When showif is a number of seconds, display puzzles that take longer.
When showif is None, don't display any puzzles."""
def time_solve(grid):
start = time.clock()
values = solve(grid)
t = time.clock()-start
## Display puzzles that take long enough
if showif is not None and t > showif:
display(grid_values(grid))
if values: display(values)
print('(%.2f seconds)\n' % t)
return (t, solved(values))
times, results = zip(*[time_solve(grid) for grid in grids])
N = len(grids)
if N > 1:
print("Solved %d of %d %s puzzles \
(avg %.2f secs (%d Hz), max %.2f secs)." \
% (sum(results), N, name, sum(times)/N, N/sum(times), max(times)))
def solved(values):
"A puzzle is solved if each unit is a permutation of the digits 1 to 9."
def unitsolved(unit): return set(values[s] for s in unit) == set(digits)
return values is not False and all(unitsolved(unit) for unit in unitlist)
def random_puzzle(N=17):
"""Make a random puzzle with N or more assignments.
Restart on contradictions.
Note the resulting puzzle is not guaranteed to be solvable, but empirically
about 99.8% of them are solvable. Some have multiple solutions."""
values = dict((s, digits) for s in squares)
for s in shuffled(squares):
if not assign(values, s, random.choice(values[s])):
break
ds = [values[s] for s in squares if len(values[s]) == 1]
if len(ds) >= N and len(set(ds)) >= 8:
return ''.join(values[s] if len(values[s])==1 else '.' \
for s in squares)
return random_puzzle(N) ## Give up and make a new puzzle
grid1 = \
'003020600900305001001806400008102900700000008006708200002609500800203009005010300'
grid2 = \
'4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
hard1 = \
'.....6....59.....82....8....45........3........6..3.54...325..6..................'
if __name__ == '__main__':
# test()
solve_all(from_file("easy50.txt", '========'), "easy", None)
solve_all(from_file("top95.txt"), "hard", None)
solve_all(from_file("hardest.txt"), "hardest", None)
solve_all([random_puzzle() for _ in range(99)], "random", 100.0)
# solve_all([grid1]) # 191行目
# solve_all([grid2])
# solve_all([hard1])
## References used:
#http://www.scanraid.com/BasicStrategies.htm
#http://www.sudokudragon.com/sudokustrategy.htm
#http://www.krazydad.com/blog/2005/09/29/an-index-of-sudoku-strategies/
#http://www2.warwick.ac.uk/fac/sci/moac/currentstudents/peter_cock/python/sudoku/
この記事の参照先（Peter Norvig氏のPythonプログラム）のコードは，Python2Xですが，Python3Xに変換してあります。
それを可能にしたのが次のサイトです。
https://medium.com/activating-robotic-minds/peter-norvigs-sudoku-solver-25779bb349ce
『Sudoku Solver by Peter Norvig』
https://www.freecodecamp.org/news/how-to-play-and-win-sudoku-using-math-and-machine-learning-to-solve-every-sudoku-puzzle/
『How to Play and Win Sudoku - Using Math and Machine Learning to Solve Every Sudoku Puzzle』