とてつもなく汚く、遅いです。
pythonのコードを参考にしたので、HSPでは書けない部分が出てきて、遠回りになりました。
どこかミスをしたらしく、難しい形は何分経っても解けません。
さらに、初心者の方には難しいモジュール機能を使用しているため、参考になるかは分かりませんが、一応載せておきます。
命令などで分からない点があったら聞いてください。
#runtime "hsp3cl"
/*----- 8パズル操作モジュール -----*/
#module puzzle_state panel, state, size
// コンストラクタ
#modinit array panel_, array state_, int size_
size = size_
dim panel, size*size ;
dim state, size*size ;
repeat size*size
panel(cnt) = panel_(cnt)
state(cnt) = state_(cnt)
loop
return
// パズルを生成
#modfunc gen_panel
// 空き場所を確認
space = puzzle_get(thismod, "space")
// 行と列
col = space / size
raw = space \ size
return
// 変数名からデータ取得
#modcfunc puzzle_get str name
ret = 0
switch name
case "size" : ret = size : swbreak
case "panel" : ret = varptr(panel) : swbreak
case "state" : ret = varptr(state) : swbreak
case "space" // 空き場所(0)
foreach panel
if ( panel(cnt) == 0 ) {
ret = cnt
break
}
loop
swbreak
swend
return ret
#global
/*----- 8パズル用キュー -----*/
#module puzzle_queue panel, state, size, index
// コンストラクタ
#modinit var puzzle_
// 各要素を仮に取得
size_ = puzzle_get(puzzle_, "size")
dupptr panel_, puzzle_get(puzzle_, "panel"), 4*size_*size_, 4
dupptr state_, puzzle_get(puzzle_, "state"), 4*size_*size_, 4
// 初期化
index = 0
dim size, 181440
dim panel, size_*size_, 181440
dim state, size_*size_, 181440
// コピー
size(index) = size_
repeat size_ * size_
panel(cnt, index) = panel_(cnt)
state(cnt, index) = state_(cnt)
loop
// 追加済み
index++
return
// 取り出す
#modfunc dequeue var puzzle_
// 一度破棄してから作成
if vartype(puzzle_) == 5 : delmod puzzle_
newmod puzzle_, puzzle_state, panel(0), state(0), size(0)
index--
// キューをずらす
mov = 0
repeat index
mov = cnt
repeat size(0) * size(0)
panel(cnt, mov) = panel(cnt, mov+1)
state(cnt, mov) = state(cnt, mov+1)
loop
loop
return
// 追加
#modfunc enqueue var puzzle_
// 初期化
size_ = puzzle_get(puzzle_, "size")
dupptr panel_, puzzle_get(puzzle_, "panel"), 4*size_*size_, 4
dupptr state_, puzzle_get(puzzle_, "state"), 4*size_*size_, 4
// 追加
repeat size_*size_
panel(cnt, index) = panel_(cnt)
state(cnt, index) = state_(cnt)
loop
index++
delmod puzzle_
return
// 空か
#modcfunc isEmpty
if ( index == 0 ) : return 1
return 0
#global
/*----- 8パズル探索モジュール -----*/
#module
#define assign2(%1, %2, %3, %4, %5, %6) %1(%2, 0) = %3 : %1(%2, 1) = %4 : %1(%2, 2) = %5 : %1(%2, 3) = %6
// 隣接リスト(3x3固定)
#deffunc bf_search_init
dim adjacent, 9, 4
assign2 adjacent, 0, 1, 3, -1, -1
assign2 adjacent, 1, 0, 2, 4, -1
assign2 adjacent, 2, 1, 5, -1, -1
assign2 adjacent, 3, 0, 4, 6, -1
assign2 adjacent, 4, 1, 3, 5, 7
assign2 adjacent, 5, 2, 4, 8, -1
assign2 adjacent, 6, 3, 7, -1, -1
assign2 adjacent, 7, 4, 6, 8, -1
assign2 adjacent, 8, 5, 7, -1, -1
return
// 探索
#deffunc bf_search int size, array goal, array panel
// 新規パズル
dim none, size*size
newmod puzzle, puzzle_state, panel, none, size
// キューを作成
newmod queue, puzzle_queue, puzzle
// 探索済みフラグ
sdim visited, 64, 181440 : visited_index = 0
// 探索開始
while( isEmpty(queue) != 1 )
dequeue queue, puzzle
repeat
space = puzzle_get(puzzle, "space")
if ( cnt == length2(adjacent) ) : break ; 要素数
x = adjacent(space, cnt)
if ( x == -1 ) : break ; 隣接面無し
// コピー
dupptr c_panel, puzzle_get(puzzle, "panel"), 4*size*size, 4
dim b, size*size
repeat size*size
b(cnt) = c_panel(cnt)
loop
// 移動
;mes strf("%d <= %d", space, x);
b(space) = b(x)
b(x) = 0
;/*
t = ""
repeat size*size
t += str(b(cnt)) + " "
loop
mes t
;*/
// 探索済みか
key = "" : v = 0
repeat length(b)
key += str(b(cnt)) + ":"
loop
repeat visited_index
if ( visited(cnt) == key ) {
;mes key
v = 1
break
}
loop
if ( v == 1 ) : continue
// 探索していない
dupptr c_prev, puzzle_get(puzzle, "panel"), 4*size*size, 4
dim prev, size*size
repeat size*size
prev(cnt) = c_prev(cnt)
loop
newmod c, puzzle_state, b, c_prev, size
// 終了
f = 1
repeat size*size
if ( b(cnt) != goal(cnt) ) {
f = 0
break
}
loop
if ( f == 1 ) : mes "done" : return
// 次
enqueue queue, c
visited(visited_index) = key
visited_index++
loop
wend
mes "nothing found..."
return
#global
size = 3
goal = 1, 2, 3, 4, 5, 6, 7, 8, 0
;panel = 5, 4, 2, 6, 7, 0, 8, 1, 3 ; NO
;panel = 8, 6, 7, 2, 5, 4, 3, 0, 1 ; NO
;panel = 1, 2, 3, 4, 5, 6, 7, 0, 8 ; OK fast
panel = 5, 3, 0, 2, 1, 6, 4, 7, 8 ; OK fast
;panel = 5, 3, 6, 0, 1, 8, 2, 4, 7 ; OK slow
bf_search_init
bf_search size, goal, panel
mes "quit"
stop
参考:
http://qiita.com/masashi127/items/63d4f5b52895af939fca
http://www.geocities.jp/m_hiroi/light/pyalgo27.html