Rosetta Code

15 puzzle solver: Difference between revisions

Page Discussion

15 puzzle solver (view source)

Revision as of 14:09, 24 July 2017

4,414 bytes added ,  6 years ago
m
improved output
(Phix)
m (improved output)
Line 21:
sequence board = tagset(15)&0
integer pos = 16
 
integer collected = 0
procedure print_board()
sequence lines = repeat("",5)
 
procedure print_board(integer last)
integer k = 2
for i=1 to length(board) do
puts(1,string this = iff(i=pos?" ":sprintf("%3d",{board[i]})))
iflines[k] mod(i,4)&=0 then puts(1,"\n") end ifthis
if mod(i,4)=0 then k+=1 end if
end for
puts(collected += 1,"\n")
if collected=6 or last then
puts(1,join(lines,"\n")&"\n\n")
lines = repeat("",5)
collected = 0
else
for i=2 to 5 do
lines[i] &= " "
end for
end if
end procedure
Line 63 ⟶ 77:
 
if 0 then
for i=1 to 5555555 do {}=move(rand(4)) end for -- (2537.5% are likely invalid)
else
board = {15,14, 1, 6,
Line 96 ⟶ 110:
integer dsv = dict_size(visited)
{?,s,{},board,pos} = boards[1]
printf(lines[1,] = sprintf("thinking... %d boards visited, best score: %d (0=solved):\n",{dsv,s})
print_board(1)
else
boards = new_boards
Line 105 ⟶ 119:
pos = pos0
board = board0
lines[1] = "solved!!: "
printf(1,"\n\nsolved!!:\n=========\n")
print_board(0)
for i=1 to length(moves) do
integer mi = moves[i]
string m = udlr[mi]
printfstring this = sprintf(1,"move %d, %s:\n",{i,m})
lines[1] &= sprintf("%-18s",{this})
moves[i] = upper(m[1])
{} = move(mi)
print_board(i=length(moves))
end for
printf(1,"solved in %d moves (%d boards visited, %s)\n",{length(moves),dict_size(visited),elapsed(time()-t0)})
Line 140 ⟶ 155:
<snip>
 
solved!!: move 1, left: move 2, down: move 3, down: move 4, left: move 5, up:
1 2 3 4
15 14 1 6 15 14 1 6 15 14 1 6 15 1 6 15 1 6 15 1 4 6
9 7 5 6
9 11 4 12 9 11 4 12 9 4 12 9 14 4 12 9 14 4 12 9 14 12
10 15 8
10 7 3 10 7 3 10 11 7 3 10 11 7 3 10 11 7 3 10 11 7 3
13 14 12 11
13 8 5 2 13 8 5 2 13 8 5 2 13 8 5 2 13 8 5 2 13 8 5 2
 
move 44, down:
1 2 3 4
9 5 6
10 7 15 8
13 14 12 11
 
move 45, left:
1 2 3 4
9 5 6
10 7 15 8
13 14 12 11
 
move 46, left:
1 2 3 4
9 5 6
10 7 15 8
13 14 12 11
 
move 47, up:
1 2 3 4
9 5 6 8
10 7 15
13 14 12 11
 
move 48, up:
1 2 3 4
9 5 6 8
10 7 15 11
13 14 12
 
move 49, right:
1 2 3 4
9 5 6 8
10 7 15 11
13 14 12
 
move 6, up: move 7, left: move 8, up: move 9, right: move 10, right: move 11, down:
move 50, down:
15 1 4 6 15 1 4 6 15 1 4 6 15 1 4 6 15 1 4 6 15 1 4 6
1 2 3 4
9 14 7 12 9 14 7 12 9 14 7 12 9 14 7 12 9 14 7 12 9 14 7 12
9 5 6 8
10 11 3 10 11 3 10 11 3 2 10 11 3 2 10 11 3 2 10 3 2
10 7 11
13 8 5 2 13 8 5 2 13 8 5 13 8 5 13 8 5 13 11 8 5
13 14 15 12
 
move 12, down: move 13, left: move 14, up: move 15, left: move 16, up: move 17, right:
move 51, right:
15 1 4 6 15 1 4 6 15 1 4 6 15 1 4 6 15 1 4 6 15 1 4 6
1 2 3 4
9 7 12 9 7 12 9 7 3 12 9 7 3 12 9 7 3 12 9 7 3 12
9 5 6 8
10 14 3 2 10 14 3 2 10 14 2 10 14 2 10 14 2 5 10 14 2 5
10 7 11
13 11 8 5 13 11 8 5 13 11 8 5 13 11 8 5 13 11 8 13 11 8
13 14 15 12
 
move 18, right: move 19, down: move 20, left: move 21, left: move 22, down: move 23, down:
move 52, right:
15 1 4 6 15 1 4 6 15 1 4 6 15 1 4 6 15 1 4 6 15 1 4
1 2 3 4
9 7 3 12 9 7 3 12 9 7 3 12 9 7 3 12 9 7 3 9 7 3 6
9 5 6 8
10 14 2 5 10 2 5 10 2 5 10 2 5 10 2 5 12 10 2 5 12
10 7 11
13 11 8 13 14 11 8 13 14 11 8 13 14 11 8 13 14 11 8 13 14 11 8
13 14 15 12
 
move 24, right: move 25, up: move 26, right: move 27, up: move 28, right: move 29, down:
move 53, down:
15 1 4 15 1 3 4 15 1 3 4 15 1 3 4 15 1 3 4 15 1 3 4
1 2 3 4
9 7 3 6 9 7 6 9 7 6 9 2 7 6 9 2 7 6 2 7 6
5 6 8
10 2 5 12 10 2 5 12 10 2 5 12 10 5 12 10 5 12 9 10 5 12
9 10 7 11
13 14 11 8 13 14 11 8 13 14 11 8 13 14 11 8 13 14 11 8 13 14 11 8
13 14 15 12
 
move 30, down: move 31, left: move 32, up: move 33, right: move 34, up: move 35, left:
move 54, left:
1 3 4 1 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4
15 2 7 6 15 2 7 6 15 7 6 15 7 6 9 15 7 6 9 15 7 6
5 6 8
9 10 5 12 9 10 5 12 9 10 5 12 9 10 5 12 10 5 12 10 5 12
9 10 7 11
13 14 11 8 13 14 11 8 13 14 11 8 13 14 11 8 13 14 11 8 13 14 11 8
13 14 15 12
 
move 36, down: move 37, left: move 38, up: move 39, left: move 40, up: move 41, right:
move 55, left:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4
9 7 6 9 7 6 9 7 5 6 9 7 5 6 9 7 5 6 9 7 5 6
5 6 8
10 15 5 12 10 15 5 12 10 15 12 10 15 12 10 15 12 8 10 15 12 8
9 10 7 11
13 14 11 8 13 14 11 8 13 14 11 8 13 14 11 8 13 14 11 13 14 11
13 14 15 12
 
move 42, down: move 43, right: move 44, down: move 45, left: move 46, left: move 47, up:
move 56, up:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4
9 7 5 6 9 7 5 6 9 5 6 9 5 6 9 5 6 9 5 6 8
5 6 7 8
10 15 8 10 15 8 10 7 15 8 10 7 15 8 10 7 15 8 10 7 15
9 10 11
13 14 12 11 13 14 12 11 13 14 12 11 13 14 12 11 13 14 12 11 13 14 12 11
13 14 15 12
 
move 48, up: move 49, right: move 50, down: move 51, right: move 52, right: move 53, down:
move 57, left:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4
9 5 6 8 9 5 6 8 9 5 6 8 9 5 6 8 9 5 6 8 5 6 8
5 6 7 8
10 7 15 11 10 7 15 11 10 7 11 10 7 11 10 7 11 9 10 7 11
9 10 11
13 14 12 13 14 12 13 14 15 12 13 14 15 12 13 14 15 12 13 14 15 12
13 14 15 12
 
move 54, left: move 55, left: move 56, up: move 57, left: move 58, up:
move 58, up:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4
5 6 8 5 6 8 5 6 7 8 5 6 7 8 5 6 7 8
5 6 7 8
9 10 7 11 9 10 7 11 9 10 11 9 10 11 9 10 11 12
9 10 11 12
13 14 15 12 13 14 15 12 13 14 15 12 13 14 15 12 13 14 15
13 14 15
 
solved in 58 moves (1330046 boards visited, 49.11s59s)
moves: LDDLUULURRDDLULURRDLLDDRURURDDLURULDLULURDRDLLUURDRRDLLULU
</pre>
Petelomax
7,820

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/276401"