

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

  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]


CC BY-SA 3.0
2014-12-22T13:05:21.857
2384
2014-12-24T13:39:19.613
2106
question
php アルゴリズム
16×16や25×25の数独を計算量を抑えて作成したい


最初に全ての空きマスに全ての数字のフラグを立てます。 16×16ならば1〜16の数字を各空きマスにセットするということです。

そして、次の4ステップを繰り返します。

  1. 数字が確定している各マスについて、そのマスの縦1列にある空きマスから確定している数字のフラグを取り除く
  2. 数字が確定している各マスについて、そのマスの横1列にある空きマスから確定している数字のフラグを取り除く
  3. 数字が確定している各マスについて、そのマスが属するグループにある空きマスから確定しているのフラグを取り除く
  4. 空きマスに残っているフラグが1つしか無い場合、そのマスを残った数字で確定する

これで結構効率良く出来るはずですが、解けないパターンがあることにも注意して下さい。

[code]

    972 538 164
    861 749 235
    345 AB6 789
    
    789 CD3 456
    126 954 378
    453 867 912
    
    214 675 893
    697 382 541
    538 491 627
    
[/code]

これは2つの正解があります。 A=1, B=2, C=2, D=1 と A=2, B=1, C=1, D=2 です。

無限ループのようになり、とおっしゃっているのはもしかしたら絶対解けない問題を解いているのかもしれません。
9×9では最初にわかっている数字が6つ以下だと解けない、と聞いたこともあります。

終了条件が難しいと思います。


CC BY-SA 3.0
2014-12-22T19:23:11.717
2400
2014-12-24T10:47:19.393
2014-12-24T10:47:19.393
705
705
2384
answer


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

手順は

  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つのシャッフルを十分な回数実行すれば、 ランダムな数独になると思います。


CC BY-SA 3.0
2014-12-24T13:39:19.613
2501
2014-12-24T13:39:19.613
5680
2384
answer