8 puzzle solver
hi i'm trying to do a 8 puzzle solver on c++ but i can't do it because i don't know how to work with heuristics solution i tried to do the 8 puzzle solver with recursivitiy using a method where i tried to put all the cases in a method and solve all the cases one by one but that wasnt best way to do it and it isnt works because it enter on a bug so if anyone can help me to find a solution without using structure or heurisitics or manhattan please
You have to use a heuristic to properly solve the problem. Manhattan distance is probably best.
Don't use recursion. Instead, use a priority queue initialized with the starting position and prioritized by lesser manhattan distance, add possible moves (except the move that leads back to the previous move), and take the best one each time to generate more moves until the manhattan distance is 0 (which is the solution).
but i can't use that because the teacher said that we have to use recursion but i saw that's impossible and i don't know what to do now
What's an "8 puzzle" ?
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
@Salem, It should be called the "sliding block puzzle", where an "8 puzzle" is one played on a 3-by-3 grid (with tiles 1 to 8 and an empty space) and a "15 puzzle" is played on a 4-by-4 grid (with tiles 1 to 15 and an empty space). It starts with the tiles scrambled up and you move tiles around until they are in order.
@kako03, I didn't mean to suggest that it couldn't be done with recursion. It just doesn't seem best to me since it's brute force. It's pretty easy, though. Just try all the directions except the one leading back to where you just came from. Since you easily get stuck in a repeating loop (e.g., moving the empty space around and around the four spaces in a corner) you either need to keep track of all the positions you've already visited or only look down to some maximum depth. Apparently the 8 puzzle can always be solved in less than 32 moves, but I'm not sure of that. Unless you iteratively limit the depth, first 1 level, then 2, etc., you won't generally get the optimal solution without keeping track of repeated states.
Note that to make a randomized puzzle position you should start with the solved position and make a bunch of random moves. You can't just place the numbers anywhere and expect it to be solvable.
