Problem 313: Sliding Game

Detailed mathematical approach

Problem Summary

A board with \(m\) rows and \(n\) columns is full of counters except for one empty cell, the space. A move slides a counter horizontally or vertically into the space, exchanging the two. The red counter starts in the top left corner and the space in the bottom right one, and the game ends when the red counter reaches that corner; \(S(m,n)\) is the least number of moves needed. The statement finishes the \(2\times 2\) game in five moves, gives \(S(5,4)=25\) and counts exactly \(5482\) grids with \(S(m,n)=p^2\) for a prime \(p\lt 100\); we need that count for every prime \(p\lt 10^6\). ^[1] These boards are the \(m\times n\) relatives of the 15 puzzle, where sorting every tile makes a shortest solution NP-hard to find; here one counter alone has a destination. ^[2]

The whole solution in one sentence: the minimum is \(6m+2n-13\) when \(m\gt n\ge 2\) and \(8n-11\) on an \(n\times n\) board, so for each prime the matching boards form one short interval, and the count is a single pass over the primes.

Mathematical Approach

1. A position is just two cells

All counters but the red one are interchangeable, so a position is just a pair of cells: the red counter's and the space's. A move picks a neighbour of the space, whose counter slides in while the space takes its cell; if that neighbour holds the red counter the red counter advances into the old space, and otherwise only the space moves.

Transposing the board swaps \(m\) with \(n\), fixes both corners and maps legal moves to legal moves, so \(S(m,n)=S(n,m)\). A side of \(1\) is useless: a slide only exchanges a counter with the space, so the order of the counters in a single row never changes, and the red counter, first in line and due to finish last, cannot pass even one other counter. Only \(S(1,2)=S(2,1)=1\) is finite there, and \(1\) is not a prime square, so \(m,n\ge 2\) from here on.

2. The \(2\times 2\) game, move by move

Number rows and columns from \(1\), so the red counter starts at \((1,1)\) and the space at \((2,2)\). Five slides finish the game, each sending the space to the cell the slider left: \((2,1)\) right, the red counter down, \((1,2)\) left, \((2,2)\) up, the red counter right. Only two of the five advance the red counter; the other three carry the space to where it is needed next, the split that drives everything below.

3. Red moves and walks of the space

Let \(P_0,\dots,P_L\) be the cells of the red counter in order, from the top left to the bottom right corner. The red counter moves from \(P_{i-1}\) to \(P_i\) only while the space stands on \(P_i\), and just afterwards the space sits on \(P_{i-1}\). A solution is thus \(L\) red moves interleaved with walks of the space: walk \(0\) from the bottom right corner to \(P_1\), then walk \(i\) from \(P_{i-1}\) to \(P_{i+1}\) for \(1\le i\le L-1\). Walk \(i\) never enters \(P_i\), since that would move the red counter, and nothing follows the last red move. The total is \(L\) plus the walk lengths, each at least the distance between its ends with \(P_i\) deleted.

4. How long a walk must be

On the full board the shortest number of steps between two cells is their taxicab distance, the sum of the absolute differences of their rows and of their columns; deleting a cell leaves it a lower bound. ^[3] Walk \(0\) runs from \((m,n)\) to \(P_1\), which is \((2,1)\) or \((1,2)\), both at distance \(m+n-3\). A shortest path to either only decreases row and column, so it cannot pass through \((1,1)\), and walk \(0\) costs exactly \(m+n-3\). For walk \(i\) let \(d\) and \(d'\) be the directions of red moves \(i\) and \(i+1\), so \(P_{i-1}=P_i-d\) and \(P_{i+1}=P_i+d'\).

• Turning back, \(d'=-d\): the walk is empty, but the position before red move \(i\) equals the position after red move \(i+1\), so dropping both shortens the solution. A shortest solution never turns the red counter back.
• Straight on, \(d'=d\): \(P_i-d\) and \(P_i+d\) end a straight stretch of three and have \(P_i\) as their only common neighbour, so without it their distance is at least \(4\); the board has two rows and two columns at least, so the line beside the stretch exists and a detour along it costs exactly \(4\).
• Turning, \(d'\perp d\): \(P_i-d\) and \(P_i+d'\) are diagonal neighbours, and the corner between them takes its row from one and its column from the other, so it lies on the board and the space crosses it in \(2\) steps, the taxicab distance.

Turning is the cheaper joint, so the red counter should zigzag rather than run along a side.

5. The cost of a route

Fix a shortest solution. Its red route never turns back, so each of the \(L-1\) joints is a turn or a straight continuation; let \(t\) count the turns and \(s\) the straight ones, \(s+t=L-1\). The solution costs at least

$$\begin{aligned}&L+(m+n-3)+4s+2t\\&\quad=5L+m+n-7-2t,\end{aligned}$$

and exactly that when every walk is shortest, which Section 4 shows is possible. Let the route use \(a\) vertical and \(b\) horizontal steps, \(L=a+b\). Its net displacement is \(m-1\) rows and \(n-1\) columns, so \(a\ge m-1\), \(b\ge n-1\), and both excesses are even. Read the route as a word in two letters, one per axis: turns are the letter changes, so \(t\) is the number of maximal runs minus \(1\). Runs alternate, so their two counts differ by at most \(1\), and one letter has at most \(a\) runs, the other at most \(b\); hence at most \(2\min(a,b)+[a\ne b]\) runs, where \([a\ne b]\) is \(1\) for \(a\ne b\) and \(0\) otherwise, and

$$t\le 2\min(a,b)+[a\ne b]-1$$

(checked for all \(a,b\le 15\)). Substituting it, and writing \(a+b+4\max(a,b)\) for \(5(a+b)-4\min(a,b)\),

$$\begin{aligned}&S(m,n)\ge a+b+4\max(a,b)\\&\quad-2[a\ne b]+m+n-5.\end{aligned}$$

Raising \(a\) or \(b\) by \(2\) raises \(a+b\) by \(2\) and never lowers \(\max(a,b)\), while the indicator can turn from \(0\) to \(1\) only when the counts were equal, and then \(\max(a,b)\) rises by \(2\) as well. The right-hand side never decreases, so its smallest value, the one valid for every route, sits at \(a=m-1\), \(b=n-1\).

6. The closed form

There the bound reads \(6m+2n-13\) for \(m\gt n\ge 2\), and for \(m=n\) the indicator vanishes and it reads \(8n-11\). An explicit route attains both. For \(m\gt n\), move the red counter down \(m-n\) times, then repeat right-then-down \(n-1\) times: this stays on the board, ends in the corner, and has \(2n-1\) runs, so \(t=2(n-1)\) and \(s=m-n-1\). On a \(4\times 2\) board it is down, down, right, down, and the \(4\) red moves, the opening walk of \(3\), one straight detour of \(4\) and two turning detours of \(2\) add up to \(15=6\cdot 4+2\cdot 2-13\). For \(m=n\), alternate down and right throughout, so \(t=L-1=2n-3\) and \(s=0\). Section 4 supplies the shortest walks in between, so both bounds are met and, with the symmetry of Section 1,

$$\begin{aligned}&S(m,n)=6\max(m,n)\\&\quad+2\min(m,n)-13\end{aligned}$$

for \(m\ne n\), while \(S(n,n)=8n-11\). Breadth-first search over the positions of Section 1, visiting them in order of the moves needed to reach them and so returning the exact minimum, ^[4] reproduces both on all \(169\) boards with \(2\le m,n\le 14\): \(S(2,2)=5\), \(S(3,2)=9\), \(S(3,3)=13\), and \(S(5,4)=25\) as the statement says.

7. Square boards never give a prime square

Every value \(8n-11\) leaves the remainder \(5\) on division by \(8\), while an odd square leaves \(1\), because \((2j+1)^2=4j(j+1)+1\) and \(j(j+1)\) is even. ^[5] The even prime gives \(p^2=4\), and \(8n-11=4\) has no integer solution. No square board is ever counted, so only the formula for \(m\ne n\) matters. A grid and its transpose count as two grids, so the number of grids with a given value is twice the number of pairs with \(m\gt n\ge 2\), which the \(5482\) checkpoint confirms.

8. One prime square, one interval of boards

Fix a target \(q\) and seek the boards with \(m\gt n\ge 2\) and \(6m+2n-13=q\). The left side is odd, so an even \(q\) has no solution; for odd \(q\), halving gives \(3m+n=h\) with \(h=(q+13)/2\). Then \(n=h-3m\) follows from \(m\), and the conditions become bounds on \(m\) alone: \(n\ge 2\) means \(3m\le h-2\), and \(m\gt h-3m\) means \(4m\gt h\). So \(m\) runs over the integers with

$$\begin{aligned} m&\ge\left\lfloor\frac h4\right\rfloor+1,\\ m&\le\left\lfloor\frac{h-2}3\right\rfloor, \end{aligned}$$

and the number of non-square grids with \(S(m,n)=q\) is twice the length of that interval, or \(0\) if it is empty. For a prime square Section 7 rules out the square boards, so that is the whole count — not so for a general odd target, since \(q=13\) gives an empty interval although \(S(3,3)=13\).

Take \(p=7\): \(q=49\), \(h=31\), and the interval is \(8\le m\le 9\), because \(\lfloor 31/4\rfloor+1=8\) and \(\lfloor 29/3\rfloor=9\). So \(m=8\) with \(n=7\), and \(m=9\) with \(n=4\); breadth-first search confirms \(S(8,7)=S(9,4)=49\), and with the transposes that is \(4\) grids. The same recipe gives \(h=19\) and the pair \((5,4)\) for \(p=5\), and \(h=11\) and the pair \((3,2)\) for \(p=3\): \(2\) grids each.

9. The contribution of one prime in closed form

A prime \(p\gt 3\) is coprime to \(6\), so \(p=6j\pm 1\) and \(p^2=12j(3j\pm 1)+1\). One of \(j\) and \(3j\pm 1\) is even, hence \(p^2\equiv 1\pmod{24}\), as was verified for every prime \(3\lt p\lt 10^6\). Writing \(p^2=24k+1\) gives \(h=12k+7\), then \(\lfloor h/4\rfloor=3k+1\) and \(\lfloor (h-2)/3\rfloor=4k+1\), so the interval holds \(k\) values of \(m\) and the prime contributes

$$2k=\frac{p^2-1}{12}\qquad(p\gt 3),$$

which is \(2\), \(4\), \(10\) and \(14\) for \(p=5,7,11,13\). The small primes are special: \((9-1)/12\) is not an integer, yet \(p=3\) contributes \(2\) by Section 8, and \(p=2\) contributes \(0\). The answer is

$$2+\sum_{3\lt p\lt 10^6}\frac{p^2-1}{12}$$

over primes \(p\), and both checkpoints follow: the primes below \(10\) give \(0+2+2+4=8\), those below \(100\) give \(5482\).

How the Code Works

All three programs implement Section 8 directly; none of them searches a board. In the C++ program ^[9] an Options record holds the prime limit, \(10^6\) by default, and a checkpoint flag; parse_arguments reads --skip-checkpoints and --prime-limit= and demands a limit of at least \(2\). Its decimal conversion does not check int overflow, so an absurdly large option is undefined behaviour, though every limit here is safe. sieve_primes is the sieve of Eratosthenes, marking the multiples of \(p\) from \(p^2\) upwards in a byte array; ^[6] solve calls it with prime_limit - 1, so the primes used are exactly those below the limit, as the question asks.

count_grids_for_prime_square is Section 8 line by line: \(0\) for an even argument, the case \(p=2\), and otherwise h, low = h / 4 + 1, high = (h - 2) / 3 and 2 * (high - low + 1), or \(0\) for an empty interval. Integer division truncates towards zero and every quantity is positive, so it matches the floor function, and the guard against a tiny h cannot fire, since \(h\ge 7\). Unless --skip-checkpoints was given, main runs run_checkpoints before the requested computation, verifying solve(100) == 5482 and solve(10) == 8.

The Python and Java ports mirror the same four steps, with a bytearray and a byte[] for the sieve. Neither carries the checkpoints. C++ takes a smaller limit on the command line and Python through the argument of solve(prime_limit=1000000), while Java fixes primeLimit at \(10^6\) inside its parameterless solve. The squares must not be formed in \(32\) bits, since \(46341^2\) exceeds \(2^{31}-1\): Java widens with (long) p * p, C++ casts to std::uint64_t, and Python's integers are unbounded. ^[8]

Complexity and Verification

Let \(P\) be the prime limit, \(10^6\) here. The sieve costs \(O(P\log\log P)\) time and \(O(P)\) memory ^[6] — about one megabyte of flags at the target, plus the list of primes each program keeps — and the interval count is \(O(1)\) for each of the \(78498\) primes below \(10^6\). ^[7] All three finish well under a second. A \(64\)-bit accumulator is ample, since no prime contributes \(10^{11}\) or more: \(0\) for \(p=2\), \(2\) for \(p=3\), and \((p^2-1)/12\le 83330500024\) beyond. Fewer than \(10^5\) primes then keep the total below \(10^{16}\), far under \(2^{63}-1\). ^[8] Individual boards get enormous: for the largest prime below \(10^6\) the interval ends at \(m=166661000049\), so it must be counted from its endpoints rather than walked.

These checks were run for this article. Breadth-first search agrees with the closed form on all \(169\) boards with \(2\le m,n\le 14\); the walk lengths of Section 4 are exactly \(4\) and \(2\) for every cell, pair of directions and board up to \(7\times 7\), and walk \(0\) is exactly \(m+n-3\) up to \(8\times 8\). For \(p\lt 100\) the largest target is \(97^2\), and \(S(m,n)\ge 6m-9\) whenever \(m\ge n\ge 2\), so \(m\le 1569\); enumerating every board with \(2\le n\le m\le 1569\) gives \(5482\) grids. A count that instead loops over \(n\) matches the interval formula for every prime below \(1000\), both giving \(4112102\) grids, and \((p^2-1)/12\) matches it for all \(78496\) primes with \(3\lt p\lt 10^6\), with \(p=2\) and \(p=3\) checked separately. C++ and Python's parameterised solve return \(8\), \(872\), \(5482\) and \(4112102\) for the limits \(10\), \(50\), \(100\) and \(1000\), and a driver calling Java's sievePrimes and countGridsForPrimeSquare gives the same four counts. At the full limit the three programs agree with each other and with an independent evaluation of the closed sum of Section 9.

Footnotes and References

The references supply the background facts; everything about the sliding game itself is derived above.

1. Project Euler 313 — Sliding Game. The official statement defines the game and S(m, n), finishes the 2 by 2 game in five moves, gives S(5, 4) = 25 and the 5482 grids for prime p < 100, and asks for prime p < 10⁶.
2. Wikipedia — 15 puzzle. It describes the same mechanics and the m by n generalisation, and states that a shortest solution of a large sliding puzzle is NP-hard to find.
3. Wikipedia — Taxicab geometry. The taxicab distance is the sum of the absolute coordinate differences and equals the length of a shortest grid path.
4. Wikipedia — Breadth-first search. It finds paths with the fewest edges, using a first-in, first-out queue, in O(|V| + |E|) time.
5. Wikipedia — Square number. It states that all odd squares leave the remainder 1 on division by 8.
6. Wikipedia — Sieve of Eratosthenes. It gives the algorithm, the marking of multiples from each prime's square onwards, and the bounds O(n log log n) and O(n).
7. OEIS A006880 — number of primes below 10ⁿ. The sequence 0, 4, 25, 168, 1229, 9592, 78498 gives 78498 primes below 10⁶.
8. cppreference — fixed width integer types documents std::uint64_t as unsigned with exactly 64 bits; Java — Long gives the range of long as −2⁶³ to 2⁶³ − 1; Python — numeric types states that Python integers have unlimited precision.
9. C++ — Euler313.cpp. The linked immutable revision holds sieve_primes, count_grids_for_prime_square, solve and run_checkpoints, and is the implementation record for this article.