Hello guys..
I'm trying to make a solver in Allegro for that famous sliding blocks puzzle.
Here's a pic of the game...
www.geocities.com/marcoblbr/diversos/puzzle.jpg
The game consists of 8 numbers, from 1 to 8 all scrambled, for example:
354
718
26
And finishes with all numbers in order...
123
456
78
I found some solvers on the net, but none of them explained the solution.
Well, I want to know if there is an algorythm for solving this game...
I'm sure there is an algorythm or tecnique for doing it quickier.. It doesn't need to be with the mininum steps, but it must be an algorythm that always work !
Thanks for any one that can help me..
You probably would have to do some form of a recursive funtion in order to solve that particular puzzle. As for the exact function, that is hard to explain...
Here's a project that I just had last week. It solves the 8-puzzle game. The concept wasn't too hard for me since it uses the A* algorithm which I know. The hard part about the project is the Language we had to use.
Now if you want an explanation of how it works:
Think of it was a one-puzzle game. Meaning you are the blank spot and you have at most 4 possible moves. UP,DOWN,LEFT,RIGHT.
Every step generate all moves possible and add them to a (sorted list). Sort them by f value
f = g + h;
g = distance ( or number of moves so far)
h = heuristic
The code's heuristic algorithm called manhattan distance. manhattan distance takes the value of each tile and finds out the distance to it's respective location in a goal state
GOAL - SAMPLE PUZZLE = MANHATTAN DISTANCE
[123] - [753] = [210]
[456] - [280] = [211] = 12
[780] - [146] = [221]
Okay so every step grab the smallest fvalue node from the list. If is goal then stop else generate children and place them in list. Repeat
Of course you need to keep track of a nodes parent, and its parent, and its ...
So when you find a goal node you can traverse it backwards to the parent.
Something you need to keep in mind though: not all puzzles are solvable. Consider this trivial one:
1 3 2 .
There is no way to arrange the numbers in the right order.
Similarly for other sizes, about half the puzzles are unsolvable.
Similarly for other sizes, about half the puzzles are unsolvable.
If you want to randomly generate a solvable puzzle, simply start from the solution and scramble it by sliding tiles randomly.
I'd imagine you'd get problems with local minima, too, if you always make the move which results in being closest to the solution... for example:
1 2 3 5 7 6 4 8
is easily solvable, but no move from this point will improve the heuristic score, unless you make the heuristic more complex or look ahead more than one move.
Other than this kind of brute-force-with-heuristic method, you could program a method. One method for solving these puzzles is to just start from the top left, and work across, filling in all the right tiles; they're all easy (on an arbitrary size puzzle) apart from the last two, which need a bit of fiddling but aren't too hard in the end. Then do the next row, until there are only two rows left at which point you don't have much space to manoeuvre.
Now it gets a bit more complicated; I've never conciously thought about what I do at this point, but if you can learn to do it, it's only slightly more difficult to write a proper algorithm for a computer to solve. The main things to notice are what compound moves are available -- don't just thing in terms of single tiles, think of the bigger picture. For example, you can view the last two rows as a series of 4-tile squares, and you're allowed to rotate the ones with the blank in them whichever way you like, which also moves the blank.
In particular, look for sequences of moves which change a few tiles but with as few side effects as possible -- e.g. a move which swaps two pairs of tiles. Then you can write a solution in terms of swapping tiles around, first getting the tiles into the positions which you know how to swap, then doing the swap, then reversing the moves you did to get them there. This is called a conjugate transform, and is very important for solving more complex puzzles like Rubik's Cubes.
It might be overkill for this simple puzzle, but that will become apparent -- if you find a simple way to finish the puzzle off, then you don't need the sledgehammer.
Hmm, perhaps the most fun thing would be to let the computer play with trial and error, and learn how to solve the puzzle itself, by deducing and remembering useful move sequences with few side effects. Then you could feed it different rule sets to simulate different puzzles. Quite a big project though...
In the 19th century sam loyd released a version of this sliding puzzle and offered a reward of $1000 to somebody who could solve it. Unfortunately the puzzle was unsolvable 
I did that one in third year. Afaik I was the only noe who's program solved it correctly, because the method we were told to use didn't work. Do it in two parts: First get the top row correct, then get the other 5 in the right place.
start with the result, randomize until you get the current state, keeping track of the moves.
reverse the process.
You need to do a search of the 'tree of possible moves' to find the 'leaf' that is the solved problem - recursion is good for you!
Even if you don't NEED the shortest path, it is probably better to aim for it - so that the algorithm doesn't just run around cluelessly in the state-space
When you Order all (max 4) available moves according to which one Seems the best (heuristic) - if a move makes a piece move away from it's desired position, give it a -1, otherwise a +1 - you might also make this more sophisticated by, for example giving 'stronger' score the further away the piece is from it's final position might be efficient
Visited states: In order to keep this algo from cycling, you have to make it remember what board-positions it has tried before (in the current branch) - since the board is so small, I guess the following representation would work:
124
763
89*
=
124763890
this gives each state a unique number, which we need to keep track of them easily.
these numbers are put in some kind of container where they can be efficiently found - maybe an STL Map?
Keep some kind of list of visited states, and an ordered one (stack) of the performed moves
-and also another stack to keep the final solution
A good way to keep track of the board is probably to keep it in a matrix 
| 1 | int best_solution = -1; |
| 2 | |
| 3 | void solve(int move_id,int moves_made){ |
| 4 | |
| 5 | // perform move_id (1-4 = up,left, etc..) |
| 6 | |
| 7 | // if best_solution > -1 and moves_made >= best_solution, undo move and exit |
| 8 | // - we shouldn't explore longer solutions than the one (if any) already found |
| 9 | |
| 10 | // if current state already visited, undo move and exit - to avoid cycling |
| 11 | // - otherwise, add the number of the current state to the 'visited' map and continue |
| 12 | |
| 13 | // push move_id to the stack of performed_moves |
| 14 | |
| 15 | // if the current state is the desired state |
| 16 | // if best_solution == -1 or moves_made < best_solution, then best_solution = moves_made, and copy the list of the performed_moves to the solution list |
| 17 | |
| 18 | // order possible following moves according to heuristic |
| 19 | |
| 20 | // perform moves in order, by calling this function recursively: solve(new_move_id, moves_made +1) |
| 21 | |
| 22 | // pop move_id from performed_moves |
| 23 | |
| 24 | // undo move_id |
| 25 | |
| 26 | } |
PS - this is just the 'main' recursive function - you'll also need one to start it up
..hmm.. tell me how it works out