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

  • 公開されている数独問題は、解がひとつしかないのが普通だ
    • 解が複数存在する問題は綺麗ではないし、解答を載せる場合にも話がややこしくなる。
  • 先に示したソルバーアルゴリズムでは解を発見したときに、探索をやめてしまうが、問題が唯一解を持つかどうかを判定したい場合は、解をひとつ発見しても探索を継続する。
  • 探索を継続し、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;
}