I’m talking about the type where you get a grid (usually 3 x 3) with one square blank. The aim is to rearrange the other squares into some given order - a picture, a shape, etc. I find some of these things really tricky, you’re usually left with one piece out of order and trying to put it in its right place makes a mess of the other ones again.
If I do manage to solve these it’s by luck rather than judgment so I wondered if there was some simple step-by-step method to follow whereby the solution is quite quickly arrived at. I live in hope.
There are certainly more than a few algorithmic approaches to solving the sliding puzzles. I would suspect though that the doing and storing the computations is too much for the human brain (we have very limited working memory). Perhaps the most well-known approach is using A* to search for a path to solution (i.e. a set of moves that solves the puzzle). Without getting into too much detail A* determines what next state (move) to look at by looking at the total cost to get to the current state and then estimating the cost from the candidate new state (move) to the goal state. A* has an advantage that it can backtrack to any previously examined state fairly easily*, whereas it is a lot of work for a person manipulating a physical puzzle. If you could do A* in your head, well, then you could solve it algorithmically. I certainly can’t do that in my head.
Oh I forgot, the heuristic (estimation) often used in A* for this puzzle is the sum of the Manhattan distances of each puzzle piece to its solved position. So again, if you could make these computations in your head, you could use that as a method to help guide you towards the correct state.
Yes, I know this isn’t strictly true but it is algorithmically true.
Note, I made a mistake in the previous post. A* estimates the costs from the current state to the goal state, not from the candidate new state to the goal state. Oops. It doesn’t really change the answer which is if you can compute the estimate in your head you could use it as a guide towards the correct solution.
I don’t know if this is a “method,” but here’s how I do it:
[spoiler]This uses an N x N grid, and assumes the traditional numbered pieces from 1 to N squared.
Get piece 1 into row 2, column N, then get piece 2 next to 1, 3 next to 2, and so on through piece N, with the empty space next to piece N. They do not all have to be in row 2, but keep them out of row 1 and column 1.
Form a “loop” going from row 1, column 1, to row 1, column N, then to piece 1, then 2, …, then N, then the empty space, then continue the loop with any remaining pieces you need to get back to row 1, column 1. Move all the pieces in the loop counterclockwise one at a time, and repeat for N loops, until pieces 1 through N are in the correct places in row 1.
Repeat 1 and 2 for row 2 and pieces N+1 through 2N (with N+1 starting in row 3, column N). Repeat this for all but the last two rows.
Finish the last two rows one column at a time, from left to right.
[/spoiler]
I don’t doubt that his approach works; however, I feel like it is replacing one goal state with another, leaving the question of “How do you get it into that configuration?”
I don’t have a slide puzzle handy, so maybe it is easier in practice than his description (that’s not a criticism, honest). Let us know how well it works for you, I’m legitimately curious.
And remember, there’s no way to swap 2 pieces in a sliding puzzle without disturbing any other pieces except for disassembling the puzzle. So if there are two identical pieces, like two letter "e"s in a word puzzle, and you can’t solve it, then you’ve probably got the "e"s opposite of where they belong.
