Algorithm for Solving a Slider Puzzle

[owensdj]

I'm trying to come up with a program that can solve a sider puzzle in the fewest possible moves. For example, you have a 4 by 4 grid with the numbers 1 through 15 in the grid in a random order with one space blank. You can only move a number into the blank space. How do you move the numbers so that they are arranged 1 through 15 with 1 in the upper left space?

Any ideas on how to come up with the algorithm? I'm stumped.

 

[DaveSimmons]

one way is to treat it as a travelling problem, "moving" from state to state, as in finding the cheapest / fastest route between two cities. A bit of googling should find more details.

The most common method I've seen is working backwards from the solution state and labeling the total cost along each pathway at each step. When you've reached all of the states that are one away from the initial state, the best path is along the chain of steps that have lowest total cost.

 

[owensdj]

I thought about treating it like finding the shortest path through a maze. At each move on a slider puzzle, you have 2, 3, or 4 possible moves. Explore each of these possible moves. Once a line of moves reaches a certain limit, such as 1000, assume it's a bad line of moves and remove it. Eventually, some of the moves will take the program to the solution. Output the one(s) with the fewest moves.

This is a brute-force approach, but I think this will work and should be easy to code.

 

[Drakkon]

I remeber when i coded this way back when it was using a tree configuration...theres only a certain number of spaces you could possibly move (for a 4x4 isnt it something like 4^4?)....but then you take your first move...try its first possible move...try that moves first possible move...if doesn't work go back and try the next possible move...so on and so forth...
As for the shortest solution...it would be using some method to find them all and giving them a weight then like said...see what the lowest cost is using dykstras algorithm...

 

[stonecold3169]

Alright, bear with me here, this may be incoherent

first of all, I have this coded in the language of Scheme, and you can put in any sized square grid and it will solve it. If you're interested in seeing my source, and have a scheme interpreter, you ar emore then welcome to.

Next: Obviously you know that the algorithm is going to be recursive, well, at least if you are going to make it work for multiple puzzle box sizes.

Next: It's important to realize ahead of time that this is going to grow in running time very exponentially. That is, this is going to get nasty. a 3 by 3 box is the base case, and everything needs to be broken up into a base case, so a 4x4 box is going to have 4 3x3 puzzle boxes inside of it, so keep that in mind too. I used scheme because its hella fast at this kind of stuff, you definitely don't want to try this in java or the such, it's just too slow.

So here is what I did... I used a list (since scheme doesn't have arrays) of lists to store in the first 3x3 grid, which is the one in the bottom left hand corner (well, the corner opposite of where you want the blank tile to be in the end). From here, it is relatively simple to solve in that the puzzle can be solved using a series of counterclockwise rotations upon the right "outside" of the grid. Where this gets complicated is that this implies you know where pieces are, which you don't... luckily, you saved a list of 3 lists with the values inside of them, and that way you don't need to scan the whole deal to find out where the first, second, third, etc pieces are. You then recursively need to move the pieces counterclockwise along the lists in which the blank goes to the outside, the piece you ar etrying to fit in goes to tehoutside, and then rotate until it gets there.

It sounds more confusing then it is, but sit down and try it. Every game can be won using counterclockwise rotations and nothing else. Clockwise rotations have a small(sub 20%) chance of cause an impossible situation by doing clockwise rotations at all. Recursion doesn't like chances of failure. After the first grid is solved, simply move over one set of blocks and do it again until you are at the end of columns, then go back to the blocks on top of the first set and solve that, etc... until it is all solved.

If you need any more help, let me know... this is some crazy head stuff, and I made a very good female friend by teaming up to tackle this my sophmore year of college ... involved many, many late nights in a comp lab.

 

[PowerMacG5]

Originally posted by: stonecold3169
Alright, bear with me here, this may be incoherent first of all, I have this coded in the language of Scheme, and you can put in any sized square grid and it will solve it. If you're interested in seeing my source, and have a scheme interpreter, you ar emore then welcome to. Next: Obviously you know that the algorithm is going to be recursive, well, at least if you are going to make it work for multiple puzzle box sizes. Next: It's important to realize ahead of time that this is going to grow in running time very exponentially. That is, this is going to get nasty. a 3 by 3 box is the base case, and everything needs to be broken up into a base case, so a 4x4 box is going to have 4 3x3 puzzle boxes inside of it, so keep that in mind too. I used scheme because its hella fast at this kind of stuff, you definitely don't want to try this in java or the such, it's just too slow. So here is what I did... I used a list (since scheme doesn't have arrays) of lists to store in the first 3x3 grid, which is the one in the bottom left hand corner (well, the corner opposite of where you want the blank tile to be in the end). From here, it is relatively simple to solve in that the puzzle can be solved using a series of counterclockwise rotations upon the right "outside" of the grid. Where this gets complicated is that this implies you know where pieces are, which you don't... luckily, you saved a list of 3 lists with the values inside of them, and that way you don't need to scan the whole deal to find out where the first, second, third, etc pieces are. You then recursively need to move the pieces counterclockwise along the lists in which the blank goes to the outside, the piece you ar etrying to fit in goes to tehoutside, and then rotate until it gets there. It sounds more confusing then it is, but sit down and try it. Every game can be won using counterclockwise rotations and nothing else. Clockwise rotations have a small(sub 20%) chance of cause an impossible situation by doing clockwise rotations at all. Recursion doesn't like chances of failure. After the first grid is solved, simply move over one set of blocks and do it again until you are at the end of columns, then go back to the blocks on top of the first set and solve that, etc... until it is all solved. If you need any more help, let me know... this is some crazy head stuff, and I made a very good female friend by teaming up to tackle this my sophmore year of college ... involved many, many late nights in a comp lab.

This sounds like a winner. As said, you definitely need recursion if you are going to be using variable box sizes. Also, as said, counter-clockwise rotations can solve many board puzzles (knights tour anyone?). Good luck, and if you need some more help, I'll do my best at cooking up a program that will solve it.