Slider Puzzles, Part 1: Dynamic Programming
In this post we present a mathematical programming technique to solve a classic mechanical puzzle. This is the first in a series of posts that discuss the problem. We will generally follow the notation and conventions described in Powell's "Approximate Dynamic Programming" textbook.
The Classic Slider Puzzle
Slider puzzles come in different shapes and sizes, and you can find wooden or plastic variants at the dollar store. Here is a version you can play in your browser by mouse or tap.
How To Play
Solve the puzzle by rearranging the numbers into ascending order from left to right and top to bottom. Click on tiles adjacent to the empty slot to move them horizontally or vertically. Each move swaps the position of the chosen tile with the empty slot.
Click the "Scramble" button to generate a new challenge. If you get stuck, click "Reset" to return the game to its solved state. Try to solve the puzzle in as few moves as possible.
Solving The Puzzle Computationally
If you play with the puzzle for a while, you will probably get the hang of how to solve it. But can we systematize a method and define an algorithm to do the job optimally? If we can devise such an algorithm, it will allow us to answer interesting questions like what is the hardest arrangement to unscramble? Or, are there any arrangements that cannot be unscrambled?
It turns out that the slider puzzle is an example of a shortest-path problem, and there are many methods for solving these. In this post we will describe a solution using dynamic programming.
To proceed, we will first define the state space and the action space. From there, we will introduce the value function and Bellman's equation, then discuss a simple algorithm that determines the length of the shortest-path from every initial configuration to the solved state. Finally, we will explain how the results can be used to construct actual shortest-paths and solve the problem.
The State Space
We need a simple representation for the different configurations that can arise in the slider puzzle. The state of the puzzle at any given time is fully-determined by the ordering of the numbered tiles, so it is natural to work with this directly. We thus represent each state as the list of twelve numbers read from left to right, top to bottom, and we represent the empty slot with the symbol '0'.
With this convention, the terminal state of the puzzle is T=[1,2,3,4,5,6,7,8,9,10,11,0].
We denote the set of all puzzle states by S. We immediately see that S has at most 12! = 479,001,600 distinct states because 12! is the number of distinct ways a list of twelve unique elements can be rearranged. As we will discuss later, only half of these configurations are reachable from the terminal state T.
Considering the simplicity of the puzzle the state space is quite large, but it is not beyond the reach of modern desktop computers. Real-world applications typically involve state spaces that are far larger, dwarfing the current problem by many orders of magnitude.
The Action Space
From any given state s, there are 2, 3, or 4 possible actions that can be taken. These actions depend on whether the blank tile is in a corner, along an edge, or away from the walls.
Every action has a deterministic outcome that results in the puzzle being in a new state s'. We refer to s' as a neighbour of s, as the two states are only a single slide apart. Likewise, s is a neighbour of s'.
The Value Function and Bellman's Equation
We define the value function V(s) to be the distance (in slides) from state s to the terminal state T. We have V(T)=0. We aim to calculate V(s) for all other reachable states so that we can construct a shortest-path and solve the puzzle.
Bellman's equation for our problem becomes:
V(s) = 1 + mins' V(s'),
where s' belongs to the states that are immediate neighbours of s (reachable with only one slide from s).
We start from the terminal state T and solve outwards. The process continues until the entire state space has been explored. We update V(s) as new states are encountered, always ensuring that V(s) is exactly one unit larger than the value function of its neighbour that is closest to T.
Constructing The Shortest-Path
Once the value function has been computed for every state, it is a simple matter to construct an optimal path from any starting point to the puzzle's terminal state. We do this iteratively. From the current state, we need only consider the value function of the immediate neighbouring states and move to the state with the lowest value. Such a step guarantees progress towards the solution. In the event that there are multiple choices with the best (lowest) value function, any of them may be chosen.
Discussion
The dynamic programming approach described above was implemented in Python. Calculations were then run to study the reachable states and find the most-scrambled configurations possible for the puzzle.
Reachable States
The results revealed that there are 239,500,800 states from which the terminal T is reachable. Notably, the number is precisely 12!/2. Exactly half of the possible 12! orderings of the numbered tiles can actually be attained using the sliding mechanism of the puzzle.
As we will explore in a future post, there are two families of configurations (each of size 12!/2) such that every state within a family is reachable by a finite sequence of slides.
How Long Are The Shortest-Paths?
We now consider how many moves are required to transition from a given state to the terminal (solved) state. Our calculations show that no matter how scrambled the puzzle becomes, it can be unscrambled in no more than 53 moves. In fact, there are 18 initial configurations from which exactly 53 moves are required to solve the puzzle.
In the table below we present the number of moves in a shortest-path and the corresponding number of states demanding that many steps.
| Shortest-Path Length | # of states |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 4 |
| 3 | 9 |
| 4 | 20 |
| 5 | 37 |
| 6 | 63 |
| 7 | 122 |
| 8 | 232 |
| 9 | 431 |
| 10 | 781 |
| 11 | 1392 |
| 12 | 2494 |
| 13 | 4442 |
| 14 | 7854 |
| 15 | 13899 |
| 16 | 24215 |
| 17 | 41802 |
| 18 | 71167 |
| 19 | 119888 |
| 20 | 198363 |
| 21 | 323206 |
| 22 | 515778 |
| 23 | 811000 |
| 24 | 1248011 |
| 25 | 1885279 |
| 26 | 2782396 |
| 27 | 4009722 |
| 28 | 5621354 |
| 29 | 7647872 |
| 30 | 10065800 |
| 31 | 12760413 |
| 32 | 15570786 |
| 33 | 18171606 |
| 34 | 20299876 |
| 35 | 21587248 |
| 36 | 21841159 |
| 37 | 20906905 |
| 38 | 18899357 |
| 39 | 16058335 |
| 40 | 12772603 |
| 41 | 9515217 |
| 42 | 6583181 |
| 43 | 4242753 |
| 44 | 2503873 |
| 45 | 1350268 |
| 46 | 643245 |
| 47 | 270303 |
| 48 | 92311 |
| 49 | 27116 |
| 50 | 5390 |
| 51 | 1115 |
| 52 | 86 |
| 53 | 18 |
The first column of the table specifies the number of moves required to solve the puzzle (the value function V(s)), while the second column describes how many initial states require that many moves in their shortest-path to the solution. As expected, there is one state requiring no moves to solve the puzzle (the terminal state), and two states requiring exactly one move. The average number of moves required to solve a puzzle is 35.1. Experience with playing the puzzle suggests few people will solve it with a near-optimal strategy.
Conclusions
In this post we have presented an algorithmic approach for tackling a mechanical slider puzzle. The slider puzzle is a simple toy, but its underlying mechanism generates a large state space, and its solution requires many of the methods needed for real-world applications in logistics and operations research.
In future posts we will delve deeper into reachable states, alternative solving techniques, and approximate methods for larger puzzles. If you have a challenging computational problem and would like to work with L1 Scientific, please reach out to us.