15 puzzle solver: Difference between revisions
Content deleted Content added
No edit summary |
Viewpoints. |
||
Line 13:
13 14 15 0
</pre>
The output must show the moves' directions, like so: left, left, left, down, right... and so on.<br />
There are
rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd<br>
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd<br>
finding either one, or both is an acceptable result.<br>▼
see: [http://www.rosettacode.org/wiki/15_puzzle_solver/Optimal_solution Pretty Print of Optimal Solution]
Those sequences describe the moves of the ''empty'' square. If instead naming the move directions of actual squares (using capital letters), the sequences are:<br>
LLLDRUURDDDRULDLUUULDRRDRDLLLUURURDDLUURDRDLLDRULULU<br>
LLLDRURDDRULDLUUURDDRDLLLURUULDRURDDLUURDRDLLDRULLUU<br>
Naming the moves of the empty square encourages thought of a variation: consider repeated moves in the same direction as being one "shove" of a compound move. A [[Run-length_encoding|run-length encoding]] of the first solution would be r3uld2lu3ldrurd3rul2ulur3d2ldlu2rd2lulur2uldrdrd which employs thirty-eight shoves. But u2r2d3ru2ld2ru3ld3l2u3r2d2l2dru3rd3l2u2r3dl3dru2r2d2 employs thirty-one shoves, though it expands to uurrdddruulddruuuldddlluuurrddlldruuurdddlluurrrdllldruurrdd which has sixty single-square moves.
;Extra credit.
| |||