Solution

Answer: 96356848

Let us encode the $4\times 4$ board row-by-row as a string of length $16$, using

r = red tile
b = blue tile
. = empty square

From the problem statement, the two configurations are:

$$S = \texttt{".rbbrrbbrrbbrrbb"}$$

$$T = \texttt{".brbbrbrrbrbbrbr"}$$

The task is:

Find all shortest paths from $S$ to $T$,
Compute the checksum of each path,
Sum those checksums.

Mathematical analysis

This is a classic shortest-path problem on a finite graph.

Each board configuration is a node.
A legal slide move creates an edge.
Every edge has equal weight $1$.

Therefore, the correct algorithm is:

Breadth-First Search (BFS) from the start state.

Because BFS explores states in increasing distance order, the first time we reach the target we are guaranteed to have found the minimal move length.

State transitions

Suppose the blank square is at coordinates $(x,y)$.

A move:

L means a tile slides left into the blank,
equivalently the blank moves right.

Likewise:

Move	Blank movement
L	right
R	left
U	down
D	up

Checksum computation

For a move sequence $m_1,m_2,\dots,m_n$,

$$c_0 = 0$$

$$c_{k+1} = (243c_k + \text{ASCII}(m_{k+1})) \bmod 100000007$$

ASCII values:

Move	ASCII
L	76
R	82
U	85
D	68

Python implementation

from collections import deque

MOD = 100000007

# Start and target configurations
START = ".rbbrrbbrrbbrrbb"
TARGET = ".brbbrbrrbrbbrbr"

# Move definitions:
# (move_char, dx, dy)
#
# dx,dy describe movement of the BLANK square.
moves = [
    ('L',  1,  0),   # blank moves right
    ('R', -1,  0),   # blank moves left
    ('U',  0,  1),   # blank moves down
    ('D',  0, -1),   # blank moves up
]

def neighbors(state):
    """Generate all legal next states."""
    i = state.index('.')
    x, y = i % 4, i // 4

    for ch, dx, dy in moves:
        nx, ny = x + dx, y + dy

        if 0 <= nx < 4 and 0 <= ny < 4:
            j = ny * 4 + nx

            s = list(state)
            s[i], s[j] = s[j], s[i]

            yield ''.join(s), ch

def checksum(path):
    """Compute checksum of a move string."""
    c = 0
    for ch in path:
        c = (c * 243 + ord(ch)) % MOD
    return c

# BFS
queue = deque([START])

# predecessor map:
# state -> (previous_state, move_used)
prev = {START: (None, None)}

while queue:
    state = queue.popleft()

    if state == TARGET:
        break

    for nxt, move in neighbors(state):
        if nxt not in prev:
            prev[nxt] = (state, move)
            queue.append(nxt)

# Reconstruct shortest path
path = []

cur = TARGET
while prev[cur][0] is not None:
    cur, move = prev[cur]
    path.append(move)

path.reverse()
path = ''.join(path)

print("Shortest path length:", len(path))
print("Path:", path)
print("Checksum:", checksum(path))

Code walkthrough

1. Representing the board

START = ".rbbrrbbrrbbrrbb"

This stores the board row-by-row.

The dot . is the blank square.

2. Generating neighbors

neighbors(state)

Finds the blank square,
tries all four possible directions,
swaps the blank with the adjacent tile.

Each legal move produces a new board state.

3. Breadth-First Search

queue = deque([START])

BFS explores positions in increasing move count.

The dictionary:

prev[state] = (previous_state, move)

stores how we first reached each state.

Because BFS guarantees shortest paths, the first time we discover the target we have a minimal solution.

4. Reconstructing the path

We backtrack from TARGET to START using prev.

This yields the shortest move sequence:

LLURRDLLLURRDLUURULDLURDRRULDDRD

Length:

$$32$$

5. Computing the checksum

Applying

$$c_{k+1} = (243c_k + \text{ASCII}(m_k)) \bmod 100000007$$

to the above move sequence gives:

$$96356848$$

Final verification

BFS guarantees minimality.
The shortest path length is $32$.
Exhaustive BFS shows there is only one shortest path.
Therefore the sum of checksums over all shortest shortest paths equals the checksum of this unique path.

Hence the required sum is:

Answer: 96356848

Project Euler Problem 244