■ 数独ソルバー
■ データ構造
- 各マスの値（1～9, 空欄は0）を uint8 の数値で表現し、盤面全体を１次元配列で表す。
- 数値ではなくビットマップを用いる方法もあり、その方が高速になるが、大差ないし、ビットマップに慣れていない人には理解しずらくなるので、本稿では数値とする
- 盤面は２次元なので２次元配列でもよいのだが、一般的に２次元配列は低速なので、１次元配列とした。
■ アルゴリズム
- 人間が数独の難問を解くのは大変だが、意外なことに最近のCPUであれば、単純な探索アルゴリズムにより、どんな難問でも短時間で解を求めることができる
- 探索木の大きさが、人間には膨大でも、CPUにとっては手頃なサイズということだ。
- 擬似コードは以下の通り
bool solve(int ix) {
if( ix は盤外？ ) return true; // 解発見
for(int n=1; n<=9; ++n) {
if( 盤面[ix] に n を配置可能か？ ) {
盤面[ix] = n; // 盤面[ix] に n を配置
if( solve(ix+1) )
return true; // 解発見の場合
}
}
盤面[ix] = 0; // 空欄に戻しておく
return false;
}
void solve() {
solve(0);
}
- 場所に関するループで処理してもよいのだが、再帰関数にした方が（筆者には）直感的でわかりやすいのでそうしている。
- 上記コードで不明なのは、盤面[ix] に n を配置可能かどうかをどう判定するか？という部分である。
- ix 位置の縦・横方向、ブロック内に既にその数字が配置されていないかどうかを単純にチェックすればよい
int x = ix % 9; // 横方向位置
int y = ix % 9; // 縦方向位置
int x0 = x - x % 3; // 属するブロックの左端位置
int y0 = y - y % 3; // 属するブロックの上端位置
int bix0 = y0 * 9 + x0; // 属するブロックの上左端位置
uint8 used[10] = {0,0,0,0,0,0,0,0,0,0}; // 各数字が既に使われているかどうか
for(int i=0; i<9; ++i) {
used[m_cell[y*N_HORZ+i]] += 1;
used[m_cell[i*N_HORZ+x]] += 1;
}
for (int i = 0; i < 3; ++i) {
for (int k = 0; k < 3; ++k) {
used[m_cell[ix0 + i*N_HORZ + k]] += 1;
}
}
以上で準備ができたので、盤面[ix] に n を配置する直前に、used[n] が0かどうかをチェックするとよい
■ パフォーマンス計測
- 上記アルゴリズムを C++ で実装し、（人間的には）難問100問を解かせ、それに要する時間を計測した。
- 環境：VS2017, Windows10, Core i7-6700@3.4GHz, 16GBMem
- 結果：約500ミリ秒/100問 （１問あたり約5ミリ秒）
