php言語を使用して、ナンプレ(数独)の答えを導き出す方法が知りたいです。
最近ハマっているナンプレを自動で計算してみたく作り出したのですが、アルゴリズムのところから
考えが煮詰まり投稿させていただきました。
PHPも勉強の一貫で使用して解きたいと考えております。
自分が考えているアルゴリズムは下記の通りです。
−−−−−−−−−−−−−
前提条件:2次元配列を使用します。
1.適当な数字をランダムに記載した配列を準備する。(09)(9)の作業を繰り返す
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)
12.問題ない場合、一行と1列と3*3マスの合計が"45"になるか確認する
13.問題なければ、結果を出力
−−−−−−−−−−−−−
発生している問題・エラーメッセージ
分からない点は、とくに上記でいう(7)の箇所です。
仮置きで数字を入れた場合、次の行などで数字が被った際に、ナンプレでは不正解となります。
その際に、どのような処理をすれば良いか検討つかなかったです。
そもそも考え方のロジックに誤りがありましたら
ご指摘いただけますと幸いです。
該当のソースコード
PHP
1 for($x = 0 ; $x < 9 ; $x++ ){ 2 for($y = 0 ; $y < 9 ; $y++ ){ //二次元配列上のあるひとつの要素に対して 3 $num[] = [1,2,3,4,5,6,7,8,9]; //どの数が入るかのチェック用配列 4 if($data[x][y]==0){ //要素が空(0)なら 5 $count = 0; //カウンタを0にする 6 $renew = 0; //代入用の数を初期化 7 $qtX = x/3; //3×3ブロックのどこに属するか判定 x軸 8 $qtY = y/3; //3×3ブロックのどこに属するか判定 y軸 9 for($n = 0 ; $n < 9; $n++ ){ 10 if($data[x][n]!=0) 11 $num[$data[x][n]-1]=1; //x軸について数を検証(全体で配列のキーは8まで) 12 } 13 for($n = 0 ; $n < 9 ; $n++){ 14 if($data[n][y]!=0){ 15 $num[$data[n][y]-1]=1; //y軸について数を検証(全体で配列のキーは8まで) 16 } 17 } 18 for($s = 3*$qtX ; $s < 3*$qtX+3 ; $s++ ){ 19 for($t = 3*$qtY ; $t < 3*$qtY+3 ; $t++ ){ 20 if($data[s][t]!=0){ 21 $num[$data[s][t]-1]=1; //3×3ブロックについて数を検証 22 } 23 } 24 } 25 for($n = 0 ; $n < 9 ; $n++ ){ //0から9まで 26 if($num[n]==1){ 27 $count++; 28 } //どこにはいるかチェック用の配列のうちON(1)になっているものを数え 29 else if($num[n]==0){ 30 $renew = $n+1; //OFF(0)になっていたら、n+1をとりあえず代入用の数としておく 31 } 32 } 33 if($count==8){ //カウンタが0(9つの数のうち8つの数の配置が確定)なら 34 $data[x][y] = $renew; //data[x][y]は一意に定められるので代入する 35 } 36 } 37 } 38 } 39 40 $count = 0; //カウンタを0にして 41 for($x = 0 ; $x < 9 ; $x++ ){ 42 for($y = 0 ; $y < 9 ; $y++ ){ 43 if($data[x][y]!=0) 44 $count++; //欄が埋まっているか確かめる 45 } 46 } 47 48 if($count==81){ 49 echo "true"; //すべての欄が埋まっていたらTFをtrueにする 50 while($count!=="true"){ 51 return; 52 }//処理はがfalseである限り繰り返される
試したこと
javascriptでナンプレを解かれている方を真似て作ってみました。
補足情報(FW/ツールのバージョンなど)
PHP 7.1.23
Visual Studio Code:バージョン: 1.39.2
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2019/10/21 23:49
2019/10/21 23:54
退会済みユーザー
2019/10/22 00:12