16×16や25×25の数独を計算量を抑えて作成したい


下記のように数独を作るプログラムをかきました。

  1. 升目を初期化する（例 1～9までの場合は9×9の升目を初期化する）
  2. 左上から幅優先探索で値をランダムに入れていく
  3. ランダムで入れていき、（行・列・ブロック内でかぶって）入れられる値がなくなったら、かぶった２つの升目を初期化して再度実行

9×9では問題なく（遅いと感じることなく）作成できたのですが、 16×16では途端に重くなり、無限ループのようになり処理が終わりません。

上記3の、 升目に入れられる値がないときに、かぶった２つの升目を初期化して再度実行、 が永遠繰り返されるように見受けられたので、
かぶった値をメモして、再度実行の際にはそれを省いて実行しようとしたのですが、 たいしたかわらずでした。（ソースは汚くなったのでここでは省略）

別の観点での実装方法やソース中の改善方法等、教えてほしいです。

[code]

    public function make()
    {
      // 数独のブロック数
      $blkNum = 9;
    
      // マスを初期化
      for ($i = 0; $i < $blkNum; $i++) {
        for ($j = 0; $j < $blkNum; $j++) {
          $d[$i][$j] = -1;
        }
      }
    
      // startを左上に設定
      $sx = 0;
      $sy = 0;
      $d[$sx][$sy] = rand(1, $blkNum); // set start to init
    
      // move vector
      $dx = [0, 1, 0, -1, 0];
      $dy = [0, 0, 1, 0, -1];
    
      $queue = [[$sx, $sy]];
      // [0] : x
      // [1] : y
    
      while ($queue) {
        $now = array_shift($queue);
        for ($i = 0; $i < 5; $i++) { // vector movement num
          // nx, ny : after move mass
          $nx = $now[0] + $dx[$i];
          $ny = $now[1] + $dy[$i];
    
          if ($nx >= 0 && $nx < $blkNum && $ny >= 0 && $ny < $blkNum && isset($d[$nx][$ny]) && $d[$nx][$ny] == -1) {
            // 挿入する値を計算する
            // ※やっていることはランダムで値を渡し、行・列・ブロックで重複しなければその値を採用する
            $calc = $this->__put($d, $nx, $ny, range(1, $blkNum));
            if ($calc['result'] === true) { // 正常に値がとれたときは値をいれ、pushする
              $d[$nx][$ny] = $calc['value'];
              array_push($queue, [$nx, $ny]);
            } else { // 正常に値がとれなかったとき
              // 重なっている部分を初期化し、
              // queueにつみpushする
              $d[$nx][$ny] = -1;
              $d[$calc['err_x']][$calc['err_y']] = -1;
              array_push($queue, [$calc['err_x'], $calc['err_y']]);
              array_push($queue, [$nx, $ny]);
            }
          }
        }
      }
    }
    
    /**
    * __put パラメータに入る値を取得する
    *
    */
    private function __put($d, $nx, $ny, $param) 
    {
      // 配列をランダムにしてqueueでとってい く
      shuffle($param);
      while($param) {
        $p = array_shift($param);
        // 値をチェックする（行・列・ブロック内での重複チェッ ク）
        $check = $this->__check($d, $nx, $ny, $p);
        if ($check['result'] === true) { // チェックok -> return
          return ['result' => true, 'value' => $p];
        } else { // チェックNG -> paramを減らしてregression
          if ($param) {
            return $this->__put($d, $nx, $ny, $param);
          } else { // paramがないと き
            // 最後まで値が入らなかったので、重複チェックで引っかかったx,yをreturnする
            return ['result' => false, 'value' => $p, 'err_x' => $check['x'], 'err_y' => $check['y']];
          }
        }
      }
    }
    
[/code]




あたりをつけて、簡単な検証しかしてませんので参考までに…

手順は

  1. 基本形の生成
  2. シャッフルする

です。

  1. は、

python ですが、以下のコードで 水平方向昇順なシンプルな数独が生成できます。

[code]

    def create(num=3):
        num2 = num * num
        g = [[0]*num2 for i in range(num2)]
    
        for y in range(num2):
            yy = (y * num) % num2 + int(y / num)
            for x in range(num2):
                g[x][yy] = (num2 - y + x) % num2 + 1
    
[/code]

9x9(num=3)だと

` a b c d e f g h i 1 2 3 4 5 6 7 8 9 7 8 9 1 2 3 4 5 6 4 5 6 7 8 9 1 2 3 9 1
2 3 4 5 6 7 8 6 7 8 9 1 2 3 4 5 3 4 5 6 7 8 9 1 2 8 9 1 2 3 4 5 6 7 5 6 7 8 9
1 2 3 4 2 3 4 5 6 7 8 9 1 `

って感じです。(a-zは 2で使うので付与してます)

  2. シャッフル

1.で生成したものを数独を壊さないようにシャッフルします。

下記条件を満たせば数独は壊れません。

  * a列 と、b(or c)列の入れ変え
  * a,b,c列と d,e,f(or g,h,i)列の入れ変え

これは、行でも成り立ちますので、計4つのシャッフルを十分な回数実行すれば、 ランダムな数独になると思います。

