新聞に数独の問題が載っているのをちょくちょく見かけて、コンピューターで解いてみたらどうなるだろうと、
思っては忘れて、また見て思い出しては忘れを繰り返していましたが、ちょっと時間ができたのでプログラミングすることにしました。
最初はコンピューターを力まかせに使って、９×９の枡に１から９まで順番に入れていけばいいのでは？
と単純に考えてたら、9の81乗を計算するのはとてもナンセンスな事に気がついて、あっ。無理か。 ってことで、
あれこれ考えた結果こんなふうになりました。
ボーっと枡を眺めながら解き方を考えてみました。
ひとつの答えを導くだけなら、１枡ずつ入れられる値を順番に見ていけばよさげです。
横軸をｘ方向、縦をｙ方向にして、左を０、右を８、上を０、下を８と考え、左から右、上から下の順番に入れられる値の候補を都度計算して
いれられなかったら、ひとつ戻って次の候補を入れなおす。
こんなやり方で解けそうです。
| X方向 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ｙ方向 |
|
始まりは左上、終わりは右下と決めたので。
右下よりも、下方向を参照しようとした時は、既に全枡に値が埋まっているわけですから完成して終了です。
逆に、左上の外側を参照しようとした時は、求める答えが見つからない時なのでエラーとしました。
着目点（赤丸の位置）に置ける候補は、赤丸から横列を見たとき、8,3,5、縦を見たとき、6,9,1があり、３×３のエリアには5があるので、
置ける候補は、2,4,7の3種類となり、この情報を保存します。
| ● | ８ | ３ | ５ | |||||
| ５ | ４ | １ | ||||||
| ６ | ９ | |||||||
| ７ | ８ | １ | ９ | |||||
| ３ | ５ | ８ | ||||||
| ９ | １ | ２ | ４ | |||||
| ３ | ６ | |||||||
| １ | ４ | ９ | ||||||
| ２ | ５ | ３ |
横列、縦列に加え、着目点の周囲（３×３のエリア）は、着目点に応じた次のテーブルを参照して4箇所確認します。
図の■が確認する位置です。
static const int chkOffset[3][3][4][2] =
{
{
{{ 1, 1},{ 2, 1},{ 1, 2},{ 2, 2}}, //1
{{-1, 1},{ 1, 1},{-1, 2},{ 1, 2}}, //2
{{-2, 1},{-1, 1},{-2, 2},{-1, 2}} //3
},
{
{{ 1,-1},{ 1, 1},{ 2,-1},{ 2, 1}}, //4
{{-1,-1},{ 1,-1},{-1, 1},{ 1, 1}}, //5
{{-2,-1},{-1,-1},{-2, 1},{-1, 1}} //6
},
{
{{ 1,-2},{ 2,-2},{ 1,-1},{ 2,-1}}, //7
{{-1,-2},{ 1,-2},{-1,-1},{ 1,-1}}, //8
{{-2,-2},{-1,-2},{-2,-1},{-1,-1}} //9
}
}
|
|
|
|||||||||||||||||||||||||||
|
|
|
|||||||||||||||||||||||||||
|
|
|
プログラムとしては核の部分になります。
候補の中から、枡に値を置いて着目点を次の位置へ移動します。
次の位置に固定値が置かれているときは、その先へ着目点を移動します。
候補が複数個あるときは、最初に該当した値を置きます。
候補が無いときは、着目点をひとつ戻して①、次の候補をに置きなおします②。
着目点を戻すときは、次の候補選びに影響を及ぼさないよう現在の着目点の値をクリアします③。
こんな感じ。
case 1: /*置けない*/
while (1)
{
if (backPos() != 0) //①
{
sw = 2;
break;
}
if (putNo() == 0) /*置けた②*/
{
if (calNextPos() != 0) /*終了*/
{
sw = 1;
}
break;
}
else /*置けなかった*/
{
clrNo(); //③
}
}
break;
作成したプログラムを、Linuxのｃコンパイラでコンパイルし実行しました。
演算中の表示を外せば、瞬時に算出できることが確認できたので目的達成です。
プログラムの例題の実行結果。
4,3,8,7,9,2,5,6,1,
6,9,1,5,8,3,7,4,2,
5,2,7,4,6,1,8,9,3,
1,8,6,3,5,7,9,2,4,
3,7,2,9,4,6,1,8,5,
9,4,5,2,1,8,3,7,6,
2,1,9,8,3,4,6,5,7,
7,5,3,6,2,9,4,1,8,
8,6,4,1,7,5,2,3,9,
作成したソースコードはここです。