2025/11/04 14:30 Solving Every Sudoku Puzzle (2006)
ロボ子、数独を解くPythonプログラムについての記事は読んだかのじゃ？
はい、博士。Peter Norvig氏が書いた記事ですね。制約伝播と探索という二つのアイデアを使っているのが面白いと思いました。
そうじゃ、そうじゃ。数独は81個のマスで構成されていて、列は1-9、行はA-Iでラベル付けされているんじゃな。
はい。各ユニット（列、行、ボックス）に同じ数字が2度出現せず、すべての数字が1度ずつ出現するようにマスを埋めるんですよね。
その通り！Pythonでの実装では、ユニット、ピア、マスの概念を実装しておる。制約伝播戦略として、あるマスに1つの可能な値しかない場合、その値をピアから削除したり、あるユニットで、ある値が1つのマスにしか入り得ない場合、そのマスにその値を配置したりするんじゃ。
なるほど。`assign(values, s, d)`関数は、マス`s`から`d`以外のすべての値を削除して制約を伝播させるんですね。`eliminate(values, s, d)`関数は、マス`s`から値`d`を削除する、と。
そうじゃ。深さ優先探索も使っておるぞ。未入力のマスの中で、可能な値が最も少ないマスを最初に選択するんじゃ（最小残存値ヒューリスティック）。
記事によると、簡単な数独パズルは1/5秒未満で解決できて、難しいパズルも0.01秒で解決できるんですね。すごい！
じゃろ？じゃろ？簡単なパズル50個、難しいパズル95個、最も難しいパズル11個、ランダムなパズル99個を解決したそうじゃ。ランダムなパズルの平均解決時間は0.01秒じゃと。
でも、最も時間がかかったランダムパズルは188.79秒もかかったんですね。複数の解を持つから真の数独パズルではない、と。
ふむ。乱数生成パズルは、少なくとも17個のマスが埋められ、少なくとも8個の異なる数字が含まれている場合、完了とみなされるんじゃ。生成されたパズルの約0.2%は解がないらしいぞ。
実行時間は正規分布ではなく、裾の重い分布を示すんですね。平均と中央値はほぼ同じだけど、最大値はサンプル数が増えるにつれて増加する、と。
この記事は、さまざまなプログラミング言語に翻訳されているそうじゃ。ロボ子も色々な言語で実装してみると良いぞ。
はい、博士。勉強になります！ところで博士、数独が得意なんですか？
ふっふっふ。私にかかれば、どんな数独もイチコロじゃ！…と言いたいところじゃが、実は数字が苦手なんじゃ。
ええっ！博士なのにですか？
まあ、天才にも苦手なことはあるんじゃよ。でも、プログラムなら完璧に解けるから問題ないぞ！
それもそうですね！
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。