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

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

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

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

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

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']];
      }
    }
  }
}