Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Following the suggestion of Gerry Myerson who commented below, I went ahead and read Johnson's "Note on the '15' Puzzle". Bearing in mind that I am not well versed in the English of 19th century mathematicians, my understanding is as follows:

If the initial state is, for example

1 2 3 4 5 6 7 8               4 2 7
4 2 7 6 5 8 3 1 ... that is,  6 5 8
                              3 1 _

We can construct 'cycles' by listing each tile and the tile that is where it should be, and the tile that is where that one should be, and so on. Listing the cycles in parenthesis we get the following:

(4 6 8 1)(2)(3 7)(5)

There are n=8 tiles and here we have m=4 cycles. If we exchange any two tiles in out initial arrangement, this will either break up a cycle or combine two cycles. In either case, if m was even it will be odd after such a swap (which Johnson calls an 'interchange'. Similarly, (n - m) will also change from even to odd.

The solved board state is made of m=8 cycles, each with 1 element. So in its solved state or natural order, (n - m) = 0. From this initial state, "any odd number of interchanges will produce an arrangement in which n - m is odd, and any even number, one in which n - m is even."

Notice that interchanges made on the naturally ordered board (or any board derived from it by interchanges) will not affect the position of the blank. Johnson calls the odd states "negative" and the even ones "positive".

Now, given an initial state (with the blank somewhere) we can determine whether it is positive or negative by taking whatever tile happens to occupy the lower right corner, pulling it up off the board, and then depositing it wherever the blank happens to be. This will give us a state that resembles the goal state, except that the numbers are all scrambled. Counting cycles as we have above, we will arrive at either an odd or even number of cycles, and we can then call this state even or odd (positive or negative).

The desired arrangement, that is the one with natural order, is a positive one (as explained above) and Johnson concludes that we cannot arrive at a positive arrangement from a negative one.


Did I read that right? So whether it is an 8, 15, or 31-puzzle, given the usual initial state (with the blank in the corner) I can rule out a state by: teleporting the blank into the bottom left corner, counting the cycles, and then saying "NO! This state is odd and can never lead to the goal state".

More generally, given any starting state at all, once I've determined its 'sign' I can determine whether other states are unsolvable by this trick of counting cycles?

Thanks,

z.


EDIT for posterity the original question is included below

Can someone explain to me how to show that a state in an 8 or 15-puzzle can't be solved to a particular goal state. I've been tasked with solving 8 and 15-puzzles with a heuristic search, and that's all well and good. The problem is that when I generate the initial state for the 8 or 15-puzzle, I'd like to avoid states that can't be solved. The other problem is that the goal state in my puzzle might have the blank in the bottom right today, and in the top left tomorrow.

The techniques I've found only tend not to be general enough for me: they deal with a particular puzzle with a particular goal state, and when I try to use their techniques to detect unsolvable states given a different board layout or a different goal state, they don't work.

Ultimately I'd like to understand this problem generally enough to be able to write an algorithm that, given an initial state, a goal state, and a dimension n, determine whether that initial state cannot be solved into that goal state in the nxn puzzle.

share|improve this question
1  
The canonical way to show that a given state can be solved is to exhibit a solution. It's to show that it cannot be solved that requires ingenuity. –  Henning Makholm Oct 10 '12 at 11:25
    
Do you think I should edit the question? You're right, what I'm more interested in is being able to show that some state can't be solved into some other state. –  Ziggy Oct 11 '12 at 17:11
2  
(atprotector) @Ziggy: Editing the question will, at least, bring some additional attention to it because it will bump its position on the front page. But rather than the can/can't issue, I think the main reason why you haven't got any answers is that it's kinda vague what you ask for. You want a general theory for all "$n$-puzzles", but it is not quite clear to me exactly what you consider an "$n$-puzzle" to be. Are you concerned solely with $m\times k$ rectangular sliding puzzles with $n=mk-1$ pieces and a single empty slot, or does your concept include more general puzzles too? –  Henning Makholm Oct 11 '12 at 17:43
1  
I think many of your questions are answered at en.wikipedia.org/wiki/Fifteen_puzzle and the links therefrom. –  Gerry Myerson Oct 12 '12 at 5:56
    
I think you have it right. –  Gerry Myerson Oct 13 '12 at 11:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.