Uniform Solvable 15-Puzzle Boards: Parity Test and Two Generators

Half of all 15-puzzle arrangements cannot reach the goal, a result Johnson and Story proved using parity in 1879. The practical test depends on the board’s width: an odd width requires an even inversion count; an even width requires an odd sum of the inversion count and the blank’s row, counted from the bottom.

For 4×4, choose a uniform shuffle with a prescribed parity-correcting swap when every solvable board should have the same chance. Taking k random moves from the goal is useful for an animation or a route you can reverse. Record the moves if you need that path.

The half you cannot reach

Include the blank in the permutation. Each legal move flips both the permutation parity and the parity of the blank’s Manhattan distance from the bottom-right corner, so their sum keeps the same parity. Swapping a fixed pair of numbered tiles pairs boards from opposite classes, making those classes equally large. Johnson and Story’s 1879 result also establishes that boards within the same class are mutually reachable, so every board in the goal’s class is solvable.

Sam Loyd offered $1,000 for solving a board with 14 and 15 exchanged. The blank stays in the bottom-right corner, but the swap changes the parity class, so no sequence of legal slides can solve it.

There are 16! arrangements in all, so the reachable set contains 16!/2 ≈ 1.05 × 10^13 boards. This is the same counting used for the 52! deck orders in Only 86 Million Ways to Shuffle: What Game RNG Certification Checks, with half the arrangements excluded here by solvability.

Two branches of the parity test

Use a rectangular board with at least two rows and two columns. For a board of n cells, the goal has tiles 1 to n−1 in order from left to right and top to bottom, with the blank in the bottom-right corner. For a different goal, compare the same parity invariant for the current board and the target.

Read the current board in that same order, leaving out the blank. An inversion is a pair in which the earlier tile has the larger number. Count those pairs, then use the appropriate branch:

Odd width: the board is solvable exactly when the inversion count is even.
Even width: the board is solvable exactly when the inversion count plus the blank’s row from the bottom is odd. The bottom row is row 1.

A horizontal move preserves tile order once the blank is removed. A vertical move takes one tile past w−1 others, where w is the width. For an odd width that is an even number of tiles, so inversion parity stays unchanged. For an even width it flips, but so does the parity of the blank’s row. Adding the row compensates for the change.

At the goal, the inversion count is 0 and the blank is in row 1 from the bottom, so the second branch tests for an odd sum. Omitting the row gives the wrong answer; counting from 0 works if you test for an even sum instead.

Exhaustive BFS on small boards

parity_bfs.py checks reachability independently of the formula. It starts at the goal and follows legal moves with breadth-first search (BFS), then compares membership of that set with the parity test for every permutation. Dimensions below are width × height, and 0 denotes the blank:

# Solvability test for sliding puzzles vs. exhaustive BFS on small boards.
# State: tuple of w*h entries, 0 is the blank; goal is 1..w*h-1 followed by the blank.
#   odd width:  solvable iff the inversion count of the tiles is even
#   even width: solvable iff inversions + (row of the blank counted from the bottom, 1-based) is odd
# The rule depends on the goal convention (blank in the bottom-right corner).
from collections import deque
from itertools import permutations

def solvable(state, w):
    tiles = [t for t in state if t]
    inversions = sum(a > b for i, a in enumerate(tiles) for b in tiles[i + 1:])
    if w % 2:
        return inversions % 2 == 0
    blank_row_from_bottom = len(state) // w - state.index(0) // w
    return (inversions + blank_row_from_bottom) % 2 == 1

def reachable(w, h):
    goal = tuple(list(range(1, w * h)) + [0])
    seen, queue = {goal}, deque([goal])
    while queue:
        s = queue.popleft()
        z = s.index(0)
        r, c = divmod(z, w)
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < h and 0 <= nc < w:
                l = list(s)
                l[z], l[nr * w + nc] = l[nr * w + nc], 0
                t = tuple(l)
                if t not in seen:
                    seen.add(t); queue.append(t)
    return seen

for w, h in ((2, 2), (2, 3), (3, 2), (3, 3), (4, 2)):
    R = reachable(w, h)
    states = list(permutations(range(w * h)))
    mismatches = sum((s in R) != solvable(s, w) for s in states)
    print(f"{w}x{h}: BFS reachable={len(R):6d} = {w * h}!/2={len(states) // 2:6d}   parity test disagrees on {mismatches} of {len(states)} states")

loyd = tuple(list(range(1, 14)) + [15, 14, 0])   # Sam Loyd's 14-15 swap on 4x4
print("4x4 with 14 and 15 swapped, blank bottom-right: solvable =", solvable(loyd, 4))

2x2: BFS reachable=    12 = 4!/2=    12   parity test disagrees on 0 of 24 states
2x3: BFS reachable=   360 = 6!/2=   360   parity test disagrees on 0 of 720 states
3x2: BFS reachable=   360 = 6!/2=   360   parity test disagrees on 0 of 720 states
3x3: BFS reachable=181440 = 9!/2=181440   parity test disagrees on 0 of 362880 states
4x2: BFS reachable= 20160 = 8!/2= 20160   parity test disagrees on 0 of 40320 states
4x4 with 14 and 15 swapped, blank bottom-right: solvable = False

The odd-width branch is exercised by 3×2 and 3×3; the even-width branch by 2×2, 2×3 and 4×2. Neither branch disagrees with BFS on a single permutation. The final 4×4 check also rejects the board with 14 and 15 exchanged.

Checking all 9! = 362,880 permutations is manageable here. Checking 16! with this script on a laptop is not. For 4×4, call the tested solvability function directly.

Two generators

Generator A uses random.shuffle and swaps the first two non-blank tiles in reading order if the result is unsolvable. The blank stays put, so the same positions are selected after the swap. To use the generator on its own, take the random import, the W and H settings with their derived N, and the solvable and gen_a functions. Set the dimensions as needed. Leave the BFS, solvable_states and counting loop in the verification script; copying the whole script would make board generation wait for an exhaustive search.

The swap reverses parity. Repeating that swap restores the original board, so it pairs each unsolvable board with exactly one solvable board. On 2×3 there are 360 of each. Every solvable output therefore has two inputs: itself and its unsolvable partner. With uniform input, every output has probability 2/720.

Generator B starts at the goal, chooses each legal move with equal probability and stops after k moves; reversing the path gives a solution. On 2×3, where BFS supplies all 360 solvable boards, uniform_generator.py uses seed 42 to generate 360,000 boards per setting and counts how often each board appears:

# Two ways to produce a solvable start position, compared on 2x3 where all 360 solvable
# states are known (from BFS), so we can count how often each one comes out.
#   A: shuffle uniformly; if the result is unsolvable, swap the first two tiles (not the blank).
#      Swapping two tiles flips the parity, so this maps the 360 unsolvable states 1-to-1 onto
#      the 360 solvable ones: the output is uniform over solvable states.
#   B: start from the goal and make k random blank moves. Always solvable, but not uniform.
import random
from collections import Counter, deque

random.seed(42)
W, H = 2, 3
N = W * H

def solvable(state, w):
    tiles = [t for t in state if t]
    inv = sum(a > b for i, a in enumerate(tiles) for b in tiles[i + 1:])
    if w % 2:
        return inv % 2 == 0
    return (inv + len(state) // w - state.index(0) // w) % 2 == 1

def moves(s):
    z = s.index(0); r, c = divmod(z, W)
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < H and 0 <= nc < W:
            l = list(s); l[z], l[nr * W + nc] = l[nr * W + nc], 0
            yield tuple(l)

goal = tuple(list(range(1, N)) + [0])
seen, q = {goal}, deque([goal])
while q:
    for t in moves(q.popleft()):
        if t not in seen:
            seen.add(t); q.append(t)
solvable_states = seen

def gen_a():
    s = list(range(N)); random.shuffle(s)
    if not solvable(s, W):
        i, j = [k for k in range(N) if s[k]][:2]
        s[i], s[j] = s[j], s[i]
    return tuple(s)

def gen_b(k):
    s = goal
    for _ in range(k):
        s = random.choice(list(moves(s)))
    return s

T = 360_000
for name, gen in (("A: shuffle + parity swap", gen_a), ("B: 20 random moves", lambda: gen_b(20)), ("B: 100 random moves", lambda: gen_b(100))):
    c = Counter(gen() for _ in range(T))
    all_ok = all(s in solvable_states for s in c)
    print(f"{name:26s} all solvable={all_ok}  distinct={len(c):3d}/360  count range {min(c.values()):5d}..{max(c.values()):5d}  (uniform: 1000 each)")

A: shuffle + parity swap   all solvable=True  distinct=360/360  count range   917.. 1103  (uniform: 1000 each)
B: 20 random moves         all solvable=True  distinct=162/360  count range     1..30221  (uniform: 1000 each)
B: 100 random moves        all solvable=True  distinct=180/360  count range   644.. 6203  (uniform: 1000 each)

A reaches all 360 boards, with counts from 917 to 1,103. Under uniform sampling, each board’s count has an expected value of 1,000 and a standard deviation of about 32.

After 20 moves, B’s sample contains 162 boards. One appears 30,221 times, while another appears just once. Increasing the walk to 100 moves produces 180 distinct boards, with counts between 644 and 6,203. The printed count range covers boards that appeared; distinct counts those boards, leaving the rest absent from the sample.

Colour the board like a chessboard: every move changes the blank’s colour, making the state graph bipartite. After an even number of moves the blank must be on the same colour as at the goal. For 2×3 this confines the walk to 180 of the 360 solvable boards; 4×4 has the same half-set restriction. The 100-move sample reaches all 180. They are all possible after 20 moves too, although this sample misses some. At finite walk lengths, the starting board still affects the probabilities. Mixing odd and even lengths does not automatically make the output uniform: the long-run fraction of time spent at a board is proportional to its number of legal moves.

A walk can retrace its steps. On this 2×3 board, the shortest route back is far shorter than 100 moves even after a 100-move shuffle. If levels are graded by shortest solution length, an optimal solver must supply that distance; k only records the length of the walk.

The 4x4 distance distribution and level selection

Every solvable 4×4 board can be solved within 80 single-tile moves, and some need that many. Brüngger and colleagues proved this bound in 1999.

Korf and Schultze computed the full distance distribution in their 2005 paper, Large-scale parallel breadth-first search. Kociemba’s 15-puzzle solver page lists the count at each distance and displays the 17 boards that require 80 moves. Those counts show how common each distance is; finding the distance of a particular board still requires solving it.

For a level generator, choose A when every solvable board should be equally likely. Choose B when the shuffle needs to be animated or reversed, and retain the move sequence. Use the counting loop to measure board coverage and frequencies. To turn it into a level filter, run each candidate through an optimal solver before accepting it, keep candidates within the required distance range, and count the distances of the accepted boards. On small boards, recording the depth of each first visit in the existing BFS gives a distance lookup; for the full puzzle, solve candidates individually.

Notes

Keep the row-count convention and parity test together: the formula here counts from 1. For a different goal, compare its invariant with the current board’s.
After changing the test, rerun the exhaustive BFS comparisons on 2×2, 2×3, 3×2, 3×3 and 4×2; both branches should agree with reachability.
Before changing the swap rule, check that applying it again selects the same non-blank positions. The pairing depends on it.
Include absent boards when checking a k-move generator’s distribution. Use the complete 2×3 set for that check, and leave the exhaustive search behind when moving to 4×4.
Only 17 of the 16!/2 solvable 4×4 boards need 80 moves. Filter for such levels using each candidate’s shortest solution length; a long shuffle supplies no such selection.