42 SILICON VALLEY Piscine 2017にはRushと呼ばれるグループ・プロジェクトが含まれている。3つの課題のうちの一つが、数独（ナンプレ）を解くプログラムの作成だった。
分からなければインターネット検索し、それでも分からなければ人に聞け、というのが42の学習スタンスだ。数独の解析プログラムの実装は、私にとってはそれを追体験するための格好の題材だった。予定のない正月三が日に集中して取り組んでみた。
1月1日の朝6時に着手し、「簡単な」数独を解けるまでの実装に、2日の午後までを要した。「難しい」数独を解けるまでの実装が完了したのが、3日の14時ごろだった。
今回はいつもとは異なり、プログラムを紹介することを目的とした投稿ではない。サンプル・コードを掲載しているとはいえ、主に紹介するのは、数独が解けるまでの実装についての記録だ。海外Piscine受講者が日々の活動をブログへを投稿している。それと同じような雰囲気を意識している。
前回、「簡単な」数独が解けるまでの記録を投稿した。今回は「難しい」数独が解けるまでの記録だ。前回の投稿を前提として記述しており、必要とされる説明の一部には、前回の投稿でだけ言及しているものがある。読み進める前に、前回の投稿に目を通してほしい。
今回は、一から自分で考えた結果ではなく、とあるサイトの情報を参考に、自分なりに実装した結果をまとめている。サンプル・コードは私が書いたもので、参照サイトのものとは大きく異なるのだが、基本的なロジックは一緒だ。
いつも通り、サンプル・コードはPythonで記述した。Piscine受講生に配慮して、C言語的な記述になるよう配慮しているが、いつも以上に読みにくいのではないかと思う。理由は前回説明した。
準備
Pythonに限らず、言語や開発ツールのインストール不用で、直接オンラインでコードを実行することのできる環境が用意されている。例えば次のサイトだ。サンプル・コードをコピーし、試行錯誤しながら参照してほしい。
paiza.io
実装作業は、次のサイトを参照しながら進めている。実装されるコードは異なるものの、そのロジックはこのサイトで言及されているものだ。
www.aoky.net
適切なロジックを理解する。
「難しい」数独を解くためには何が欠けているのか？テスト結果を確認すると、各マスの候補番号を1つに絞り切れないまま、プログラムが終了している。これらをさらに絞り込むための追加処理が必要なのだ。
この未完成な回答を新たなパズルとして、候補番号の長さが2つ以上のマスに対する検証処理を実装することになる。この検証処理をオリジナルではsearchと呼んでいる。searchはこのような手順を実装している。
- 候補番号の長さが最短のマスを特定する。
- 候補番号の一つが確定したと仮定して、assignを実行する。
- このassign以降の処理は、前回の処理と同一。
- assignは不完全な回答を提示するかもしれない。これを新たなパズルとしてsearchを再帰する。
- 全マスの候補番号の長さが1になれば、それが回答。
- searchを最初に呼び出したパズルの終わりまで処理を繰り返す。
特定マスの値を＜仮定＞することで、その結果を「探索」する試みだ。一見、総当たり的な試みなのだが、候補数が少ない順に処理を進めることで、効率的に対処していることが分かる。
＜仮定＞に際し、バックトラックを使用していない。過程に伴う処理分岐が多すぎるため、バックトラックの巻き戻しは複雑さを伴う。数独の場合は、特定マス一つに対して、番号を一つを保存するだけでは済まず、その仮定の結果生じたピア、ユニットへの変化も巻き戻す必要がある。これの複雑さを回避するため、オリジナルは検証の度にパズル（不完全な回答）を複製し、複製に対して検証を実施している。
写経－ロジックを理解し、書き直す。繰り返して理解を深める。
このロジックを理解するためオリジナルを書き写すのだが、その前にやらなければならないことがある。前回、私はロジックをそのままに、プログラムの構成を独自に変更していた。主要関数の返り値をTrue/Falseにし、回答となるmy_workbdをグローバル変数として実装していた。これらをオリジナルの構成に準拠させなければならない。次のように変更することにした。
- 主要関数の返り値をworkbd（オリジナルのvaluesに相当）に変更した。
- ただし矛盾が生じた場合にはNoneを返す。
NoneはCで言うところのNullポインタと認識してもらえば、当たらずとも遠からずだ。指し示す先が「何もない」、つまりNoneだ。Piscine受講生がサンプル・コードを真似るならば、Noneの代わりにNullポインタを代用することになるだろう。
searchに関する実装を始める前に、これらの変更を反映し、プログラムが正常に動作することを確認しておく。
オリジナルで言うsearchを、サンプルではexploreとして実装している。パズルの中で、候補番号の長さが最短であるマスの座標を特定する処理、全マスで、候補番号の長さが1になったかを検証する処理をそれぞれ、関数getMinPos、isAll1をとして実装した。
補助的な関数を除いて、新しい実装はこれだけだ。その他の処理は前回までのコードを踏襲している。
全体の構成はこのようになった。末尾のサンプル・コードは、ここまでを実装したものだ。
前回までの処理を実行する。そこで出力された結果を新たなパズルとしてexploreが実行される。exploreの再帰を除いて、explorer以降の処理は、前回までの処理と同様であることが分かる。
ハマり処
1月3日、11時までには、ここまでの実装を終えていた。バグがないのは結構なことだが、実は気づいていないだけ、ということもある。
今回の実装では、ハマり処と言われるような場面に遭遇することはなかったのだが、次の悩みどころがあった。
- isAll1 == True時の回答を保存する。
- isAll1 == Trueならば、即座にプログラムを終了させたい。
参照サイトには次の言及がある。
あいにくとこの問題には解が複数あって本当の数独パズルとは言えない。
どうやら一つのパズルが複数の回答を持つことがあるようだ。おそらくオリジナルの次の箇所は、それらを全て捉えることを意図したのだろう。
return some(search(assign(values.copy(), s, d)) for d in values[s]) def some(seq): "seqの要素からtrueであるものをどれか返す。" for e in seq: if e: return e return False
しかしPiscineでは無用の対応だ。回答は一つだけ、と課題は言及している。
• A valid sudoku has only one possible solution.
exploreは再帰する。ループ処理ではないので、isAll1がTrueだからと言って、一連の処理から抜け出ることはできない。再帰中、workbdは複製され続けるのだが、再帰処理の途上で見つかった回答は、再帰元に戻るまでに更新されてしまうかもしれない。これを同時に解決する方法を考えたのだが、結局は安直な方法に走ってしまった。
isAll1 == Trueの回答を、グローバル変数のmy_workbdに保存する。そして、すべての再起が終了するのを待つ。それだけだ。
実行結果
テスト結果を投稿末尾に掲載している。
Piscine資料に掲載されている問題、オリジナルのgrid1に指定された問題は、前回同様、良好な結果を得られた。
問題は次の難問だ。こちらも良好な回答を得ることができた。
ここまでで1月3日のお昼過ぎ、2時前くらい。
本来グループワークである課題を、個人課題としてこなしたのはイレギュラーだが、仮にグループワークを金曜日に始めたとしたならば、日曜日中の提出には間に合ったという格好だ。
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......'
🔎結果
417|369|825 632|158|947 958|724|316 ---+---+--- 825|437|169 791|586|432 346|912|758 ---+---+--- 289|643|571 573|291|684 164|875|293 417369825 632158947 958724316 825437169 791586432 346912758 289643571 573291684 164875293
サンプル・コード
