On Sat, Jan 12, 2008 at 06:34:41PM -0800, SJS wrote:
For larger puzzles, a smarter algorithm is definitely needed. There are
actually fairly simple algorithms to always solve the puzzle, but they
won't necessarily have the smallest number of moves.
I think they'd be harder to grok than the plain old search. What do they
do, have a series of "swap" operations that leave the other tiles unmoved?
Just a couple of simple transforms:
- First, mutate the goal until the blank space is in the center (or as
close as it can be. Remember these moves.
- For n>3 solve the corners, then the edges. The rules aren't all that
complicated, with a few cases to move pairs in. When n=3, you can
brute force it, or there are a few simple rules to do it easily. When
n=2, it's just a rotation. n=1 is a completely empty board, so is
trivially.
- Now there is a solved ring around the edge. Ignore that, and treat it
as an n-2/n-2 board, and solve that.
- Once it's solved, reverse the moves you made on the goal to get the
true goal.
It's probably easier code, since it doesn't have to remember previous
positions. It still takes a long time for large boards, but it is on the
order of n^3 and needs reasonable memory (only enough for the board and a
few extra variables).
Dave
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
