ブログトップ

電子工作やってみたよ

数独(ナンプレ)をHP電卓で解けるかな? 3

4x4の数独(ナンプレ)をBASIC言語で解けるようになりました。
池田書店の「小学生のナンプレ」に載っている4x4の練習問題20問すべて解けたのでまず間違いないとおもいます。
前回は乱数を使って答えが合うまでやり直すという無茶な方法でしたが、今回は人間が考えるのと同じ手順で理屈に合わせながらすすめる方法でやりました。
解いていく過程で行き詰まって逆戻りしてやり直す機能が必要かなと思っていましたが、そのような機能は必要ありませんでした。
ニコリで出している「数独攻略ガイド」の9ページに


「面倒な先読みは数独では一切不要なのです。
「ここは確実にこれだ」という推理を積み重ねていくことで、
必ずただ1つの正解にたどりつくことができますよ。」
これだと 問題を作るとき、いい加減には出来ないですね。
ちゃんと1つづつ手順を考えて矛盾が起きないようにする必要がありますね。
逆に考えると、先読みが必要だったり逆戻りして数値入れ替えてやり直す必要がある問題なんて言うのも楽しいかもしれません。
すがわらさんが言っていた乱数とのハイブリッドなんていうのもいいですね。


いろいろと悩んだ原因で思いついたことは、「パズルは数式で表せないので、プログラム化し難い」という事でした。
数学や制御の計算ならば必ず「数式」があるのでそれに基づいてプログラム化できますが、「パズルの数式」というのは世の中にあるのでしょうか。

今回やった答えを出す手順を言葉で表すとするならば以下のようになります。
1、左上から右方向に空欄を探していく
2、空欄があれば、その座標の横方向、縦方向、含まれるブロック、の3種の縛りから各々の取りうる可能性のある数値をだす。
3、例えば横方向に1、と3、の数値が置かれていたらその空欄の取りうる可能性のある数値は2、と4、になります。
4、縦の方向に2、と3、の数値が置かれていたらその空欄の取りうる数値は1、と4、になります。
5、そのブロックに1、と2、が置かれていたら取りうる数値は3、と4、になります。
6、この3っつの縛りに共通しているのは4、だけなのでここは4で確定するということになります。
7、もし共通する数値が2個以上あるということならば確定しないのでそこは何もしないでパスします。
8、これをすべての空欄について行うと必ず答えが見つかります。
  (まだ 4x4 でしか動かしていませんが)

わたしにとっては、このような言葉での説明が一番わかりやすいですね。
それは、私の頭の中でこのような言葉で考えているからでしょうか。

つぎは、これがHP電卓で動作できるか、そして 9x9に対応させられるかというところですね。
c0335218_15183401.jpg


c0335218_15190578.jpg


c0335218_15193404.jpg


c0335218_15200548.jpg


F-BASIC97 人間が考えるのと同じ手順でやってます。



'数独 SDOK_61B

'基本テーブル配列の定義
dim AL(4,4) '4行4列の元データ
dim CHK(12) '可能性データの集合 横4個 縦4個 ブロック4個
dim INV1(4) '変換前のテーブルデータ
dim INV2(4) '変換後の可能性数値データ
'
'問題のテーブルデータの設定
gosub *TBL020 '小学生のナンプレ 例題 020
gosub *DISP3 '数値確認のため 画面表示
stop
'空欄のマスをサーチする
for Y=1 to 4
for X=1 to 4
'?" X=";X;:?" Y=";Y;
if AL(X,Y)=0 then gosub *SHORI   'もし空欄ならSHORIルーチンへ行く
next X
next Y
?" All kaitou"
stop:stop 'メインルーチン 終わり
'-------------------------------------------------------------------------
'空欄のたて、横、ブロックのデータを読み込む
*SHORI
for XX=1 to 12
CHK(XX)=0 '変換テーブルをクリアする
next XX


for XX=1 to 4
INV1(XX)=AL(XX,Y) '該当する横軸データ4個を変換テーブルにコピーする
next XX
'空欄に入る可能性データに変換する
for XX=1 to 4
INV2(XX)=XX  ’変換テーブルの種データ1~4を入れておく
next XX
for YY=1 to 4
for XX=1 to 4
if INV2(XX)=INV1(YY) then INV2(XX)=0  ’同一データの時は消す
next XX
next YY
for XX=1 to 4
CHK(XX)=INV2(XX)   ’残った可能性有りデータを移す
next XX
'------------------------------------------------
'問題のテーブルから縦の列データをコピーする
for YY=1 to 4
INV1(YY)=AL(X,YY)
next YY
'空欄に入る可能性データに変換する
for XX=1 to 4
INV2(XX)=XX
next XX
for YY=1 to 4
for XX=1 to 4
if INV2(XX)=INV1(YY) then INV2(XX)=0  ’可能性無いのを消し有りを残す
next XX
next YY
for XX=1 to 4
CHK(XX+4)=INV2(XX)
next XX
'-------------------------------------------------
'問題のテーブルからブロックデータをINV1へコピーする
if (X<=2)and(Y<=2) then gosub *AA:goto *BLKMOVEND
if (X>=3)and(Y<=2) then gosub *BB:goto *BLKMOVEND
if (X<=2)and(Y>=3) then gosub *CC:goto *BLKMOVEND
if (X>=3)and(Y>=3) then gosub *DD:goto *BLKMOVEND
?" ERR_blkend":stop
*BLKMOVEND
'空欄に入る可能性データに変換する
for XX=1 to 4
INV2(XX)=XX
next XX
for YY=1 to 4
for XX=1 to 4
if INV2(XX)=INV1(YY) then INV2(XX)=0
next XX
next YY
for XX=1 to 4
CHK(XX+8)=INV2(XX)
next XX
'-------------------------------------------------
'
BF(1)=0:BF(2)=0:BF(3)=0:BF(4)=0
for M=1 to 4
KZ=0:GT=0
for T=1 to 12
if CHK(T)=M then KZ=KZ+1
if KZ>=3 then ANS=M:GT=1:BF(M)=1:T=12: ’同一数値が3個あれば可能性有りとする
next T
next M
OKCHK=BF(1)+BF(2)+BF(3)+BF(4) ’可能性有りフラグを合計する
if OKCHK<>1 then goto *NON    ’可能性有りが1つ以外ならダメ
AL(X,Y)=ANS          ’可能性OKなので空欄に書き込む
*NON
gosub *disp3
?" LOOP end"
return
'-------------------------------------------------
’該当するブロックデータを変換テーブルに移す
*AA
INV1(1)=AL(1,1): INV1(2)=AL(2,1): INV1(3)=AL(1,2): INV1(4)=AL(2,2): return
*BB
INV1(1)=AL(3,1): INV1(2)=AL(4,1): INV1(3)=AL(3,2): INV1(4)=AL(4,2): return
*CC
INV1(1)=AL(1,3): INV1(2)=AL(2,3): INV1(3)=AL(1,4): INV1(4)=AL(2,4): return
*DD
INV1(1)=AL(3,3): INV1(2)=AL(4,3): INV1(3)=AL(3,4): INV1(4)=AL(4,4): return
'-------------------------------------------------------
*DISP1   ’デバッグ用画面表示
?" INV1(1)=";INV1(1),
?" INV1(2)=";INV1(2),
?" INV1(3)=";INV1(3),
?" INV1(4)=";INV1(4)
return

*DISP2   ’デバッグ用画面表示
?" INV2(1)=";INV2(1),
?" INV2(2)=";INV2(2),
?" INV2(3)=";INV2(3),
?" INV2(4)=";INV2(4)
return

*DISP3   ’デバッグ用画面表示
?AL(1,1);:?AL(2,1);:?AL(3,1);:?AL(4,1)
?AL(1,2);:?AL(2,2);:?AL(3,2);:?AL(4,2)
?AL(1,3);:?AL(2,3);:?AL(3,3);:?AL(4,3)
?AL(1,4);:?AL(2,4);:?AL(3,4);:?AL(4,4)
return

*DISP4   ’デバッグ用画面表示
for X12=1 to 12
? CHK(X12);
next X12
?" "
return

'問題のテーブルデータの設定

*TBL020
AL(1,1)=4:AL(2,1)=0:AL(3,1)=0:AL(4,1)=0:
AL(1,2)=2:AL(2,2)=0:AL(3,2)=3:AL(4,2)=4:
AL(1,3)=3:AL(2,3)=4:AL(3,3)=0:AL(4,3)=1:
AL(1,4)=0:AL(2,4)=0:AL(3,4)=0:AL(4,4)=3:
return




庭の花です。  今年はもう咲きだしました。 アルストロメリアでしたよね。
c0335218_15221863.jpg

これは なでしこ ですね。

c0335218_15204173.jpg



c0335218_15213889.jpg


トラックバックURL : https://telmic.exblog.jp/tb/29532659
トラックバックする(会員専用) [ヘルプ]
※このブログはトラックバック承認制を適用しています。 ブログの持ち主が承認するまでトラックバックは表示されません。
Commented by Kusaka at 2018-06-03 19:11 x
可能性が2個以上ある空欄しか残っていないときにどうするかが問題ですね。
私の方はそこで行き詰って進んでいません。 
ところで電卓とかBasicでなくて得意のエクセル+VBAで作ったらどうですか?
Commented by telmic-gunma at 2018-06-03 21:16
> Kusakaさん
ありがとうございます。
9x9のソフト 早く作ってkusakaさんが行き詰っている問題に挑戦してみたいですね。
たぶん問題を解いていく順番(空マスを埋めていく順)で解ける解けないが出てくるのかもしれません。
今回の私のソフトは人間とのやり取りが全くできていないので、エクセルVBAを使えば表示や入力がスマートになりそうですね。




Commented by あけび at 2018-06-04 12:52 x
そう、アルストロメリアです。 これはピンクっぽいですが濃赤や黄色もあるんですよ・・
今年も開花したということは宿根か球根てことですね。
我が家にもなでしこがあり満開ですが地面がみえないほどビッシリとは咲いていません。
両方とも切花にして玄関に飾ると帰宅したときなど イイ香りがしてホッとしますよ・・・
しかし、アルストロメリアは香りません。 厳密にいうとあるのでしょうがヒトの鼻では嗅ぎ取れないです。きれいな写真をいつもありがとうございます^^
Commented by telmic-gunma at 2018-06-05 06:10
> あけびさん
ありがとうございます。
切花にしていつも見られるところに飾るのはいいですね。
いま両方の花とも家から一番遠いところにあり、近くまで歩いて行かないとみることができません。
いままで香を嗅いだことなかったですね。見るだけでなくそういう楽しみもあったのですね。
名前
URL
削除用パスワード

※このブログはコメント承認制を適用しています。ブログの持ち主が承認するまでコメントは表示されません。

by telmic-gunma | 2018-06-03 16:08 | HP電卓 | Trackback | Comments(4)