ブログトップ

電子工作やってみたよ

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

前回の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






トラックバックURL : https://telmic.exblog.jp/tb/29588064
トラックバックする(会員専用) [ヘルプ]
Commented by kusaka at 2018-06-21 10:25 x
頑張っていますね。
この問題ではGcに入る数字が1しかないので解けますが、そのような
確定マスが9x9のマス中に1つもない問題でも解けるようなプログラムをお願いします。
Commented by telmic-gunma at 2018-06-21 15:26
> kusakaさん
ありがとうございます。
しかし 「確定マスが1つもない問題」というのは、もはや問題と言えなくないですか。
それこそ、「仮置き」で進めないと答えに近づきませんよね。
まあ 最初に私がやった「乱数」をはめ込んでやるよりは、はるかに真ともと思いますが。
最後の最後には挑戦して見ようと思います。
Commented by kusaka at 2018-06-21 21:33 x
確定マスが初めからあって、それを埋めれば次の確定マスが出てくるのは初心者向けの問題だと思いますよ。難度の高い問題は仮置きを何度かしないと解けないようです。
Commented by telmic-gunma at 2018-06-22 06:31
> kusakaさん
ありがとうございます。
そうですね。
仮置きというのは、乱数よりも確率が高いやり方でしょうから、やってみれば意外と簡単に行くのかもしれませんね。
「いろいろ考えているより、やってみたらすぐ済んだ」という事 多いですから。
私のやる気がその段階まで持続しているかが、一番の懸念材料ですが。
Commented by あけび at 2018-06-22 15:26 x
みなさんスゴイですね・・・知的レベルというか考えていることが凡人の私とは違いますね・・

一枚目の花は 柏手あじさいです。葉形が柏餅をつつむ柏の葉に似ているからです。
花も三角形で変わってますよね。たしか開花が進むとともに花色が変化していくんですよね・・
二枚目の観葉植物は初めて見ました!!カニの手足みたいでおもしろいですね~~
Commented by telmic-gunma at 2018-06-24 19:05
> あけびさん
いつも お世話になります。ありがとうございます。
知的レベルは全くありませんが、仕事と関係ない、どうでもいいことほど夢中になってしまう、ということでしょうか。
この数独 まだまだ先は長いです。それだけ楽しめるということだと思います。
柏手あじさい ありがとうございます。 あじさいってたくさんの種類が有るんですね。
名前
URL
削除用パスワード

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

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