N88-BASICでスライドパズル (3回目)

2022/2/26(土)
N88-BASICでスライドパズル (3回目)
 
Sliding puzzle(8)の解答探索
123      123      123
456　→   45　 →  456
78       786      78
 
スペースの場所へ1～8を動かしてから、
元に戻すパズルです。
上の例では1回しか動かしていないので
すぐ元に戻せますが、たくさん動かせば
元に戻すのが難しくなります。
 
動かしたい方向のカーソルキーで移動します。
(移動方向表示は30回またはEnterで改行)
sキーで30回適当に移動します。
aキーで解答探索します。(qキーで途中中断)
スペースキーで終了です。
 
解答探索
      (1)    (2)    (3)
      xxx    xxx    xxx
盤面   xx2 → xxx  , xx  
      x1     x 1    xx2
方法   ""     "→"   "↓"
 
(1)からは(2)と(3)の動かし方があります
PUZZNは(1),(2),(3)の盤面を記憶する最大数です
MOVENは(2),(3)へ至る方法を記憶する最大値です
(2),(3)について(1)と同様に繰り返し、
初めに見つけた答えを表示しています。
 
深さ探索(スタックの先入れ後出し)ではなく
幅探索(ストリームの先入れ先出し)で検索しています
ので初めに見つけた答えは最短経路の一つです。
 
1. (1)を保存
2. (1)を取出し移動可能な盤(2),(3)を保存
3. (2)を取出し移動可能な盤保存…(4)とします
4. (3)を取出し移動可能な盤保存…(5)～とします
5. (4)を取出し....
と保存しようとする盤が答えになるまで繰り返します。
ただし、今までと同じ盤面になったときは保存しない
チェックを入れています。
このチェックを入れると、答えを見つけるまでの
時間が節約できる代わりに、メモリーが多く必要です。
 
以下のメモリーでは、メモリーが不足で途中中断
する場合が多いです
1050 PUZZN = 45000
1060 MOVEN = 15000
を増やせば最後まで検索できると思います。
 
NL-BASICはNLBasic01.txtの
M,    0を
M,    Eとして
NLBasic.exeのある場所にコピーすると
メモリーを増やせますので両方共、
10倍ぐらいで試して見て下さい。
1050 PUZZN = 450000
1060 MOVEN = 150000
 
NL-BASICとblg～.zip(puzz003.bas)は

以下のリンクからダウンロードできます
]

https://ulprojectmail.blogspot.com

Readme.txtを読んで遊んで下さい