About the solvability of tags
Hello, I'm the creator famous in narrow circles 15 Puzzle apps for Android.
In this article I will discuss how I generate starting positions for my game, as well as how I added new puzzle configurations.
Game “Tag”
Classical game “Tag” consists of a 4×4 grid containing tiles with numbers from 1 to 15 and one empty square:
The goal of the game is to move the pieces to arrange them in ascending order:
You can only move those chips that are next to an empty cell (you cannot move diagonally). The solution might look like this:
Generating starting positions
Solving the same position every time will be boring, so it would be nice to find a way to generate them.
But first, let's figure out how many unique starting positions there are.
Since we have 16 cells, and each cell can have one of 16 states (number or empty), there are only 16! (20 922 789 888 000) options. However, only half of them are solvable. Thus we have 16! / 2 (about 1013) starting positions from which we can reach the target.
This means that when generating the initial state, we need to guarantee its solvability, otherwise the player will not be able to solve the puzzle.
Set of predefined positions
One solution might look like this – take those starting states that we are sure are solvable, and choose a random one each time.
This solution has a problem – you need to store these states somewhere. If we keep 16! / 2 positions as an array of 16 32-bit numbers, we will need approximately 608 TB. And if we also want to have different sizes of puzzles (3×3, 5×5, etc.), then we will need even more space.
There is another problem – somehow you need to generate 1013 positions (and somehow check that each of them is solvable). You can create, for example, 105 starting states, but at some point they will begin to repeat.
But if we can generate even 10 in advance5 states, maybe we can do this “on the fly”?
Random moves
Instead of preparing starting positions, we can generate them upon request. The algorithm could be like this:
We start from the final position (hereinafter
0– empty cell):1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0We choose a random chip, for example,
6:1 2 3 4 5 >6< 7 8 9 10 11 12 13 14 15 >0<Making legal moves, we move
0in place6:1 2 3 4 5 >0< 6 7 9 10 11 8 13 14 15 12Repeat steps 2-3 until we get an acceptable result
This method ensures that the resulting position is solvable. The only question that remains is – how many times should you repeat steps 2-3?
Here is a graph of my simulation with different numbers of iterations and the average number of moves required for an optimal solution:
The average length of the optimal solution is 52.59that is, 150 iterations (repetitions of steps 2-3 of the algorithm) are quite enough.
The problem with this method is that at each iteration of the algorithm (where we move 0 to the selected cell) on average we will do ~2.67 exchange operations in the state array (in total ~400 in 150 iterations). While this won't be noticeable on modern computers (and phones), there is a better option.
Mixing with checking
A better option is to also take the starting position and mix it. For 4×4, shuffling an array of 16 numbers can be done in 15 exchange operationswhich is much better than 400.
For 15 exchange operations (we will ignore the additional 0.5 for now), the average length of the solution is 53 moves, which is almost 1 move “more difficult” than the method of 150 random moves.
But since 50% of states are unsolvable, half the time we will generate a deadlock.
What if there was a way to check whether the resulting configuration is solvable or not? We take the final position, mix it, check it, and, if everything is still unsolvable, repeat the process. With a 50% chance of success, you will only need to repeat the process a few times.
And there is such a way.
Decisiveness
The essence of solvability is parity and inversions.
The first step is to count the number of inversions in our position:
For every number k in position (from left to right, top to bottom), we count the number of numbers that stand after k and less than that k (except 0)
Essentially, we are counting the number of violations of the natural order. For the final position, the number of inversions will be 0, because all numbers are in ascending order.
Let's see how the number of inversions changes when we make a move. For example, there are 52 inversions in this position:
8 4 12 3
14 0 9 15
7 2 5 1
10 11 13 6
Calculations
8 4 12 3 14 0 9 15 7 2 5 1 10 11 13 6 → 7
^ 4 12 3 14 0 9 15 7 2 5 1 10 11 13 6 → 3
^ 12 3 14 0 9 15 7 2 5 1 10 11 13 6 → 9
^ 3 14 0 9 15 7 2 5 1 10 11 13 6 → 2
^ 14 0 9 15 7 2 5 1 10 11 13 6 → 9
^ 0 9 15 7 2 5 1 10 11 13 6 → 5
^ 15 7 2 5 1 10 11 13 6 → 8
^ 7 2 5 1 10 11 13 6 → 4
^ 2 5 1 10 11 13 6 → 1
^ 5 1 10 11 13 6 → 1
^ 1 10 11 13 6 → 0
^ 10 11 13 6 → 1
^ 11 13 6 → 1
^ 13 6 → 1
^ 6 → 0
^ ==
52
If we make a move in horizontal direction, then the number of inversions does not change:
8 4 12 3
14 >9< >0< 15
7 2 5 1
10 11 13 6
Because we don't count 0the order of the numbers remains the same.
However, the move vertically changes number of inversions. By moving 4we get 53:
8 >0< 12 3
14 >4< 9 15
7 2 5 1
10 11 13 6
Please note that we not only change the number of inversions, but also the parity: it was 52, now it is 53.
To understand why the number of inversions changes, let's look at the states before:
8 4 12 3 14 0 - остальные числа -
And after:
8 0 12 3 14 4 - остальные числа -
In table form:
Number | Numbers less (worth before) | Numbers smaller (coming after) | Changing inversions |
|---|---|---|---|
|
|
| 0 |
|
| – | -1 |
|
|
| +1 |
| – | – | 0 |
| – |
| +1 |
For puzzles with a width of 4 cells between 0 and the number being moved will always be 3 other numbers. Since 3 is odd, there will never be a situation where the number of numbers “before” and the number of numbers “after” will be the same. Thus, the following options are possible:
If 3 numbers are greater than the number being moved, then the number of inversions is reduced by 3
If 2 numbers are greater than the number being moved, then the number of inversions is reduced by 1
If 1 number is greater than the number being moved, then the number of inversions increases by 1
If there are no numbers greater than the number being moved, then the number of inversions increases by 3
For puzzles with odd the width will always contain an even number of numbers, so the parity of the inversions does not change
In final position 0 is in the first line from the bottom (we will always consider from below), i.e. the parity of inversions won't match with parity of the line number of the empty cell.
Thus, the position will be decided in two cases:
The entire algorithm for determining the solvability of a position:
Count the number of inversions
Look at the width of the puzzle:
if width odd and number of inversions eventhen the position is solvable (otherwise – unsolvable)
if width even:
Find the row number of an empty cell by counting from below
Look at the number of inversions:
if the number of inversions even and the line number of the empty cell oddthen the position solvable (otherwise – unsolvable)
if the number of inversions odd and the line number of the empty cell honestthen the position solvable (otherwise – unsolvable)
Example:
12 13 11 2
4 5 3 14
1 9 15 6
8 7 0 10
Count the number of inversions – 52
The width of the puzzle is even, the line number of the empty cell is 1
The number of inversions is even (52), the row number of the empty cell is odd (1), so the position is solvable (in 57 moves)
What to do if the position is unsolvable? As I said earlier, you can shuffle an array of numbers until you get a solved position. Or you can use a little trick:
By swapping the two largest numbers (
14And15for 4×4), we will change the parity of the inversions
That is, when we get an unsolvable combination after shuffling, we simply swap two numbers, making it solvable.
This is where the extra 0.5 on the chart comes from – in 50% of cases we will immediately get the correct position, and in the rest we will need to make one additional operation (the 16th), which as a result gives us 15.5 exchange operations on average.
Game expansion
Various width and height
You may have noticed that the solveability of the tags is tied to the width of the puzzle, but not a word is said about the height. There is no mistake: the height of the puzzle can be any, but the same rules will apply.
Snake, spiral and others
Up to this point, we have only considered the final positions, where the numbers are in ascending order, from left to right, from top to bottom. But we can also arrange the numbers in a different order. For example, “snake”:
1 2 3 4
8 7 6 5
9 10 11 12
0 15 14 13
Unfortunately, our algorithm will not work for such a configuration. To fix this problem, let's look at how exactly we count inversions:
For every number k in position (left to right, top to bottom)
That is, we go around the cells in numerical order of the final position (o – Start, x – end):
o → → →
→ → → →
→ → → →
→ → → x
But for the “snake” the order is different:
o → → ↘
↙ ← ← ↙
↘ → → ↘
x ← ← ↙
We just need to change the traversal order for every other line.
And no need to check the width
To understand this, let's see what happens when we make a move in the snake:
1 2 3 4
8 7 6 5
>9< 10 11 12
>0< 15 14 13
For simplicity, we will look only at the numbers involved:
- - - -
- - - -
>0< 10 11 12
>9< 15 14 13
In any case, even for other puzzle sizes, the number of numbers between the empty cell and the one being moved will be even:
1 2 3
6 >0< 4
7 >5< 8
- - -
6 >5< -
7 >0< -
As we can see, the parity of the inversions does not change.
The algorithm is simple:
We go around the cells in the order in which the numbers are in the final position, counting the number of inversions
If the number of inversions evenposition can be solvedotherwise – it is forbidden
For such a “spiral”:
o → → ↘
↗ → ↘ ↓
↑ x ↙ ↓
↖ ← ← ↙
The algorithm is similar. Also, the algorithm will work for any configuration if we can draw a line without lifting the pen from the paper:
↗ ↘ x o
↑ ↓ ↑ ↓
↑ ↘ ↗ ↓
↖ ← ← ↙
Random missing number
There is another interesting configuration of tags: instead of deleting 16 from the field, remove any other random number.
Applying our algorithm on such configurations, we will get 50% unsolvable states, although the algorithm will say the opposite:
12 8 7 15
0 6 4 1
10 9 13 11
3 16 14 5
There is no number in this position 2, 50 inversions and an empty cell is in the third line (remember that we are counting from below), that is, the position is solvable. However, if you try to solve it, you will get something like this (11 And 10 in reverse order):
1 0 3 4
5 6 7 8
9 11<>10 12
13 14 15 16
This will happen in cases where the line number of an empty cell in final positions honest.
What can you do here?
Universal algorithm
Let's pay attention to two things:
Parity of the number of inversions in the starting and final position
Parity of the line number of an empty cell in the starting and ending position
For puzzles with odd widths, we check to see if the parity of the number of inversions for the starting and ending positions is the same.
For even-width puzzles, the line number of the empty cell can be anything, so we'll just take the difference between the line numbers in the starting and ending positions.
To summarize, the reachability algorithm from the starting position S final position G such:
Count the number of inversions in
G–I(G)Count the number of inversions in
S–I(S)If:
width oddand parity
I(G)AndI(S)matches,Greachable fromS(in other words,S– decided position)width even:
Find line number1 empty cells in
G–B(G)Find the row number of an empty cell in
S–B(S)If
I(G):evenand parity
I(S)AndB(G) - B(S)2 matches,Greachable fromSoddand parity
I(S)AndB(G) - B(S)varies,Greachable fromS
In other cases
Gunreachable fromS
1 You can count from below, from above, from 0 or 1 – it doesn’t matter. Since in the next step we subtract the line numbers, we are only interested in the difference in the positions of empty cells in the starting and final states
2 B(G) - B(S) can be replaced by B(G) + B(S)because we only need parity
Hidden text
In fact, we don't need any additional algorithms.
We can simply map the position we need onto the position of classic tags.
Implementation of the algorithm in Java:
/**
* Подсчет количества инверсий в {@code list}
*/
int inversions(
List<Integer> list
) {
int inversions = 0;
int size = list.size();
for (int i = 0; i < size; i++) {
int n = list.get(i);
if (n <= 1) {
// для 0 и 1 проверка не нужна
continue;
}
for (int j = i + 1; j < size; j++) {
int m = list.get(j);
if (m > 0 && n > m) {
inversions++;
}
}
}
return inversions;
}
/**
* Проверка на то, что состояние {@code goal} достижимо из состояния
* {@code start} для пазла шириной {@code width}
*/
boolean isSolvable(
List<Integer> start,
List<Integer> goal,
int width
) {
int startInversions = inversions(start);
int goalInversions = inversions(goal);
if (width % 2 == 0) {
int goalZeroRow = goal.indexOf(0) / width;
int startZeroRow = start.indexOf(0) / width;
if (goalInversions % 2 == 0) {
return startInversions % 2 == (goalZeroRow + startZeroRow) % 2;
} else {
return startInversions % 2 != (goalZeroRow + startZeroRow) % 2;
}
} else {
// четность 'startInversions' и 'goalInversions' должна совпадать
return startInversions % 2 == goalInversions % 2;
}
}
Bonus: random targets
The universal algorithm will work for any puzzle configuration, regardless of the position of an empty cell or a missing number.
Conclusion
Thank you for reading the article to the end. I hope you now know a little more about spots.
And if you want to play the game itself, try it my implementation on Android.
