クロススクエアドナンバーパズル(Cross Squared Number Puzzle)

下図のような盤面の □ 部分に0~9の数字を入れ、2桁以上の数値は平方数(n==r*r)となるようにするパズルを「クロススクエアドナンバーパズル(Cross Squared Number Puzzle)」と言う。
※ Cマガジン2000/01 電脳クラブより
本稿では、このパズルを解くためのC/C++プログラムについて解説する。

□□□□■□
□□■□□□
□□□□□■
■□□□□□
□□□■□□
□■□□□□

ちなみに、下図は上記パズルの回答例だ。

1225#6
49#324
49729#
#25921
196#49
6#9216

盤面が大きくなければ単純な探索でも(今時のCPUであれば)すぐに全部の解を求めることができる。
番人付きの1次元配列を用意しておき、最初のマスから最後のマスまで、0~9 の数字を順に入れていき、パズルの条件が成立していれば、それを解として表示すればよい。
全部の場合を生成し、それを逐一チェックするのはパズルプログラミングの基本だ。今時のCPUは驚くほど高速なので、この基本アルゴリズムを使うことで実用的な時間内で解ける問題は数多くある。

void solve(char *board, int ix) {  // ix: 数字を入れる位置
  if( 盤面全部に数字を入れた ) {
    解発見;
    return;
  }
  for(int n = 0; n <= 9; ++9) {
    if( n == 0 && ix が複数桁の先頭 ) continue;
    board[ix] = n;
    if( 複数桁 && 右または下が番人 ) {
      if( 平方数になっていない )
        continue;
    }
    solve(board, ix+1);
  }
}

で、このパズルの場合、考えなくてはいけないのは、入れた数字が平方数かどうかをどうやってチェックするかだ。
単純な方法としては以下のものがすぐに思いつく。

・ int r = (int)sqrt(n) を計算し、n == r*r で判定
・ (6x6までという制限をつければ、)6桁分のテーブルを用意し、数値が平方数かどうかを予め計算しておく

前者は桁数制限がゆるいが、sqrt() の計算時間が大きくなりそうだ。整数演算で平方根を求めるコードを書けば、より高速化できるかもしれない。
後者は処理速度は速いが、桁数が大きくなるとテーブルサイズが肥大化する。平方数である確率は極めて低いので、なんらかの方法でテーブルを圧縮することを考える必要がありそうだ。

んで、実際にコードを書いて処理時間を計測してみたところ、sqrt() を使う版は約1秒、6桁分の平方数かどうかを判定するテーブルを用いたものは約0.66秒であった。
概ね予想どおりだが、sqrt() の処理速度は想像していたよりは遥かに高速だった。
整数演算により平方根を求める関数も書いてみたが、処理時間は約3秒で返って遅くなってしまった。
最近の x86 は sqrt() を処理する命令を持っているので、ソフトで処理するより遥かに高速、ということみたいだ。