すべての縦の列、横の列、3×3のブロックに1から9までの数字をひとつずつ入れていくパズルです。
これを解くプログラムをC言語で作成しました。
解くためのアルゴリズムはほかにもアイデアはあるのですが、ここではバックトラックを取り上げてみました。 問題の解を求めるのにある定まった解法のアルゴリズムに従うのではなく、試行錯誤を用いるものです。 チェス盤で行う「騎士の巡回(knight's tour)」や「八王妃問題(eight queen problem)」などに使用されます*。 まず、空き枡を見つけ1から置けるかどうか試し、置けなければつぎの値と順次調べます。 置けたら置いて、つぎの空きを見つけてというように再帰的に調べます。 9まで調べて置けない場合は先ほど置いた数を取り除いて、つぎの値を調べる。 すべて置けた場合でも、それ以外の値でも可能かどうか、 すなわち別解がないかを試すことになります。 つぎのステップが解を求めるための本体部分です。
int Try(int Ban[9][9])
{
int x,y,k;
if (findBlank(&x,&y,Ban)) /* 盤に空いた枡(x,y)があるか */
for(k=1;k<=N;k++)
{
if(isOkeru(x,y,k,Ban)) /* 枡(x,y)にkを置けるか */
{
Ban[x][y] = k; /* 置けるなら置く */
Try(Ban); /* 次を確かめる */
Ban[x][y] = 0; /* 枡(x,y)にkを置けないとして別の置き方はないか */
}
}
else
{
printf("Solution\n"); /* 解が見つかった */
PrintBan(Ban);
}
return 0;
}
盤上の空きを調べるには、問題のデータに空白の印として0を入れておき、
盤の左上から順番に調べて空き枡(x,y)を探します。もしあればその座標xとyおよび
返値として真(True)を、なければ偽(False)を返します。盤に空きがなければ完成です。
なお、あらかじめTrueには非零、ここでは-1を、Falesには零を定義しておきます。
空いた枡を見つける関数はつぎのように書けます。
int findBlank(int *x,int *y,int Ban[9][9])
{
int i,j;
for(i=0;i<:9;i++)
for(j=0;j<9;j++)
if (Ban[i][j] == 0)
{
*x=i; *y=j;
return True;
}
return False;
}
もう一つの小道具ルーチンはkを盤BAN[x][y]に置けるかどうかを調べるもので、
横、縦、ブロック内に同じ数がないかを調べます。
int isOkeru(int x,int y,int k,int Ban[9][9])
{
int i,j;
for(i=0;i<:9;i++) if (Ban[i][y] == k) return False; /* 横に同じ数はないか */
for(j=0;j<:9;j++) if (Ban[x][j] == k) return False; /* 縦に同じ数はないか */
for(i=0;i<:3;i++) /* blockに同じ数はないか */
for(j=0;j<:3;j++)
if (Ban[3*(x/3)+i][3*(y/3)+j] == k) return False;
return True;
}
この3つのルーチンが本プログラムの本体部分で、これ以外に、データ入力、
盤の出力などの機能と全体を制御する主関数が必要です。
ここではデータ入力は主関数で行っています。全体のソースプログラムははこのようになっています。 MS Windowsのコマンドプロンプトで動く 実行プログラム、 サンプルのデータファイルは こちらとこちらです。実行ファイルはzip形式で圧縮してありますので解凍してお使いください。 Sudoku.exeとデータファイルを同じフォルダに置いて、
Sudoku BS0612.txt
と入力、最後にEnterキーを押して実行してみてください。
つぎの図は左上の問題のときの出力例です。 つぎは問題のテーブルから4行1列の6を空白にして解が2つある場合の例です。  極端な例として全部空白の場合でも解を求めることができます。 適当なところでCtrl+Cを入力して止めないと延々と解を出力し続けます。
*(Niklaus Wirth:ALGORITHS+DATA STRUCTURE=PROGRAMS)
|