15 puzzle solver: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: added syntax colouring the hard way) |
m (added syntax colouring the hard way) |
||
Line 5,812: | Line 5,812: | ||
while (not solveable_with_at_most_n_non_free_moves(n)) n++ |
while (not solveable_with_at_most_n_non_free_moves(n)) n++ |
||
-- (clearly optimal by exhaustively disproving all lesser n) |
-- (clearly optimal by exhaustively disproving all lesser n) |
||
<lang Phix>-- demo/rosetta/Solve15puzzle_simple.exw |
|||
enum left, down, up, right -- (nb 5-move flips it, as in down===5-up, etc) |
|||
<!--<lang Phix>--> |
|||
constant valid_moves = {{ 0, 0, 5, 2}, { 1, 0, 6, 3}, { 2, 0, 7, 4}, { 3, 0, 8, 0}, |
|||
<span style="color: #000080;font-style:italic;">-- demo/rosetta/Solve15puzzle_simple.exw</span> |
|||
{ 0, 1, 9, 6}, { 5, 2,10, 7}, { 6, 3,11, 8}, { 7, 4,12, 0}, |
|||
<span style="color: #008080;">enum</span> <span style="color: #000000;">left<span style="color: #0000FF;">,</span> <span style="color: #000000;">down<span style="color: #0000FF;">,</span> <span style="color: #000000;">up<span style="color: #0000FF;">,</span> <span style="color: #000000;">right</span> <span style="color: #000080;font-style:italic;">-- (nb 5-move flips it, as in down===5-up, etc)</span> |
|||
{ 0, 5,13,10}, { 9, 6,14,11}, {10, 7,15,12}, {11, 8,16, 0}, |
|||
{ 0, 9, 0,14}, {13,10, 0,15}, {14,11, 0,16}, {15,12, 0, 0}} |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">valid_moves</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{<span style="color: #0000FF;">{</span> <span style="color: #000000;">0<span style="color: #0000FF;">,</span> <span style="color: #000000;">0<span style="color: #0000FF;">,</span> <span style="color: #000000;">5<span style="color: #0000FF;">,</span> <span style="color: #000000;">2<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">1<span style="color: #0000FF;">,</span> <span style="color: #000000;">0<span style="color: #0000FF;">,</span> <span style="color: #000000;">6<span style="color: #0000FF;">,</span> <span style="color: #000000;">3<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">2<span style="color: #0000FF;">,</span> <span style="color: #000000;">0<span style="color: #0000FF;">,</span> <span style="color: #000000;">7<span style="color: #0000FF;">,</span> <span style="color: #000000;">4<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">3<span style="color: #0000FF;">,</span> <span style="color: #000000;">0<span style="color: #0000FF;">,</span> <span style="color: #000000;">8<span style="color: #0000FF;">,</span> <span style="color: #000000;">0<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0<span style="color: #0000FF;">,</span> <span style="color: #000000;">1<span style="color: #0000FF;">,</span> <span style="color: #000000;">9<span style="color: #0000FF;">,</span> <span style="color: #000000;">6<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">5<span style="color: #0000FF;">,</span> <span style="color: #000000;">2<span style="color: #0000FF;">,<span style="color: #000000;">10<span style="color: #0000FF;">,</span> <span style="color: #000000;">7<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">6<span style="color: #0000FF;">,</span> <span style="color: #000000;">3<span style="color: #0000FF;">,<span style="color: #000000;">11<span style="color: #0000FF;">,</span> <span style="color: #000000;">8<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">7<span style="color: #0000FF;">,</span> <span style="color: #000000;">4<span style="color: #0000FF;">,<span style="color: #000000;">12<span style="color: #0000FF;">,</span> <span style="color: #000000;">0<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
constant zero_cost = {{0b000000000000000,0b000000000000000,0b000000000001111,0b001000100010001}, |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0<span style="color: #0000FF;">,</span> <span style="color: #000000;">5<span style="color: #0000FF;">,<span style="color: #000000;">13<span style="color: #0000FF;">,<span style="color: #000000;">10<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">9<span style="color: #0000FF;">,</span> <span style="color: #000000;">6<span style="color: #0000FF;">,<span style="color: #000000;">14<span style="color: #0000FF;">,<span style="color: #000000;">11<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{<span style="color: #000000;">10<span style="color: #0000FF;">,</span> <span style="color: #000000;">7<span style="color: #0000FF;">,<span style="color: #000000;">15<span style="color: #0000FF;">,<span style="color: #000000;">12<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{<span style="color: #000000;">11<span style="color: #0000FF;">,</span> <span style="color: #000000;">8<span style="color: #0000FF;">,<span style="color: #000000;">16<span style="color: #0000FF;">,</span> <span style="color: #000000;">0<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
{0b110111011101110,0b000000000000000,0b000000000001111,0b011001100110011}, |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0<span style="color: #0000FF;">,</span> <span style="color: #000000;">9<span style="color: #0000FF;">,</span> <span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">14<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{<span style="color: #000000;">13<span style="color: #0000FF;">,<span style="color: #000000;">10<span style="color: #0000FF;">,</span> <span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">15<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{<span style="color: #000000;">14<span style="color: #0000FF;">,<span style="color: #000000;">11<span style="color: #0000FF;">,</span> <span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">16<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{<span style="color: #000000;">15<span style="color: #0000FF;">,<span style="color: #000000;">12<span style="color: #0000FF;">,</span> <span style="color: #000000;">0<span style="color: #0000FF;">,</span> <span style="color: #000000;">0<span style="color: #0000FF;">}<span style="color: #0000FF;">}</span> |
|||
{0b100110011001100,0b000000000000000,0b000000000001111,0b111011101110111}, |
|||
{0b000100010001000,0b000000000000000,0b000000000001111,0b000000000000000}, |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">zero_cost</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{<span style="color: #0000FF;">{<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000001111<span style="color: #0000FF;">,<span style="color: #000000;">0b001000100010001<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
{0b000000000000000,0b111111111110000,0b000000011111111,0b001000100010001}, |
|||
<span style="color: #0000FF;">{<span style="color: #000000;">0b110111011101110<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000001111<span style="color: #0000FF;">,<span style="color: #000000;">0b011001100110011<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
{0b110111011101110,0b111111111110000,0b000000011111111,0b011001100110011}, |
|||
<span style="color: #0000FF;">{<span style="color: #000000;">0b100110011001100<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000001111<span style="color: #0000FF;">,<span style="color: #000000;">0b111011101110111<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
{0b100110011001100,0b111111111110000,0b000000011111111,0b111011101110111}, |
|||
<span style="color: #0000FF;">{<span style="color: #000000;">0b000100010001000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000001111<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
{0b000100010001000,0b111111111110000,0b000000011111111,0b000000000000000}, |
|||
<span style="color: #0000FF;">{<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b111111111110000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000011111111<span style="color: #0000FF;">,<span style="color: #000000;">0b001000100010001<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
{0b000000000000000,0b111111100000000,0b000111111111111,0b001000100010001}, |
|||
<span style="color: #0000FF;">{<span style="color: #000000;">0b110111011101110<span style="color: #0000FF;">,<span style="color: #000000;">0b111111111110000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000011111111<span style="color: #0000FF;">,<span style="color: #000000;">0b011001100110011<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
{0b110111011101110,0b111111100000000,0b000111111111111,0b011001100110011}, |
|||
<span style="color: #0000FF;">{<span style="color: #000000;">0b100110011001100<span style="color: #0000FF;">,<span style="color: #000000;">0b111111111110000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000011111111<span style="color: #0000FF;">,<span style="color: #000000;">0b111011101110111<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
{0b100110011001100,0b111111100000000,0b000111111111111,0b111011101110111}, |
|||
<span style="color: #0000FF;">{<span style="color: #000000;">0b000100010001000<span style="color: #0000FF;">,<span style="color: #000000;">0b111111111110000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000011111111<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
{0b000100010001000,0b111111100000000,0b000111111111111,0b000000000000000}, |
|||
<span style="color: #0000FF;">{<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b111111100000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000111111111111<span style="color: #0000FF;">,<span style="color: #000000;">0b001000100010001<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
{0b000000000000000,0b111000000000000,0b000000000000000,0b001000100010001}, |
|||
<span style="color: #0000FF;">{<span style="color: #000000;">0b110111011101110<span style="color: #0000FF;">,<span style="color: #000000;">0b111111100000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000111111111111<span style="color: #0000FF;">,<span style="color: #000000;">0b011001100110011<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
{0b110111011101110,0b111000000000000,0b000000000000000,0b011001100110011}, |
|||
<span style="color: #0000FF;">{<span style="color: #000000;">0b100110011001100<span style="color: #0000FF;">,<span style="color: #000000;">0b111111100000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000111111111111<span style="color: #0000FF;">,<span style="color: #000000;">0b111011101110111<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
{0b100110011001100,0b111000000000000,0b000000000000000,0b111011101110111}, |
|||
<span style="color: #0000FF;">{<span style="color: #000000;">0b000100010001000<span style="color: #0000FF;">,<span style="color: #000000;">0b111111100000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000111111111111<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
{0b000100010001000,0b111000000000000,0b000000000000000,0b000000000000000}} |
|||
<span style="color: #0000FF;">{<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b111000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b001000100010001<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
<span style="color: #0000FF;">{<span style="color: #000000;">0b110111011101110<span style="color: #0000FF;">,<span style="color: #000000;">0b111000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b011001100110011<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
constant masks = {0b000000000000001,0b000000000000010,0b000000000000100,0b000000000001000, |
|||
<span style="color: #0000FF;">{<span style="color: #000000;">0b100110011001100<span style="color: #0000FF;">,<span style="color: #000000;">0b111000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b111011101110111<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> |
|||
0b000000000010000,0b000000000100000,0b000000001000000,0b000000010000000, |
|||
<span style="color: #0000FF;">{<span style="color: #000000;">0b000100010001000<span style="color: #0000FF;">,<span style="color: #000000;">0b111000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000000000<span style="color: #0000FF;">}<span style="color: #0000FF;">}</span> |
|||
0b000000100000000,0b000001000000000,0b000010000000000,0b000100000000000, |
|||
0b001000000000000,0b010000000000000,0b100000000000000} |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">masks</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{<span style="color: #000000;">0b000000000000001<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000000010<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000000100<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000001000<span style="color: #0000FF;">,</span> |
|||
<span style="color: #000000;">0b000000000010000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000000100000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000001000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000000010000000<span style="color: #0000FF;">,</span> |
|||
-- Or, if you prefer to build those with code (but I really wanted to show the above bitmasks): |
|||
<span style="color: #000000;">0b000000100000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000001000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000010000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b000100000000000<span style="color: #0000FF;">,</span> |
|||
--/* |
|||
<span style="color: #000000;">0b001000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b010000000000000<span style="color: #0000FF;">,<span style="color: #000000;">0b100000000000000<span style="color: #0000FF;">}</span> |
|||
sequence valid_moves = repeat(repeat(0,4),16), |
|||
zero_cost = repeat(repeat(0,4),16) |
|||
<span style="color: #000080;font-style:italic;">-- Or, if you prefer to build those with code (but I really wanted to show the above bitmasks): |
|||
constant masks = sq_power(2,tagset(14,0)) |
|||
--/* |
|||
for square=1 to 16 do |
|||
sequence valid_moves = repeat(repeat(0,4),16), |
|||
integer s_row = floor((square+3)/4), |
|||
zero_cost = repeat(repeat(0,4),16) |
|||
constant masks = sq_power(2,tagset(14,0)) |
|||
for move=left to right do -- (via up/down) |
|||
for square=1 to 16 do |
|||
if (move=left and s_col>1) |
|||
integer s_row = floor((square+3)/4), |
|||
or (move=down and s_row>1) |
|||
s_col = remainder((square-1),4)+1 |
|||
for move=left to right do -- (via up/down) |
|||
if (move=left and s_col>1) |
|||
or (move=down and s_row>1) |
|||
or (move=up and s_row<4) |
|||
or (move=right and s_col<4) then |
|||
integer origin = square+{-1,-4,+4,+1}[move], |
|||
o_row = floor((origin+3)/4), |
|||
o_col = remainder((origin-1),4)+1 |
|||
valid_moves[square][move] = origin |
|||
for piece=1 to 15 do -- (aka target) |
|||
integer t_row = floor((piece+3)/4), |
|||
t_col = remainder((piece-1),4)+1, |
|||
p_md = abs(t_row-o_row)+abs(t_col-o_col), |
|||
n_md = abs(t_row-s_row)+abs(t_col-s_col) |
|||
end for |
|||
if n_md<=p_md then |
|||
zero_cost[square][move] += masks[piece] |
|||
end for |
|||
end if |
|||
end for |
|||
end for |
|||
--pp(valid_moves,{pp_IntFmt,"%2d",pp_Maxlen,70}) |
|||
end if |
|||
--pp(zero_cost,{pp_IntFmt,"%015b"}) |
|||
end for |
|||
--pp(masks,{pp_IntFmt,"%015b",pp_IntCh,false}) |
|||
end for |
|||
--*/ |
|||
--pp(valid_moves,{pp_IntFmt,"%2d",pp_Maxlen,70}) |
|||
if up or down then end if -- (suppress unused warnings, since the above commented out) |
|||
--pp(zero_cost,{pp_IntFmt,"%015b"}) |
|||
--pp(masks,{pp_IntFmt,"%015b",pp_IntCh,false}) |
|||
string moves = "" |
|||
--*/</span> |
|||
sequence board = {15,14, 1, 6, |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">up</span> <span style="color: #008080;">or</span> <span style="color: #000000;">down</span> <span style="color: #008080;">then</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- (suppress unused warnings, since the above commented out)</span> |
|||
9,11, 4,12, |
|||
0,10, 7, 3, |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span> |
|||
13, 8, 5, 2} |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">board</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{<span style="color: #000000;">15<span style="color: #0000FF;">,<span style="color: #000000;">14<span style="color: #0000FF;">,</span> <span style="color: #000000;">1<span style="color: #0000FF;">,</span> <span style="color: #000000;">6<span style="color: #0000FF;">,</span> |
|||
integer space = 9 |
|||
<span style="color: #000000;">9<span style="color: #0000FF;">,<span style="color: #000000;">11<span style="color: #0000FF;">,</span> <span style="color: #000000;">4<span style="color: #0000FF;">,<span style="color: #000000;">12<span style="color: #0000FF;">,</span> |
|||
<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">10<span style="color: #0000FF;">,</span> <span style="color: #000000;">7<span style="color: #0000FF;">,</span> <span style="color: #000000;">3<span style="color: #0000FF;">,</span> |
|||
constant goal = { 1, 2, 3, 4, |
|||
<span style="color: #000000;">13<span style="color: #0000FF;">,</span> <span style="color: #000000;">8<span style="color: #0000FF;">,</span> <span style="color: #000000;">5<span style="color: #0000FF;">,</span> <span style="color: #000000;">2<span style="color: #0000FF;">}</span> |
|||
5, 6, 7, 8, |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">space</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">9</span> |
|||
9,10,11,12, |
|||
13,14,15, 0} |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">goal</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">1<span style="color: #0000FF;">,</span> <span style="color: #000000;">2<span style="color: #0000FF;">,</span> <span style="color: #000000;">3<span style="color: #0000FF;">,</span> <span style="color: #000000;">4<span style="color: #0000FF;">,</span> |
|||
<span style="color: #000000;">5<span style="color: #0000FF;">,</span> <span style="color: #000000;">6<span style="color: #0000FF;">,</span> <span style="color: #000000;">7<span style="color: #0000FF;">,</span> <span style="color: #000000;">8<span style="color: #0000FF;">,</span> |
|||
atom t1 = time()+1 |
|||
<span style="color: #000000;">9<span style="color: #0000FF;">,<span style="color: #000000;">10<span style="color: #0000FF;">,<span style="color: #000000;">11<span style="color: #0000FF;">,<span style="color: #000000;">12<span style="color: #0000FF;">,</span> |
|||
<span style="color: #000000;">13<span style="color: #0000FF;">,<span style="color: #000000;">14<span style="color: #0000FF;">,<span style="color: #000000;">15<span style="color: #0000FF;">,</span> <span style="color: #000000;">0<span style="color: #0000FF;">}</span> |
|||
function solve(integer nfree, space, mdx=1, skip_move=0) |
|||
-- |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time<span style="color: #0000FF;">(<span style="color: #0000FF;">)<span style="color: #0000FF;">+<span style="color: #000000;">1</span> |
|||
-- nfree is the number of non-free moves we can yet make |
|||
-- space is the location of the space (duh), [1..16] |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">solve<span style="color: #0000FF;">(<span style="color: #004080;">integer</span> <span style="color: #000000;">nfree<span style="color: #0000FF;">,</span> <span style="color: #000000;">space<span style="color: #0000FF;">,</span> <span style="color: #000000;">mdx<span style="color: #0000FF;">=<span style="color: #000000;">1<span style="color: #0000FF;">,</span> <span style="color: #000000;">skip_move<span style="color: #0000FF;">=<span style="color: #000000;">0<span style="color: #0000FF;">)</span> |
|||
-- mdx is just the move index for building the solution |
|||
<span style="color: #000080;font-style:italic;">-- |
|||
-- skip_move significantly narrows search space (1000 or |
|||
-- nfree is the number of non-free moves we can yet make |
|||
-- more times faster, believe it or not, simply by not |
|||
-- |
-- space is the location of the space (duh), [1..16] |
||
-- mdx is just the move index for building the solution |
|||
-- |
|||
-- skip_move significantly narrows search space (1000 or |
|||
for move=left to right do -- (via up/down) |
|||
-- more times faster, believe it or not, simply by not |
|||
integer new_space = valid_moves[space][move] |
|||
-- allowing the immediate undoing of the last move) |
|||
if move!=skip_move and new_space then |
|||
--</span> |
|||
integer piece = board[new_space], |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">move<span style="color: #0000FF;">=<span style="color: #000000;">left</span> <span style="color: #008080;">to</span> <span style="color: #000000;">right</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- (via up/down)</span> |
|||
zcsmv = zero_cost[space][move], |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">new_space</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">valid_moves<span style="color: #0000FF;">[<span style="color: #000000;">space<span style="color: #0000FF;">]<span style="color: #0000FF;">[<span style="color: #000000;">move<span style="color: #0000FF;">]</span> |
|||
maskp = masks[piece], |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">move<span style="color: #0000FF;">!=<span style="color: #000000;">skip_move</span> <span style="color: #008080;">and</span> <span style="color: #000000;">new_space</span> <span style="color: #008080;">then</span> |
|||
zcost = (and_bits(zcsmv,maskp)=0) -- (0==free, 1==not) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">piece</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">board<span style="color: #0000FF;">[<span style="color: #000000;">new_space<span style="color: #0000FF;">]<span style="color: #0000FF;">,</span> |
|||
if nfree>=zcost then |
|||
<span style="color: #000000;">zcsmv</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">zero_cost<span style="color: #0000FF;">[<span style="color: #000000;">space<span style="color: #0000FF;">]<span style="color: #0000FF;">[<span style="color: #000000;">move<span style="color: #0000FF;">]<span style="color: #0000FF;">,</span> |
|||
if mdx>length(moves) then moves &= '?' end if |
|||
<span style="color: #000000;">maskp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">masks<span style="color: #0000FF;">[<span style="color: #000000;">piece<span style="color: #0000FF;">]<span style="color: #0000FF;">,</span> |
|||
-- moves[mdx] = "ludr"[move] |
|||
<span style="color: #000000;">zcost</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(<span style="color: #000000;">and_bits<span style="color: #0000FF;">(<span style="color: #000000;">zcsmv<span style="color: #0000FF;">,<span style="color: #000000;">maskp<span style="color: #0000FF;">)<span style="color: #0000FF;">=<span style="color: #000000;">0<span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (0==free, 1==not)</span> |
|||
moves[mdx] = "ludrLUDR"[move+zcost*4] |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">nfree<span style="color: #0000FF;">>=<span style="color: #000000;">zcost</span> <span style="color: #008080;">then</span> |
|||
board[space] = piece |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">mdx<span style="color: #0000FF;">><span style="color: #7060A8;">length<span style="color: #0000FF;">(<span style="color: #000000;">moves<span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">moves</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">'?'</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
board[new_space] = 0 |
|||
<span style="color: #000080;font-style:italic;">-- moves[mdx] = "ludr"[move]</span> |
|||
if time()>t1 then |
|||
<span style="color: #000000;">moves<span style="color: #0000FF;">[<span style="color: #000000;">mdx<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"ludrLUDR"<span style="color: #0000FF;">[<span style="color: #000000;">move<span style="color: #0000FF;">+<span style="color: #000000;">zcost<span style="color: #0000FF;">*<span style="color: #000000;">4<span style="color: #0000FF;">]</span> |
|||
printf(1,"%s\r",{moves}) |
|||
<span style="color: #000000;">board<span style="color: #0000FF;">[<span style="color: #000000;">space<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">piece</span> |
|||
t1 = time()+1 |
|||
<span style="color: #000000;">board<span style="color: #0000FF;">[<span style="color: #000000;">new_space<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
end if |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time<span style="color: #0000FF;">(<span style="color: #0000FF;">)<span style="color: #0000FF;">><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span> |
|||
if space=piece and board=goal then |
|||
<span style="color: #7060A8;">printf<span style="color: #0000FF;">(<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #008000;">"%s\r"<span style="color: #0000FF;">,<span style="color: #0000FF;">{<span style="color: #000000;">moves<span style="color: #0000FF;">}<span style="color: #0000FF;">)</span> |
|||
moves = moves[1..mdx] -- (trim) |
|||
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time<span style="color: #0000FF;">(<span style="color: #0000FF;">)<span style="color: #0000FF;">+<span style="color: #000000;">1</span> |
|||
return true |
|||
end if |
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
<span style="color: #008080;">if</span> <span style="color: #000000;">space<span style="color: #0000FF;">=<span style="color: #000000;">piece</span> <span style="color: #008080;">and</span> <span style="color: #000000;">board<span style="color: #0000FF;">=<span style="color: #000000;">goal</span> <span style="color: #008080;">then</span> |
|||
if solve(nfree-zcost,new_space,mdx+1,5-move) then |
|||
<span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">moves<span style="color: #0000FF;">[<span style="color: #000000;">1<span style="color: #0000FF;">..<span style="color: #000000;">mdx<span style="color: #0000FF;">]</span> <span style="color: #000080;font-style:italic;">-- (trim)</span> |
|||
return true |
|||
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
board[new_space] = piece |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">solve<span style="color: #0000FF;">(<span style="color: #000000;">nfree<span style="color: #0000FF;">-<span style="color: #000000;">zcost<span style="color: #0000FF;">,<span style="color: #000000;">new_space<span style="color: #0000FF;">,<span style="color: #000000;">mdx<span style="color: #0000FF;">+<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">5<span style="color: #0000FF;">-<span style="color: #000000;">move<span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
board[space] = 0 |
|||
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end if |
|||
<span style="color: #000000;">board<span style="color: #0000FF;">[<span style="color: #000000;">new_space<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">piece</span> |
|||
end for |
|||
<span style="color: #000000;">board<span style="color: #0000FF;">[<span style="color: #000000;">space<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
return false |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
pp(board,{pp_IntFmt,"%2d",pp_Maxlen,17}) |
|||
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
atom t0 = time() |
|||
integer n = 0 |
|||
<span style="color: #7060A8;">pp<span style="color: #0000FF;">(<span style="color: #000000;">board<span style="color: #0000FF;">,<span style="color: #0000FF;">{<span style="color: #000000;">pp_IntFmt<span style="color: #0000FF;">,<span style="color: #008000;">"%2d"<span style="color: #0000FF;">,<span style="color: #000000;">pp_Maxlen<span style="color: #0000FF;">,<span style="color: #000000;">17<span style="color: #0000FF;">}<span style="color: #0000FF;">)</span> |
|||
while not solve(n,space) do n += 1 end while |
|||
printf(1,"solution of %d moves found in %s: %s\n", |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time<span style="color: #0000FF;">(<span style="color: #0000FF;">)</span> |
|||
{length(moves),elapsed(time()-t0),moves})</lang> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #000000;">solve<span style="color: #0000FF;">(<span style="color: #000000;">n<span style="color: #0000FF;">,<span style="color: #000000;">space<span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #7060A8;">printf<span style="color: #0000FF;">(<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #008000;">"solution of %d moves found in %s: %s\n"<span style="color: #0000FF;">,</span> |
|||
<span style="color: #0000FF;">{<span style="color: #7060A8;">length<span style="color: #0000FF;">(<span style="color: #000000;">moves<span style="color: #0000FF;">)<span style="color: #0000FF;">,<span style="color: #7060A8;">elapsed<span style="color: #0000FF;">(<span style="color: #7060A8;">time<span style="color: #0000FF;">(<span style="color: #0000FF;">)<span style="color: #0000FF;">-<span style="color: #000000;">t0<span style="color: #0000FF;">)<span style="color: #0000FF;">,<span style="color: #000000;">moves<span style="color: #0000FF;">}<span style="color: #0000FF;">) |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
uppercase indicates the non-free moves (in manhattan cost terms). |
uppercase indicates the non-free moves (in manhattan cost terms). |