数独を解くプログラム
数独の正式版を解くプログラムを考える前に、 数字の数を少なくしたよりシンプルな
簡易版を解くプログラムを検討しましょう。
プログラムの構成は メインプログラムと機能別に分れた複数の外部副プログラムか
らなります。 枠の表示や数字の表示そしてブランキングに関する外部副プログラム
については 既に問題作成プログラムの所で説明しているので、 ここでは説明を省略
します。
メインプログラムはテキストファイルから問題のデータを読み込むようになっています
。ブランキングされたマス目については、数字の０が割り当てられています。したがっ
て、以下のような問題の場合は、
＜数独の問題（例）＞
（図１、十進ＢＡＳＩＣによる２Ｄグラフィックス）
次のようなデータ内容を持つファイルが必要となります（半角の数字で入力）。
一行目 -> ０，０，３，２
二行目 -> ０，０，０，０
三行目 -> ４，０，０，０
四行目 -> ２，０，１，０
メインプログラムを起動すると、 図１のような問題画面ウィンドウがポップアップしま
す。 数字とブランキング位置に問題がなければ、 ”解を表示しますか？”というメッセ
ージボックスのＯＫボタンを押して解を表示させます（図２参照）。
＜数独の問題（解）＞
（図２、十進ＢＡＳＩＣによる２Ｄグラフィックス）
次に、 このプログラムの主要部であるＳＯＬVERという問題を解く外部副プログラム
について簡単に説明します。
ＳＯＬＶＥＲのプログラムは数独のルールに基づいて作られています。 基本的に、 数
字の整合性をチェックする４つの部分から構成されます。
（１）太枠内、 縦及び横に並んだ各４つの数字の内３つが既知ならば 残りの一つの
数字を決定できる
（２）ある特定の数字が３つ存在すれば、４つ目の数字のマス目を決定できる
（３）太枠内の数字の内２つが判らなくても、枠外の数字の情報からそれらを決定でき
る場合がある
（４）太枠内の数字の内３つが判らなくても、枠外の数字の情報から判っている数字の
上下左右の数字を決定できる場合がある
以上のポイントに従って各部分はコーディングされています。（２）〜（４）に関しては判
り辛いと思うので、以下の図を参考にしてください（図３〜図５を参照）。
＜（２）に関する説明図＞
（図３、十進ＢＡＳＩＣによる２Ｄグラフィックス）
赤マルのマス目の位置に同じ数字が入っているとすると、 黒マルのマス目の位置に
も同じ数字が入ることに注意してください。
＜（３）に関する説明図＞
（図４、十進ＢＡＳＩＣによる２Ｄグラフィックス）
左下の太枠内で赤マルと青マルのマス目に既に異なる数字が入っている状況で、枠
外の緑マルのマス目に数字があれば、枠内の黒マルのマス目にも同じ数字が入るこ
とに注意してください。
＜（４）に関する説明図＞
（図５、十進ＢＡＳＩＣによる２Ｄグラフィックス）
左下の太枠内で赤マルのマス目に数字が一つだけ入っている状況で、 枠外の緑マ
ルのマス目に数字があれば、枠内の黒マルのマス目にも同じ数字が入ることに注意
してください。
課題（その１）
上記のプログラムで解けない問題があるか調べてください。もし、あるとすれば、ＳＯ
ＬＶＥＲのプログラムにどのようなコードを追加しなければなりませんか。
課題（その２）
問題そのものに論理矛盾があった場合に、 それを検知し警告を出すプログラムを作
成してください。 また、 このプログラムをＳＯＬＶＥＲのプログラムに組み込んでくださ
い。
それでは、数独（正式版）の問題を解くプログラムを考えてみましょう。メインプログラ
ムとＳＯＬＶＥＲのコード部分を除いた他の外部副プログラムは以下のようになります
。
ＳＯＬＶＥＲの具体的なコードがここに入ります。
ＳＯＬＶＥＲのプログラムコードを考えるために必要なポイントを纏めてみます。 簡易
版の所で出てきたポイントが基本になりますが、 その内容はさらに複雑になります。
ウィキペディアの問題例（図６参照）が解けるレベルのものを考えます。
＜ウィキペディアの問題例＞
（図６、十進ＢＡＳＩＣによる２Ｄグラフィックス）
（１）と（２）は以下のようにストレートに拡張できますが、中級レベル以上の問題を解く
初期の段階では、 これらのポイントはあまり役に立ちません（但し、 終盤では極めて
有効なポイント）。
（５）太枠内、 縦及び横に並んだ各９つの数字の内８つが既知ならば、 残りの一つの
数字を決定できる
（６）ある特定の数字が８つ存在すれば、９つ目の数字のマス目を決定できる
（３）や（４）に相当する初期の段階でも使えるポイントを探してみます。 数字を求める
手順を複雑にし過ぎると、コーディング自体も煩雑になるので注意してください。プロ
グラムのコンパクト化と判り易さはトレードオフになります。 正式版の場合、 求める
数字の数もかなり増えるので、 ここではプログラムのコンパクト化に焦点を当てて考
えます。 従って、 上記の２つのポイントだけでなく、（６）の内容も統合したポイントは
次のようになります。
（７）太枠内の判らない特定の数字のマス目は 枠外のその数字の情報から決定でき
る場合がある
このポイントに関する記述はシンプルですが、 これを使えば中級レベル以下の問題
は解けるようになると思います。
＜（７）に関する説明図＞
（図７、十進ＢＡＳＩＣによる２Ｄグラフィックス）
左下の太枠内を見てください。 左側の一列に数字が全て入っている状態で、枠外の
緑マルに同じ数字が入っていれば、黒マルにもその数字が入ることに注意してくださ
い。
課題（その３）
（７）のポイントだけを使って、ウィキペディアの問題例（図６参照）を最後まで解いてく
ださい。
（７）のポイントのみを考慮したＳＯＬＶＥＲのプログラムコードは以下のようになります
。
中間部分は省略します。
このプログラムを使ってウィキぺディアの問題例（図６参照）を解いた結果を図８に示
します。
＜ウィキペディアの問題例（解）＞
（図８、十進ＢＡＳＩＣによる２Ｄグラフィックス）
プログラム自体は人間が作ったものですが、一瞬で問題を解くコンピュータの処理速
度の凄さを実感してください。ＩＱが飛びぬけて高い人間でも、このコンピュータの速度
には付いていけません。
課題（その４）
上記のＳＯＬＶＥＲのプログラムコードに （５） のポイントも考慮したコードを追加してく
ださい。
課題（その５）
上記のプログラムでは数独の難問は解けません。 難問を解くために必要なポイント
を纏めてください。また、それ（又はそれら）をコード化してください。