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

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. Because the blue squares are indistinguishable from each other and the red squares are indistinguishable from each other, a state is determined completely by the position of the white square together with the set of positions occupied by the seven red squares; the eight blue squares fill the remaining cells automatically. So there are at most

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

different colorings to worry about, which makes a full graph search feasible.

Connect two states by an edge when one legal slide transforms one board into the other. This produces a finite unweighted graph $G$. Every legal move is reversible, so if $v$ is adjacent to $w$, then $w$ is also adjacent to $v$. That reversibility is what makes two breadth-first searches enough to describe every shortest path.

Distances Pick Out Exactly the Shortest States

Let $s$ be the start state and $t$ the target state. Write $d_s(v)$ for the graph distance from $s$ to a state $v$, and $d_t(v)$ for the graph distance from $v$ to $t$. If

$$D=d_s(t),$$

then $D$ is the minimum number of moves required by the problem.

A state $v$ lies on at least one shortest path from $s$ to $t$ exactly when

$$d_s(v)+d_t(v)=D.$$

The proof is standard and important. If $v$ lies on a shortest path, then the path splits into a shortest prefix from $s$ to $v$ and a shortest suffix from $v$ to $t$, so the two distances add to $D$. Conversely, if the two distances add to $D$, concatenating a shortest $s\to v$ path with a shortest $v\to t$ path gives a shortest $s\to t$ path passing through $v$.

Now orient an edge $v\to w$ only when it advances one BFS layer from the start and still stays on a shortest route:

$$d_s(w)=d_s(v)+1,\qquad d_t(w)=D-d_s(w).$$

These are exactly the directed edges that can appear in a shortest solution. Since $d_s$ strictly increases along every retained edge, the retained subgraph is a directed acyclic graph.

The Checksum Is a Linear Recurrence

Let $\chi(L)=76$, $\chi(R)=82$, $\chi(U)=85$, and $\chi(D)=68$. For a shortest path with move string $m_1m_2\cdots m_\ell$, the checksum recurrence can be unrolled as

$$\operatorname{chk}(m_1\cdots m_\ell)\equiv \sum_{i=1}^{\ell}\chi(m_i)\,243^{\ell-i}\pmod{100000007}.$$

So the checksum is a polynomial hash of the move letters in base $243$. The implementations update it one step at a time, but mathematically this closed form makes clear why the order of moves matters so strongly.

This linearity also gives a useful path-aggregation recurrence. If $N(v)$ is the number of shortest-path prefixes ending at $v$, and $S(v)$ is the sum of their checksums, then for every shortest-path edge $v\to w$ labeled by letter $a$,

$$N(w)\mathrel{+}=N(v),$$

$$S(w)\mathrel{+}=243\,S(v)+\chi(a)\,N(v)\pmod{100000007}.$$

The current implementations do not materialize these two tables explicitly; instead they carry the running checksum during a depth-first traversal of the shortest-path DAG. But this recurrence is the mathematical reason that the traversal is correct.

Worked Example: The Sample Word $LULUR$

The sample move string $LULUR$ is useful because it fixes the direction convention. Starting from the initial board and applying those five moves gives

R R B B
R B B B
R W R B
R R B B

and the checksum recurrence produces

$$\operatorname{chk}(LULUR)=19761398.$$

That example shows two problem-specific facts at once: the letters record tile directions, and the checksum is attached to the exact move string rather than to the destination state alone.

The Final Reduction

If $\mathcal{P}_{\min}$ denotes the set of all shortest paths from $s$ to $t$, then the required quantity is simply

$$\boxed{\sum_{P\in\mathcal{P}_{\min}}\operatorname{chk}(P).}$$

The search problem is therefore reduced to a finite DAG sum: find every shortest path and accumulate its rolling checksum. No longer paths need to be explored, because the distance identities above exclude them completely.

How the Code Works

Board Representation and Neighbor Generation

The C++, Python, and Java implementations encode each of the 16 cells with 2 bits, using one code for white, one for red, and one for blue. That packs the whole board into a 32-bit integer. From any encoded state, the implementation locates the white square, checks the at most four neighboring cells, swaps white with a legal neighbor, and records both the next state and the ASCII code associated with the move letter.

Building the Reachable Component and the Distance Arrays

A first breadth-first search starts from the initial board. It discovers every reachable state, assigns it an integer identifier, and stores its distance from the start. Once those states are known, the implementation builds an adjacency list for the entire reachable component. A second breadth-first search starts from the target and runs on the same reversible graph, producing the distance-to-target array. The shortest solution length is the target's distance from the start.

Traversing Only Shortest Solutions

The final traversal carries three pieces of information: the current state, the current depth, and the checksum of the move prefix used to get there. A transition is followed only if it advances one level from the start and still satisfies the shortest-path condition for the destination. When the traversal reaches depth $D$, it contributes to the total only if the current state is the target. Because every retained edge increases depth by exactly one, the traversal never cycles.

The C++ and Java implementations additionally split the shortest-path DAG by short prefixes and let several workers explore disjoint subtrees before adding their local totals together. The Python implementation performs the same traversal serially.

Complexity Analysis

Let $V$ be the number of reachable board states and $E$ the number of legal transitions among them. Since every board position has degree at most 4, we have $E=O(V)$. The state-discovery BFS, adjacency construction, and reverse BFS therefore take $O(V+E)$ time and $O(V+E)$ memory.

The final shortest-path traversal is output-sensitive. It is linear in the size of the shortest-path DAG plus the number of shortest-path prefixes actually explored. That is exactly the cost paid by the implementations, because they enumerate shortest solutions rather than compressing them into a separate dynamic program. The crucial saving is that the search never touches non-shortest continuations.

Footnotes and References

Project Euler problem page: https://projecteuler.net/problem=244
Breadth-first search: Wikipedia - Breadth-first search
Shortest path problem: Wikipedia - Shortest path problem
15 puzzle and sliding puzzles: Wikipedia - 15 puzzle
Directed acyclic graph: Wikipedia - Directed acyclic graph
ASCII: Wikipedia - ASCII

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());
    }
}