Problem 244: Sliders

Project Euler Problem 244 Solution

EulerSolve provides an optimized solution for Project Euler Problem 244, Sliders, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The puzzle uses a $4\times4$ board containing one white square $W$, seven red squares $R$, and eight blue squares $B$. The initial board is W R B B R R B B R R B B R R B B and the target board is W B R B B R B R R B R B B R B R A legal move slides one colored square into the white square. The move letters $L,R,U,D$ are the letters used in the checksum rule, so they describe the direction of the tile that moves, not the direction of the white square. Among all legal move sequences that transform the start board into the target board, we consider only those with minimum length. For a move sequence $m_1m_2\cdots m_\ell$, the checksum is defined by $$c_0=0,\qquad c_{i+1}\equiv 243c_i+\mathrm{ASCII}(m_{i+1}) \pmod{100000007}.$$ The required answer is the sum of the final checksum over every shortest sequence. Mathematical Approach The heart of the problem is not numerical optimization but graph structure. We must identify the right state graph, isolate the shortest-path subgraph, and then accumulate the checksum over that restricted set of paths. The State Graph of Colored Boards Each board position is a state....

Detailed mathematical approach

Problem Summary

A $4\times4$ board holds seven red tiles, eight blue tiles and one empty square. A move slides a tile next to the empty square into it and is written as the initial $\mathtt L$, $\mathtt R$, $\mathtt U$ or $\mathtt D$ of the direction in which the tile moves: left, right, up or down. The empty square moves the opposite way. With $0$ for the empty square, $1$ for red and $2$ for blue, the starting board $S$ and the target board $T$ are ^[1]

$$S=\begin{pmatrix}0&1&2&2\\1&1&2&2\\1&1&2&2\\1&1&2&2\end{pmatrix},$$

$$T=\begin{pmatrix}0&2&1&2\\2&1&2&1\\1&2&1&2\\2&1&2&1\end{pmatrix},$$

so in $T$ the colours alternate like the squares of a chessboard. A move sequence $m_1m_2\cdots m_n$ has the checksum $c_n$, where $c_0=0$ and

$$\begin{aligned}c_k&=\bigl(243\,c_{k-1}+a(m_k)\bigr)\bmod p,\\p&=100\,000\,007,\end{aligned}$$

with the ASCII codes $a(\mathtt L)=76$, $a(\mathtt R)=82$, $a(\mathtt U)=85$ and $a(\mathtt D)=68$. For example, $\mathtt{LULUR}$ leads from $S$ to the board

$$E=\begin{pmatrix}1&1&2&2\\1&2&2&2\\1&0&1&2\\1&1&2&2\end{pmatrix}$$

and has the checksum $19761398$. We must add up the checksums of all move sequences of the smallest possible length that lead from $S$ to $T$.

The whole solution in one sentence: tiles of one colour are interchangeable, so there are only $102960$ boards, and two breadth-first searches, from $S$ and from $T$, single out the moves on shortest routes, along which a final search walks through every shortest sequence and adds up the checksums.

Mathematical Approach

We make the boards the nodes of a graph, measure distances in it, and use them to pick out the shortest move sequences; Section 6 does all of this by hand.

1. A board is a colouring

Tiles of one colour cannot be told apart, so a board is fixed by the cell of the empty square and by the cells of the seven red tiles among the other $15$; the blue tiles fill the rest. There are therefore

$$16\binom{15}{7}=16\cdot6435=102960$$

boards. Different move sequences can reach the same board: from $S$, both $\mathtt{LU}$ and $\mathtt{UL}$ move two red tiles, put a red tile into the corner and leave the empty square in the second row and second column, so they end on the same board.

All $102960$ boards can be reached from $S$. With numbered tiles, as Johnson and Story showed in 1879, two arrangements can be turned into each other exactly when they agree in whether the parity of the permutation of the $16$ squares equals the parity of the taxicab distance of the empty square from a fixed corner, which splits the $16!$ arrangements into two classes of $16!/2\approx1.05\cdot10^{13}$ each. ^[2] Number the tiles of $S$, and give the red tiles of any colouring the red numbers of $S$ and its blue tiles the blue ones. If this numbering lies in the other class, exchanging two red numbers moves it into the class of the numbered $S$, since it changes the parity of the permutation ^[5] but not the colouring. The moves that reach it then reach the colouring.

2. Moves and the graph of boards

Number the cells $0,1,\dots,15$ row by row, so that cell $z=4r+c$ lies in row $r$ and column $c$, both counted from $0$. With the empty square at $z$, the possible moves are:

$\mathtt L$: the tile at $z+1$ slides left, possible when $c\lt3$;
$\mathtt R$: the tile at $z-1$ slides right, possible when $c\gt0$;
$\mathtt U$: the tile at $z+4$ slides up, possible when $r\lt3$;
$\mathtt D$: the tile at $z-4$ slides down, possible when $r\gt0$.

Each move is undone by the opposite letter. Joining two boards when one move turns one into the other gives an undirected graph on the $102960$ boards, in which a move sequence is a walk: different moves send the empty square to different cells and so lead to different boards. The empty square has $2$, $3$ or $4$ neighbouring cells in a corner, on a side or in the middle, $4\cdot2+8\cdot3+4\cdot4=48$ in total over its $16$ cells, so the graph has $6435\cdot48/2=154440$ edges.

3. Distances by breadth-first search

Breadth-first search finds the smallest number of moves from $S$ to every board. ^[3] It gives $S$ the distance $0$ and takes the boards from a first-in-first-out queue, giving every neighbour not seen before the distance of the current board plus one and putting it at the back. Boards leave the queue in the order of their distances, and each one is first seen from a board one move closer to $S$, so it receives its true distance $d_S(v)$. By hand, $\mathtt L$ and $\mathtt U$ give $2$ boards at distance $1$, and their moves give $3$ new boards at distance $2$, one of them twice, as in Section 1. The layers hold $1,2,3,5,8,15,\dots$ boards, and the farthest boards are $48$ moves from $S$. A second search from $T$ gives $d_T(v)$, which is also the smallest number of moves from $v$ to $T$, since every move can be undone. The length we need is $D=d_S(T)$.

4. The empty square fixes the parity

$\mathtt L$ and $\mathtt R$ move the empty square one column right or left, and $\mathtt U$ and $\mathtt D$ one row down or up. So the length of a move sequence is at least the taxicab distance between the cells where the empty square starts and ends, and has the same parity. A sequence from $S$ to $T$ brings the empty square back to the corner, so it contains as many letters $\mathtt L$ as $\mathtt R$ and as many $\mathtt U$ as $\mathtt D$, and its length is even.

5. Which moves lie on a shortest route

Call a move from a board $v$ to a board $w$ useful if

$$\begin{aligned}d_S(w)&=d_S(v)+1,\\d_S(w)+d_T(w)&=D.\end{aligned}$$

Claim. The shortest move sequences from $S$ to $T$ are exactly the sequences of $D$ useful moves that start at $S$, and a search from $S$ along useful moves never gets stuck before it has made $D$ moves.

Proof. Let $S=v_0,v_1,\dots,v_D=T$ be the boards of a shortest sequence. Its first $i$ moves lead to $v_i$ and its last $D-i$ moves from $v_i$ to $T$, so $d_S(v_i)\le i$ and $d_T(v_i)\le D-i$; a route from $S$ via $v_i$ to $T$ has at least $D$ moves, so $d_S(v_i)+d_T(v_i)\ge D$. Hence $d_S(v_i)=i$ and $d_T(v_i)=D-i$, and every move of the sequence is useful. Conversely, $d_S$ grows by one with each useful move, so after $i$ useful moves from $S$ we stand on a board $v$ with $d_S(v)=i$ and $d_T(v)=D-i$: for $i=0$ because $d_T(S)=d_S(T)$, and for $i\ge1$ by the second condition of the last move. For $i=D$ this means $d_T(v)=0$, so $v=T$ and the sequence is a shortest one. If $i\lt D$, let $u$ be the next board on a shortest route from $v$ to $T$, so that $d_T(u)=D-i-1$. As a neighbour of $v$, $u$ has $d_S(u)\le i+1$, and a route via $u$ has at least $D$ moves, so $d_S(u)\ge D-d_T(u)=i+1$. The move from $v$ to $u$ is therefore useful. $\square$

The useful moves form the shortest-path graph. Since $d_S$ grows along its moves, it has no cycles: it is a directed acyclic graph with the layers $d_S=0,1,\dots,D$. ^[4] A search from $S$ along useful moves therefore follows every shortest sequence exactly once.

6. Worked example: the shortest ways from $S$ to $E$

Take the board $E$ of the statement as the target; a search from $E$ gives distances $d_E$, which take the place of $d_T$. The empty square of $E$ lies in row $2$, column $1$, three steps from the corner, so by Section 4 a sequence from $S$ to $E$ has odd length, at least $3$. The three-move sequences that take the empty square there, $\mathtt{LUU}$, $\mathtt{ULU}$ and $\mathtt{UUL}$, move only red tiles, so the cell in row $1$, column $1$ stays red, while it is blue in $E$. Hence $d_S(E)=5$, the length of $\mathtt{LULUR}$, and $5$ takes the place of $D$. Along $\mathtt{LULUR}$ the six boards have the distance pairs $(d_S,d_E)$ equal to $(0,5)$, $(1,4)$, $(2,3)$, $(3,2)$, $(4,1)$ and $(5,0)$, each with the sum $5$, so all five moves are useful. The other board at distance $1$, reached by $\mathtt U$, also has $d_E=4$, and from it $\mathtt L$ leads to the board reached by $\mathtt{LU}$, as in Section 1; from there $\mathtt{LUR}$ is the only useful continuation. The shortest-path graph for $E$ thus has $7$ boards, in layers of $1,2,1,1,1,1$, and there are exactly two shortest ways, $\mathtt{LULUR}$ and $\mathtt{ULLUR}$. Their checksums, step by step:

$\mathtt{LULUR}$: $76$, $18553$, $4508455$, then $1095554650-10p=95554580$ and $23219763022-232p=19761398$;
$\mathtt{ULLUR}$: $85$, $20731$, $5037709$, then $1224163372-12p=24163288$ and $5871679066-58p=71678660$.

The final checksum of $\mathtt{LULUR}$ is the checkpoint of the statement. With $E$ as the target, the requested sum would be $19761398+71678660=91440058$. The two ways end on the same board with different checksums.

7. The checksum is a polynomial hash

Unrolling the recurrence gives, for a sequence of $n$ moves,

$$c_n\equiv\sum_{k=1}^{n}a(m_k)\,243^{\,n-k}\pmod{p}.$$

The recurrence is Horner's rule for this polynomial in $243$, ^[6] and the checksum is a polynomial rolling hash of the word. ^[7] The weight of a letter depends on its position, so the board reached does not determine the checksum: two sequences that meet on a board can be merged only if their checksums agree as well, and a search keeps the checksum with each prefix. Before the reduction, $243\,c_{k-1}+a(m_k)$ can reach $243(p-1)+85\approx2.4\cdot10^{10}$, more than $2^{32}$, so it needs $64$-bit integers. The requested result is the ordinary sum of the reduced checksums.

Counting needs no listing. Let $N(v)$ be the number of shortest sequences from $S$ to a board $v$ of the shortest-path graph; then $N(S)=1$, and layer by layer $N(w)$ is the sum of $N(v)$ over the useful moves from $v$ to $w$. With $C(S)=0$, the sums $C(v)$ of the checksums of these sequences follow the same pattern modulo $p$, with $m$ the letter of the move from $v$ to $w$:

$$C(w)\equiv\sum_{v\to w}\bigl(243C(v)+a(m)N(v)\bigr)$$

In general this gives the requested sum only modulo $p$. Listing the sequences one by one keeps every checksum exact, and $N(T)$ tells in advance whether listing is affordable.

8. The instance of the problem

For the boards of the problem the two searches give $D=32$, an even length as Section 4 requires. The shortest-path graph has only $33$ boards, one in each layer, joined by $32$ useful moves, and $N(T)=1$: the minimum is reached by a single move sequence, so the requested sum consists of one checksum, which the residue $C(T)$ would also give exactly. The statement does not reveal this, and the search does not assume it: it follows every shortest sequence, whatever their number.

How the Code Works

The C++ program ^[8] writes the boards row by row as strings, with W for the empty square, R for red and B for blue: kStartBoard is WRBBRRBBRRBBRRBB, kTargetBoard is WBRBBRBRRBRBBRBR, and kExampleAfterLULUR holds $E$. encode_board packs a board into a 32-bit State with two bits per cell, which hold the digits of the matrices above. generate_moves finds the empty cell and fills an array with at most four pairs of a new state and an ASCII code, in the order $\mathtt L$, $\mathtt R$, $\mathtt U$, $\mathtt D$, under the conditions of Section 2. update_checksum performs one step of the recurrence with a 64-bit product.

build_reachable_space is the search of Section 3 from $S$: the hash map id_of numbers the boards in the order of discovery, dist_from_start keeps their distances, and a vector with a read position serves as the queue. build_adjacency stores for every board its neighbours with their letter codes, and bfs_dist repeats the search from $T$ on these lists. is_shortest_dag_edge tests the two conditions of Section 5, and the recursive dfs_enumerate follows only useful moves, carrying the board, the depth and the checksum; at depth $D$ it counts the sequence and adds its checksum to a sum of type unsigned __int128 if the board is $T$, which Section 5 guarantees. build_prefix_tasks and solve_shortest_checksum_sum can split the search into independent pieces, one per useful prefix of a common length, and add up their results; here the only prefix is the start, because every layer holds one board.

Before the main computation, validate checks the tile counts of both boards, the checksum $19761398$ of $\mathtt{LULUR}$, that these moves turn $S$ into $E$ and that a shortest sequence exists; it can also compare count and sum with a second run that asks for more prefixes, which here repeats the same search. main then builds the data again and prints the sum. The Python and Java versions have no such checks. They run the same two searches, Python level by level in build_solver_data and Java with list queues in solve, generate the moves again for the search from $T$ instead of reading stored lists, and replace the recursion by an explicit stack. Python integers are unbounded. Java keeps a board in a signed int whose sign bit belongs to the last cell, which the mask & 3 after the shift handles correctly, and its checksums and sum are long values, ample because the sum is less than $p\cdot N(T)=p$.

Complexity and Verification

Each breadth-first search handles each of the $102960$ boards once and looks at its at most four moves, so its time is proportional to the number of boards plus the $154440$ edges, with an expected constant number of hash-map operations per move. ^[3] Memory is proportional to the number of boards as well; on a desktop computer the C++ program peaks at about 12 MB, and each of the three programs finishes in less than a second. The listing handles every prefix of a shortest sequence once, the empty prefix included, and tries at most four moves for each; there are $\sum_v N(v)$ such prefixes, $11$ for the target $E$ of Section 6 and $33$ for $T$. In general their number can grow exponentially with $D$; here the two searches dominate.

The checks of validate pass, and all three programs print the same value. An independent Python program written for this article, with boards stored as strings of letters, recomputed every number above, from the $102960$ boards to $N(T)=1$; its listing search meets no dead end, its sequence replays from $S$ to $T$, and its sum agrees with the output of the three programs. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The useful moves, the worked example and the counts for the instance of the problem are derived in this article.

Project Euler 244 — Sliders. The official statement shows the start, example and target configurations of a Fifteen Puzzle with seven red and eight blue tiles, names moves by the direction of the sliding tile, defines the checksum with factor 243 and modulus 100 000 007, gives the checksum 19761398 of LULUR, and asks for the sum of the checksums of all shortest paths from the start to the target.
Wikipedia — 15 puzzle. The parity of the permutation of all 16 squares plus the parity of the taxicab distance of the empty square from the lower right corner is invariant. Johnson and Story (1879) used this argument to show that half of the starting positions are unsolvable, and also showed that all even permutations are solvable, so there are exactly two classes of mutually accessible arrangements.
Wikipedia — Breadth-first search. The search explores all nodes at the present depth before those at the next depth level, using a first-in-first-out queue; it finds shortest paths measured by the number of edges, in time O(|V| + |E|).
Wikipedia — Directed acyclic graph. A directed graph without directed cycles has a topological ordering, and processing its vertices in that order computes the value of each vertex from its incoming edges, as N(v) and C(v) are computed in Section 7.
Wikipedia — Parity of a permutation. All decompositions of a permutation into transpositions have the same parity, and the sign is a group homomorphism, so composing with one more transposition changes the parity.
Wikipedia — Horner's method. The nested rule bₙ = aₙ, bᵢ = aᵢ + bᵢ₊₁x evaluates a₀ + a₁x + … + aₙxⁿ with n multiplications and n additions; the checksum recurrence is this rule with x = 243.
Wikipedia — Rolling hash. The polynomial rolling hash of the characters c₁, …, cₖ is c₁aᵏ⁻¹ + c₂aᵏ⁻² + … + cₖa⁰ for a constant a, with all arithmetic modulo n; the checksum is this hash of the move codes with a = 243 and n = 100 000 007.
C++ — Euler244.cpp. The linked immutable C++ revision contains build_reachable_space, bfs_dist, is_shortest_dag_edge, dfs_enumerate and validate. It is the implementation record for this article.

Problem 244 source code

C++

#include <algorithm>
#include <array>
#include <atomic>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <string>
#include <thread>
#include <unordered_map>
#include <vector>

namespace {

constexpr std::uint32_t kMod = 100'000'007U;
constexpr int kCells = 16;
constexpr std::uint8_t kAsciiL = 76;
constexpr std::uint8_t kAsciiR = 82;
constexpr std::uint8_t kAsciiU = 85;
constexpr std::uint8_t kAsciiD = 68;

constexpr const char* kStartBoard = "WRBBRRBBRRBBRRBB";
constexpr const char* kTargetBoard = "WBRBBRBRRBRBBRBR";
constexpr const char* kExampleAfterLULUR = "RRBBRBBBRWRBRRBB";

using State = std::uint32_t;

struct Move {
    State next_state = 0;
    std::uint8_t ascii = 0;
};

struct Edge {
    int to = -1;
    std::uint8_t ascii = 0;
};

struct AdjList {
    std::array<Edge, 4> edges{};
    int degree = 0;
};

struct SearchSpace {
    std::vector<State> states;
    std::unordered_map<State, int> id_of;
    std::vector<int> dist_from_start;
};

struct SolverData {
    int start_id = -1;
    int target_id = -1;
    int shortest_len = -1;
    std::vector<int> dist_from_start;
    std::vector<int> dist_to_target;
    std::vector<AdjList> adjacency;
};

struct SolveResult {
    std::uint64_t path_count = 0;
    unsigned __int128 checksum_sum = 0;
};

inline int get_cell(State s, int idx) {
    return static_cast<int>((s >> (2 * idx)) & 3U);
}

inline State set_cell(State s, int idx, int value) {
    const State mask = 3U << (2 * idx);
    s &= ~mask;
    s |= (static_cast<State>(value) << (2 * idx));
    return s;
}

State encode_board(const std::string& board) {
    if (board.size() != kCells) return 0;
    State s = 0;
    for (int i = 0; i < kCells; ++i) {
        int value = 0;
        if (board[static_cast<std::size_t>(i)] == 'R') {
            value = 1;
        } else if (board[static_cast<std::size_t>(i)] == 'B') {
            value = 2;
        }
        s = set_cell(s, i, value);
    }
    return s;
}

bool has_expected_tile_counts(State s) {
    int blank = 0;
    int red = 0;
    int blue = 0;
    for (int i = 0; i < kCells; ++i) {
        const int cell = get_cell(s, i);
        if (cell == 0) {
            ++blank;
        } else if (cell == 1) {
            ++red;
        } else if (cell == 2) {
            ++blue;
        } else {
            return false;
        }
    }
    return blank == 1 && red == 7 && blue == 8;
}

int find_blank(State s) {
    for (int i = 0; i < kCells; ++i) {
        if (get_cell(s, i) == 0) return i;
    }
    return -1;
}

Move make_move(State s, int blank_pos, int other_pos, std::uint8_t ascii) {
    Move mv;
    mv.ascii = ascii;
    const int tile = get_cell(s, other_pos);
    s = set_cell(s, blank_pos, tile);
    s = set_cell(s, other_pos, 0);
    mv.next_state = s;
    return mv;
}

int generate_moves(State s, std::array<Move, 4>& out) {
    const int blank = find_blank(s);
    const int r = blank / 4;
    const int c = blank % 4;
    int count = 0;

    // Tile moves left => blank moves right.
    if (c < 3) out[static_cast<std::size_t>(count++)] = make_move(s, blank, blank + 1, kAsciiL);
    // Tile moves right => blank moves left.
    if (c > 0) out[static_cast<std::size_t>(count++)] = make_move(s, blank, blank - 1, kAsciiR);
    // Tile moves up => blank moves down.
    if (r < 3) out[static_cast<std::size_t>(count++)] = make_move(s, blank, blank + 4, kAsciiU);
    // Tile moves down => blank moves up.
    if (r > 0) out[static_cast<std::size_t>(count++)] = make_move(s, blank, blank - 4, kAsciiD);

    return count;
}

std::uint32_t update_checksum(std::uint32_t checksum, std::uint8_t ascii) {
    return static_cast<std::uint32_t>((static_cast<std::uint64_t>(checksum) * 243ULL + ascii) % kMod);
}

std::uint32_t checksum_for_sequence(const std::string& sequence) {
    std::uint32_t checksum = 0;
    for (char ch : sequence) {
        std::uint8_t ascii = 0;
        if (ch == 'L') ascii = kAsciiL;
        if (ch == 'R') ascii = kAsciiR;
        if (ch == 'U') ascii = kAsciiU;
        if (ch == 'D') ascii = kAsciiD;
        checksum = update_checksum(checksum, ascii);
    }
    return checksum;
}

State apply_sequence(State start, const std::string& sequence) {
    State s = start;
    for (char ch : sequence) {
        const int blank = find_blank(s);
        const int r = blank / 4;
        const int c = blank % 4;
        int other = -1;

        if (ch == 'L' && c < 3) other = blank + 1;
        if (ch == 'R' && c > 0) other = blank - 1;
        if (ch == 'U' && r < 3) other = blank + 4;
        if (ch == 'D' && r > 0) other = blank - 4;

        if (other < 0) return 0;
        const int tile = get_cell(s, other);
        s = set_cell(s, blank, tile);
        s = set_cell(s, other, 0);
    }
    return s;
}

SearchSpace build_reachable_space(State start_state) {
    SearchSpace out;
    out.states.reserve(110'000);
    out.id_of.reserve(140'000);
    out.dist_from_start.reserve(110'000);

    out.id_of.emplace(start_state, 0);
    out.states.push_back(start_state);
    out.dist_from_start.push_back(0);

    std::vector<int> queue;
    queue.reserve(110'000);
    queue.push_back(0);

    std::array<Move, 4> moves{};
    for (std::size_t qpos = 0; qpos < queue.size(); ++qpos) {
        const int v = queue[qpos];
        const State s = out.states[static_cast<std::size_t>(v)];
        const int degree = generate_moves(s, moves);

        for (int i = 0; i < degree; ++i) {
            const State ns = moves[static_cast<std::size_t>(i)].next_state;
            auto it_insert = out.id_of.emplace(ns, static_cast<int>(out.states.size()));
            if (it_insert.second) {
                out.states.push_back(ns);
                out.dist_from_start.push_back(-1);
            }

            const int nid = it_insert.first->second;
            if (out.dist_from_start[static_cast<std::size_t>(nid)] == -1) {
                out.dist_from_start[static_cast<std::size_t>(nid)] =
                    out.dist_from_start[static_cast<std::size_t>(v)] + 1;
                queue.push_back(nid);
            }
        }
    }

    return out;
}

std::vector<AdjList> build_adjacency(const std::vector<State>& states,
                                     const std::unordered_map<State, int>& id_of) {
    std::vector<AdjList> adjacency(states.size());
    std::array<Move, 4> moves{};

    for (std::size_t i = 0; i < states.size(); ++i) {
        const int degree = generate_moves(states[i], moves);
        AdjList& row = adjacency[i];
        row.degree = degree;
        for (int j = 0; j < degree; ++j) {
            const Move mv = moves[static_cast<std::size_t>(j)];
            auto it = id_of.find(mv.next_state);
            row.edges[static_cast<std::size_t>(j)] = {it->second, mv.ascii};
        }
    }

    return adjacency;
}

std::vector<int> bfs_dist(const std::vector<AdjList>& adjacency, int source_id) {
    std::vector<int> dist(adjacency.size(), -1);
    dist[static_cast<std::size_t>(source_id)] = 0;

    std::vector<int> queue;
    queue.reserve(adjacency.size());
    queue.push_back(source_id);

    for (std::size_t qpos = 0; qpos < queue.size(); ++qpos) {
        const int v = queue[qpos];
        const AdjList& row = adjacency[static_cast<std::size_t>(v)];
        const int nd = dist[static_cast<std::size_t>(v)] + 1;

        for (int i = 0; i < row.degree; ++i) {
            const int to = row.edges[static_cast<std::size_t>(i)].to;
            if (dist[static_cast<std::size_t>(to)] == -1) {
                dist[static_cast<std::size_t>(to)] = nd;
                queue.push_back(to);
            }
        }
    }

    return dist;
}

SolverData build_solver_data(State start_state, State target_state) {
    SolverData data;
    SearchSpace space = build_reachable_space(start_state);

    data.start_id = 0;
    auto it_target = space.id_of.find(target_state);
    if (it_target == space.id_of.end()) return data;
    data.target_id = it_target->second;
    data.dist_from_start = std::move(space.dist_from_start);
    data.adjacency = build_adjacency(space.states, space.id_of);
    data.dist_to_target = bfs_dist(data.adjacency, data.target_id);
    data.shortest_len = data.dist_from_start[static_cast<std::size_t>(data.target_id)];
    return data;
}

inline bool is_shortest_dag_edge(const SolverData& data, int from, int to) {
    const int d_to = data.dist_from_start[static_cast<std::size_t>(to)];
    return d_to == data.dist_from_start[static_cast<std::size_t>(from)] + 1 &&
           data.dist_to_target[static_cast<std::size_t>(to)] == data.shortest_len - d_to;
}

void dfs_enumerate(const SolverData& data,
                   int node,
                   int depth,
                   std::uint32_t checksum,
                   std::uint64_t& path_count,
                   unsigned __int128& checksum_sum) {
    if (depth == data.shortest_len) {
        if (node == data.target_id) {
            ++path_count;
            checksum_sum += checksum;
        }
        return;
    }

    const AdjList& row = data.adjacency[static_cast<std::size_t>(node)];
    for (int i = 0; i < row.degree; ++i) {
        const Edge& edge = row.edges[static_cast<std::size_t>(i)];
        const int to = edge.to;
        if (!is_shortest_dag_edge(data, node, to)) continue;
        dfs_enumerate(data,
                      to,
                      depth + 1,
                      update_checksum(checksum, edge.ascii),
                      path_count,
                      checksum_sum);
    }
}

struct PrefixTask {
    int node = -1;
    int depth = 0;
    std::uint32_t checksum = 0;
};

std::vector<PrefixTask> build_prefix_tasks(const SolverData& data, std::size_t desired_tasks) {
    std::vector<PrefixTask> tasks(1, PrefixTask{data.start_id, 0, 0});
    if (desired_tasks <= 1 || data.shortest_len <= 0) return tasks;

    while (tasks.size() < desired_tasks) {
        std::vector<PrefixTask> next;
        next.reserve(tasks.size() * 2);

        for (const PrefixTask& t : tasks) {
            if (t.depth >= data.shortest_len) {
                next.push_back(t);
                continue;
            }

            const AdjList& row = data.adjacency[static_cast<std::size_t>(t.node)];
            for (int i = 0; i < row.degree; ++i) {
                const Edge& edge = row.edges[static_cast<std::size_t>(i)];
                const int to = edge.to;
                if (!is_shortest_dag_edge(data, t.node, to)) continue;
                next.push_back(PrefixTask{
                    to,
                    t.depth + 1,
                    update_checksum(t.checksum, edge.ascii),
                });
            }
        }

        if (next.empty() || next.size() == tasks.size()) break;
        tasks.swap(next);
    }

    return tasks;
}

SolveResult solve_shortest_checksum_sum(const SolverData& data, int threads) {
    SolveResult out;
    if (data.start_id < 0 || data.target_id < 0 || data.shortest_len < 0) return out;

    if (threads < 1) threads = 1;
    const std::size_t target_task_count = static_cast<std::size_t>(threads) * 64U;
    const std::vector<PrefixTask> tasks = build_prefix_tasks(data, target_task_count);

    if (threads == 1 || tasks.size() <= 1) {
        for (const PrefixTask& t : tasks) {
            dfs_enumerate(data, t.node, t.depth, t.checksum, out.path_count, out.checksum_sum);
        }
        return out;
    }

    std::atomic<std::size_t> next_task{0};
    std::vector<std::uint64_t> local_counts(static_cast<std::size_t>(threads), 0);
    std::vector<unsigned __int128> local_sums(static_cast<std::size_t>(threads), 0);
    std::vector<std::thread> pool;
    pool.reserve(static_cast<std::size_t>(threads));

    for (int tid = 0; tid < threads; ++tid) {
        pool.emplace_back([&, tid]() {
            std::uint64_t count = 0;
            unsigned __int128 sum = 0;

            while (true) {
                const std::size_t idx = next_task.fetch_add(1, std::memory_order_relaxed);
                if (idx >= tasks.size()) break;
                const PrefixTask& task = tasks[idx];
                dfs_enumerate(data, task.node, task.depth, task.checksum, count, sum);
            }

            local_counts[static_cast<std::size_t>(tid)] = count;
            local_sums[static_cast<std::size_t>(tid)] = sum;
        });
    }

    for (std::thread& th : pool) th.join();
    for (int tid = 0; tid < threads; ++tid) {
        out.path_count += local_counts[static_cast<std::size_t>(tid)];
        out.checksum_sum += local_sums[static_cast<std::size_t>(tid)];
    }

    return out;
}

std::string to_string_u128(unsigned __int128 value) {
    if (value == 0) return "0";
    std::string out;
    while (value > 0) {
        const unsigned digit = static_cast<unsigned>(value % 10);
        out.push_back(static_cast<char>('0' + digit));
        value /= 10;
    }
    std::reverse(out.begin(), out.end());
    return out;
}

bool validate() {
    const State start_state = encode_board(kStartBoard);
    const State target_state = encode_board(kTargetBoard);
    const State example_state = encode_board(kExampleAfterLULUR);

    if (!has_expected_tile_counts(start_state) || !has_expected_tile_counts(target_state)) {
        std::cerr << "Validation failed: tile counts are invalid.\n";
        return false;
    }

    const std::uint32_t checksum_sample = checksum_for_sequence("LULUR");
    if (checksum_sample != 19'761'398U) {
        std::cerr << "Validation failed: checksum(LULUR) expected 19761398, got "
                  << checksum_sample << "\n";
        return false;
    }

    const State moved = apply_sequence(start_state, "LULUR");
    if (moved != example_state) {
        std::cerr << "Validation failed: LULUR did not reach the official example state.\n";
        return false;
    }

    const SolverData data = build_solver_data(start_state, target_state);
    if (data.shortest_len <= 0) {
        std::cerr << "Validation failed: target is not reachable from start.\n";
        return false;
    }

    const SolveResult single = solve_shortest_checksum_sum(data, 1);
    if (single.path_count == 0) {
        std::cerr << "Validation failed: no shortest path found.\n";
        return false;
    }

    unsigned hw = std::thread::hardware_concurrency();
    if (hw == 0) hw = 2;
    const int threads = static_cast<int>(std::min<unsigned>(hw, 8));
    if (threads > 1) {
        const SolveResult parallel = solve_shortest_checksum_sum(data, threads);
        if (parallel.path_count != single.path_count || parallel.checksum_sum != single.checksum_sum) {
            std::cerr << "Validation failed: single-thread and multi-thread results differ.\n";
            return false;
        }
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    if (!validate()) return 1;

    int threads = 0;
    if (argc > 1) {
        threads = std::max(1, std::atoi(argv[1]));
    } else {
        unsigned hw = std::thread::hardware_concurrency();
        if (hw == 0) hw = 2;
        threads = static_cast<int>(std::min<unsigned>(hw, 8));
    }

    const State start_state = encode_board(kStartBoard);
    const State target_state = encode_board(kTargetBoard);
    const SolverData data = build_solver_data(start_state, target_state);
    const SolveResult result = solve_shortest_checksum_sum(data, threads);
    std::cout << to_string_u128(result.checksum_sum) << '\n';
    return 0;
}

Python

from collections import deque

MOD = 100000007
ASCII_L = 76
ASCII_R = 82
ASCII_U = 85
ASCII_D = 68

START_BOARD = "WRBBRRBBRRBBRRBB"
TARGET_BOARD = "WBRBBRBRRBRBBRBR"

def encode_board(board):
    if len(board) != 16:
        return 0
    s = 0
    for i, char in enumerate(board):
        val = 0
        if char == 'R': val = 1
        elif char == 'B': val = 2
        s |= (val << (2 * i))
    return s

def get_cell(s, idx):
    return (s >> (2 * idx)) & 3

def set_cell(s, idx, val):
    mask = 3 << (2 * idx)
    s &= ~mask
    s |= (val << (2 * idx))
    return s

def find_blank(s):
    for i in range(16):
        if get_cell(s, i) == 0:
            return i
    return -1

def generate_moves(s):
    blank = find_blank(s)
    r = blank // 4
    c = blank % 4
    moves = []
    
    # L: tile moves left => blank moves right
    if c < 3:
        n_blank = blank + 1
        tile = get_cell(s, n_blank)
        ns = set_cell(s, blank, tile)
        ns = set_cell(ns, n_blank, 0)
        moves.append((ns, ASCII_L))
        
    # R: tile moves right => blank moves left
    if c > 0:
        n_blank = blank - 1
        tile = get_cell(s, n_blank)
        ns = set_cell(s, blank, tile)
        ns = set_cell(ns, n_blank, 0)
        moves.append((ns, ASCII_R))
        
    # U: tile moves up => blank moves down
    if r < 3:
        n_blank = blank + 4
        tile = get_cell(s, n_blank)
        ns = set_cell(s, blank, tile)
        ns = set_cell(ns, n_blank, 0)
        moves.append((ns, ASCII_U))
        
    # D: tile moves down => blank moves up
    if r > 0:
        n_blank = blank - 4
        tile = get_cell(s, n_blank)
        ns = set_cell(s, blank, tile)
        ns = set_cell(ns, n_blank, 0)
        moves.append((ns, ASCII_D))
        
    return moves

def build_solver_data(start_state, target_state):
    states = [start_state]
    id_of = {start_state: 0}
    dist_from_start = [0]
    
    queue = [0]
    while queue:
        curr_queue = []
        for v in queue:
            s = states[v]
            for ns, ascii_code in generate_moves(s):
                if ns not in id_of:
                    nid = len(states)
                    id_of[ns] = nid
                    states.append(ns)
                    dist_from_start.append(dist_from_start[v] + 1)
                    curr_queue.append(nid)
        queue = curr_queue
                    
    target_id = id_of.get(target_state, -1)
    if target_id == -1:
        return None
        
    adjacency = [[] for _ in range(len(states))]
    for i, s in enumerate(states):
        for ns, ascii_code in generate_moves(s):
            adjacency[i].append((id_of[ns], ascii_code))
            
    dist_to_target = [-1] * len(states)
    dist_to_target[target_id] = 0
    
    queue = [target_id]
    while queue:
        curr_queue = []
        for v in queue:
            nd = dist_to_target[v] + 1
            # Inverse adjacency is same structure, but we can do a backwards BFS using standard transitions from all nodes?
            # Actually, standard transitions are reversible. Tile moves L means it can move R to go back.
            s = states[v]
            for ns, _ in generate_moves(s):
                to = id_of[ns]
                if dist_to_target[to] == -1:
                    dist_to_target[to] = nd
                    curr_queue.append(to)
        queue = curr_queue
                    
    return adjacency, dist_from_start, dist_to_target, target_id, dist_from_start[target_id]

def solve():
    start_state = encode_board(START_BOARD)
    target_state = encode_board(TARGET_BOARD)
    
    data = build_solver_data(start_state, target_state)
    if not data: return "0"
    
    adjacency, dist_from_start, dist_to_target, target_id, shortest_len = data
    
    checksum_sum = 0
    path_count = 0
    
    # Simple DFS iteration
    stack = [(0, 0, 0)] # node, depth, checksum
    
    while stack:
        node, depth, checksum = stack.pop()
        
        if depth == shortest_len:
            if node == target_id:
                path_count += 1
                checksum_sum += checksum
            continue
            
        for to, ascii_code in adjacency[node]:
            if dist_from_start[to] == depth + 1 and dist_to_target[to] == shortest_len - dist_from_start[to]:
                ncs = (checksum * 243 + ascii_code) % MOD
                stack.append((to, depth + 1, ncs))
                
    return str(checksum_sum)

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;

public class Euler244 {
    static final int MOD = 100000007;

    static final int ASCII_L = 76;
    static final int ASCII_R = 82;
    static final int ASCII_U = 85;
    static final int ASCII_D = 68;

    static final String START_BOARD = "WRBBRRBBRRBBRRBB";
    static final String TARGET_BOARD = "WBRBBRBRRBRBBRBR";

    static int getCell(int s, int idx) {
        return (s >> (2 * idx)) & 3;
    }

    static int setCell(int s, int idx, int val) {
        int mask = 3 << (2 * idx);
        s &= ~mask;
        s |= (val << (2 * idx));
        return s;
    }

    static int encodeBoard(String board) {
        if (board.length() != 16)
            return 0;
        int s = 0;
        for (int i = 0; i < 16; ++i) {
            int val = 0;
            if (board.charAt(i) == 'R')
                val = 1;
            else if (board.charAt(i) == 'B')
                val = 2;
            s = setCell(s, i, val);
        }
        return s;
    }

    static int findBlank(int s) {
        for (int i = 0; i < 16; ++i) {
            if (getCell(s, i) == 0)
                return i;
        }
        return -1;
    }

    static class Move {
        int nextState;
        int ascii;

        Move(int n, int a) {
            nextState = n;
            ascii = a;
        }
    }

    static List<Move> generateMoves(int s) {
        int blank = findBlank(s);
        int r = blank / 4;
        int c = blank % 4;
        List<Move> moves = new ArrayList<>();

        if (c < 3) {
            int nBlank = blank + 1;
            int tile = getCell(s, nBlank);
            int ns = setCell(s, blank, tile);
            ns = setCell(ns, nBlank, 0);
            moves.add(new Move(ns, ASCII_L));
        }
        if (c > 0) {
            int nBlank = blank - 1;
            int tile = getCell(s, nBlank);
            int ns = setCell(s, blank, tile);
            ns = setCell(ns, nBlank, 0);
            moves.add(new Move(ns, ASCII_R));
        }
        if (r < 3) {
            int nBlank = blank + 4;
            int tile = getCell(s, nBlank);
            int ns = setCell(s, blank, tile);
            ns = setCell(ns, nBlank, 0);
            moves.add(new Move(ns, ASCII_U));
        }
        if (r > 0) {
            int nBlank = blank - 4;
            int tile = getCell(s, nBlank);
            int ns = setCell(s, blank, tile);
            ns = setCell(ns, nBlank, 0);
            moves.add(new Move(ns, ASCII_D));
        }
        return moves;
    }

    public static String solve() {
        int startState = encodeBoard(START_BOARD);
        int targetState = encodeBoard(TARGET_BOARD);

        List<Integer> states = new ArrayList<>();
        Map<Integer, Integer> idOf = new HashMap<>();
        List<Integer> distFromStart = new ArrayList<>();

        states.add(startState);
        idOf.put(startState, 0);
        distFromStart.add(0);

        List<Integer> queue = new ArrayList<>();
        queue.add(0);

        int head = 0;
        while (head < queue.size()) {
            int v = queue.get(head++);
            int s = states.get(v);
            for (Move m : generateMoves(s)) {
                int ns = m.nextState;
                if (!idOf.containsKey(ns)) {
                    int nid = states.size();
                    idOf.put(ns, nid);
                    states.add(ns);
                    distFromStart.add(distFromStart.get(v) + 1);
                    queue.add(nid);
                }
            }
        }

        if (!idOf.containsKey(targetState))
            return "0";
        int targetId = idOf.get(targetState);
        int shortestLen = distFromStart.get(targetId);

        List<List<Move>> adjacency = new ArrayList<>(states.size());
        for (int i = 0; i < states.size(); ++i) {
            List<Move> edges = new ArrayList<>();
            for (Move m : generateMoves(states.get(i))) {
                edges.add(new Move(idOf.get(m.nextState), m.ascii));
            }
            adjacency.add(edges);
        }

        int[] distToTarget = new int[states.size()];
        Arrays.fill(distToTarget, -1);
        distToTarget[targetId] = 0;

        List<Integer> qRev = new ArrayList<>();
        qRev.add(targetId);
        int headRev = 0;
        while (headRev < qRev.size()) {
            int v = qRev.get(headRev++);
            int nd = distToTarget[v] + 1;
            int s = states.get(v);
            for (Move m : generateMoves(s)) {
                int to = idOf.get(m.nextState);
                if (distToTarget[to] == -1) {
                    distToTarget[to] = nd;
                    qRev.add(to);
                }
            }
        }

        class DFSState {
            int node, depth;
            long checksum;

            DFSState(int n, int d, long c) {
                node = n;
                depth = d;
                checksum = c;
            }
        }

        Stack<DFSState> stack = new Stack<>();
        stack.push(new DFSState(0, 0, 0L));

        long checksumSum = 0;

        while (!stack.isEmpty()) {
            DFSState curr = stack.pop();

            if (curr.depth == shortestLen) {
                if (curr.node == targetId) {
                    checksumSum += curr.checksum;
                }
                continue;
            }

            for (Move m : adjacency.get(curr.node)) {
                int to = m.nextState;
                if (distFromStart.get(to) == curr.depth + 1
                        && distToTarget[to] == shortestLen - distFromStart.get(to)) {
                    long ncs = (curr.checksum * 243 + m.ascii) % MOD;
                    stack.push(new DFSState(to, curr.depth + 1, ncs));
                }
            }
        }

        return String.valueOf(checksumSum);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}