Abstract
The fifteen puzzle places tiles $1$ to $15$ and one blank on a $4\times4$ board; a tile next to the blank is slid into it to rearrange them. Whether every arrangement can be brought back to the solved position is checked here in numbers. No new theorem or law is claimed.
First, searching small boards, exactly half the positions are reachable——$12$ of $24$ on $2\times2$, $360$ of $720$ on $2\times3$, and $181440$ of $362880$ on $3\times3$. On $3\times3$ the longest distance is $31$ moves ($2$ positions) and the mean is $\mathbf{21.972399}$ moves (Section 2).
Second, one quantity tells the reachable side——the sum of the parity of the tiles’ arrangement (how many swaps make it from the solved position) and the parity of the blank’s distance from its home. Splitting all $362880$ positions of $3\times3$ by this quantity, the $181440$ with value $0$ coincide exactly with those reached by search (Section 3).
Third, the fifteen puzzle is also half——of all $16!=20922789888000$ positions, $10461394944000$ are reachable. The position with only $14$ and $15$ swapped has value $1$ and is on the unreachable side. In a random walk of $200000$ moves, the value stayed $0$ (Section 4).
Fourth, and this is the core. The quantity never changes because the board can be coloured in two colours——each move sends the blank to a neighbouring square, that is, to the other colour, and changes the arrangement by exactly one swap. The two parities always flip together (Section 5).
Fifth, the separator is whether there is a cycle of odd length——joining the left and right edges so that $3$ columns form a cycle creates a cycle of length $3$, the board can no longer be coloured in two colours, and $2\times3$ reaches all $720$ positions and $3\times3$ all $362880$. Joining $4$ columns gives a cycle of length $4$, still two-colourable, and $2\times4$ stays at $20160$ of $40320$ (Section 5).
Sixth, in checking, I once predicted wrongly——I expected that on a $4\times4$ board with edges joined the count by distance parity would stop being preserved, but it was preserved: a move across the edge changes the blank’s distance by $3$, which is odd. Distance parity and colour parity are the same quantity, agreeing on all $362880$ positions (Section 5).
Keywords: 15 puzzle, parity of permutations, invariant, reachability, two-colouring.
Scope (what is not claimed)
No new theorem or law is claimed——that half the fifteen puzzle cannot be reached (Johnson and Story, $1879$), the general theorem for such puzzles on graphs (Wilson, $1974$), and that the longest distance on $3\times3$ is $31$ moves (Reinefeld, $1993$) are all known. The $16!$ positions are not searched——$4\times4$ is only checked by the quantity and a random walk; that the other half is all reachable rests on the search of small boards and on known results. How to find shortest solutions is not treated——the longest and mean distances are values from breadth-first search over all positions. Wilson’s theorem is not proved——boards with joined edges are examples to check the separator in numbers. Relation to earlier papers: Paper 247 counted eight ways of “splitting into even and odd”, listing half-integers of the gamma function, time reversal, the support of Green’s functions, the sign of a determinant and others——the parity here is that of the tiles’ arrangement (the sign of the determinant of a permutation matrix), and whether it matters is decided by the shape of the board. What is added is matching search and the parity count position by position on small boards, placing the separator on whether there is a cycle of odd length and checking it in numbers on boards with joined edges, and checking on all positions that distance parity and colour parity are the same quantity.
1. Notation and the Question
Setting: on an $r\times c$ board, tiles $1$ to $rc-1$ and a blank are placed. The solved position has the tiles in order from the top left and the blank at the bottom right. A move exchanges the blank with a tile adjacent to it up, down, left or right.
The quantity watched: for a position $s$, let $\mathrm{par}(s)$ be the parity of the permutation that makes $s$ from the solved position (counting the blank as a tile), and $d(s)=|r_0-r_*|+|c_0-c_*|$ the distance between the blank’s square $(r_0,c_0)$ and its home $(r_*,c_*)$; set
$$I(s)=\bigl(\mathrm{par}(s)+d(s)\bigr)\bmod 2 .$$The solved position has $I=0$.
Question: how many positions can be reached from the solved one, can $I$ tell them apart, and why?
2. Counting by Search
Computation 2.1: all positions reachable from the solved one were counted by breadth-first search.
| board | all positions | reachable | longest (positions) | mean moves |
|---|---|---|---|---|
| $2\times2$ | $24$ | $12$ | $6$ moves ($1$) | $3.000000$ |
| $2\times3$ | $720$ | $360$ | $21$ moves ($1$) | $12.622222$ |
| $3\times3$ | $362880$ | $181440$ | $31$ moves ($2$) | $\mathbf{21.972399}$ |
Observation 2.2 on all three boards exactly half are reachable. The share is $0.500000$ each time, and the $31$ moves and $2$ positions on $3\times3$ agree with the value Reinefeld obtained by solving all positions——from the other half, no sequence of moves returns to the solved position.
3. Counting by Parity
Computation 3.1: independently of the search, $I$ was computed for all $362880$ positions of $3\times3$. $181440$ have $I=0$ and $181440$ have $I=1$.
Observation 3.2 the set with $I=0$ coincides exactly with the set reached by search. Not only the numbers but each position agrees, and $2\times3$ also agrees——whether a position can be reached is known from $I$ alone, without searching.
Observation 3.3 why $I$ does not change. Exchanging the blank with a tile changes the permutation by one swap, so $\mathrm{par}$ flips. At the same time the blank moves one square, so $d$ goes up or down by $1$ and its parity flips——the two always flip together, so the parity of the sum does not change. Positions with $I=1$ are therefore never reached, and at most half can be.
4. The Fifteen Puzzle
Computation 4.1: $4\times4$ has $16!=20922789888000$ positions, too many to search. Split by $I$, the reachable side has at most $10461394944000$. The position with only $14$ and $15$ swapped (known as the one on which Loyd offered a prize) has $I=1$. A random walk of $200000$ moves from the solved position, checking $I$ $200$ times at every $1000$ moves, never gave $1$.
Observation 4.2 the quantity does the same work on the fifteen puzzle. The swap of $14$ and $15$ cannot be made however many moves are spent——that every position with $I=0$ is reachable was shown by Johnson and Story; this paper only confirmed it by searching small boards.
5. The Separator
Observation 5.1 this is the core: $I$ works because the board can be coloured in two colours. In a chequerboard colouring, neighbouring squares always differ in colour. Each move sends the blank to the other colour and changes the arrangement by one swap——the parity of $d$ is nothing but whether the blank is on the same colour as its home.
Computation 5.2: boards whose left and right edges are joined, making each row a cycle, were searched.
| board (left and right joined) | all positions | reachable | longest (positions) | mean moves |
|---|---|---|---|---|
| $2\times3$ | $720$ | $720$ | $13$ moves ($1$) | $7.950000$ |
| $2\times4$ | $40320$ | $20160$ | $19$ moves ($18$) | $12.971429$ |
| $3\times3$ (top and bottom joined too) | $362880$ | $362880$ | $19$ moves ($4$) | $12.681729$ |
Observation 5.3 the separator is whether there is a cycle of odd length. Joining $3$ columns makes a cycle of length $3$, and the chequerboard colouring is no longer possible; then every position is reachable. Joining $4$ columns gives a cycle of length $4$, still colourable, and half remains——a move across the edge changes the blank’s distance $d$ by one less than the number of columns: $2$ (even) for $3$ columns, which does not cancel the flip of the permutation, and $3$ (odd) for $4$ columns, which does.
Observation 5.4 in checking, I once predicted wrongly. For $4\times4$ with edges joined, I expected that “$I$ counted by distance parity stops being preserved and must be recounted by colour”, and wrote that check. In the measurement, $I$ counted by distance never became $1$ either——I had missed that a move across the edge changes the distance by $3$. Distance parity and colour parity are the same quantity, since $|x|$ and $x$ have the same parity, and they agreed on all $362880$ positions of $3\times3$. The check was corrected to the measurement.
Observation 5.5 beside Paper 247. Paper 247 counted eight ways of “splitting into even and odd”——the parity here is that of the tiles’ arrangement, the sign of the determinant of a permutation matrix; but whether it separates reachable from unreachable is decided not by parity itself but by whether the board has a cycle of odd length.
Observation 5.6 what is not said. The $16!$ positions were not searched, Wilson’s general theorem is not proved, and how to find shortest solutions is not treated——what is shown is that the two routes agree position by position on small boards, and that moving the separator changes the number of reachable positions.
6. Roll Call and Closing
- $181440$ of $362880$ reachable on $3\times3$ (Computation 2.1): exactly half.
- longest $31$ moves ($2$ positions), mean $\mathbf{21.972399}$ (Computation 2.1): agrees with the known value.
- the set with $I=0$ matches the searched set position by position (Observation 3.2): two routes.
- each move flips both parities together (Observation 3.3): the sum does not change.
- $10461394944000$ of $16!$ reachable (Computation 4.1): half on the fifteen puzzle too.
- the swap of $14$ and $15$ has $I=1$ (Computation 4.1): it cannot be made.
- it works because the board is two-colourable (Observation 5.1): the core.
- joining $3$ columns reaches every position; $4$ columns, half (Computation 5.2): the separator is an odd cycle.
- a move across the edge changes the distance by $2$ or $3$ (Observation 5.3): even breaks it, odd keeps it.
- distance parity and colour parity are the same quantity (Observation 5.4): found from a wrong prediction.
Closing: The fifteen puzzle looks as if any arrangement could be returned to the solved position. In fact exactly half can——on $3\times3$, breadth-first search reached $181440$ of $362880$ positions, and they coincided position by position with the $181440$ split off by the sum of the arrangement’s parity and the blank’s distance parity. On $4\times4$ the number is $10461394944000$ of $16!$. The quantity never changes because the board can be coloured in two colours——each move sends the blank to the other colour and changes the arrangement by one swap, so the two parities always flip together. The separator is whether there is a cycle of odd length——joining edges to make a cycle of length $3$, $2\times3$ reached all $720$ and $3\times3$ all $362880$ positions, while with a cycle of length $4$, $2\times4$ stayed at $20160$ of $40320$. Placed among the earlier papers——to the splits by parity counted in Paper 247 it adds one parity whose effect is decided by the shape of the board. To be honest——the $16!$ positions were not searched, and that the other half is all reachable rests on small boards and known results. In checking I once predicted wrongly about $4\times4$ with joined edges, and corrected the check to the measurement.
References
- Johnson, W. W., & Story, W. E. (1879). Notes on the “15” puzzle. American Journal of Mathematics.
- Reinefeld, A. (1993). Complete solution of the eight-puzzle and the benefit of node ordering in IDA*. Proceedings of the International Joint Conference on Artificial Intelligence.
- Wilson, R. M. (1974). Graph puzzles, homotopy, and the alternating group. Journal of Combinatorial Theory, Series B.
- Yamagishi, Y. (2026). Splitting by Parity Is Not One Phenomenon [Paper 247]. Zenodo. 10.5281/zenodo.22159832
Reference
Yamagishi, Y. (2026). Half of the Fifteen Puzzle’s Positions Can Never Be Reached [Paper 601]. YOI: https://www.yamagishiyuuki.com/yoi/601
DOI: 10.5281/zenodo.22805752
ORCID: 0009-0006-8587-3450
PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS
The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 601. This paper is a preprint and has not been peer reviewed.