Solvability if two pieces of the fifteen puzzle are identical?

114 Views Asked by At

It's known that only half of all the permutations in the fifteen puzzle can be solved (in the sense of recovering the sequential order of numbers, with the empty slot in the lower right corner), for example see Wikipedia entry. I am wondering what happens if two of the pieces are identical, say we have number 14 and 14 instead of number 14 and 15.

I also think the empty piece is not that special and can be replace by a piece numbered 16, just with the additional rule that a number can switch position only with number 16. With this the above assumption of two identical numbers also include the case where we have two empty slots.

I feel, but not sure, that under this assumption all configurations of the (new) fifteen puzzle can be solved (i.e., transformed to the sequential number configuration, with empty slot at lower right corner), any thoughts?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes. All permutations are solvable.*

Think of it this way. Standardly, it is impossible to exchange the 14 and the 15 because they have different parities. But imagine instead of having two 14s, imagine that the 14 and 15 are allowed to switch places with each other whenever you choose. As you said in the question, half of all puzzles can be solved with a given parity. Combining the two above statements, we know that if switching the 14 and 15 requires a different parity, and that each parity can solve half of all puzzles, when you are allowed to switch the 14 and 15 at will, all puzzles are solvable, half without needing to switch 14 and 15, half requiring it. This can easily be adapted to having to identical numbers.

*An exception to this would be if the two identical numbers had the same parity (i.e. they were both odd or both even). Then, switching them does not change the parity, and therefore also only half of puzzles would be solvable.