「数独」と呼ばれるパズルをご存知だろうか。名をナンバープレイス、あるいは略してナンプレともいう。一定のルールに従って、9×9のマス目に数字を埋めていくパズルである。ルールはいたって簡単で、制約は「タテヨコの各列、および、全体を9分割して3×3に区切った各領域で、いずれも1から9までの数字が重複なく配置されるように数字を並べなさい」というだけのもの。いくつかのマスにはあらかじめ初期値が与えられており、それをヒントに空いているマスを埋めていく。制約を満たしつつ全てのマス目に数字を書き入れることができれば、それがゴールである。フィンランドの数学者が作った「世界一難しい数独」」と題した記事がある。この記事で紹介されている「世界一難しい数独」とは、次のような問題だ。世界一難しい数独(ITmediaより)数独を解くことに関してはいささか自信があった私だが、確かにこの問題は難しく、かなりの歯ごたえを感じた。一朝一夕には解けそうもない。業を煮やした私は、計算機の力を借りて解くことにした。既存の数独を解くソフトウェアを利用するのではつまらない。解を探索するプログラムを書くところから始めてみる。解の探索プログラムこの手の問題に対する最も単純な解き方は、力任せに解を探していく方法である。アルゴリズムの骨子は、以下のとおり。空いているマスを、端から順番に試していく。途中まで問題なく進んできたとして、対象とするマスを考えてみる。このマスに、1から9までの数字を順番に埋めて試すことを考えよう。数字を入れて、その段階で制約を満たしているかどうか、判定する。制約を満たしているなら、次の空いているマスに進もう。対象とするマスを1つ進めて、1から次の手順を始めよう。制約を満たしていないときは、数字を更新して、2.に戻る。1から9まで全て試してみて、どれもダメだったら、ここまでの手順に問題があったはず。ここまで埋めてきたマスを1つ戻し、やり直してみる。これは、再帰呼び出しを利用した(深さ優先)探索が適用できる問題の典型的な例だ。再帰呼び出しの終端条件は、制約を満たしたまま、空いている最後のマスまで到達したことに相当する。これをCふうの擬似コードで表現すると、次のように書くことができる。関数check(cell*)は、引数で取るマス目が制約を満たしているか否かを判定するための関数とする。関数の構造を右側のコメントで示した。単純な構成であることが分かるだろう。NGを返そう(やり直し)}ここで、構造体cellの定義は下記のとおり。次に空いているマスへのポインタ};この構造体は、マス目の値と、別の構造体cellデータへのポインタを持つ。このポインタを利用して、あらかじめ次に空いているマスへのポインタを利用したリンク構造を事前の準備で実現しているものとしよう。再帰による解の探索過程では、このリンク構造を上手に使い、空いているマスを辿っていく。リンク構造の終端はNULL、すなわち次を指すポインタがNULLであることで、最後のマスまで到達したかどうかを判定できるというしくみだ。前処理や制約の判定処理まで含め、Cで記述したコードを本稿の末尾に示しておく。クイック・ハックで書いたコードなので、多少の改善を加える余地、リファクタリングすべきコードがまだ残されている点には目をつぶって頂きたい。本プログラム、解を探索するアルゴリズム部分の記述は全体の1割に満たない。データ構造をうまく構築することで、すっきりと記述できることを確認できるだろう。世の中にはいろいろなことを考える人がいるもので、SQLで数独を解くという解説もある。確かに条件に合致した検索を得意とするSQLや、宣言型プログラミングのPrologなどは、この手のパズルを解くためのプログラミングと親和性が高いだろう。本稿で紹介したブルートフォース的なアプローチではなく、人間の思考を辿るような、よりエレガントな解法による解の探求を実現しようという試みもある。このソルバーは、いくつかの定石に従って部分的な解を求めた後で、虱潰しの探索を試みる。本稿で試した問題を実際に試してみると、けっこうな時間がかかったのち、「超むつかしい(別解あるかも?)」というメッセージとともに正解が出た。解の探索方法は本稿で紹介したものと同じながら、探索の過程を可視化して示してくれるツールもある。可視化のスピードを変化させることができ、探索の手順を確認しやすくなっている。数独だけでなく、様々なパズルをプログラミングで解くという課題は、パズルに対する搦め手からのチャレンジだ。皆さんも、夏休みの宿題に、頭の体操として挑戦してみてはいかがだろうか。(MSF)を使って解こうという挑戦。0;}次回は2020年1月下旬に更新予定です。Easyは創刊以来週刊でお届けして参りましたが、2012年4月からは隔週とさせて頂きます。2018年10月にサイトデザインをリニューアルし、SSL対応いたしました。引き続きご愛顧のほどよろしくお願いいたします。