9
$\begingroup$

puzzle

For those that are not familiar with (this type of) sliding puzzles, basically you have a number of tiles on a board equal to (n * m) - 1 (possibly more holes if you want). The goal is to re-arrange the tiles in such a way that solves the puzzle.

The puzzle could be anything, from number games to images.

While writing a small app for this, I found that if I were to initialize the puzzle by randomly shuffle all of the pieces, I could end up in a situation where there is no solution if my puzzle was 2x2.

So the problem I have is: given a sliding puzzle with n-by-m dimensions, is there always a solution if there are a sufficient number of tiles (eg: a 3x3 board)? How would I even begin to prove this, or simply convince myself that it is the case?

If it is possible that a random shuffle could result in no-solution, then I'd have to figure out how to verify that there exists a solution, which is a completely different beast.

$\endgroup$
5
  • $\begingroup$ If it started in a solved position, simply doing the reverse of all the random moves would bring you back to it. $\endgroup$
    – VBCPP
    Apr 14, 2014 at 16:53
  • 8
    $\begingroup$ Wikipedia -> 15 puzzle -> Solvability: "Johnson & Story (1879) used a parity argument to show that half of the starting positions for the n-puzzle are impossible to resolve, no matter how many moves are made..." $\endgroup$
    – gnat
    Apr 14, 2014 at 16:56
  • $\begingroup$ Thanks, I didn't know there was a specific name for this class of puzzles. $\endgroup$
    – MxLDevs
    Apr 14, 2014 at 17:36
  • $\begingroup$ If I'm understanding the conclusions correctly, if I just randomly swap two tiles at a time, for an even number of times, I should have a solvable configuration. $\endgroup$
    – MxLDevs
    Apr 14, 2014 at 18:07
  • 1
    $\begingroup$ This question appears to be off-topic because it is about puzzles not programming. While algorithms are used to find (optimal) solutions to puzzles, this question is asking if a solution always exists. $\endgroup$
    – GlenH7
    Apr 14, 2014 at 22:40

5 Answers 5

6
$\begingroup$

Martin Gardner had a very good writeup on the 14-15 puzzle in one of his Mathematical Games books.

Sam Loyd invented the puzzle. He periodically posted rewards for solutions to certain starting configurations. None of those rewards were claimed.

Much analysis was expended, and it was finally determined, through a parity argument (as mentioned in the comment above), that half of the possible starting configurations were unsolvable. Interestingly, ALL of Loyd's reward configurations were unsolvable.

SO: No, every possible configuration is not solvable. If you START with a solved puzzle, and apply only legal transformations (moves) to it, you always wind up at a solvable configuration.

For the GENERAL nxm question, you'd probably have to expand the parity argument.

$\endgroup$
2
  • 1
    $\begingroup$ You don't have to expand the parity argument at all. The puzzle is solvable precisely when the parity of the configuration is even. This applies to general $n \times m$ as well, as long as $n,m \ge 3$ so you have enough room. $\endgroup$ Apr 15, 2014 at 14:24
  • $\begingroup$ This history in this answer is incorrect on almost all counts. Sam LLoyd did claim to have invented the puzzle, but he had nothing to do with it (see this 2006 book). Furthermore, it was known almost as early as the puzzle first became popular that it some configurations are unsolvable; the parity argument was published already in 1879. Therefore, it was almost certainly by design and not by accident that Lloyd's configurations were unsolvable. $\endgroup$
    – Sid
    Apr 30 at 17:09
4
$\begingroup$

Just a hint. Once I had to show with basic algebra (permutation groups) that a standard $15$ puzzle had no solution. The idea there was the following:

to rearrange the puzzle, you have to perform a permutation of the $15$ tiles.

Now, notice that once you write any permutation allowed, it is written as a product of an even number of $2$-cycles (you always move the "empty" tile, it starts in the corner and it has to be still there at the end of your moves). Hence permutation with sign $-1$ are not allowed.

In my case it was enough to conclude the puzzle had no solution (I had to perform an exchange between two tiles, so it had sign $-1$). Maybe it can help you to exclude some configurations.

$\endgroup$
2
$\begingroup$

The solvability of an n puzzle can be tested after shuffling by computing the permutations of the puzzle. "While odd permutations of the puzzle are impossible to solve, all even permutations are solvable."

For the math behind this, please see http://mathworld.wolfram.com/15Puzzle.html

$\endgroup$
2
  • $\begingroup$ While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review $\endgroup$
    – Joey Zou
    Oct 3, 2016 at 3:14
  • 1
    $\begingroup$ The answer is useful and is summarized in "While odd permutations of the puzzle are impossible to solve, all even permutations are solvable." The provided link is a reliable one. $\endgroup$
    – Kokeb
    Oct 3, 2016 at 15:00
1
$\begingroup$

Yes, it will always have a solution as long as you start with a good solution and then make legal moves to randomize the tiles.

BUT if you, for example, pop two pieces out and switch them, then you can get an insolvable puzzle. ;) As you discovered.

$\endgroup$
-1
$\begingroup$

Here, we consider the following problem: For a given position on the board to say whether there is a sequence of moves leading to a decision or not.

Let there be given a position on the board:

+------------------+.  
| 11 | 15 | 2 | 13 |.  
|----|----|---|----|.  
| 14 | 1  | 8 | 3  |.  
|----|----|---|----|.  
| 7  | 6  | 0 | 10 |.  
|----|----|---|----|.  
| 4  | 12 | 9 | 5  |.  
+------------------+.

wherein one of the elements is zero and indicates an empty cell. Consider the numbers in the matrix serially (rowwise):

11 12 2 13 14 1 8 3 7 6 0 10 4 12 9 5

Denote N - the number of inversions in the permutation (i.e. the number of such elements a[i] and a[j] that i < j but a[i] > a[j]).

Next, let K- line number in which there is an empty element (i.e. in our notation K = 3).

Then, a solution exists if and only if N + K is even.

$\endgroup$
2
  • 1
    $\begingroup$ I tried to edit your post to make the math formatting work, but I failed (partly because I could not understand some of it). Have a look at the introduction to posting mathematical expressions. $\endgroup$
    – hardmath
    May 31, 2017 at 2:08
  • $\begingroup$ Thanks @hardmath. Fixed the formatting. $\endgroup$ Aug 2, 2017 at 12:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .