Arto Inkala氏の「世界一難しい数独」より難しい数独問題を無制限につくる
「世界一難しい数独」を秒殺で解くPeter Norvig氏のPythonプログラムで問題作成
難易度別に1000問提供。問題と解答と候補の絞り込み結果と難易度を表示します
Python3(3.10)で動くソースコード（.pyファイル .ipynbファイル）あります
「anaconda3」on .py「PyCharm」.ipynb「Jupyter Notebook」
「世界一難しい数独」の難易度は，25，31，36（2006, 2010, 2012年版）
数独の難易度とは，絞り込みの結果残る候補の個数を掛け合わせた数字；残りの探索回数の指数部
外部ファイルの問題を解くプログラム，問題を作りながら解くプログラム
Peter Norvig氏のオリジナル問題，このプログラムが作った1000問の問題
すべて左上隅よりダウンロードできます
Peter Norvig氏のオリジナルはPython2.7，しかも動作時間しか表示しない
そこでPython3.6に改造して問題の解答を表示できるようにして，さらに，問題をランダムに作ることができるように改造しました。
問題の解答を表示するプログラム，問題をランダムにつくるプログラムは左上隅からダウンロードできます。プログラムの動作はこのWebサイトの別記事で解説します。
https://yamakatsusan.web.fc2.com/python14.html
『Python3でArto Inkala氏の「世界一難しい数独」を解きます』
ここでは，オリジナルプログラムをPython3.6に改造して，その動作を巧みなデバッグで解説します。Python3プログラムは巻末に掲載してあり，左上隅からダウンロードできます。ダウンロードファイルの解説は巻末にあります。
（2023-11-14）Python3.10で動作確認済み，コードを追加「time.clock = time.time」，旧いモジュールが使えなくなったので新しいモジュールを変換して旧いプログラムと互換とする。
「Pycharm」では，def test()が存在するだけでエラーになるのでコメントアウトしました。「Jupyter Notebook」では，正常に動作します。巻末のソースコードと左上隅からダウンロードできる「.py」ファイルは修正してあります（動作確認済）。
Arto Inkala氏「世界一難しい数独」の問題と解答。2006版, 2010版, 2012版
次図の左は2010年版，右は2012年版です。2006版も含めて，問題と解答は次図の下の表にあります。数独の難易度が解説が下にあります。理論的に納得できる定義です。
世界一難しい数独の難易度は，25，31，36（2006, 2010, 2012年版）
数独の問題を解くとき最初に機械的な絞り込みをやります。確定するマスといくつかの候補が残るマスがあります。
この候補の個数を掛け合わせた数字は残りの探索回数です。おおきな数字なのでその指数部分に注目します。それが難易度なのです。10の何乗とかと言う累乗の部分です。
Peter Norvig氏のプログラム付属のオリジナル問題
問題の確定数字の個数（squares）と難易度（levelの指数部）
Peter Norvig氏は，やさしい数独から難しい数独まで150問ほど用意してくれました。問題の書式は何種類かあります。
外部ファイルeasy50.txtに問題は50問ありますが，そのうち40問は機械的な絞り込みを実施しただけで解が得られてしまいました。すなわち，
level = 1.0e+00（1を81回掛けた結果が1である，指数は0なので難易度は0）
でした。絞り切れない10問でも指数は20前後でした。この指数が難易度です。世界一難しい数独の2006年版よりもかなり簡単だと思われます。
外部ファイルeasy50.txtの問題のsquares = は 30 前後です。squaresというのは，問題の確定数字の個数です。これが少ないほど問題が難しくなる傾向がありますが，完全な相関というわけではありません。やはり難易度の方がよい指標です。
自己テストの直前のハードコードの問題（オリジナルプログラムの191行目），grid1, grid2, hard1の難易度は，0, 38, 46 であり，hard1は1分ほどかかりました。ちなみに，squares = 32, 17, 17 です。hard1は人間では解けない恐れがあります。
数独問題を作るプログラム，設定できるのは，確定数字の個数の下限だけ
確定数字の個数の下限をいくつにすればよいのか
確定数字の個数が17というのは，これ未満（16以下）にすると解答が複数ある可能性があるということです。
Arto Inkala氏の「世界一難しい数独」では，squares = 22，23，21 であり，難易度が25，31，36 ですから，確定数字の個数をあまり動かさず相当多くの問題から選ばれたものだと思います。
sudoku3X_parseでランダムに問題を作れますが，196行目 def random_puzzle(N=17):で確定個数squaresの最低を決めることができます。
その問題集NumberPlace25.txtでは，N=25 としていますが，squares = 25～32 で，難易度は，20～38 でした。難易度は，30強に集中しています。
これは世界一難しい数独の2010年版の難易度に近いです。確定個数squaresの最低Nを少しずつ刻みながら多くの問題を作り，問題の確定数字の個数 squares と難易度 level の指数から問題を選ぶのが良いでしょう。
◆◆オリジナルプログラム，問題を解くプログラム，問題を作るプログラム◆◆
Peter Norvig氏のPythonプログラムのオリジナルは冒頭に紹介した同じサイトの別Webページで解説したように問題を解いた時間しか表示しません。そこで問題と解答を表示するように改造します。すべてのソースコードは左上隅からダウンロードできます。
問題を作るプログラムsudoku3X_parse.pyは，問題の解答を表示するとともに，機械的な絞り込み結果を表示し，それから難易度を算出します。
問題を解くプログラムsudoku3X_txt.pyは，単純に結果だけを表示します。
198 199 200 201 202 203 198 199 200 201 202 203 218 219 220 221 222 223 224
sudoku3X.py（このWebサイトの別記事にソースコードあり）
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)
sudoku3X_txt.py（巻末にソースコードあり）
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)
sudoku3X_parse.py（巻末にソースコードあり）
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(3)], "random", 0.0)
（def solve（113-133行目）も改造）
（問題をランダムに作るなら，
sudoku3X_txtでは，203行目，sudoku3X_parseでは，224行目だけを動作させる）
◆◆巧みなデバッグでプログラムを詳細に解説します◆◆
Peter Norvig氏のPythonプログラムのオリジナルは冒頭に紹介した同じサイトの別Webページで解説したように問題を解いた時間しか表示しません。そこで問題と解答を表示するように改造します。すべてのソースコードは左上隅からダウンロードできます。外部ファイルのArto Inkala.txtは「世界一難しい数独」の2006年版，2010年版，2012年版です。その問題と解答が出力されています。
年が新しくなるほど難しくなるのですが，このままではあまりよく判りません。あとで詳しく解説しますが，解いた時間は難易度を示しているとは限らないのです。
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) 8 . . |. . . |. . . . . 3 |6 . . |. . . . 7 . |. 9 . |2 . . ------+------+------ . 5 . |. . 7 |. . . . . . |. 4 5 |7 . . . . . |1 . . |. 3 . ------+------+------ . . 1 |. . . |. 6 8 . . 8 |5 . . |. 1 . . 9 . |. . . |4 . . 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 (0.04 seconds) Solved 3 of 3 Arto Inkala puzzles (avg 0.02 secs (60 Hz), max 0.04 secs). random_puzzle()の問題と解答は省略
◆◆解が複数ないか？◆◆
上のプログラムではアトランダムにつくられた問題とその解答を表示できます。その問題に解が複数ないかをどのように確認するのでしょうか。
Peter Norvig氏によれば，問題の段階で確定しているsquareの数が17個未満か，確定している数字が8種未満だと，解が複数になるそうだ。
この条件が必要十分であるかは判らないが，スーパーコンピュータで膨大な問題を解いてみて得られた結論だそうだ。
◆◆Peter Norvig氏の数独の解法は「候補の絞り込み」と「深さ優先探索」◆◆
人が数独を解く場合，最初に数独の規則を使いsquareマスに入る数字の候補を絞り込んでいきます。これは人でもコンピュータでも機械的にできます。
Peter Norvig氏のつくった問題の外部ファイルは，易しい順に，
easy50.txt
top95.txt
hardest.txt
です。
Arto Inkala.txt
の難易度はあとで解説します。
外部ファイルeasy50.txtに問題は50問ありますが，そのうち40問は機械的な絞り込みを実施しただけで解が得られてしまいました（難易度=0）。初心者向けと言ってもよいと思います。
人が数独を解く場合，「候補の絞り込み」の次にできる戦略は何十もあるそうです。しかし，コンピュータで実装するにはアルゴリズムが複雑すぎてコードが長くなるそうです。
そこでコンピュータでは「候補の絞り込み」のあとに「深さ優先探索」をやります。人がやる場合はある戦略により絞り込めてないsquareマスにある戦略をもって仮に数字を置いて他のsquareマス確定できないかを調べていきます。
コンピュータでは戦略なしでこれを強引に進めます。絞り込めてないsquareマスに仮に数字を置くことを繰り返し解が得られるまでひたすら仮置きするのです。これを「深さ優先探索」と言います。やる回数は膨大なのですが，コードは意外と短くできます。
◆◆「候補の絞り込み」の結果と「難易度」を表示するプログラム◆◆
113 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133
sudoku3X_txt.ipynb（巻末にソースコードあり）
def solve(grid): return search(parse_grid(grid))
sudoku3X_parse.ipynb（巻末にソースコードあり）
def solve(grid): #return search(parse_grid(grid))
gridparse = parse_grid(grid)
values = search(gridparse)
if values == False: return False
gridA = grid_values(grid)
gridAline = ''.join(gridA[s] if len(gridA[s])==1 else '.' for s in squares)
print gridAline
display(gridA)
z = 0
for s in gridA:
if gridA[s] in digits:
z = z + 1
print "squares =",z
y = 1
for x in squares:
y = y * len(gridparse[x])
print "level =", '%.1e' %y
display(gridparse)
display(values)
print '========'
return values
まず最初に200行目以降（sudoku3X_parseでは220行目）の解を要求するコマンドのパラメータを改造し，解を出力しないようにします。これは計算過程で難易度を出力するためです。
次の113行目の1行のサブルーチンを改造します。133行目まで長くなっています。もっとPythonらしい書き方があると思いますが，どうしてもJavaやC/C++みたいになってしまいました。この方が読みやすいかなと思っています。
上のプログラムを走らせた結果，Arto Inkala.txt「世界一難しい数独」の結果つまり解は次です。2006年版，2010年版，2012年版の順です。ランダムの方は省略しています。
85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4. 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 ======== ..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97.. . . 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..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....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 ======== Solved 3 of 3 Arto Inkala puzzles (avg 0.20 secs (4 Hz), max 0.23 secs).
◆◆プログラムでは難易度は何で決定されるのか◆◆
Peter Norvig氏のプログラムでは，アトランダムに問題を作る場合，上の確定しているsquareマスの数の最低を決めることができます。次の行です。
176 def random_puzzle(N=17):（sudoku3X_parseでは196行目）
N=17という数字は解が複数にならないための最低限の数であり，このままの設定では難易度が高くなりすぎます。ここでは，
N=30
にしてみます。
5..4........8..3.58..5..74.148.75....7.1.8...3.5.2...765..8..7..8.7....37.......8 5 . . |4 . . |. . . . . . |8 . . |3 . 5 8 . . |5 . . |7 4 . ------+------+------ 1 4 8 |. 7 5 |. . . . 7 . |1 . 8 |. . . 3 . 5 |. 2 . |. . 7 ------+------+------ 6 5 . |. 8 . |. 7 . . 8 . |7 . . |. . 3 7 . . |. . . |. . 8 squares = 30 level = 3.6e+31 5 12369 123679| 4 1369 123679| 12689 12689 1269 249 1269 124679| 8 169 12679 | 3 1269 5 8 12369 12369 | 5 1369 12369 | 7 4 1269 ---------------------+---------------------+--------------------- 1 4 8 | 369 7 5 | 269 2369 269 29 7 269 | 1 3469 8 | 24569 23569 2469 3 69 5 | 69 2 469 | 14689 1689 7 ---------------------+---------------------+--------------------- 6 5 12349 | 239 8 12349 | 1249 7 1249 249 8 1249 | 7 14569 12469 | 124569 12569 3 7 1239 12349 | 2369 134569 123469| 124569 12569 8 5 6 1 |4 3 7 |8 9 2 4 2 7 |8 1 9 |3 6 5 8 3 9 |5 6 2 |7 4 1 ------+------+------ 1 4 8 |3 7 5 |9 2 6 2 7 6 |1 9 8 |5 3 4 3 9 5 |6 2 4 |1 8 7 ------+------+------ 6 5 3 |2 8 1 |4 7 9 9 8 4 |7 5 6 |2 1 3 7 1 2 |9 4 3 |6 5 8 ======== ...4..51..51.2....8...5.2......7.6951.5692.7...6...12..1....7.2..7....51....17..6 . . . |4 . . |5 1 . . 5 1 |. 2 . |. . . 8 . . |. 5 . |2 . . ------+------+------ . . . |. 7 . |6 9 5 1 . 5 |6 9 2 |. 7 . . . 6 |. . . |1 2 . ------+------+------ . 1 . |. . . |7 . 2 . . 7 |. . . |. 5 1 . . . |. 1 7 |. . 6 squares = 31 level = 9.2e+29 23679 23679 239 | 4 368 3689 | 5 1 3789 34679 5 1 | 3789 2 3689 | 3489 3468 34789 8 34679 349 | 1379 5 1369 | 2 346 3479 ---------------------+---------------------+--------------------- 234 2348 2348 | 138 7 1348 | 6 9 5 1 348 5 | 6 9 2 | 348 7 348 3479 34789 6 | 358 348 3458 | 1 2 348 ---------------------+---------------------+--------------------- 34569 1 3489 | 3589 3468 345689| 7 348 2 23469 234689 7 | 2389 3468 34689 | 3489 5 1 23459 23489 23489 | 23589 1 7 | 3489 348 6 7 9 2 |4 3 6 |5 1 8 3 5 1 |8 2 9 |4 6 7 8 6 4 |7 5 1 |2 3 9 ------+------+------ 2 4 8 |1 7 3 |6 9 5 1 3 5 |6 9 2 |8 7 4 9 7 6 |5 4 8 |1 2 3 ------+------+------ 4 1 3 |9 6 5 |7 8 2 6 2 7 |3 8 4 |9 5 1 5 8 9 |2 1 7 |3 4 6 ======== .....7....86..5.47..7.14...715...9.....7...1.....517..6..579..8.7.2486....8136.7. . . . |. . 7 |. . . . 8 6 |. . 5 |. 4 7 . . 7 |. 1 4 |. . . ------+------+------ 7 1 5 |. . . |9 . . . . . |7 . . |. 1 . . . . |. 5 1 |7 . . ------+------+------ 6 . . |5 7 9 |. . 8 . 7 . |2 4 8 |6 . . . . 8 |1 3 6 |. 7 . squares = 33 level = 2.6e+28 123459 23459 12349 | 3689 2689 7 | 12358 235689 123569 1239 8 6 | 39 29 5 | 123 4 7 2359 2359 7 | 3689 1 4 | 2358 235689 23569 ---------------------+---------------------+--------------------- 7 1 5 | 3468 268 23 | 9 2368 2346 23489 23469 2349 | 7 2689 23 | 23458 1 23456 23489 23469 2349 | 34689 5 1 | 7 2368 2346 ---------------------+---------------------+--------------------- 6 234 1234 | 5 7 9 | 1234 23 8 1359 7 139 | 2 4 8 | 6 359 1359 2459 2459 8 | 1 3 6 | 245 7 2459 1 2 4 |6 8 7 |3 5 9 9 8 6 |3 2 5 |1 4 7 3 5 7 |9 1 4 |8 2 6 ------+------+------ 7 1 5 |4 6 2 |9 8 3 8 6 2 |7 9 3 |4 1 5 4 3 9 |8 5 1 |7 6 2 ------+------+------ 6 4 1 |5 7 9 |2 3 8 5 7 3 |2 4 8 |6 9 1 2 9 8 |1 3 6 |5 7 4 ======== Solved 3 of 3 random puzzles (avg 0.19 secs (5 Hz), max 0.21 secs).
level = の指数は
31，29，28
となっています。世界一難しい数独2010年版の 31 とほぼ同じですが，2012年版の 36 より低い数字になっています。
level = の指数とsquares = の数を指定して問題をつくることはできません。Peter Norvig氏は百万単位で問題をつくり，その中から適当なものを選んでいるのです。私が改造したプログラムは，level = とsquares = と絞り込みの結果を表示するので，お気に入りの問題を選べるはずです。
N=20, 25, 30, 35, 40を200問ずつ計1000問が左上隅からダウンロードできます。
これらの数独問題は，sudoku3X_parse.ipynb でつくります。224行目のrangeの()の中の数字が問題数であり，223行目はコメントアウトした方が良いでしょう。
◆◆ソースコード◆◆
この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_txt.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/
【sudoku3X_parse.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 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233
## 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))
gridparse = parse_grid(grid)
values = search(gridparse)
if values == False: return False
gridA = grid_values(grid)
gridAline = ''.join(gridA[s] if len(gridA[s])==1 else '.' for s in squares)
print(gridAline)
display(gridA)
z = 0
for s in gridA:
if gridA[s] in digits:
z = z + 1
print("squares =",z)
y = 1
for x in squares:
y = y * len(gridparse[x])
print("level =", '%.1e' %y)
display(gridparse)
display(values)
print('========')
return values
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=30):
"""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", 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(3)], "random", 0.0)
# solve_all([grid1]) # 191行目
# solve_all([grid2])
# solve_all([hard1]) # 1分ほどかかる
## 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/
オリジナルプログラムの解説は，このWebサイトの別記事にあります。
https://yamakatsusan.web.fc2.com/python14.html
『Python3でArto Inkala氏の「世界一難しい数独」を解きます』
有名なPeter Norvig氏の「数独」の解法プログラムは次のWebページにあります。
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
『あらゆる数独パズルを解く』
著作権の問題があるかもしれないので日本語訳の方からは一切コピペしていません。