🎄teratailクリスマスプレゼントキャンペーン2024🎄』開催中!

\teratail特別グッズやAmazonギフトカード最大2,000円分が当たる!/

詳細はこちら
PHP

PHPは、Webサイト構築に特化して開発されたプログラミング言語です。大きな特徴のひとつは、HTMLに直接プログラムを埋め込むことができるという点です。PHPを用いることで、HTMLを動的コンテンツとして出力できます。HTMLがそのままブラウザに表示されるのに対し、PHPプログラムはサーバ側で実行された結果がブラウザに表示されるため、PHPスクリプトは「サーバサイドスクリプト」と呼ばれています。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

配列

配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

Q&A

解決済

2回答

2064閲覧

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

kishin

総合スコア5

PHP

PHPは、Webサイト構築に特化して開発されたプログラミング言語です。大きな特徴のひとつは、HTMLに直接プログラムを埋め込むことができるという点です。PHPを用いることで、HTMLを動的コンテンツとして出力できます。HTMLがそのままブラウザに表示されるのに対し、PHPプログラムはサーバ側で実行された結果がブラウザに表示されるため、PHPスクリプトは「サーバサイドスクリプト」と呼ばれています。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

配列

配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

0グッド

0クリップ

投稿2019/10/21 07:02

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

最近ハマっているナンプレを自動で計算してみたく作り出したのですが、アルゴリズムのところから
考えが煮詰まり投稿させていただきました。
PHPも勉強の一貫で使用して解きたいと考えております。
自分が考えているアルゴリズムは下記の通りです。
−−−−−−−−−−−−−
前提条件:2次元配列を使用します。
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.3
3マスも同様の作業を行う
10.すべてのマスに"0"以外の数字が入っている状態かを確認する
11.0が入っていた場合、(6)
(9)の作業を繰り返す
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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

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

[ [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),]

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

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

投稿2019/10/21 23:37

退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2019/10/21 23:49

1箇所変更したときの影響範囲って ・縦 ・横 ・枠(?)内 って決まってるんで、計算量は大分絞れそうですね。 空白箇所情報に座標 [x,y,枠(?)番号] でも持たせてやると楽な気がします。
kishin

2019/10/21 23:54

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

退会済みユーザー

2019/10/22 00:12

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

0

ベストアンサー

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

// $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()です。

投稿2019/10/21 14:20

Kapustin

総合スコア1186

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kishin

2019/10/21 23:08

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.36%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問