Posted: 4/25/2006 6:37 AM
Post subject: Sliding Puzzle Challenge
Quote
Zurreco
Former player
Joined: 8/1/2004
Posts: 2687
Location: Seattle, WA
In case any of you don't know, sliding tile puzzles are the same as the 15 puzzle; you have a grid of scrambled images that, when slid into proper configuration, eventually make one giant picture. For reference, think of the red coins in Mario 64's lava level. Anyways, I've recently come to an impasse. While making a quick run through a puzzle game, I came across the final trial: a 6x6 sliding puzzle. As easy as they are to solve, I don't have the sheer brain power to deduce what the optimal path for such a puzzle would be. Therefore, I'm challenging whoever is reading this to create a program that solves sliding tile puzzles and outputs the optimal moves for any said puzzle. There is currently a java or flash applet out there that solves randomized 4x4 puzzles, but that does me no good. The given puzzle is as follows (X is the blank tile): 
1   9   8   23  10  11
7   2   20  5   3   6
13  15  X   18  17  4
19  14  22  16  24  12
25  26  21  28  35  29
31  32  27  33  34  30
There is a site that is able to randomly create and solve sliding tile puzzles, but it doesn't allow you to input the position values for the tile. Feel free to check it out.
hi nitrodon streamline: cyn-chine
Posted: 4/25/2006 12:48 PM
Quote
Ramzi
Joined: 3/25/2004
Posts: 459
I can't help, but here's some mathematical analysis. http://www.cut-the-knot.org/pythagoras/fifteen.shtml
Posted: 4/25/2006 2:31 PM
Quote
primorial_soup
Player (88)
Joined: 1/15/2006
Posts: 333
Location: Bangkok, Thailand
It seems like your best bet may be to use a beam search of some sort. I've done this for other puzzles with varying success. The idea is to use an iterative search, but after the queue has reached a certain size, 1000 for example, weed out bad paths so that there is once again only 1000. It doesn't guarentee an optimal solution, but it's nice that in that it has linear complexity, instead of exponential. A simple heuristic could probably be something along these lines: For each tile in the puzzle, calculate how far it is from its proper location (that is, how many shifts it would take to move it there). The sum of these could be used to compare various paths. A value of zero would be a solved state, and larger values would be further from a solution, and thus would be weeded out. If there are multiple optimal paths, you could then decide which would be the fastest to execute (if there is in fact a difference in input time). There may be better heuristic functions, but this one seems pretty intuitive and would be easy to implement. I could probably crunch a small app out in about an hour or so if you'd like.
print reduce(lambda x,p:p/2*x/p+2*10**1000,range(6643,1,-2))
Posted: 4/25/2006 4:59 PM
Quote
Luke
Player (87)
Joined: 2/10/2006
Posts: 113
Location: US
The way to solve these optimally is to use an A* search with heuristic function = how many tiles are out-of-place. Although I don't have the time to program this right now... Edit: Primorial Soup is right, an even better heuristic is the sum of the distances of each tile to its final location. An A* with this should find the solution almost instantly.
Use the force
Posted: 4/25/2006 5:51 PM
Quote
primorial_soup
Player (88)
Joined: 1/15/2006
Posts: 333
Location: Bangkok, Thailand
I had some time after work, so I decided to implement this quick. I was able to find two solutions, both of length 54. The directive 'up' means to slide a tile upwards into the blank spot, and other directives are defined similarly. 
Solution 1:
down down right up left left left down right up right down left up left down left up up up right down down left up right right up right down right up left up up left left down left down down right right down left down right up up left up left up up

Solution 2:
down left left down right up right down right up left down left up left down left up up up right down down left up right right up right down right up left up up left left down left down down right right down left down right up up left up left up up
In case you'd like the code for other puzzles, it can be found in the following locations: SlidePuzzle.java PuzzleState.java It should work for any size puzzle (even non-squares), you just need to define the initial array value in the SlidePuzzle class. If you want to adjust the beam size, you can do so by changing the parameter sent to the weed method. Both of these solutions were found with a beam size of 1000, but I also tried 10000 which didn't find any better ones, so they are probably optimal. Good luck :)
print reduce(lambda x,p:p/2*x/p+2*10**1000,range(6643,1,-2))
Posted: 4/25/2006 6:13 PM
Quote
Luke
Player (87)
Joined: 2/10/2006
Posts: 113
Location: US
In all probability, using a heuristic that strong, a search shouldn't need more than a few thousand nodes. So a beam search should be fine, and your results should be optimal, even though A* would do the same job faster :) Although admittedly a beam search is probably easier to program if you don't have A* code lying around.
Use the force
Posted: 4/25/2006 8:12 PM
Quote
Boco
Former player
Joined: 3/30/2004
Posts: 1354
Location: Heather's imagination
Solve the right and bottom edge, then recur
someone is out there who will like you. take off your mask so they can find you faster. I support the new Nekketsu Kouha Kunio-kun.
Posted: 4/25/2006 8:13 PM
Quote
Bag_of_Magic_Food
He/Him
Player (206)
Joined: 5/29/2004
Posts: 5712
I think Xebra's program tried that, but he wasn't sure if it was the most optimal way, and it probably doesn't simplify the problem enough anyway.
put yourself in my rocketpack if that poochie is one outrageous dude
Posted: 4/25/2006 8:14 PM
Quote
Zurreco
Former player
Joined: 8/1/2004
Posts: 2687
Location: Seattle, WA
Looking at this puzzle, that would be a terrible Idea, considering the left side is already solved. Also, that would be terribly inefficient. primorial: Your routes worked excellently. Thanks for you help. Xebra said that no one on this forum would be able to find a way to solve these on their own: way to prove him wrong.
hi nitrodon streamline: cyn-chine
Posted: 4/25/2006 10:23 PM
Quote
xebra
Joined: 5/3/2004
Posts: 1203
To be accurate I said no one on this forum would be able to find the optimal path, which I am still convinced of :P . Also, BoMF, I used IDA* which is different than what Boco proposed.
Posted: 4/25/2006 11:50 PM
Quote
primorial_soup
Player (88)
Joined: 1/15/2006
Posts: 333
Location: Bangkok, Thailand
After running an A* search, I found a path of 50, which by definition of the algorithm is optimal. I know you said you don't need it anymore, but I figured I'd post it anyway :) 
down down right up left left down left up right up left down right down left left up up up right down down left up right right down right down left up left down right up up up right down right up left up up left left down left up
print reduce(lambda x,p:p/2*x/p+2*10**1000,range(6643,1,-2))
Posted: 4/25/2006 11:53 PM
Quote
xebra
Joined: 5/3/2004
Posts: 1203
Very nice, got the source for that one, too?
Posted: 4/26/2006 12:01 AM
Quote
Boco
Former player
Joined: 3/30/2004
Posts: 1354
Location: Heather's imagination
Well, any two connected edges would work.
someone is out there who will like you. take off your mask so they can find you faster. I support the new Nekketsu Kouha Kunio-kun.
Posted: 4/26/2006 9:01 PM
Quote
primorial_soup
Player (88)
Joined: 1/15/2006
Posts: 333
Location: Bangkok, Thailand
xebra wrote:
Very nice, got the source for that one, too?
Certainly :) SlidePuzzle.java PuzzleState.java So, after a little experimentation, I found that my A* search had the same problem as xebra's... for a completely random puzzle (as small as 4x4), java would run out of heap space long before it found the (optimal) solution. The only reason why I was able to find the solution for the 6x6, is because it wasn't mixed up too badly. Although more heap space can be allocated by adding -Xmx256M (for 256Mb) option to java.exe, it really doesn't solve the problem, so I added a little pruning. I'm using a completely different heuristic for pruning, however. That being the minimum average distance for the remaining incorrect pieces. The logic behind it is pretty intuitive; if a puzzle state has two incorrect pieces, each an average of three tiles away, it is far less likely to lead to an optimal solution than a state which has six incorrect pieces each one tile away from where they belong. I use this as an example, becuse using the other heuristic, they would both be weighted equally (assuming a path of equal length to get there). Overall, it seems to work pretty well. The 6x6 puzzle Zurreco provided can be solved with a pruning beam as small as 100. Although a random puzzle, like the 4x4 in the code, took a beam of 5000 to find the optimal solution of 62. To turn on pruning, uncomment line 48 in SlidePuzzle.java, and the beam size can be adjusted by changing the BEAM value on line 25. All in all, this was a fun problem to work on, considering that I really like these puzzles. I've actually made my own applet, which can be found on my site. Cheers :)
print reduce(lambda x,p:p/2*x/p+2*10**1000,range(6643,1,-2))
Posted: 4/26/2006 10:34 PM
Quote
xebra
Joined: 5/3/2004
Posts: 1203
Hah, that's what I get for not actually trying to solve the 6x6 after my program choked on a random 4x4 >< .
Posted: 4/27/2006 6:58 AM
Quote
Luke
Player (87)
Joined: 2/10/2006
Posts: 113
Location: US
I will have to eat my words about saying it should only be a few thousand nodes. I did an A* in C++, using the heuristic sum(distance from final position). The 6x6 took 100k nodes, 50 moves as you said. I then optimized the program for 4x4 puzzles, getting about 280k node/sec on my computer using the C++ STL priority queue (a binary heap, not optimal for this problem). The 4x4 you mentioned as being difficult took 54 moves, not 62. It used 8.1M nodes, with the final heap (aka priority queue) being 4.1M nodes, using 12bytes/node. However my program doesn't generate solutions, sadly. So it's possible I'm wrong (although it was working fine for smaller puzzles). I would have to write my own heap to do that. I'll edit this post when I do that, maybe tonight, maybe not :) This is a good problem for id-A* as someone mentioned. 50MB of RAM is not worth it for a 4x4 puzzle :) Edit: I implemented the iterative deepening A*, and now it goes crazy fast (probably since the program fits in the cache?). I get 2.6M nodes/s now. Here is the 54-step solution: (Whoops, L = right, R = left. :P) 
 1 11  7  5
14  3  4 13
 2  9  0 12
10  8  6 **

DDDLULULDRDRUULLURRRDLLDRRU
LLURRDLLLDRDLURRRDLUULLURRR
depth 54, nodes 8405436
3.204 s
I tried various random 4x4's and most take a few seconds. Here are the hardest I found if you want to try to optimize your solver: 
10 ** 14  3
12  6 11  0
13  1  9  2
 8  5  4  7

depth 55, nodes 899119579
UURULDRDDLUUURDDRDLLURRUULDLULDD
RDLURDRURDLULUULDRRDRUU
342.741 s

 5  4 11 10
** 14  6  9
 1 13 12  8
 0  7  2  3

depth 57, nodes 919366955
URRULDDDRUULLURRDRULLDDDRURDLLLU
URRDLDLUURRDRULURDLDDRUUU
345.206 s
Here is source and .exe: http://media2.uploadjar.com/file.php?file=uploads/slidepuzzle.zip (The source is hard to read because I went general A* -> 4x4 A* -> 4x4 IDA*, and there's a lot of optimized bit manipulation)
Use the force
Posted: 4/27/2006 5:15 PM
Quote
primorial_soup
Player (88)
Joined: 1/15/2006
Posts: 333
Location: Bangkok, Thailand
Very nice. That's definately a much better way to conduct the search. Instead of keeping a heap of all the nodes which need to be visited, you're keeping track of only the path used to get there. Although it needs to rebuild the entire tree every time the depth is increased, it only requires a constant amount of memory to do so, instead of exponential. It also doesn't keep track of which states it's already visited either (not paths, but states), so it ends up looking at a lot more nodes than necessary, but then again, that would require a lot of memory to do. I'm actually quite glad you posted this... I'll be able to optimize some of my other solvers because of it as well :)
print reduce(lambda x,p:p/2*x/p+2*10**1000,range(6643,1,-2))