Rosetta Code

15 puzzle solver: Difference between revisions

Page Discussion

15 puzzle solver (view source)

Revision as of 06:34, 23 March 2021

54,418 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 5,502:
 
=={{header|Phix}}==
<!--<lang Phix>-- demo\rosetta\Solve15puzzle.exw>
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Solve15puzzle.exw</span>
constant STM = 0 -- single-tile metrics.
<span style="color: #008080;">constant</span> <span style="color: #000000;">STM</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- single-tile metrics.</span>
constant MTM = 0 -- multi-tile metrics.
<span style="color: #008080;">constant</span> <span style="color: #000000;">MTM</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- multi-tile metrics.</span>
if STM and MTM then ?9/0 end if -- both prohibited
<span style="color: #008080;">if</span> <span style="color: #000000;">STM</span> <span style="color: #008080;">and</span> <span style="color: #000000;">MTM</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?<span style="color: #000000;">9<span style="color: #0000FF;">/<span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- both prohibited
-- 0 0 -- fastest, but non-optimal
-- 10 0 -- optimalfastest, inbut STMnon-optimal
-- 01 10 -- optimal in MTM (slowest by far)STM
-- 0 1 -- optimal in MTM (slowest by far)
--Note: The fast method uses an inadmissible heuristic - see "not STM" in iddfs().
-- It explores mtm-style using the higher stm heuristic and may therefore
-- fail badly in some cases.</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">SIZE</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</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: #000080;font-style:italic;">--
-- multi-tile-metric walking distance heuristic lookup (mmwd).
-- ==========================================================
-- Uses patterns of counts of tiles in/from row/col, eg the solved state
-- (ie goal above) could be represented by the following:
-- {{4,0,0,0},
-- {0,4,0,0},
-- {0,0,4,0},
-- {0,0,0,3}}
-- ie row/col 1 contains 4 tiles from col/row 1, etc. In this case
-- both are identical, but you can count row/col or col/row, and then
-- add them together. There are up to 24964 possible patterns. The
-- blank space is not counted. Note that a vertical move cannot change
-- a vertical pattern, ditto horizontal, and basic symmetry means that
-- row/col and col/row patterns will match (at least, that is, if they
-- are calculated sympathetically), halving the setup cost.
-- The data is just the number of moves made before this pattern was
-- first encountered, in a breadth-first search, backwards from the
-- goal state, until all patterns have been enumerated.
-- (The same ideas/vars are now also used for stm metrics when MTM=0)
--</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">wdkey</span> <span style="color: #000080;font-style:italic;">-- one such 4x4 pattern</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">mmwd</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict<span style="color: #0000FF;">(<span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- lookup table, data is walking distance.
--
-- We use two to-do lists: todo is the current list, and everything
-- of walkingdistance+1 ends up on tdnx. Once todo is exhausted, we
-- swap the dictionary-ids, so tdnx automatically becomes empty.
-- Key is an mmwd pattern as above, and data is {distance,space_idx}.
--</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">todo</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict<span style="color: #0000FF;">(<span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">tdnx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict<span style="color: #0000FF;">(<span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">UP</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1<span style="color: #0000FF;">,</span> <span style="color: #000000;">DOWN</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-<span style="color: #000000;">1</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">explore<span style="color: #0000FF;">(<span style="color: #004080;">integer</span> <span style="color: #000000;">space_idx<span style="color: #0000FF;">,</span> <span style="color: #000000;">walking_distance<span style="color: #0000FF;">,</span> <span style="color: #000000;">direction<span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- Given a space index, explore all the possible moves in direction,
-- setting the distance and extending the tdnx table.
--</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">tile_idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">space_idx<span style="color: #0000FF;">+<span style="color: #000000;">direction</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">group<span style="color: #0000FF;">=<span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">SIZE</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">wdkey<span style="color: #0000FF;">[<span style="color: #000000;">tile_idx<span style="color: #0000FF;">]<span style="color: #0000FF;">[<span style="color: #000000;">group<span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- ie: check row tile_idx for tiles belonging to rows 1..4
-- Swap one of those tiles with the space</span>
<span style="color: #000000;">wdkey<span style="color: #0000FF;">[<span style="color: #000000;">tile_idx<span style="color: #0000FF;">]<span style="color: #0000FF;">[<span style="color: #000000;">group<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">wdkey<span style="color: #0000FF;">[<span style="color: #000000;">space_idx<span style="color: #0000FF;">]<span style="color: #0000FF;">[<span style="color: #000000;">group<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">getd_index<span style="color: #0000FF;">(<span style="color: #000000;">wdkey<span style="color: #0000FF;">,<span style="color: #000000;">mmwd<span style="color: #0000FF;">)<span style="color: #0000FF;">=<span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- save the walking distance value</span>
<span style="color: #7060A8;">setd<span style="color: #0000FF;">(<span style="color: #000000;">wdkey<span style="color: #0000FF;">,<span style="color: #000000;">walking_distance<span style="color: #0000FF;">+<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">mmwd<span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- and add to the todo next list:</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">getd_index<span style="color: #0000FF;">(<span style="color: #000000;">wdkey<span style="color: #0000FF;">,<span style="color: #000000;">tdnx<span style="color: #0000FF;">)<span style="color: #0000FF;">!=<span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?<span style="color: #000000;">9<span style="color: #0000FF;">/<span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">setd<span style="color: #0000FF;">(<span style="color: #000000;">wdkey<span style="color: #0000FF;">,<span style="color: #0000FF;">{<span style="color: #000000;">walking_distance<span style="color: #0000FF;">+<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">tile_idx<span style="color: #0000FF;">}<span style="color: #0000FF;">,<span style="color: #000000;">tdnx<span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">MTM</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">tile_idx<span style="color: #0000FF;">><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">tile_idx<span style="color: #0000FF;"><<span style="color: #000000;">SIZE</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- mtm: same direction means same distance:</span>
<span style="color: #000000;">explore<span style="color: #0000FF;">(<span style="color: #000000;">tile_idx<span style="color: #0000FF;">,</span> <span style="color: #000000;">walking_distance<span style="color: #0000FF;">,</span> <span style="color: #000000;">direction<span style="color: #0000FF;">)</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: #000080;font-style:italic;">-- Revert the swap so we can look at the next candidate.</span>
<span style="color: #000000;">wdkey<span style="color: #0000FF;">[<span style="color: #000000;">tile_idx<span style="color: #0000FF;">]<span style="color: #0000FF;">[<span style="color: #000000;">group<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">wdkey<span style="color: #0000FF;">[<span style="color: #000000;">space_idx<span style="color: #0000FF;">]<span style="color: #0000FF;">[<span style="color: #000000;">group<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</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;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">generate_mmwd<span style="color: #0000FF;">(<span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Perform a breadth-first search begining with the solved puzzle state
-- and exploring from there until no more new patterns emerge.</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">walking_distance</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0<span style="color: #0000FF;">,</span> <span style="color: #000000;">space</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span>
<span style="color: #000000;">wdkey</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{<span style="color: #0000FF;">{<span style="color: #000000;">4<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- \</span>
<span style="color: #0000FF;">{<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">4<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- } 4 tiles in correct row positions</span>
<span style="color: #0000FF;">{<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">4<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- /</span>
<span style="color: #0000FF;">{<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">3<span style="color: #0000FF;">}<span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- 3 tiles in correct row position</span>
<span style="color: #7060A8;">setd<span style="color: #0000FF;">(<span style="color: #000000;">wdkey<span style="color: #0000FF;">,<span style="color: #000000;">walking_distance<span style="color: #0000FF;">,<span style="color: #000000;">mmwd<span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">space<span style="color: #0000FF;"><<span style="color: #000000;">4</span> <span style="color: #008080;">then</span> <span style="color: #000000;">explore<span style="color: #0000FF;">(<span style="color: #000000;">space<span style="color: #0000FF;">,</span> <span style="color: #000000;">walking_distance<span style="color: #0000FF;">,</span> <span style="color: #000000;">UP<span style="color: #0000FF;">)</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;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">explore<span style="color: #0000FF;">(<span style="color: #000000;">space<span style="color: #0000FF;">,</span> <span style="color: #000000;">walking_distance<span style="color: #0000FF;">,</span> <span style="color: #000000;">DOWN<span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">dict_size<span style="color: #0000FF;">(<span style="color: #000000;">todo<span style="color: #0000FF;">)<span style="color: #0000FF;">=<span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">dict_size<span style="color: #0000FF;">(<span style="color: #000000;">tdnx<span style="color: #0000FF;">)<span style="color: #0000FF;">=<span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #0000FF;">{<span style="color: #000000;">todo<span style="color: #0000FF;">,<span style="color: #000000;">tdnx<span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{<span style="color: #000000;">tdnx<span style="color: #0000FF;">,<span style="color: #000000;">todo<span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">wdkey</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_partial_key<span style="color: #0000FF;">(<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">todo<span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{<span style="color: #000000;">walking_distance<span style="color: #0000FF;">,<span style="color: #000000;">space<span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd<span style="color: #0000FF;">(<span style="color: #000000;">wdkey<span style="color: #0000FF;">,<span style="color: #000000;">todo<span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">deld<span style="color: #0000FF;">(<span style="color: #000000;">wdkey<span style="color: #0000FF;">,<span style="color: #000000;">todo<span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">walking_distance<span style="color: #0000FF;">(<span style="color: #004080;">sequence</span> <span style="color: #000000;">puzzle<span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rkey</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat<span style="color: #0000FF;">(<span style="color: #7060A8;">repeat<span style="color: #0000FF;">(<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">SIZE<span style="color: #0000FF;">)<span style="color: #0000FF;">,<span style="color: #000000;">SIZE<span style="color: #0000FF;">)<span style="color: #0000FF;">,</span>
<span style="color: #000000;">ckey</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat<span style="color: #0000FF;">(<span style="color: #7060A8;">repeat<span style="color: #0000FF;">(<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">SIZE<span style="color: #0000FF;">)<span style="color: #0000FF;">,<span style="color: #000000;">SIZE<span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i<span style="color: #0000FF;">=<span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">SIZE</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- rows</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j<span style="color: #0000FF;">=<span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">SIZE</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- columns</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">tile</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">puzzle<span style="color: #0000FF;">[<span style="color: #000000;">k<span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">tile<span style="color: #0000FF;">!=<span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">row</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor<span style="color: #0000FF;">(<span style="color: #0000FF;">(<span style="color: #000000;">tile<span style="color: #0000FF;">-<span style="color: #000000;">1<span style="color: #0000FF;">)<span style="color: #0000FF;">/<span style="color: #000000;">4<span style="color: #0000FF;">)<span style="color: #0000FF;">+<span style="color: #000000;">1<span style="color: #0000FF;">,</span>
<span style="color: #000000;">col</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod<span style="color: #0000FF;">(<span style="color: #000000;">tile<span style="color: #0000FF;">-<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">4<span style="color: #0000FF;">)<span style="color: #0000FF;">+<span style="color: #000000;">1</span>
<span style="color: #000000;">rkey<span style="color: #0000FF;">[<span style="color: #000000;">i<span style="color: #0000FF;">]<span style="color: #0000FF;">[<span style="color: #000000;">row<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">ckey<span style="color: #0000FF;">[<span style="color: #000000;">j<span style="color: #0000FF;">]<span style="color: #0000FF;">[<span style="color: #000000;">col<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">getd_index<span style="color: #0000FF;">(<span style="color: #000000;">rkey<span style="color: #0000FF;">,<span style="color: #000000;">mmwd<span style="color: #0000FF;">)<span style="color: #0000FF;">=<span style="color: #000000;">0</span>
<span style="color: #008080;">or</span> <span style="color: #7060A8;">getd_index<span style="color: #0000FF;">(<span style="color: #000000;">ckey<span style="color: #0000FF;">,<span style="color: #000000;">mmwd<span style="color: #0000FF;">)<span style="color: #0000FF;">=<span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">?<span style="color: #000000;">9<span style="color: #0000FF;">/<span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- sanity check</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">rwd</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd<span style="color: #0000FF;">(<span style="color: #000000;">rkey<span style="color: #0000FF;">,<span style="color: #000000;">mmwd<span style="color: #0000FF;">)<span style="color: #0000FF;">,</span>
<span style="color: #000000;">cwd</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd<span style="color: #0000FF;">(<span style="color: #000000;">ckey<span style="color: #0000FF;">,<span style="color: #000000;">mmwd<span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">rwd<span style="color: #0000FF;">+<span style="color: #000000;">cwd</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">puzzle</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</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 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: #004080;">atom</span> <span style="color: #000000;">tries</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">ok</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{<span style="color: #0000FF;">{<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- left</span>
<span style="color: #0000FF;">{<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- up</span>
<span style="color: #0000FF;">{<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- down</span>
<span style="color: #0000FF;">{<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">}<span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- right
<!--</lang>-->
 
<!--<lang Phix>-->
--Note: The fast method uses an inadmissible heuristic - see "not STM" in iddfs().
<span style="color: #008080;">function</span> <span style="color: #000000;">iddfs<span style="color: #0000FF;">(<span style="color: #004080;">integer</span> <span style="color: #000000;">step<span style="color: #0000FF;">,</span> <span style="color: #000000;">lim<span style="color: #0000FF;">,</span> <span style="color: #000000;">space<span style="color: #0000FF;">,</span> <span style="color: #000000;">prevmv<span style="color: #0000FF;">)</span>
-- It explores mtm-style using the higher stm heuristic and may therefore
<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>
-- fail badly in some cases.
<span style="color: #7060A8;">printf<span style="color: #0000FF;">(<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #008000;">"working... (depth=%d, tries=%d, time=%3ds)\r"<span style="color: #0000FF;">,<span style="color: #0000FF;">{<span style="color: #000000;">lim<span style="color: #0000FF;">,<span style="color: #000000;">tries<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>
 
<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>
constant SIZE = 4
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
 
<span style="color: #000000;">tries</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
constant goal = { 1, 2, 3, 4,
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff<span style="color: #0000FF;">(<span style="color: #000000;">step<span style="color: #0000FF;">==<span style="color: #000000;">lim<span style="color: #0000FF;">?<span style="color: #000000;">0<span style="color: #0000FF;">:<span style="color: #000000;">walking_distance<span style="color: #0000FF;">(<span style="color: #000000;">puzzle<span style="color: #0000FF;">)<span style="color: #0000FF;">)</span>
5, 6, 7, 8,
<span style="color: #008080;">if</span> <span style="color: #000000;">d<span style="color: #0000FF;">=<span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
9,10,11,12,
13,14,15, 0}
<span style="color: #008080;">return</span> <span style="color: #0000FF;">(<span style="color: #000000;">puzzle<span style="color: #0000FF;">==<span style="color: #000000;">goal<span style="color: #0000FF;">)</span>
 
--
<span style="color: #008080;">elsif</span> <span style="color: #000000;">step<span style="color: #0000FF;">+<span style="color: #000000;">d<span style="color: #0000FF;"><=<span style="color: #000000;">lim</span> <span style="color: #008080;">then</span>
-- multi-tile-metric walking distance heuristic lookup (mmwd).
-- ==========================================================
<span style="color: #008080;">for</span> <span style="color: #000000;">mv<span style="color: #0000FF;">=<span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">4</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- l/u/d/r</span>
-- Uses patterns of counts of tiles in/from row/col, eg the solved state
<span style="color: #008080;">if</span> <span style="color: #000000;">prevmv<span style="color: #0000FF;">!=<span style="color: #0000FF;">(<span style="color: #000000;">5<span style="color: #0000FF;">-<span style="color: #000000;">mv<span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- not l after r or vice versa, ditto u/d</span>
-- (ie goal above) could be represented by the following:
<span style="color: #008080;">and</span> <span style="color: #000000;">ok<span style="color: #0000FF;">[<span style="color: #000000;">mv<span style="color: #0000FF;">]<span style="color: #0000FF;">[<span style="color: #000000;">space<span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
-- {{4,0,0,0},
<span style="color: #004080;">integer</span> <span style="color: #000000;">nspace</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">space<span style="color: #0000FF;">+<span style="color: #0000FF;">{<span style="color: #0000FF;">-<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #0000FF;">-<span style="color: #000000;">4<span style="color: #0000FF;">,<span style="color: #0000FF;">+<span style="color: #000000;">4<span style="color: #0000FF;">,<span style="color: #0000FF;">+<span style="color: #000000;">1<span style="color: #0000FF;">}<span style="color: #0000FF;">[<span style="color: #000000;">mv<span style="color: #0000FF;">]</span>
-- {0,4,0,0},
<span style="color: #004080;">integer</span> <span style="color: #000000;">tile</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">puzzle<span style="color: #0000FF;">[<span style="color: #000000;">nspace<span style="color: #0000FF;">]</span>
-- {0,0,4,0},
<span style="color: #008080;">if</span> <span style="color: #000000;">puzzle<span style="color: #0000FF;">[<span style="color: #000000;">space<span style="color: #0000FF;">]<span style="color: #0000FF;">!=<span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?<span style="color: #000000;">9<span style="color: #0000FF;">/<span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- sanity check </span>
-- {0,0,0,3}}
<span style="color: #000000;">puzzle<span style="color: #0000FF;">[<span style="color: #000000;">space<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tile</span>
-- ie row/col 1 contains 4 tiles from col/row 1, etc. In this case
<span style="color: #000000;">puzzle<span style="color: #0000FF;">[<span style="color: #000000;">nspace<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
-- both are identical, but you can count row/col or col/row, and then
<span style="color: #008080;">if</span> <span style="color: #000000;">iddfs<span style="color: #0000FF;">(<span style="color: #000000;">step<span style="color: #0000FF;">+<span style="color: #008080;">iff<span style="color: #0000FF;">(<span style="color: #000000;">MTM</span> <span style="color: #008080;">or</span> <span style="color: #008080;">not</span> <span style="color: #000000;">STM<span style="color: #0000FF;">?<span style="color: #0000FF;">(<span style="color: #000000;">prevmv<span style="color: #0000FF;">!=<span style="color: #000000;">mv<span style="color: #0000FF;">)<span style="color: #0000FF;">:<span style="color: #000000;">1<span style="color: #0000FF;">)<span style="color: #0000FF;">,<span style="color: #000000;">lim<span style="color: #0000FF;">,<span style="color: #000000;">nspace<span style="color: #0000FF;">,<span style="color: #000000;">mv<span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
-- add them together. There are up to 24964 possible patterns. The
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">"ludr"<span style="color: #0000FF;">[<span style="color: #000000;">mv<span style="color: #0000FF;">]</span>
-- blank space is not counted. Note that a vertical move cannot change
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
-- a vertical pattern, ditto horizontal, and basic symmetry means that
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-- row/col and col/row patterns will match (at least, that is, if they
<span style="color: #000000;">puzzle<span style="color: #0000FF;">[<span style="color: #000000;">nspace<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tile</span>
-- are calculated sympathetically), halving the setup cost.
<span style="color: #000000;">puzzle<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>
-- The data is just the number of moves made before this pattern was
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-- first encountered, in a breadth-first search, backwards from the
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
-- goal state, until all patterns have been enumerated.
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-- (The same ideas/vars are now also used for stm metrics when MTM=0)
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
--
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
sequence wdkey -- one such 4x4 pattern
constant mmwd = new_dict() -- lookup table, data is walking distance.
<span style="color: #008080;">function</span> <span style="color: #000000;">pack<span style="color: #0000FF;">(<span style="color: #004080;">string</span> <span style="color: #000000;">s<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: #7060A8;">length<span style="color: #0000FF;">(<span style="color: #000000;">s<span style="color: #0000FF;">)<span style="color: #0000FF;">,</span> <span style="color: #000000;">n0</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
 
<span style="color: #008080;">for</span> <span style="color: #000000;">i<span style="color: #0000FF;">=<span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">4</span> <span style="color: #008080;">do</span>
--
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"lrud"<span style="color: #0000FF;">[<span style="color: #000000;">i<span style="color: #0000FF;">]<span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span>
-- We use two to-do lists: todo is the current list, and everything
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
-- of walkingdistance+1 ends up on tdnx. Once todo is exhausted, we
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">match<span style="color: #0000FF;">(<span style="color: #7060A8;">repeat<span style="color: #0000FF;">(<span style="color: #000000;">ch<span style="color: #0000FF;">,<span style="color: #000000;">3<span style="color: #0000FF;">)<span style="color: #0000FF;">,<span style="color: #000000;">s<span style="color: #0000FF;">)</span>
-- swap the dictionary-ids, so tdnx automatically becomes empty.
<span style="color: #008080;">if</span> <span style="color: #000000;">k<span style="color: #0000FF;">=<span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-- Key is an mmwd pattern as above, and data is {distance,space_idx}.
<span style="color: #000000;">s<span style="color: #0000FF;">[<span style="color: #000000;">k<span style="color: #0000FF;">+<span style="color: #000000;">1<span style="color: #0000FF;">..<span style="color: #000000;">k<span style="color: #0000FF;">+<span style="color: #000000;">2<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"3"</span>
--
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">2</span>
integer todo = new_dict()
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
integer tdnx = new_dict()
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
 
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">match<span style="color: #0000FF;">(<span style="color: #7060A8;">repeat<span style="color: #0000FF;">(<span style="color: #000000;">ch<span style="color: #0000FF;">,<span style="color: #000000;">2<span style="color: #0000FF;">)<span style="color: #0000FF;">,<span style="color: #000000;">s<span style="color: #0000FF;">)</span>
--
<span style="color: #008080;">if</span> <span style="color: #000000;">k<span style="color: #0000FF;">=<span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
 
<span style="color: #000000;">s<span style="color: #0000FF;">[<span style="color: #000000;">k<span style="color: #0000FF;">+<span style="color: #000000;">1<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'2'</span>
enum UP = 1, DOWN = -1
<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>
procedure explore(integer space_idx, walking_distance, direction)
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
--
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{<span style="color: #000000;">n<span style="color: #0000FF;">,<span style="color: #008080;">iff<span style="color: #0000FF;">(<span style="color: #000000;">MTM<span style="color: #0000FF;">?<span style="color: #7060A8;">sprintf<span style="color: #0000FF;">(<span style="color: #008000;">"%d"<span style="color: #0000FF;">,<span style="color: #000000;">n<span style="color: #0000FF;">)<span style="color: #0000FF;">:<span style="color: #7060A8;">sprintf<span style="color: #0000FF;">(<span style="color: #008000;">"%d(%d)"<span style="color: #0000FF;">,<span style="color: #0000FF;">{<span style="color: #000000;">n<span style="color: #0000FF;">,<span style="color: #000000;">n0<span style="color: #0000FF;">}<span style="color: #0000FF;">)<span style="color: #0000FF;">)<span style="color: #0000FF;">,<span style="color: #000000;">s<span style="color: #0000FF;">}</span>
-- Given a space index, explore all the possible moves in direction,
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
-- setting the distance and extending the tdnx table.
--
<span style="color: #008080;">procedure</span> <span style="color: #000000;">apply_moves<span style="color: #0000FF;">(<span style="color: #004080;">string</span> <span style="color: #000000;">moves<span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">space<span style="color: #0000FF;">)</span>
integer tile_idx = space_idx+direction
<span style="color: #004080;">integer</span> <span style="color: #000000;">move<span style="color: #0000FF;">,</span> <span style="color: #000000;">ch<span style="color: #0000FF;">,</span> <span style="color: #000000;">nspace</span>
for group=1 to SIZE do
<span style="color: #000000;">puzzle<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>
if wdkey[tile_idx][group] then
<span style="color: #008080;">for</span> <span style="color: #000000;">i<span style="color: #0000FF;">=<span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length<span style="color: #0000FF;">(<span style="color: #000000;">moves<span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
-- ie: check row tile_idx for tiles belonging to rows 1..4
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">moves<span style="color: #0000FF;">[<span style="color: #000000;">i<span style="color: #0000FF;">]</span>
-- Swap one of those tiles with the space
<span style="color: #008080;">if</span> <span style="color: #000000;">ch<span style="color: #0000FF;">><span style="color: #008000;">'3'</span> <span style="color: #008080;">then</span>
wdkey[tile_idx][group] -= 1
<span style="color: #000000;">move</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find<span style="color: #0000FF;">(<span style="color: #000000;">ch<span style="color: #0000FF;">,<span style="color: #008000;">"ulrd"<span style="color: #0000FF;">)</span>
wdkey[space_idx][group] += 1
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
 
<span style="color: #000080;font-style:italic;">-- (hint: "r" -> the 'r' does 1
if getd_index(wdkey,mmwd)=0 then
-- "r2" --> the 'r' does save1, the walking'2' distancedoes value1
-- setd(wdkey,walking_distance+ "r3" -> the 'r' does 1,mmwd the '3' does 2!)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j<span style="color: #0000FF;">=<span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1<span style="color: #0000FF;">+<span style="color: #0000FF;">(<span style="color: #000000;">ch<span style="color: #0000FF;">=<span style="color: #008000;">'3'<span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
-- and add to the todo next list:
<span style="color: #000000;">nspace</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">space<span style="color: #0000FF;">+<span style="color: #0000FF;">{<span style="color: #0000FF;">-<span style="color: #000000;">4<span style="color: #0000FF;">,<span style="color: #0000FF;">-<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #0000FF;">+<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">4<span style="color: #0000FF;">}<span style="color: #0000FF;">[<span style="color: #000000;">move<span style="color: #0000FF;">]</span>
if getd_index(wdkey,tdnx)!=0 then ?9/0 end if
<span style="color: #000000;">puzzle<span style="color: #0000FF;">[<span style="color: #000000;">space<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">puzzle<span style="color: #0000FF;">[<span style="color: #000000;">nspace<span style="color: #0000FF;">]</span>
setd(wdkey,{walking_distance+1,tile_idx},tdnx)
<span style="color: #000000;">space</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nspace</span>
end if
<span style="color: #000000;">puzzle<span style="color: #0000FF;">[<span style="color: #000000;">nspace<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;">for</span>
if MTM then
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
if tile_idx>1 and tile_idx<SIZE then
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
-- mtm: same direction means same distance:
explore(tile_idx, walking_distance, direction)
<span style="color: #008080;">function</span> <span style="color: #000000;">solvable<span style="color: #0000FF;">(<span style="color: #004080;">sequence</span> <span style="color: #000000;">board<span style="color: #0000FF;">)</span>
end if
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length<span style="color: #0000FF;">(<span style="color: #000000;">board<span style="color: #0000FF;">)</span>
end if
<span style="color: #004080;">sequence</span> <span style="color: #000000;">positions</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat<span style="color: #0000FF;">(<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">n<span style="color: #0000FF;">)</span>
 
<span style="color: #000080;font-style:italic;">-- prepare the mapping from each tile to its position</span>
-- Revert the swap so we can look at the next candidate.
<span style="color: #000000;">board<span style="color: #0000FF;">[<span style="color: #7060A8;">find<span style="color: #0000FF;">(<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">board<span style="color: #0000FF;">)<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
wdkey[tile_idx][group] += 1
<span style="color: #008080;">for</span> <span style="color: #000000;">i<span style="color: #0000FF;">=<span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
wdkey[space_idx][group] -= 1
<span style="color: #000000;">positions<span style="color: #0000FF;">[<span style="color: #000000;">board<span style="color: #0000FF;">[<span style="color: #000000;">i<span style="color: #0000FF;">]<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
end procedure
<span style="color: #000080;font-style:italic;">-- check whether this is an even or odd state</span>
 
<span style="color: #004080;">integer</span> <span style="color: #000000;">row</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor<span style="color: #0000FF;">(<span style="color: #0000FF;">(<span style="color: #000000;">positions<span style="color: #0000FF;">[<span style="color: #000000;">16<span style="color: #0000FF;">]<span style="color: #0000FF;">-<span style="color: #000000;">1<span style="color: #0000FF;">)<span style="color: #0000FF;">/<span style="color: #000000;">4<span style="color: #0000FF;">)<span style="color: #0000FF;">,</span>
procedure generate_mmwd()
<span style="color: #000000;">col</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(<span style="color: #000000;">positions<span style="color: #0000FF;">[<span style="color: #000000;">16<span style="color: #0000FF;">]<span style="color: #0000FF;">-<span style="color: #000000;">1<span style="color: #0000FF;">)<span style="color: #0000FF;">-<span style="color: #000000;">row<span style="color: #0000FF;">*<span style="color: #000000;">4</span>
-- Perform a breadth-first search begining with the solved puzzle state
<span style="color: #004080;">bool</span> <span style="color: #000000;">even_state</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(<span style="color: #000000;">positions<span style="color: #0000FF;">[<span style="color: #000000;">16<span style="color: #0000FF;">]<span style="color: #0000FF;">==<span style="color: #000000;">16<span style="color: #0000FF;">)</span> <span style="color: #008080;">or</span> <span style="color: #0000FF;">(<span style="color: #7060A8;">mod<span style="color: #0000FF;">(<span style="color: #000000;">row<span style="color: #0000FF;">,<span style="color: #000000;">2<span style="color: #0000FF;">)<span style="color: #0000FF;">==<span style="color: #7060A8;">mod<span style="color: #0000FF;">(<span style="color: #000000;">col<span style="color: #0000FF;">,<span style="color: #000000;">2<span style="color: #0000FF;">)<span style="color: #0000FF;">)</span>
-- and exploring from there until no more new patterns emerge.
integer walking_distance = 0, space = 4
<span style="color: #000080;font-style:italic;">-- count the even cycles</span>
 
<span style="color: #004080;">integer</span> <span style="color: #000000;">even_count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
wdkey = {{4,0,0,0}, -- \
<span style="color: #004080;">sequence</span> <span style="color: #000000;">visited</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat<span style="color: #0000FF;">(<span style="color: #004600;">false<span style="color: #0000FF;">,<span style="color: #000000;">16<span style="color: #0000FF;">)</span>
{0,4,0,0}, -- } 4 tiles in correct row positions
<span style="color: #008080;">for</span> <span style="color: #000000;">i<span style="color: #0000FF;">=<span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
{0,0,4,0}, -- /
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">visited<span style="color: #0000FF;">[<span style="color: #000000;">i<span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
{0,0,0,3}} -- 3 tiles in correct row position
<span style="color: #000080;font-style:italic;">-- a new cycle starts at i. Count its length..</span>
setd(wdkey,walking_distance,mmwd)
<span style="color: #004080;">integer</span> <span style="color: #000000;">cycle_length</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0<span style="color: #0000FF;">,</span>
while 1 do
<span style="color: #000000;">next_tile</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
if space<4 then explore(space, walking_distance, UP) end if
<span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #000000;">visited<span style="color: #0000FF;">[<span style="color: #000000;">next_tile<span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
if space>1 then explore(space, walking_distance, DOWN) end if
<span style="color: #000000;">cycle_length</span> <span style="color: #0000FF;">+=<span style="color: #000000;">1</span>
if dict_size(todo)=0 then
<span style="color: #000000;">visited<span style="color: #0000FF;">[<span style="color: #000000;">next_tile<span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
if dict_size(tdnx)=0 then exit end if
<span style="color: #000000;">next_tile</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">positions<span style="color: #0000FF;">[<span style="color: #000000;">next_tile<span style="color: #0000FF;">]</span>
{todo,tdnx} = {tdnx,todo}
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
end if
<span style="color: #000000;">even_count</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">(<span style="color: #7060A8;">mod<span style="color: #0000FF;">(<span style="color: #000000;">cycle_length<span style="color: #0000FF;">,<span style="color: #000000;">2<span style="color: #0000FF;">)<span style="color: #0000FF;">==<span style="color: #000000;">0<span style="color: #0000FF;">)</span>
wdkey = getd_partial_key(0,todo)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
{walking_distance,space} = getd(wdkey,todo)
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
deld(wdkey,todo)
<span style="color: #008080;">return</span> <span style="color: #000000;">even_state</span> <span style="color: #0000FF;">==</span> <span style="color: #0000FF;">(<span style="color: #7060A8;">mod<span style="color: #0000FF;">(<span style="color: #000000;">even_count<span style="color: #0000FF;">,<span style="color: #000000;">2<span style="color: #0000FF;">)<span style="color: #0000FF;">==<span style="color: #000000;">0<span style="color: #0000FF;">)</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
end procedure
 
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main<span style="color: #0000FF;">(<span style="color: #0000FF;">)</span>
function walking_distance(sequence puzzle)
sequence rkey = repeat(repeat(0,SIZE),SIZE),
<span style="color: #000000;">puzzle</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>
ckey = repeat(repeat(0,SIZE),SIZE)
<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>
integer k = 1
<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>
for i=1 to SIZE do -- rows
<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>
for j=1 to SIZE do -- columns
integer tile = puzzle[k]
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">solvable<span style="color: #0000FF;">(<span style="color: #000000;">puzzle<span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
if tile!=0 then
<span style="color: #0000FF;">?<span style="color: #000000;">puzzle</span>
integer row = floor((tile-1)/4)+1,
<span style="color: #7060A8;">printf<span style="color: #0000FF;">(<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #008000;">"puzzle is not solveable\n"<span style="color: #0000FF;">)</span>
col = mod(tile-1,4)+1
<span style="color: #008080;">else</span>
rkey[i][row] += 1
ckey[j][col] += 1
<span style="color: #000000;">generate_mmwd<span style="color: #0000FF;">(<span style="color: #0000FF;">)</span>
end if
k += 1
<span style="color: #004080;">sequence</span> <span style="color: #000000;">original</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">puzzle</span>
end for
<span style="color: #004080;">integer</span> <span style="color: #000000;">space</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find<span style="color: #0000FF;">(<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">puzzle<span style="color: #0000FF;">)</span>
end for
if getd_index(rkey,mmwd)=0
<span style="color: #008080;">for</span> <span style="color: #000000;">lim<span style="color: #0000FF;">=<span style="color: #000000;">walking_distance<span style="color: #0000FF;">(<span style="color: #000000;">puzzle<span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #008080;">iff<span style="color: #0000FF;">(<span style="color: #000000;">MTM<span style="color: #0000FF;">?<span style="color: #000000;">43<span style="color: #0000FF;">:<span style="color: #000000;">80<span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
or getd_index(ckey,mmwd)=0 then
<span style="color: #008080;">if</span> <span style="color: #000000;">iddfs<span style="color: #0000FF;">(<span style="color: #000000;">0<span style="color: #0000FF;">,</span> <span style="color: #000000;">lim<span style="color: #0000FF;">,</span> <span style="color: #000000;">space<span style="color: #0000FF;">,</span> <span style="color: #008000;">'-'<span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
?9/0 -- sanity check
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end if
integer rwd = getd(rkey,mmwd),
<span style="color: #0000FF;">{<span style="color: #004080;">integer</span> <span style="color: #000000;">n<span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">ns<span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">ans<span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pack<span style="color: #0000FF;">(<span style="color: #7060A8;">reverse<span style="color: #0000FF;">(<span style="color: #000000;">res<span style="color: #0000FF;">)<span style="color: #0000FF;">)</span>
cwd = getd(ckey,mmwd)
return rwd+cwd
<span style="color: #7060A8;">printf<span style="color: #0000FF;">(<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #008000;">"\n\noriginal:"<span style="color: #0000FF;">)</span>
end function
<span style="color: #0000FF;">?<span style="color: #000000;">original</span>
 
<span style="color: #004080;">atom</span> <span style="color: #000000;">t</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;">t0</span>
sequence puzzle
<span style="color: #7060A8;">printf<span style="color: #0000FF;">(<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #008000;">"\n%soptimal solution of %s moves found in %s: %s\n\nresult: "<span style="color: #0000FF;">,</span>
string res = ""
<span style="color: #0000FF;">{<span style="color: #008080;">iff<span style="color: #0000FF;">(<span style="color: #000000;">MTM<span style="color: #0000FF;">?<span style="color: #008000;">"mtm-"<span style="color: #0000FF;">:<span style="color: #008080;">iff<span style="color: #0000FF;">(<span style="color: #000000;">STM<span style="color: #0000FF;">?<span style="color: #008000;">"stm-"<span style="color: #0000FF;">:<span style="color: #008000;">"non-"<span style="color: #0000FF;">)<span style="color: #0000FF;">)<span style="color: #0000FF;">,<span style="color: #000000;">ns<span style="color: #0000FF;">,<span style="color: #7060A8;">elapsed<span style="color: #0000FF;">(<span style="color: #000000;">t<span style="color: #0000FF;">)<span style="color: #0000FF;">,<span style="color: #000000;">ans<span style="color: #0000FF;">}<span style="color: #0000FF;">)</span>
atom t0 = time(),
<span style="color: #000000;">puzzle</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">original</span>
t1 = time()+1
<span style="color: #000000;">apply_moves<span style="color: #0000FF;">(<span style="color: #000000;">ans<span style="color: #0000FF;">,<span style="color: #000000;">space<span style="color: #0000FF;">)</span>
atom tries = 0
<span style="color: #0000FF;">?<span style="color: #000000;">puzzle</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
constant ok = {{0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1}, -- left
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
{0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1}, -- up
<span style="color: #000000;">main<span style="color: #0000FF;">(<span style="color: #0000FF;">)
{1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0}, -- down
<!--</lang>-->
{1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0}} -- right
 
function iddfs(integer step, lim, space, prevmv)
if time()>t1 then
printf(1,"working... (depth=%d, tries=%d, time=%3ds)\r",{lim,tries,time()-t0})
t1 = time()+1
end if
tries += 1
integer d = iff(step==lim?0:walking_distance(puzzle))
if d=0 then
 
return (puzzle==goal)
 
elsif step+d<=lim then
 
for mv=1 to 4 do -- l/u/d/r
if prevmv!=(5-mv) -- not l after r or vice versa, ditto u/d
and ok[mv][space] then
integer nspace = space+{-1,-4,+4,+1}[mv]
integer tile = puzzle[nspace]
if puzzle[space]!=0 then ?9/0 end if -- sanity check
puzzle[space] = tile
puzzle[nspace] = 0
if iddfs(step+iff(MTM or not STM?(prevmv!=mv):1),lim,nspace,mv) then
res &= "ludr"[mv]
return true
end if
puzzle[nspace] = tile
puzzle[space] = 0
end if
end for
end if
return false
end function
 
function pack(string s)
integer n = length(s), n0 = n
for i=1 to 4 do
integer ch = "lrud"[i], k
while 1 do
k = match(repeat(ch,3),s)
if k=0 then exit end if
s[k+1..k+2] = "3"
n -= 2
end while
while 1 do
k = match(repeat(ch,2),s)
if k=0 then exit end if
s[k+1] = '2'
n -= 1
end while
end for
return {n,iff(MTM?sprintf("%d",n):sprintf("%d(%d)",{n,n0})),s}
end function
 
procedure apply_moves(string moves, integer space)
integer move, ch, nspace
puzzle[space] = 0
for i=1 to length(moves) do
ch = moves[i]
if ch>'3' then
move = find(ch,"ulrd")
end if
-- (hint: "r" -> the 'r' does 1
-- "r2" -> the 'r' does 1, the '2' does 1
-- "r3" -> the 'r' does 1, the '3' does 2!)
for j=1 to 1+(ch='3') do
nspace = space+{-4,-1,+1,4}[move]
puzzle[space] = puzzle[nspace]
space = nspace
puzzle[nspace] = 0
end for
end for
end procedure
 
function solvable(sequence board)
integer n = length(board)
sequence positions = repeat(0,n)
-- prepare the mapping from each tile to its position
board[find(0,board)] = n
for i=1 to n do
positions[board[i]] = i
end for
-- check whether this is an even or odd state
integer row = floor((positions[16]-1)/4),
col = (positions[16]-1)-row*4
bool even_state = (positions[16]==16) or (mod(row,2)==mod(col,2))
-- count the even cycles
integer even_count = 0
sequence visited = repeat(false,16)
for i=1 to n do
if not visited[i] then
-- a new cycle starts at i. Count its length..
integer cycle_length = 0,
next_tile = i
while not visited[next_tile] do
cycle_length +=1
visited[next_tile] = true
next_tile = positions[next_tile]
end while
even_count += (mod(cycle_length,2)==0)
end if
end for
return even_state == (mod(even_count,2)==0)
end function
 
procedure main()
 
puzzle = {15,14, 1, 6,
9,11, 4,12,
0,10, 7, 3,
13, 8, 5, 2}
 
if not solvable(puzzle) then
?puzzle
printf(1,"puzzle is not solveable\n")
else
 
generate_mmwd()
 
sequence original = puzzle
integer space = find(0,puzzle)
 
for lim=walking_distance(puzzle) to iff(MTM?43:80) do
if iddfs(0, lim, space, '-') then exit end if
end for
 
{integer n, string ns, string ans} = pack(reverse(res))
 
printf(1,"\n\noriginal:")
?original
atom t = time()-t0
printf(1,"\n%soptimal solution of %s moves found in %s: %s\n\nresult: ",
{iff(MTM?"mtm-":iff(STM?"stm-":"non-")),ns,elapsed(t),ans})
puzzle = original
apply_moves(ans,space)
?puzzle
end if
end procedure
main()</lang>
{{out}}
<pre>
Petelomax
7,796

edits

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