42 SILICON VALLEY Piscine 2017にはRushと呼ばれるグループ・プロジェクトが含まれている。3つの課題のうちの一つが、数独（ナンプレ）を解くプログラムの作成だった。
分からなければインターネット検索し、それでも分からなければ人に聞け、というのが42の学習スタンスだ。数独の解析プログラムの実装は、私にとってはそれを追体験するための格好の題材だった。予定のない正月三が日に集中して取り組んでみた。
1月1日の朝6時に着手し、「簡単な」数独を解けるまでの実装に、2日の午後までを要した。「難しい」数独を解けるまでの実装が完了したのが、3日の14時ごろだった。
今回はいつもとは異なり、プログラムを説明することを目的とした投稿ではない。私の作成したサンプル・コードを掲載しているとはいえ、主に紹介するのは、数独が解けるまでの実装についての記録だ。海外Piscine受講者が日々の活動をブログへを投稿している。それと同じような雰囲気を意識している。
特に今回は「簡単な」数独が解けるまでの記録を投稿する。「難しい」数独が解けるまでの記録は次回だ。
今回は、一から自分で考えた結果ではなく、とあるサイトの情報を参考に、自分なりに実装した結果をまとめている。サンプル・コードは参照サイトのものとは大きく異なるのだが、ロジックは一緒だ。
いつも通り、サンプル・コードはPythonで記述した。Piscine受講生に配慮して、C言語的な記述になるよう配慮しているが、いつも以上に読みにくいのではないかと思う。参照元のコードに比して、全体が長くなっている。理由は追って説明する。
準備
Pythonに限らず、言語や開発ツールのインストール不用で、直接オンラインでコードを実行することのできる環境が用意されている。例えば次のサイトだ。サンプル・コードをコピーし、試行錯誤しながら参照してほしい。
paiza.io
分からなければ調べる。
1日の朝6時から作業に着手した。まず数独の定石を調べることにした。最初に期待していたのは、基本的な戦略や定石を実装できれば、それで作業は終わるのではないか、ということだった。参照したサイトの一例だ。
数独自動解法-数独の解答と解答までのステップを自動計算！
ナンプレのルール＆解き方
ナンプレ テクニック
後ほど気づくのだが、これは決定的に誤ったアプローチだった。率直に言えば、解法が多すぎるのだ。とてもではないが、全てを網羅することはできない。ただ、後に見つかる実装方法を理解するための手助けにはなった。
ここで素直に、既にあるアルゴリズムの知見を参照しようと考え直した。まずWikipediaを参照した。
Sudoku solving algorithms - Wikipedia
Mathematics of Sudoku - Wikipedia
直接的にプログラムに繋がる知見を得ることはなかったが、得られた情報から次の二点について容易に想像することができた。
- 検証分岐が多すぎ、バックトラッキング法では複雑すぎる。
- 1マスに対する総当たり検証では、対象が多すぎる。
いずれにせよ結果として、処理は複雑になり、処理時間も長大になることが懸念される。最終的にたどり着いたのが次のサイトだった。このサイトを読み終え、この方針を採用すると決めたのは、開始から3時間が過ぎたところだった。
www.aoky.net
適切なロジックを理解する。
私のサンプル・コードは、上記サイトのものを参考にしている。上記サイトに掲載のコードを、オリジナルと呼ぶことにする。
まずサイトを熟読した。先の懸念、二つは当たっていた。上記サイトでも同じことに言及している。
根本的なアプローチの違いに気づく。解法を実装するのではなく、プログラムに「解かせる」ための手順を実装しているのだ。基本戦略は次の通りだ。
- 各マスに候補番号を列記した盤面（オリジナル中のvalues）を用意する。
- 初期状態で、全てのマスに「123456789」が格納されている。
- 検証マスの番号を、ピアから消しながら矛盾を見つける。
- ここで消去関数eliminateへ再帰する。
- 矛盾がなければ、消去を確定する。
- この部分が「制約伝播」と呼ばれている。
- 検証マスの番号を、ユニット（units）で検証する。
- ユニット中に指定番号が残っている箇所を対象に、新たに検証する。
- 新たな検証としてassignへ再帰する。
パズルの数字が確定しているマスを対象に検証を進めていくことで、values上の候補番号が削除されていく。最後に残った番号が回答となる。この「消していく」という発想が、私には全くなかった。
ユニットとは、下図で言うところの色付きのマス全てを指す。行、列、ボックスの組合わせで、それぞれの重複したマス目は考慮しない。それぞれ9マス、合計27マスで構成される。図示されているのは赤いマス(3, 3)のユニットだ。
ピアとは、ユニットから重複するマス目、赤いマス目を排除したものだ。合計20マスで構成される。図示されているのは、同じく赤いマス(3, 3)のピアだ。
特定マスに番号を割り振る処理がassign、特定マスから指定の候補番号を削除するのがeliminateだ。assignは入力されたパズル上で数字が確定している箇所に対して実行される。assignはeliminateを呼び出す。
elimninateでは指定箇所のピアから、指定番号を削除する。この作業はeliminateの再帰となる。
この結果、ピア内で候補番号が確定することがある。該当マスのユニットを対象に、候補番号が残っているマスに対して、さらにassignを実行する。この作業はassignの再帰となる。
確定マスに対して、そのピアに対する候補番号削除、この削除により確定した状態でユニットを検証し、対象マスに対するさらに候補番号削除、この状態でさらに...と検証を続けていく。
これを繰り返し続けることで、最終的に矛盾なく完了したときに残った番号が回答となる。
ロジックの理解を深める。－写経
このロジックについての実装を理解するため、オリジナルを書き写す。いわゆる「写経」だ。コピー＆ペーストではなく、全て打ち直す。写経に際し、私が心掛けているのは次の事柄だ。
- 省略記法は、ことごとく書き下す。
- ロジックはそのまま、構成を自分なりに変える。
オリジナルでは省略記法を多用している。オリジナルに比して、サンプルが長大なのは、それらを全て書き下しているのが理由だ。加えて機能ごとに異なる関数に分けたことで、さらに長くなった。
省略記法を書き下すことで、ロジックをより精緻に理解することができる。例えば、次のコードを書き下せば、このようになる。
- オリジナル
if not all(eliminate(values, s2, d2) for s2 in peers[s]): return False
- 書き下し
for s2 in peers[s]: if eliminate(values, s2, d2) == False: return False
all()だからと言って、全ての戻り値がTrueであることを確認するわけではなく、Falseが判明した時点で処理は終了することが明確に理解できる。
Pythonには内包記法と呼ばれる、このような省略記法が多用される。コードを短くすると同時に、処理速度を向上するための工夫なのだが、慣れないと読みにくいし、なによりロジックを正しく理解するためには分解したほうが良い。
オリジナルではvaluesからユニット、ピアまでの座標を全てハッシュ・テーブルで実装している。加えて各関数の引数に指定することで、各所での参照、更新を行っている。私はvaluesをmy_workbdというlist（二次元配列）でグローバル変数として実装することにした。workbdは作業用の板書、workboardを意図している。
検証対象となるマスを指定したら、そのユニット、ピアの座標を生成する関数get_posを作成する。そしてユニット、ピアを検証するための関数を、それぞれcheck_unit、check_peerとして実装することにした。
関数get_posは、引数isPeerがTrueならばピアの座標を返し、Falseならばユニットの座標を返す。
候補番号の削除は二通りある。
- 該当マスを更新する。
- 更新後の状態を取得する。該当マスは更新しない。
これを関数update_workbdとして実装した。引数isOWとはisOverWriteを意図している。Trueならば更新するし、Falseならば更新しない。
オリジナルでは矛盾が生じた場合、主要関数はFalseを返し、そうでなければvaluesを返している。私は単純にFalse、Trueを返すことにした。但し補助的な関数については、求められている値を返す。
全体の構成はこのようになった。末尾のサンプル・コードは、ここまでを実装したものだ。
サイトを一読し、コードを書き始め、サイトとコードを行き来しながら作業を進めた。一通りのコーディングを終え、デバッグに専念し始めたのが夕方6時頃だった。ここからのデバッグが長かった。ロジックの理解不足、その実装ミスが原因だと思い込んでいたのだが、実際には単なるコーディング・ミスだった。
ハマり処
ロジックが同一であることを期待しているからと言って、一から手打ちし直したコード、さらに構造も再編したコードが素直に動作するわけがない。ここから問題を追って、手直しを加えていくのは手間もかかるし、まどろこしくもなるのだが、休憩を挟みながら、地道に根気よく、手直しを繰り返してくことで、ロジックの理解が深まる。
期待通りの結果が返らず、assign、eliminateの番号消去に問題がある、と疑っていた。そこでcheck_unit、check_peerのロジックを追いかけていた。結局、エラーの原因は別のところにあった。ユニット、ピアを生成するget_posのロジックに問題があったのだが、これに気付くまでに何時間を要したことか。生成されているピアの座標に重複が含まれていることに「偶然」気づいたのだ。
最初の実装では行、列座標を生成し、ボックス座標の生成中に重複排除を行っていた。このやり方は不味かった。重複排除は行、列で実施したほうが考えやすいことに気付いた。それが現在の実装に反映されている。
ここまでで2日の正午過ぎ。勘違いから、見当違いの箇所を無駄に追跡し続けていたのだ。率直に言って、かなりの時間を無駄にした。
実行結果
テスト結果を投稿末尾に掲載している。
まずPiscine資料に掲載されている問題を試す。良好な結果が返される。オリジナルのgrid1に指定されていた問題を試す。こちらも良好な結果が返された。
問題は次の難問だ。参照サイトにて言及されているように、ここまでの実装では、まだ不十分なのだ。このような難問に対処するための実装が残っている。
小さな成功の積み重ねが、自信につながる。
By Odin, by Thor ! Use your brain !!!
テスト結果
Piscine掲載の問題
"9...7...." "2...9..53" ".6..124.." "84...1.9." "5.....8.." ".31..4..." "..37..68."
🔎結果
914|375|268 287|496|153 365|812|479 ---+---+--- 846|521|397 529|637|814 731|984|526 ---+---+--- 153|749|682 698|253|741 472|168|935 914375268 287496153 365812479 846521397 529637814 731984526 153749682 698253741 472168935
grid1指定の問題
'..3.2.6..' '9..3.5..1' '..18.64..' '..81.29..' '7.......8' '..67.82..' '..26.95..' '8..2.3..9' '..5.1.3..'
🔎結果
483|921|657 967|345|821 251|876|493 ---+---+--- 548|132|976 729|564|138 136|798|245 ---+---+--- 372|689|514 814|253|769 695|417|382 483921657 967345821 251876493 548132976 729564138 136798245 372689514 814253769 695417382
難問
'4.....8.5' '.3.......' '...7.....' '.2.....6.' '....8.4..' '....1....' '...6.3.7.' '5..2.....' '1.4......'
🔎結果
4167912679|13923691269|812395 2678931256789|14589245691245689|126791249124679 268915689125689|72345691245689|1236912349123469 ---+---+--- 37892135789|3459345794579|13579613789 367915679135679|359825679|41235912379 36789456789356789|34591245679|235792358923789 ---+---+--- 28989289|64593|1259712489 5678936789|247914789|136913489134689 167894|5895795789|235692358923689 416791267913923691269812395 267893125678914589245691245689126791249124679 268915689125689723456912456891236912349123469 37892135789345934579457913579613789 36791567913567935982567941235912379 3678945678935678934591245679235792358923789 28989289645931259712489 5678936789247914789136913489134689 1678945895795789235692358923689
サンプル・コード
