ブログトップ

電子工作やってみたよ

前回の4x4の解き方をそのまま9x9の拡張してやってみました。
しかし4x4ではうまく行っていた方法も9x9では単純な問題しか解くことができなくなりました。
そこで数独の解説書などを参考に新たな方法に挑戦してみました。
ここでも 人力で解くことは可能なのですが、それをプログラム化するところで四苦八苦してしまいました。
何とか出来上がったソフトでいろいろ試したのですが、やはりオールマイティーということはなくて、

限られた問題しか解けません。
やはり いろいろな問題を解くには、いろいろな方式のプログラムを作りそれを組み合わせていかなくてはならないようです。

今回の方式は、3x3の一つのブロックに注目しその中にない数値がどの場所ならば置くことが出来るかをさがしていく方法です。
これは ニコリの「全問解説数独」のP6に載っている方法をプログラム化したものです。

1) 1~9までの注目する数値を決める(実際は「1」から順番にやる)
2) その数値がない3x3のブロックを順に見つける。(今回は上の右端)
3) 横方向の行で注目数値「1」が入らないところを見つける。
   a行 b行には「1」が有るので入らない。
4) 縦方向で「1」が入らないのは I列です。
5) 上記より「1」の入る可能性はGcとHcです。
6) しかしHcはすでに「2」が入っている。
7) ゆえに残るのはGcだけなのでここに「1」が入ります。

表題に出している「HP電卓」はどうしたのと言われそうですが、ベーシックで問題が解けるようになったら、人間コンパイラになってHP電卓に書き直してみようと思います。
c0335218_19035428.jpg



この問題は 最初にやった4x4の延長の方式では解くことが出来ませんでした。
今回の各ブロックに注目してやる方法で解けました。
だけど この方式でも解けない問題がわんさか有ります。

c0335218_19045525.jpg



画面上側が問題です。  問題のブランクの所には、ゼロが入っています。
下側はパソコンが出した回答です。
Fベーシック97で3秒ほどかかりました。
デバッグのための途中経過を表示しているので、その時間がかかっていると思います。


c0335218_19042435.jpg





( Fベーシック97  富士通が作った20年前のBASIC言語をWinXPで動かしてます)


'数独(ナンプレ) SDOK9x9_30D 2018-06-20
'基本テーブル配列の定義
dim AL(9,9)
dim CHK(27)
dim INV1(9)
'
'問題のテーブルデータの設定
gosub *TBL_P6
gosub *DISP3
stop
'空欄のマスをサーチする
for ALOOP=1 to 10
for CHUMOKU=1 to 9
for BLKNO=1 to 9 ' *AA: 1 *BB: 2 ----
'          ?" CHUMOKU=";CHUMOKU;  :?" BLKNO=";BLKNO;
'stop
gosub *BLOCK
next BLKNO
next CHUMOKU
next ALOOP
?"  All end"
gosub *DISP3
stop:stop
'------------------------------------------------------------
*BLOCK
if BLKNO=1 then BLKYUP=1:BLKXLF=1:gosub *AAA:goto *BLKXX
if BLKNO=2 then BLKYUP=1:BLKXLF=4:gosub *BBB:goto *BLKXX
if BLKNO=3 then BLKYUP=1:BLKXLF=7:gosub *CCC:goto *BLKXX
if BLKNO=4 then BLKYUP=4:BLKXLF=1:gosub *DDD:goto *BLKXX
if BLKNO=5 then BLKYUP=4:BLKXLF=4:gosub *EEE:goto *BLKXX
if BLKNO=6 then BLKYUP=4:BLKXLF=7:gosub *FFF:goto *BLKXX
if BLKNO=7 then BLKYUP=7:BLKXLF=1:gosub *GGG:goto *BLKXX
if BLKNO=8 then BLKYUP=7:BLKXLF=4:gosub *HHH:goto *BLKXX
if BLKNO=9 then BLKYUP=7:BLKXLF=7:gosub *III:goto *BLKXX
?" BLK ERR":stop
'---------------------------------------------------------------
*BLKXX
CNT=0
'このブロックの中に注目している(CHUMOKU)数値があれば何もせずリターン
for XXX=1 to 9
CNT=CNT+1
if INV1(XXX)=CHUMOKU then CNT=0:XXX=9:?"同一文字有り":return
next XXX
'----------------------------------------
YCHU(1)=0:YCHU(2)=0:YCHU(3)=0:
for BKJJ=0 to 2
'ブロックの上横1行9文字をINV1へコピー
for XX=1 to 9: INV1(XX)=AL(XX,BLKYUP+BKJJ): next XX
CNT=0
for XXX=1 to 9
CNT=CNT+1
if INV1(XXX)=CHUMOKU then CNT=0:XXX=9:YCHU(BKJJ+1)=1
next XXX
next BKJJ
'-------------------------
XCHU(1)=0:XCHU(2)=0:XCHU(3)=0:
for BKJJ=0 to 2
'ブロックの左縦から1行9文字をINV1へコピー
for YY=1 to 9: INV1(YY)=AL(BLKXLF+BKJJ,YY): next YY
CNT=0
for YYY=1 to 9
CNT=CNT+1
if INV1(YYY)=CHUMOKU then CNT=0:YYY=9:XCHU(BKJJ+1)=1
next YYY
next BKJJ
'-------------------------------------------
for BLKX=1 to 9
INV1(BLKX)=BLKOUT(BLKX)
next BLKX
if YCHU(1)=0 then goto *LBL200
INV1(1)=10:INV1(2)=10:INV1(3)=10:
*LBL200
if YCHU(2)=0 then goto *LBL210
INV1(4)=10:INV1(5)=10:INV1(6)=10:
*LBL210
if YCHU(3)=0 then goto *LBL220
INV1(7)=10:INV1(8)=10:INV1(9)=10:
*LBL220
if XCHU(1)=0 then goto *LBL300
INV1(1)=10:INV1(4)=10:INV1(7)=10:
*LBL300
if XCHU(2)=0 then goto *LBL310
INV1(2)=10:INV1(5)=10:INV1(8)=10:
*LBL310
if XCHU(3)=0 then goto *LBL320
INV1(3)=10:INV1(6)=10:INV1(9)=10:
*LBL320
WCHK=0
for III=1 to 9
if INV1(III)=0 then WCHK=WCHK+1:POJ=III
next III
if WCHK>=2 then ?"空マスが2個以上あった":return
if POJ<=3 then YY=1:XX=POJ:goto *MTRX
if (POJ>=4)and(POJ<=6)then YY=2:XX=POJ-3:goto *MTRX
if(POJ<=9) then YY=3: XX=POJ-6: goto *MTRX
?"ERR 5 ":stop
*MTRX
if BLKNO=1 then X=XX:Y=YY: goto *DTSET
if BLKNO=2 then X=XX+3:Y=YY: goto *DTSET
if BLKNO=3 then X=XX+6:Y=YY: goto *DTSET
if BLKNO=4 then X=XX:Y=YY+3: goto *DTSET
if BLKNO=5 then X=XX+3:Y=YY+3: goto *DTSET
if BLKNO=6 then X=XX+6:Y=YY+3: goto *DTSET
if BLKNO=7 then X=XX:Y=YY+6: goto *DTSET
if BLKNO=8 then X=XX+3:Y=YY+6: goto *DTSET
if BLKNO=9 then X=XX+6:Y=YY+6: goto *DTSET
?" ERROR 10 ": stop
*DTSET
AL(X,Y)=CHUMOKU
ALLCNT=ALLCNT+1
?" ":?" X=";X," Y=";Y," DATA=";CHUMOKU,"ALL CNT=";ALLCNT
'gosub *DISP3
?" ================ "
return
'---------------------------------------------------------------
*AAA
INV1(1)=AL(1,1): INV1(2)=AL(2,1): INV1(3)=AL(3,1)
INV1(4)=AL(1,2): INV1(5)=AL(2,2): INV1(6)=AL(3,2)
INV1(7)=AL(1,3): INV1(8)=AL(2,3): INV1(9)=AL(3,3)
gosub *BLKOUTCOPY
return
*BBB
INV1(1)=AL(4,1): INV1(2)=AL(5,1): INV1(3)=AL(6,1)
INV1(4)=AL(4,2): INV1(5)=AL(5,2): INV1(6)=AL(6,2)
INV1(7)=AL(4,3): INV1(8)=AL(5,3): INV1(9)=AL(6,3)
gosub *BLKOUTCOPY
return
*CCC
INV1(1)=AL(7,1): INV1(2)=AL(8,1): INV1(3)=AL(9,1)
INV1(4)=AL(7,2): INV1(5)=AL(8,2): INV1(6)=AL(9,2)
INV1(7)=AL(7,3): INV1(8)=AL(8,3): INV1(9)=AL(9,3)
gosub *BLKOUTCOPY
return
*DDD
INV1(1)=AL(1,4): INV1(2)=AL(2,4): INV1(3)=AL(3,4)
INV1(4)=AL(1,5): INV1(5)=AL(2,5): INV1(6)=AL(3,5)
INV1(7)=AL(1,6): INV1(8)=AL(2,6): INV1(9)=AL(3,6)
gosub *BLKOUTCOPY
return
*EEE
INV1(1)=AL(4,4): INV1(2)=AL(5,4): INV1(3)=AL(6,4)
INV1(4)=AL(4,5): INV1(5)=AL(5,5): INV1(6)=AL(6,5)
INV1(7)=AL(4,6): INV1(8)=AL(5,6): INV1(9)=AL(6,6)
gosub *BLKOUTCOPY
return
*FFF
INV1(1)=AL(7,4): INV1(2)=AL(8,4): INV1(3)=AL(9,4)
INV1(4)=AL(7,5): INV1(5)=AL(8,5): INV1(6)=AL(9,5)
INV1(7)=AL(7,6): INV1(8)=AL(8,6): INV1(9)=AL(9,6)
gosub *BLKOUTCOPY
return
*GGG
INV1(1)=AL(1,7): INV1(2)=AL(2,7): INV1(3)=AL(3,7)
INV1(4)=AL(1,8): INV1(5)=AL(2,8): INV1(6)=AL(3,8)
INV1(7)=AL(1,9): INV1(8)=AL(2,9): INV1(9)=AL(3,9)
gosub *BLKOUTCOPY
return
*HHH
INV1(1)=AL(4,7): INV1(2)=AL(5,7): INV1(3)=AL(6,7)
INV1(4)=AL(4,8): INV1(5)=AL(5,8): INV1(6)=AL(6,8)
INV1(7)=AL(4,9): INV1(8)=AL(5,9): INV1(9)=AL(6,9)
gosub *BLKOUTCOPY
return
*III
INV1(1)=AL(7,7): INV1(2)=AL(8,7): INV1(3)=AL(9,7)
INV1(4)=AL(7,8): INV1(5)=AL(8,8): INV1(6)=AL(9,8)
INV1(7)=AL(7,9): INV1(8)=AL(8,9): INV1(9)=AL(9,9)
gosub *BLKOUTCOPY
return
'----------------------------------------------------------------------------
*BLKOUTCOPY
for BLKX=1 to 9
BLKOUT(BLKX)=INV1(BLKX)
next BLKX
return
'----------------------------------------------------------------------------
*DISP1
'?" INV1(1~)=";
for KKK=1 to 9
?INV1(KKK);
next kkk
return
'---------------------------------------
*DISP3
?" "
for YYY=1 to 9
for XXX=1 to 9
?AL(XXX,YYY);
if XXX=3 then ?" ";
if XXX=6 then ?" ";
next XXX
if YYY=3 then ?" "
if YYY=6 then ?" "
?" "
next YYY
return
'---------------------------------------
'問題のテーブルデータの設定
'ニコリ全問解説数独P6
*TBL_P6
data 6,0,2,0,0,1,0,0,5
data 0,0,1,0,0,0,6,0,0
data 0,8,0,0,5,0,0,2,3
data 3,0,0,9,0,2,0,0,0
data 0,0,4,0,0,0,8,0,0
data 0,0,0,1,0,3,0,0,7
data 5,1,0,0,6,0,0,8,0
data 0,0,3,0,0,0,2,0,0
data 2,0,0,7,0,0,5,0,1

for YY=1 to 9
for XX=1 to 9
read AL(XX,YY)
next XX
next YY
return





今我が家の庭に大きく咲きだした変わった形のアジサイ
ばあちゃんが大事にしていた形見です。

c0335218_20195548.jpg

とんがり帽子の形をしています。 まだこれから大きくなるところですね。

c0335218_20200528.jpg


何という花?



c0335218_20201743.jpg

葉っぱの中心に紫色のかわいい花が咲いています。
c0335218_20204033.jpg






by telmic-gunma | 2018-06-20 20:41 | HP電卓 | Trackback | Comments(6)

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


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