15 puzzle solver: Difference between revisions
m
added syntax colouring the hard way
m (→{{header|Phix}}: added syntax colouring the hard way) |
m (added syntax colouring the hard way) |
||
Line 5,812:
while (not solveable_with_at_most_n_non_free_moves(n)) n++
-- (clearly optimal by exhaustively disproving all lesser n)
<!--<lang Phix>-->
<span style="color: #000080;font-style:italic;">-- demo/rosetta/Solve15puzzle_simple.exw</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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):
--/*
sequence valid_moves = repeat(repeat(0,4),16),
zero_cost
constant masks = sq_power(2,tagset(14,0))
for square=1 to 16 do
integer s_row = floor((square+3)/4),
for
if (move=left
or (move=down and
or (move=up and
or (move=right and
for piece=1 to 15 do -- (aka
n_md = abs(t_row-s_row)+abs(t_col-s_col)
zero_cost[square][move] += masks[piece]
end if
end for
end if
end for
end for
--pp(valid_moves,{pp_IntFmt,"%2d",pp_Maxlen,70})
--pp(zero_cost,{pp_IntFmt,"%015b"})
--pp(masks,{pp_IntFmt,"%015b",pp_IntCh,false})
--*/</span>
<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>
<span style="color: #004080;">string</span> <span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<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>
<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>
<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>
<span style="color: #004080;">integer</span> <span style="color: #000000;">space</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">9</span>
<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>
<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>
<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>
<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>
<span style="color: #000080;font-style:italic;">--
-- nfree is the number of non-free moves we can yet make
-- space
-- mdx is just the move index for building the solution
-- skip_move significantly narrows search space (1000 or
-- more times faster, believe it or not, simply by not
-- allowing the immediate undoing of the last move)
--</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #000080;font-style:italic;">-- moves[mdx] = "ludr"[move]</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<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>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<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>
<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>
<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}}
uppercase indicates the non-free moves (in manhattan cost terms).
|