「ナンバープレース」の解法プログラムです。
拙作の「ナンバープレース」には、問題自動生成プログラム mknmpl??.exe が付属していますが、そこに組み込まれている解法アルゴリズムでは解けない問題があったので、バックトラックにより力ずくで解くことにしました。ところで、ドキュメントには「解法プログラムは Tcl でも簡単に作成でき、短時間で答えが出せる」と書きましたが、バックトラックで問題を解くとなると、話が違ってくるのです。大きな盤面になると Tcl では時間がかかるので、Ｃ言語でプログラムを作りました。
ナンバープレースは、ヒントの数字から次に示す条件を使って、空き場所の数字を決定することができます。
(1) 数字がひとつしか入らない場所を探す (2) 縦、横、枠のそれぞれについて、置ける場所がひとつしかない数字を探す
これを「確定サーチ」と呼ぶことにします。空き場所に置くことができる数字は、その場所が属している、縦、横、枠のいずれにも使用されていない数字です。9 行 9 列盤であれば、1 から 9 までの数字の中から、縦、横、枠で使われている数字を削除すれば求めることができます。そして、残った数字がひとつであれば、その数字で確定することができます。これが条件 (1) です。これで確定できない場合は条件 (2) を使います。次の表を見てください。
| 行 | 確定した数字 | 置くことができる数字 |
|---|---|---|
| １ | １ | 確定 |
| ２ | ０ | ３，６ |
| ３ | ０ | ３，５，６ |
| ４ | ８ | 確定 |
| ５ | ４ | 確定 |
| ６ | ０ | ３，６ |
| ７ | ２ | 確定 |
| ８ | ９ | 確定 |
| ９ | ７ | 確定 |
表では 3, 5, 6 の数字が未確定です。ここで数字 5 に注目してください。縦の中で 5 を置くことができる場所は、3 行目の 1 カ所しかありませんね。したがって、この場所は 5 に確定することができるのです。同じように、横、枠の中からもこの条件を満たす数字を探すことができます。
数字をひとつ確定すると、そのことにより条件 (1) や (2) を満たす場所が出てくるので、その場所を探して数字を確定します。あとはこれを繰り返すだけです。この解き方は、人間がナンバープレースを解くときに使う方法です。拙作のナンバープレースは、入力できる数字を水色のボタンで表示しているので、条件 (1) や (2) を満たす場所を簡単に探すことができるようになっています。雑誌に掲載されているナンバープレースは、この確定サーチだけでほとんどの問題が解けるのですが、世の中そう甘くはありません。これでは解けない難しい問題があるのです。
そのような難問をどうやって解いたらよいのでしょうか。筆者には見当もつかないのですが、コンピュータを使えば「総当たり」という力技で解を見つけることができます。つまり、確定サーチでも決まらない場所は、可能性のある数字を入れてみて、それで解けなければ違う数字を試してみる、という試行錯誤によって数字を決定しよう、というわけです。試行錯誤を実現するのに適したアルゴリズムがバックトラックです。パズルを解くプログラムでは常套手段であり、再帰を使えば簡単にプログラムを作ることができます。
実際にプログラムを作る場合、置くことができる数字を高速で求めるための工夫が必要です。問題生成プログラムでは、場所ごとに置くことができる数字をフラグで表しています。数字が確定したら、縦、横、枠の各場所のフラグをクリアすればいいわけです。フラグが立っていれば、その数字を置くことができます。とてもわかりやすいデータ構造ですね。実際に、フラグをクリアするプログラムを示しましょう。
リスト：フラグのクリア
void clear_flag( int n, int x, int y )
{
int i, j, x1, y1;
int off = bitoff[n];
/* 縦横のクリア */
for( i = 0; i < SIZE; i++ ){
flag[x][i] &= off;
flag[i][y] &= off;
}
/* 枠のクリア */
x1 = (x / GRX) * GRX;
y1 = (y / GRY) * GRY;
for( i = 0; i < GRX; i++ ){
for( j = 0; j < GRY; j++ ){
flag[x1 + i][y1 + j] &= off;
}
}
}
配列 board が盤面を表します。置くことができる数字はビットで表し、配列 flag に格納しています。配列 bitoff はビットをクリアするためのデータを格納します。プログラムはフラグをクリアするだけの単純な処理なので、すぐに理解できるでしょう。
ところがバックトラックする場合、各場所ごとにフラグを持たせておくと都合が悪いのです。試行錯誤するのですから、数字を置くだけではなく取り消す処理も必要です。このとき、フラグの状態も元に戻さなければいけないのですが、縦、横、枠の各場所に対して単純にフラグをセットするだけでは、元の状態に戻すことができないのです。次の表を見てください。
上の状態では、5, 6, 8 行目に 3 を置くことができません。ここで、2 行目の場所に 3 を置いてみましょう。すると、3 行目で置くことができる数字は [4, 6] になりますが、5, 6, 8 行目のフラグに変化はありません。ここで、バックトラックが発生して、2 行目の 3 を取り消すことになりました。3 行目の位置は、フラグをセットすれば元の状態に戻りますが、5, 6, 8 行目では無条件にフラグをセットすると、3 を置くことができる状態になり矛盾してしまいますね。結局、フラグの状態を元に戻すには、盤上の数字からフラグを改めて作り直さなければいけないのです。これでは、大きな盤面になると時間がかかってしまいます。16 行 16 列盤の問題生成に時間がかかるのは、これが原因だったのです。
| 行 | 確定した数字 | 置くことができる数字 |
|---|---|---|
| １ | ９ | 確定 |
| ２ | ０ | ３，４，６ |
| ３ | ０ | ３，４，６ |
| ４ | ５ | 確定 |
| ５ | ０ | １，６，８ |
| ６ | ０ | １，６，８ |
| ７ | ７ | 確定 |
| ８ | ０ | １，６，８ |
| ９ | ２ | 確定 |
この対策のために、フラグの状態を保存しておこうか、と考えたのですが、松田晋氏の記事 (参考文献 [1]) によい方法が書いてありました。それは、縦、横、枠のそれぞれについて、置くことができる数字をビットで保持しておく、という方法です。具体的に説明すると、縦、横、枠を表す３つの配列 xflag[], yflag[], gflag[][] を用意し、まだ使っていない数字をビットで表します。このデータ構造にすると、場所 (x, y) に数字を置く処理は、次のようにプログラムできます。
リスト：数字を置く処理
void write_number( int n, int x, int y )
{
int off = bitoff[n];
board[x][y] = 0;
xflag[x] &= off;
yflag[y] &= off;
gflag[ xgrp[x] ][ ygrp[y] ] &= off;
}
配列 xgrp[] と ygrp[] は x と y から枠を求めるための配列です。3 つの配列から数字を表すビットをクリアするだけです。その代わりに、場所 (x, y) で置くことができる数字は、次の計算で求めなければいけません。
( xflag[x] & yflag[y] & gflag[ xgrp[x] ][ ygrp[y] ] )
いちいち AND 演算しなければいけないので面倒なようですが、数字を取り消す処理はとても簡単になります。
リスト：数字を取り消す処理
void delete_number( int n, int x, int y )
{
int on = biton[n];
board[x][y] = n;
xflag[x] |= on;
yflag[y] |= on;
gflag[ xgrp[x] ][ ygrp[y] ] |= on;
}
配列 biton[] はフラグをセットするためのデータを格納しています。縦、横、枠の各フラグをセットするだけなので、短時間で元の状態に戻すことができます。バックトラックする場合、このデータ構造の方が適しています。実際の探索プログラムは、次のようになります。
リスト：探索処理
void search( int pos )
{
int x, y, f;
if( pos == position_count ){
find_count++;
print_board();
return;
}
x = position[pos];
y = position[pos + 1];
f = GET_BIT( x, y );
if( f ){
int n;
for( n = 1; n <= SIZE; n++ ){
if( f & biton[n] ){
write_number( n, x, y );
search( pos + 2 );
delete_number( n, x, y );
}
}
}
}
関数 search() を実行する前に確定サーチを行います。そのときに、確定できなかった場所は配列 position に、個数は position_count に格納します。あとは search() で、これをすべて確定すればいいわけです。
プログラムのポイントは再帰呼び出しです。数字 n を置くことができる場合、write_number() で数字を書き込みます。そして、次の場所の数字を決めるため、search() を再帰呼び出しします。再帰呼び出しから戻ってきたら、delete_number() で数字を取り消して、次の数字を選びます。これで置くことができる数字をすべて試すことができます。
search() の引数 pos の値が position_count と同じ値になれば、すべての場所を確定することができたので、関数 print_board() で盤面を出力します。ここで再帰呼び出しが打ち切られ、これ以上 search() を呼び出すことはありません。
関数を再帰呼び出しする場合、このような停止条件が必要になります。もしも、停止条件を忘れたり、設定した条件を満たさない場合は、再帰呼び出しが止まらず、Ｃ言語では暴走することになります。ご注意くださいませ。
このように、再帰呼び出しを利用すると、バックトラックは簡単に実現することができます。ただし、再帰呼び出しに慣れていないと、このプログラムを理解するは難しいかもしれません。納得できない方は、人間トレーサーになってプログラムの動作を追いかけてみてください。
ところで、松田晋氏が作成されたプログラム (参考文献 [1]) では、バックトラックの中で確定サーチを行っています。これに対し、このプログラムは確定サーチで数字を決定し、それでも決まらない場所に対して、単純にバックトラックで数字を決定します。確定サーチだけでも解ける問題がありますし、たとえ数字が決まらなくても、確定サーチを行うことで可能性のある数字を減らすことができるので実行時間は速くなります。
どのプログラミング言語でもそうですが、上達の秘訣は実際にプログラムを作ってみることです。ところが、いざとなると「さて、何を作ろうか？」と困ってしまう方も多いのではないでしょうか。このようなときにぴったりの題材が「パズルの解法」です。なんといっても、実際にパズルが解けたときの喜びは大きく、プログラムを作る意欲をかきたててくれます。このプログラムに興味を持った方は、ほかのパズルにも挑戦してください。