PHPでナンプレを解くプログラム

Question

php言語を使用して、ナンプレ（数独）の答えを導き出す方法が知りたいです。

最近ハマっているナンプレを自動で計算してみたく作り出したのですが、アルゴリズムのところから
考えが煮詰まり投稿させていただきました。
PHPも勉強の一貫で使用して解きたいと考えております。
自分が考えているアルゴリズムは下記の通りです。
−−−−−−−−−−−−−
前提条件：２次元配列を使用します。
1.適当な数字をランダムに記載した配列を準備する。（09）
2.配列に格納されている値をスキャンする（x軸とy軸、33マス）
3.スキャンした値を変数に格納
4.チェック用の配列を準備する[1,2,3,4,5,6,7,8,9]
5.x軸から検証する
6.スキャンしたx軸とチェック用の配列を比べて、該当しそうな数字を仮で決める
7.仮で決めた数字を配列に代入する
8.y軸も(6),(7)の作業を行う
9.33マスも同様の作業を行う
10.すべてのマスに"0"以外の数字が入っている状態かを確認する
11.0が入っていた場合、(6)(9)の作業を繰り返す
12.問題ない場合、一行と１列と3*3マスの合計が"45"になるか確認する
13.問題なければ、結果を出力
−−−−−−−−−−−−−

発生している問題・エラーメッセージ

分からない点は、とくに上記でいう(7)の箇所です。
仮置きで数字を入れた場合、次の行などで数字が被った際に、ナンプレでは不正解となります。
その際に、どのような処理をすれば良いか検討つかなかったです。

そもそも考え方のロジックに誤りがありましたら
ご指摘いただけますと幸いです。

該当のソースコード

           for($x = 0 ; $x < 9 ; $x++ ){
               for($y = 0 ; $y < 9 ; $y++ ){        //二次元配列上のあるひとつの要素に対して
                   $num[] = [1,2,3,4,5,6,7,8,9]; //どの数が入るかのチェック用配列
                   if($data[x][y]==0){       //要素が空（0）なら
                       $count = 0;       //カウンタを0にする
                       $renew = 0;       //代入用の数を初期化
                       $qtX   = x/3;       //3×3ブロックのどこに属するか判定　x軸
                       $qtY   = y/3;       //3×3ブロックのどこに属するか判定　y軸
                       for($n = 0 ; $n < 9; $n++ ){
                           if($data[x][n]!=0)
                            $num[$data[x][n]-1]=1;   //x軸について数を検証（全体で配列のキーは８まで）
                       }
                       for($n = 0 ; $n < 9 ; $n++){
                           if($data[n][y]!=0){
                            $num[$data[n][y]-1]=1;   //y軸について数を検証（全体で配列のキーは８まで）
                       }
                    }
                       for($s = 3*$qtX ; $s < 3*$qtX+3 ; $s++ ){
                           for($t = 3*$qtY ; $t < 3*$qtY+3 ; $t++ ){
                               if($data[s][t]!=0){
                                $num[$data[s][t]-1]=1;   //3×3ブロックについて数を検証
                           }
                       }
                    }
                       for($n = 0 ; $n < 9 ; $n++ ){    //0から9まで
                           if($num[n]==1){
                            $count++;
                        }   //どこにはいるかチェック用の配列のうちON(1)になっているものを数え
                           else if($num[n]==0){
                            $renew = $n+1;  //OFF(0)になっていたら、n+1をとりあえず代入用の数としておく
                       }
                    }
                       if($count==8){    //カウンタが0（9つの数のうち8つの数の配置が確定）なら
                           $data[x][y] = $renew;  //data[x][y]は一意に定められるので代入する
                       }
                   }
               }
           }

           $count = 0;       //カウンタを0にして
           for($x = 0 ; $x < 9 ; $x++ ){
               for($y = 0 ; $y < 9 ; $y++ ){
                   if($data[x][y]!=0)
                    $count++;   //欄が埋まっているか確かめる
               }
           }

           if($count==81){
               echo "true"; //すべての欄が埋まっていたらTFをtrueにする
       while($count!=="true"){
        return;
       }//処理はがfalseである限り繰り返される

試したこと

javascriptでナンプレを解かれている方を真似て作ってみました。

補足情報（FW/ツールのバージョンなど）

PHP 7.1.23
Visual Studio Code:バージョン: 1.39.2

Answer 1

総当りで行くのであれば、全「空白箇所」を配列で持ち、その配列に対して総当りできるようにすれば良いです。

[
 [1,2,3,4,$num[0],6,7,8,9],
 [4,5,6,$num[1],8,9,1,2,3],
 …
]

みたいな感じで、全体を持ち

空白箇所が5箇所であれば、

[(1-9),(1-9),(1-9),(1-9),(1-9),]

を試せば良いことになります。

かなりの力技なので、相当マシンパワーを必要としそうですけど。。。

Comments

[退会済みユーザー]

1箇所変更したときの影響範囲って
・縦
・横
・枠(?)内
って決まってるんで、計算量は大分絞れそうですね。

空白箇所情報に座標 [x,y,枠(?)番号] でも持たせてやると楽な気がします。

[kishin]

@te2ji様
ご回答いただきありがとうございます！
早速参考にさせていただきます。
僕のプログラミング力が追いついておらず良く力技になってしまいがちです...
もし、正攻法のようなマシン負荷の少ない方法などございましたらご教示いただけますでしょうか。

[退会済みユーザー]

実際に手で解くときと同じく、(1-9)の候補を絞ると計算量は減ります。
ただし、絞る方法の実装は総当たりと比べて難しくなります。
空白箇所情報に「可能性のある数字」情報を入れて、それを計算する仕組みにしておけば、絞り込みのアルゴリズムを追加していくことで徐々に計算量を減らすことが可能になると思います。

Answer 2

上記の考え方であれば、一つの手段として
・ マスを埋めた順番を保存しておく配列を用意する
・ 上記の情報に「そのマスが仮置きかどうか」のフラグをつけておく

// $filled_cells: 1番目に埋めたマス, 2番目に埋めたマス, ..., n番目に埋めたマス,  
// マスの情報は array(x座標, y座標, 仮置きならtrue); 
$filled_cells = array(array(5, 3, false), array(6, 2, true), ..., array(8, 7, false));

1. とりあえず仮置きしながら進めていく（仮置きする場合は「候補の数字の中の一番小さい数字」をおく）
2. その後不正解となった場合、直近の仮置きマスまで白紙に戻し、仮置きした数字を「候補の数字の中で次に大きい数字」にして1.に戻る。候補がなくなったら3に進む。
3. さらに直近の仮置きマスまで白紙に戻し、仮置きした数字を「候補の数字の中で次に大きい数字」にして1.に戻る

力技ですが、、いずれは正解にたどり着くかと思います。
なお、配列に要素を追加する関数はarray_push()で、末尾を取り除く関数はarray_pop()です。

Comments

[kishin]

@Kapustin様
早速の回答ありがとうございます！
また分かりやすい回答をしていただき感謝申し上げます。
頭ではイメージ出来ましたので、動かしてみて問題なく解けるか確認作業をしてみます。