カテゴリー別アーカイブ: 数独

【数独プログラミング】問題チェック

  • 公開されている数独問題は、解がひとつしかないのが普通だ
    • 解が複数存在する問題は綺麗ではないし、解答を載せる場合にも話がややこしくなる。
  • 先に示したソルバーアルゴリズムでは解を発見したときに、探索をやめてしまうが、問題が唯一解を持つかどうかを判定したい場合は、解をひとつ発見しても探索を継続する。
  • 探索を継続し、2つめの解を発見した場合は、別解を持つことが確定するので、そこで探索をやめる。
  • 探索を終了した時点で、解を発見していた場合は、正しい問題となる。
  • チェック処理には、先のソルバーの約2倍の時間が必要
  • コードは以下のようになる
int g_count;  //  発見した解の個数
bool check() {
  g_count = 0;
  check(0);
  return g_count == 1;
}
bool check(int ix) {
  if( ix が盤面外 ) {  //  解を発見
    if( ++g_count > 1 ) {  // 解を複数発見
      return false;
    }
    //  最初の解を発見した場合は、探索を継続
  }
  for(int n = 1; n <= 9; ++n) {
    盤面[ix] に n を設定
    if( !check(ix+1) ) return false;  //  解を複数発見した場合
  }
  盤面[ix] = 0;
  return true;
}

数独プログラミング:ソルバー

■ 数独ソルバー

  • 数独」(Sudoku, ナンプレ、ナンバープレースとも呼ばれる)は非常に人気のあるパズルで、制約充足問題の一種である。
  • 「ソルバー」とは問題を解くプログラムのことである

■ データ構造

  • 各マスの値(1~9, 空欄は0)を uint8 の数値で表現し、盤面全体を1次元配列で表す。
  • 数値ではなくビットマップを用いる方法もあり、その方が高速になるが、大差ないし、ビットマップに慣れていない人には理解しずらくなるので、本稿では数値とする
  • 盤面は2次元なので2次元配列でもよいのだが、一般的に2次元配列は低速なので、1次元配列とした。

■ アルゴリズム

  • 人間が数独の難問を解くのは大変だが、意外なことに最近の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問 (1問あたり約5ミリ秒)