Outreach module (grades 9-12)
Part 5: Solvability
Warm-up: the 7 puzzle
For the puzzle argument, we do not simply ignore the blank. Instead, we move the blank to the lower-right corner along a fixed snake and then read off the numbered entries.
In the 7 puzzle, this lets us represent a board by a permutation in \(S_7\). Then the job is to show that, after snaking the blank to the lower-right corner, the resulting forms are exactly the even permutations. The same idea then solves the fifteen puzzle.
On a \(2\times4\) board, the blank follows a fixed path: move left across the bottom row, then up to the top-left corner, then right across the top row, and finally down to the lower-right corner.
Two 7-puzzle boards are shown. The first has top row 1, 2, 3, 4 and bottom row 5, blank, 6, 7. The second has top row 2, 3, blank, 4 and bottom row 1, 5, 6, 7. For this argument they count as the same because snaking the blank to the lower-right corner gives the same lower-right form.
These count as the same for this argument because the blank in both cases snakes to the same lower-right form.
For this argument, two boards count as the same whenever one can be turned into the other just by following this prescribed blank motion.
So we do not track the exact location of the blank. We replace each board by the version you get after snaking the blank to the lower-right corner.
After doing that, every board is recorded by a picture of the form
This 7-puzzle form has top row i sub 1, i sub 2, i sub 3, i sub 4 and bottom row i sub 5, i sub 6, i sub 7, blank.
\([i_1\ i_2\ i_3\ i_4\ i_5\ i_6\ i_7]\in S_7\)
Example 1 has top row 1, 2, 3, 4 and bottom row 5, blank, 6, 7.
Example 2 has top row 1, 2, blank, 4 and bottom row 5, 3, 6, 7.
Example 3 has top row 1, blank, 3, 4 and bottom row 5, 2, 6, 7.
Example 4 has top row 1, 4, 2, blank and bottom row 5, 3, 6, 7.
Example 1: \([2\ 3\ 4\ 7\ 1\ 5\ 6]=(1\ 2\ 3\ 4\ 7\ 6\ 5)\).
Example 2: \([1\ 2\ 4\ 7\ 5\ 3\ 6]=(3\ 4\ 7\ 6)\).
Example 3: \([1\ 3\ 4\ 7\ 5\ 2\ 6]=(2\ 3\ 4\ 7\ 6)\).
Example 4: \([1\ 4\ 2\ 7\ 5\ 3\ 6]=(2\ 4\ 7\ 6\ 3)\).
From the previous page, we know that every even rearrangement of \(1,2,\dots,7\) can be built by combining adjacent 3-cycles \(t_i=(i\ i+1\ i+2)\) and their inverses.
A legal 7-puzzle maneuver can produce The adjacent 3-cycle t sub 1 is the permutation [2 3 1 4 5 6 7], which is the cycle (1 2 3). \[ t_1=[2\ 3\ 1\ 4\ 5\ 6\ 7]=(1\ 2\ 3) \] and also Its inverse is [3 1 2 4 5 6 7], which is the cycle (1 3 2). \[ t_1^{-1}=[3\ 1\ 2\ 4\ 5\ 6\ 7]=(1\ 3\ 2). \] The idea is to run the blank around the outer \(2\times4\) rectangle to isolate the tiles \(1,2,3\) in the upper-left \(2\times2\) square, rotate that square once, and then snake the blank back.
By choosing a different outer loop first, one gets additional 3-cycles such as \((3\ 4\ 7)\), \((4\ 7\ 6)\), \((5\ 6\ 7)\), \((1\ 5\ 6)\), and \((1\ 5\ 2)\), together with their inverses.
After relabeling \(5\) and \(7\) on paper, this family contains the same adjacent 3-cycles \(t_1,\dots,t_5\) from Part 4. Therefore their compositions give every even rearrangement of \(1,2,\dots,7\).
Conclusion
Starting from the solved lower-right form, admissible 7-puzzle moves can build every even rearrangement of \(\{1,2,\dots,7\}\).
To show that the 7 puzzle gives only even permutations, we have to understand what a legal move does after we first snake the blank to the lower-right corner. Work with a board written in this lower-right form. Horizontal slides of the blank do not change the recorded permutation, because those slides are already part of the snake. The recorded permutation changes only when the blank crosses between the two rows.
So every move we need to study looks the same: slide the blank along the bottom row to one of the four slots, move it up once, and then snake it back to the lower-right corner. These are the four basic moves. Their inverses come from moving the blank from the top row back down.
In other words, once the board has been rewritten in lower-right form, the only new information comes from the step where the blank moves between rows.
A worked basic move example. The left board is the solved lower-right form with rows 1, 2, 3, 4 and 5, 6, 7, blank. The middle board moves the blank to the top row, giving rows 1, blank, 3, 4 and 5, 2, 6, 7.
After snaking the blank back to the lower-right corner, the board becomes rows 1, 3, 4, 7 and 5, 2, 6, blank.
The resulting permutation is \([1\ 3\ 4\ 7\ 5\ 2\ 6]=(2\ 3\ 4\ 7\ 6)\), a 5-cycle.
Starting from the solved lower-right form, the four bottom-row choices give
The four basic moves give the identity permutation, the 3-cycle (3 4 7), the 5-cycle (2 3 4 7 6), and the 7-cycle (1 2 3 4 7 6 5).\[ e,\qquad (3\ 4\ 7),\qquad (2\ 3\ 4\ 7\ 6),\qquad (1\ 2\ 3\ 4\ 7\ 6\ 5). \]
These are a 1-cycle, a 3-cycle, a 5-cycle, and a 7-cycle, so all four are even.
A general legal sequence may cross between the two rows several times. Each such crossing contributes one of these basic moves or one of their inverses, while the horizontal parts are absorbed by the snake. Therefore every legal move gives an even permutation after the board has been rewritten in lower-right form.
Sections 3 and 4 now give the full answer for the 7 puzzle. Section 3 builds every even lower-right form. Section 4 shows that an odd lower-right form can never appear. If a board snakes to an even lower-right form, then that board is solvable too: first build the lower-right form, then reverse the snake to place the blank back where it started.
7-puzzle theorem
A 7-puzzle board is solvable exactly when the permutation obtained after snaking the blank to the lower-right corner is even.
The same argument works on the fifteen puzzle by viewing it as three overlapping copies of the 7 puzzle. The highlighted pairs of adjacent rows, namely rows \(1\)-\(2\), rows \(2\)-\(3\), and rows \(3\)-\(4\), are the three overlapping \(2\times4\) strips.
Because these strips overlap, the same 3-cycle maneuvers let us build every even permutation of the fifteen numbered tiles. The same basic-move check inside each strip shows that odd permutations cannot appear. That is enough to resolve Loyd's challenge.
Loyd's challenge board corresponds to
Loyd's challenge corresponds to the permutation [1 2 3 4 5 6 7 8 9 10 11 12 13 15 14], which is the transposition (14 15).\[ [1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\ 11\ 12\ 13\ 15\ 14]=(14\ 15), \]
which is odd. The solved board is even. Therefore Loyd's challenge has no solution.
Before thinking about a systematic solution method, try to decide whether a board can be solved at all. Start with the 7 puzzle, make a guess, and then use the workbench below to check your reasoning.
Use the workbench to practice looking at a board and deciding whether it is worth trying to solve.
Focus the board, then use Arrow keys or WASD. Click or tap a neighboring tile to slide it. Try to decide whether the board is solvable before revealing the answer.
7 puzzle board. 2 rows and 4 columns. Blank at row 2, column 4.
Moves: 0
Time: 00:00
Best solved runs: none yet