Problem 766: Sliding Block Puzzle
View on Project EulerProject Euler Problem 766 Solution
EulerSolve provides an optimized solution for Project Euler Problem 766, Sliding Block Puzzle, with C++, Python, Java, and a step-by-step mathematical explanation.
Problem Summary This problem asks for the number of distinct positions reachable in a fixed sliding block puzzle. The board has size \(5\times 6\), so it contains \(30\) cells. The given starting arrangement uses two red L-trominoes, two green L-trominoes of the mirrored orientation, two vertical dominoes, six single squares, one \(2\times 2\) square, and one horizontal domino. Altogether these pieces occupy \(28\) cells, so exactly two cells are empty in every legal position. A legal move chooses one piece and slides it horizontally or vertically by a positive number of cells. The piece may not rotate, leave the board, or overlap another piece. The task is to count every position reachable from the initial one, not just the positions at minimum distance. The state space is large, but it is still finite, so the problem can be solved by building the reachable part of the state graph exactly. Mathematical Approach Let \(\mathcal{S}\) be the set of all legal board positions for this puzzle, and let \(s_0\in\mathcal{S}\) be the given start. If one legal slide transforms \(s\) into \(t\), we place a directed edge \(s\to t\). The required quantity is therefore $$A=\left|\operatorname{Reach}(s_0)\right|,$$ where \(\operatorname{Reach}(s_0)\) is the set of states reachable from \(s_0\) by zero or more legal moves....
Detailed mathematical approach
Problem Summary
This problem asks for the number of distinct positions reachable in a fixed sliding block puzzle. The board has size \(5\times 6\), so it contains \(30\) cells. The given starting arrangement uses two red L-trominoes, two green L-trominoes of the mirrored orientation, two vertical dominoes, six single squares, one \(2\times 2\) square, and one horizontal domino. Altogether these pieces occupy \(28\) cells, so exactly two cells are empty in every legal position.
A legal move chooses one piece and slides it horizontally or vertically by a positive number of cells. The piece may not rotate, leave the board, or overlap another piece. The task is to count every position reachable from the initial one, not just the positions at minimum distance. The state space is large, but it is still finite, so the problem can be solved by building the reachable part of the state graph exactly.
Mathematical Approach
Let \(\mathcal{S}\) be the set of all legal board positions for this puzzle, and let \(s_0\in\mathcal{S}\) be the given start. If one legal slide transforms \(s\) into \(t\), we place a directed edge \(s\to t\). The required quantity is therefore
$$A=\left|\operatorname{Reach}(s_0)\right|,$$
where \(\operatorname{Reach}(s_0)\) is the set of states reachable from \(s_0\) by zero or more legal moves.
Step 1: Model Every Piece by an Anchor and an Occupancy Mask
For each piece family, fix an anchor cell and list the occupied offsets relative to that anchor. If a piece of family \(F\) is placed at anchor \(a=(r,c)\), its occupied cells are
$$M_F(a)=\{(r+\Delta r_j,\ c+\Delta c_j)\}_j.$$
A board position is legal exactly when all chosen masks are pairwise disjoint and remain inside the \(5\times 6\) rectangle. If state \(s\) contains piece anchors \(a_1,\dots,a_m\), its total occupancy set is
$$O(s)=\bigcup_{i=1}^{m} M_i(a_i).$$
Now suppose piece \(i\) moves from anchor \(a_i\) to a new anchor \(a_i'\). That new placement is collision free precisely when
$$M_i(a_i')\cap\left(O(s)\setminus M_i(a_i)\right)=\varnothing.$$
This is the geometric core of the algorithm. In the implementation each occupancy set is stored as a bitmask over the \(30\) board cells, so this condition becomes a single bit-intersection test.
Step 2: Canonicalize Identical Pieces
Several pieces are indistinguishable within their own family: there are two red L-pieces, two green L-pieces, two vertical dominoes, and six single-square pieces. If we assigned labels to those pieces, the same geometric board position would appear many times under harmless permutations. To avoid overcounting, each repeated family is stored as a sorted list of anchors.
That turns each family into a combination rather than an ordered tuple. On the \(5\times 6\) board, the available anchor counts are:
$$20,\ 20,\ 24,\ 30,\ 20,\ 25,$$
corresponding respectively to the two red L-pieces, the two green L-pieces, the two vertical dominoes, the six single squares, the \(2\times 2\) square, and the horizontal domino. Therefore the repeated families contribute the combination counts
$$\binom{20}{2},\qquad \binom{20}{2},\qquad \binom{24}{2},\qquad \binom{30}{6},$$
while the two unique pieces contribute factors \(20\) and \(25\). So a collision-free canonical state fits naturally into a finite mixed-radix key space of size
$$\binom{20}{2}\binom{20}{2}\binom{24}{2}\binom{30}{6}\cdot 20\cdot 25.$$
Most keys do not correspond to legal reachable positions, but this count tells us that a compact exact encoding is possible.
Step 3: Rank Each Sorted Anchor Set with the Combinatorial Number System
If a repeated family uses sorted anchors
$$0\le a_0<a_1<\cdots<a_{k-1},$$
its combination rank is
$$\operatorname{rank}(a_0,\dots,a_{k-1})=\sum_{i=0}^{k-1}\binom{a_i}{i+1}.$$
This is the standard combinadic ranking formula. It assigns a unique integer in the range \(0\) to \(\binom{n}{k}-1\) to every \(k\)-subset of \(\{0,\dots,n-1\}\). Using that rank for each repeated family, and the plain anchor index for each unique piece, we can pack the whole state into one collision-free integer by mixed radix composition.
The important mathematical point is that canonicalization and ranking commute with reachability: two states are considered equal exactly when every family occupies the same anchor set, so the encoding loses no information relevant to the puzzle.
Step 4: Generate the Entire Reachable State Graph
Starting from \(s_0\), we perform a breadth-first traversal of the state graph. When a state is removed from the queue, the algorithm reconstructs its full occupancy mask, then examines every piece and every direction.
For a chosen direction, the piece is advanced one anchor step at a time until either the board boundary is reached or a collision would occur. Every intermediate legal anchor gives a distinct legal slide distance, hence a distinct outgoing edge of the graph. After the moved family is canonicalized again, the resulting state is encoded and inserted into the visited set if it has not been seen before.
Because each canonical state is processed once, the final answer is simply the number of visited keys:
$$A=\left|\mathcal{V}\right|.$$
Worked Example: The Smaller Checkpoint Puzzle
The implementation also contains a smaller \(3\times 4\) checkpoint puzzle with one L-tromino and seven single squares. This board has \(12\) cells, of which \(10\) are occupied, so again there are exactly two empty cells.
For that smaller puzzle the L-piece has \(6\) possible anchors, while the seven single squares form a sorted \(7\)-subset of the \(12\) board cells. Hence the natural state count before legality checks is
$$6\binom{12}{7}=6\cdot 792=4752.$$
A perfect key is obtained by taking the combination rank of the seven single-square anchors and then appending the L-anchor as the final radix-\(6\) digit:
$$K_{\text{sample}}=6\,\operatorname{rank}(S)+\ell.$$
Running the same reachability traversal on that reduced puzzle produces exactly \(208\) states. This checkpoint is useful because it shows the whole method on a board small enough to reason about directly, while using the same canonical encoding and move-generation logic as the full puzzle.
How the Code Works
The C++, Python, and Java implementations all follow the same mathematical model of the state space. They begin by precomputing a small binomial table for combinadic ranking and, for every admissible anchor of every piece family, the occupied-cell mask together with the neighboring anchor reached by moving one step in each of the four directions.
The C++ and Python implementations then perform the actual graph traversal. For each visited state they assemble the global occupancy mask once, remove the moved piece temporarily, and test candidate placements with a constant-time mask intersection. Repeated families are sorted immediately after a move, encoded into a unique integer key, and inserted into the visited structure only if they are new.
The Java implementation uses the same underlying mathematical strategy but delegates the heavy enumeration to the optimized C++ solver and returns the parsed numeric result. So all three language paths agree on the same state definition, the same legal-move rule, and the same exact answer.
Complexity Analysis
Let \(V=\left|\operatorname{Reach}(s_0)\right|\) be the number of reachable states and let \(E\) be the number of legal directed moves between them. The precomputation of masks, neighbor anchors, and small binomial values is \(O(1)\) for this fixed puzzle size. The graph traversal itself processes each discovered state once and examines each legal outgoing move once, so the overall running time is
$$O(V+E).$$
The visited set and queue store at most one record per reachable state, so the memory usage is
$$O(V).$$
Since the board dimensions and the multiset of pieces are fixed, the per-state work is bounded by a puzzle-specific constant. In that sense the actual program behaves essentially linearly in the number of reachable states.
Footnotes and References
- Project Euler problem page: https://projecteuler.net/problem=766
- Sliding puzzle background: Wikipedia - Sliding puzzle
- Breadth-first search: Wikipedia - Breadth-first search
- Combinatorial number system: Wikipedia - Combinatorial number system
- Bitwise operations: Wikipedia - Bitwise operation
Problem 766 source code
C++
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <unordered_set>
#include <utility>
#include <vector>
namespace {
using u32 = std::uint32_t;
using u64 = std::uint64_t;
constexpr int DIRS = 4;
constexpr std::array<int, DIRS> DR = {-1, 1, 0, 0};
constexpr std::array<int, DIRS> DC = {0, 0, -1, 1};
std::array<std::array<u64, 8>, 31> build_binom() {
std::array<std::array<u64, 8>, 31> c{};
for (int n = 0; n <= 30; ++n) {
c[n][0] = 1;
for (int k = 1; k <= 7; ++k) {
c[n][k] = (k > n) ? 0 : c[n - 1][k - 1] + c[n - 1][k];
}
}
return c;
}
const std::array<std::array<u64, 8>, 31> kBinom = build_binom();
template <std::size_t K>
u64 rank_combination(const std::array<std::uint8_t, K>& a) {
u64 rank = 0;
for (std::size_t i = 0; i < K; ++i) {
rank += kBinom[a[i]][i + 1];
}
return rank;
}
struct Shape {
int h = 0;
int w = 0;
int max_r = 0;
int max_c = 0;
int rows = 0;
int cols = 0;
std::vector<u32> masks;
std::vector<std::array<int16_t, DIRS>> next;
int idx_of(int r, int c) const {
return r * cols + c;
}
};
Shape build_shape(const int h, const int w, const std::vector<std::pair<int, int>>& cells) {
Shape s;
s.h = h;
s.w = w;
for (const auto& [r, c] : cells) {
s.max_r = std::max(s.max_r, r);
s.max_c = std::max(s.max_c, c);
}
s.rows = h - s.max_r;
s.cols = w - s.max_c;
const int total = s.rows * s.cols;
s.masks.resize(total);
s.next.resize(total);
for (int ar = 0; ar < s.rows; ++ar) {
for (int ac = 0; ac < s.cols; ++ac) {
const int idx = s.idx_of(ar, ac);
u32 mask = 0;
for (const auto& [dr, dc] : cells) {
const int rr = ar + dr;
const int cc = ac + dc;
mask |= (1u << (rr * w + cc));
}
s.masks[idx] = mask;
for (int d = 0; d < DIRS; ++d) {
const int nr = ar + DR[d];
const int nc = ac + DC[d];
if (nr >= 0 && nr < s.rows && nc >= 0 && nc < s.cols) {
s.next[idx][d] = static_cast<int16_t>(s.idx_of(nr, nc));
} else {
s.next[idx][d] = -1;
}
}
}
}
return s;
}
struct TargetState {
std::array<std::uint8_t, 2> red{};
std::array<std::uint8_t, 2> green{};
std::array<std::uint8_t, 2> yellow{};
std::array<std::uint8_t, 6> pink{};
std::uint8_t blue = 0;
std::uint8_t cyan = 0;
};
void canonicalize(TargetState& s) {
if (s.red[0] > s.red[1]) {
std::swap(s.red[0], s.red[1]);
}
if (s.green[0] > s.green[1]) {
std::swap(s.green[0], s.green[1]);
}
if (s.yellow[0] > s.yellow[1]) {
std::swap(s.yellow[0], s.yellow[1]);
}
std::sort(s.pink.begin(), s.pink.end());
}
u64 encode_target(const TargetState& s) {
constexpr u64 kR = 190; // C(20,2)
constexpr u64 kG = 190; // C(20,2)
constexpr u64 kY = 276; // C(24,2)
constexpr u64 kP = 593775; // C(30,6)
constexpr u64 kB = 20;
constexpr u64 kC = 25;
const u64 rr = rank_combination(s.red);
const u64 gg = rank_combination(s.green);
const u64 yy = rank_combination(s.yellow);
const u64 pp = rank_combination(s.pink);
u64 key = rr;
key = key * kG + gg;
key = key * kY + yy;
key = key * kP + pp;
key = key * kB + s.blue;
key = key * kC + s.cyan;
return key;
}
u64 solve_target() {
constexpr int H = 5;
constexpr int W = 6;
const Shape red_l = build_shape(H, W, {{0, 0}, {0, 1}, {1, 0}});
const Shape green_l = build_shape(H, W, {{0, 1}, {1, 0}, {1, 1}});
const Shape v_domino = build_shape(H, W, {{0, 0}, {1, 0}});
const Shape single = build_shape(H, W, {{0, 0}});
const Shape blue_sq = build_shape(H, W, {{0, 0}, {0, 1}, {1, 0}, {1, 1}});
const Shape h_domino = build_shape(H, W, {{0, 0}, {0, 1}});
TargetState start;
start.red = {static_cast<std::uint8_t>(red_l.idx_of(0, 1)),
static_cast<std::uint8_t>(red_l.idx_of(0, 4))};
start.green = {static_cast<std::uint8_t>(green_l.idx_of(0, 2)),
static_cast<std::uint8_t>(green_l.idx_of(3, 4))};
start.yellow = {static_cast<std::uint8_t>(v_domino.idx_of(1, 5)),
static_cast<std::uint8_t>(v_domino.idx_of(2, 4))};
start.pink = {static_cast<std::uint8_t>(single.idx_of(2, 0)),
static_cast<std::uint8_t>(single.idx_of(2, 1)),
static_cast<std::uint8_t>(single.idx_of(3, 0)),
static_cast<std::uint8_t>(single.idx_of(3, 1)),
static_cast<std::uint8_t>(single.idx_of(4, 0)),
static_cast<std::uint8_t>(single.idx_of(4, 1))};
start.blue = static_cast<std::uint8_t>(blue_sq.idx_of(2, 2));
start.cyan = static_cast<std::uint8_t>(h_domino.idx_of(4, 2));
canonicalize(start);
std::unordered_set<u64> seen;
seen.reserve(3'000'000);
std::vector<TargetState> q;
q.reserve(3'000'000);
seen.insert(encode_target(start));
q.push_back(start);
auto push_state = [&](const TargetState& ns) {
const u64 key = encode_target(ns);
if (seen.insert(key).second) {
q.push_back(ns);
}
};
for (std::size_t head = 0; head < q.size(); ++head) {
const TargetState cur = q[head];
const u32 m_r0 = red_l.masks[cur.red[0]];
const u32 m_r1 = red_l.masks[cur.red[1]];
const u32 m_g0 = green_l.masks[cur.green[0]];
const u32 m_g1 = green_l.masks[cur.green[1]];
const u32 m_y0 = v_domino.masks[cur.yellow[0]];
const u32 m_y1 = v_domino.masks[cur.yellow[1]];
const std::array<u32, 6> m_p = {
single.masks[cur.pink[0]],
single.masks[cur.pink[1]],
single.masks[cur.pink[2]],
single.masks[cur.pink[3]],
single.masks[cur.pink[4]],
single.masks[cur.pink[5]],
};
const u32 m_b = blue_sq.masks[cur.blue];
const u32 m_c = h_domino.masks[cur.cyan];
u32 occ = 0;
occ |= m_r0;
occ |= m_r1;
occ |= m_g0;
occ |= m_g1;
occ |= m_y0;
occ |= m_y1;
for (u32 m : m_p) {
occ |= m;
}
occ |= m_b;
occ |= m_c;
for (int i = 0; i < 2; ++i) {
const std::uint8_t base = cur.red[i];
const u32 own = (i == 0) ? m_r0 : m_r1;
const u32 occ_wo = occ ^ own;
for (int d = 0; d < DIRS; ++d) {
int cur_idx = base;
while (true) {
const int next_idx = red_l.next[cur_idx][d];
if (next_idx < 0) {
break;
}
const u32 nm = red_l.masks[next_idx];
if ((nm & occ_wo) != 0) {
break;
}
TargetState ns = cur;
ns.red[i] = static_cast<std::uint8_t>(next_idx);
if (ns.red[0] > ns.red[1]) {
std::swap(ns.red[0], ns.red[1]);
}
push_state(ns);
cur_idx = next_idx;
}
}
}
for (int i = 0; i < 2; ++i) {
const std::uint8_t base = cur.green[i];
const u32 own = (i == 0) ? m_g0 : m_g1;
const u32 occ_wo = occ ^ own;
for (int d = 0; d < DIRS; ++d) {
int cur_idx = base;
while (true) {
const int next_idx = green_l.next[cur_idx][d];
if (next_idx < 0) {
break;
}
const u32 nm = green_l.masks[next_idx];
if ((nm & occ_wo) != 0) {
break;
}
TargetState ns = cur;
ns.green[i] = static_cast<std::uint8_t>(next_idx);
if (ns.green[0] > ns.green[1]) {
std::swap(ns.green[0], ns.green[1]);
}
push_state(ns);
cur_idx = next_idx;
}
}
}
for (int i = 0; i < 2; ++i) {
const std::uint8_t base = cur.yellow[i];
const u32 own = (i == 0) ? m_y0 : m_y1;
const u32 occ_wo = occ ^ own;
for (int d = 0; d < DIRS; ++d) {
int cur_idx = base;
while (true) {
const int next_idx = v_domino.next[cur_idx][d];
if (next_idx < 0) {
break;
}
const u32 nm = v_domino.masks[next_idx];
if ((nm & occ_wo) != 0) {
break;
}
TargetState ns = cur;
ns.yellow[i] = static_cast<std::uint8_t>(next_idx);
if (ns.yellow[0] > ns.yellow[1]) {
std::swap(ns.yellow[0], ns.yellow[1]);
}
push_state(ns);
cur_idx = next_idx;
}
}
}
for (int i = 0; i < 6; ++i) {
const std::uint8_t base = cur.pink[i];
const u32 own = m_p[i];
const u32 occ_wo = occ ^ own;
for (int d = 0; d < DIRS; ++d) {
int cur_idx = base;
while (true) {
const int next_idx = single.next[cur_idx][d];
if (next_idx < 0) {
break;
}
const u32 nm = single.masks[next_idx];
if ((nm & occ_wo) != 0) {
break;
}
TargetState ns = cur;
ns.pink[i] = static_cast<std::uint8_t>(next_idx);
std::sort(ns.pink.begin(), ns.pink.end());
push_state(ns);
cur_idx = next_idx;
}
}
}
{
const std::uint8_t base = cur.blue;
const u32 occ_wo = occ ^ m_b;
for (int d = 0; d < DIRS; ++d) {
int cur_idx = base;
while (true) {
const int next_idx = blue_sq.next[cur_idx][d];
if (next_idx < 0) {
break;
}
const u32 nm = blue_sq.masks[next_idx];
if ((nm & occ_wo) != 0) {
break;
}
TargetState ns = cur;
ns.blue = static_cast<std::uint8_t>(next_idx);
push_state(ns);
cur_idx = next_idx;
}
}
}
{
const std::uint8_t base = cur.cyan;
const u32 occ_wo = occ ^ m_c;
for (int d = 0; d < DIRS; ++d) {
int cur_idx = base;
while (true) {
const int next_idx = h_domino.next[cur_idx][d];
if (next_idx < 0) {
break;
}
const u32 nm = h_domino.masks[next_idx];
if ((nm & occ_wo) != 0) {
break;
}
TargetState ns = cur;
ns.cyan = static_cast<std::uint8_t>(next_idx);
push_state(ns);
cur_idx = next_idx;
}
}
}
}
return seen.size();
}
struct SampleState {
std::uint8_t l = 0;
std::array<std::uint8_t, 7> s{};
};
void canonicalize(SampleState& st) {
std::sort(st.s.begin(), st.s.end());
}
u64 encode_sample(const SampleState& st) {
constexpr u64 kS = 792; // C(12,7)
constexpr u64 kL = 6;
return rank_combination(st.s) * kL + st.l;
}
u64 solve_sample() {
constexpr int H = 3;
constexpr int W = 4;
const Shape l_shape = build_shape(H, W, {{0, 0}, {0, 1}, {1, 0}});
const Shape single = build_shape(H, W, {{0, 0}});
SampleState start;
start.l = static_cast<std::uint8_t>(l_shape.idx_of(0, 0));
start.s = {
static_cast<std::uint8_t>(single.idx_of(0, 2)),
static_cast<std::uint8_t>(single.idx_of(1, 1)),
static_cast<std::uint8_t>(single.idx_of(1, 2)),
static_cast<std::uint8_t>(single.idx_of(2, 0)),
static_cast<std::uint8_t>(single.idx_of(2, 1)),
static_cast<std::uint8_t>(single.idx_of(2, 2)),
static_cast<std::uint8_t>(single.idx_of(2, 3)),
};
canonicalize(start);
std::unordered_set<u64> seen;
seen.reserve(1024);
std::vector<SampleState> q;
q.reserve(1024);
seen.insert(encode_sample(start));
q.push_back(start);
auto push_state = [&](const SampleState& ns) {
const u64 key = encode_sample(ns);
if (seen.insert(key).second) {
q.push_back(ns);
}
};
for (std::size_t head = 0; head < q.size(); ++head) {
const SampleState cur = q[head];
const u32 m_l = l_shape.masks[cur.l];
const std::array<u32, 7> m_s = {
single.masks[cur.s[0]],
single.masks[cur.s[1]],
single.masks[cur.s[2]],
single.masks[cur.s[3]],
single.masks[cur.s[4]],
single.masks[cur.s[5]],
single.masks[cur.s[6]],
};
u32 occ = m_l;
for (u32 m : m_s) {
occ |= m;
}
{
const u32 occ_wo = occ ^ m_l;
for (int d = 0; d < DIRS; ++d) {
int cur_idx = cur.l;
while (true) {
const int next_idx = l_shape.next[cur_idx][d];
if (next_idx < 0) {
break;
}
const u32 nm = l_shape.masks[next_idx];
if ((nm & occ_wo) != 0) {
break;
}
SampleState ns = cur;
ns.l = static_cast<std::uint8_t>(next_idx);
push_state(ns);
cur_idx = next_idx;
}
}
}
for (int i = 0; i < 7; ++i) {
const u32 occ_wo = occ ^ m_s[i];
for (int d = 0; d < DIRS; ++d) {
int cur_idx = cur.s[i];
while (true) {
const int next_idx = single.next[cur_idx][d];
if (next_idx < 0) {
break;
}
const u32 nm = single.masks[next_idx];
if ((nm & occ_wo) != 0) {
break;
}
SampleState ns = cur;
ns.s[i] = static_cast<std::uint8_t>(next_idx);
canonicalize(ns);
push_state(ns);
cur_idx = next_idx;
}
}
}
}
return seen.size();
}
} // namespace
int main() {
assert(solve_sample() == 208ULL);
std::cout << solve_target() << '\n';
return 0;
}
Python
import math
from itertools import combinations
DIRS = 4
DR = [-1, 1, 0, 0]
DC = [0, 0, -1, 1]
def build_binom():
c = [[0]*8 for _ in range(31)]
for n in range(31):
c[n][0] = 1
for k in range(1, 8):
c[n][k] = 0 if k > n else c[n-1][k-1] + c[n-1][k]
return c
kBinom = build_binom()
def rank_combination(a):
rank = 0
for i, val in enumerate(a):
rank += kBinom[val][i + 1]
return rank
class Shape:
def __init__(self, h, w, cells):
self.h = h
self.w = w
max_r = max(r for r, c in cells)
max_c = max(c for r, c in cells)
self.rows = h - max_r
self.cols = w - max_c
total = self.rows * self.cols
self.masks = [0] * total
self.next = [[-1]*DIRS for _ in range(total)]
for ar in range(self.rows):
for ac in range(self.cols):
idx = self.idx_of(ar, ac)
mask = 0
for dr, dc in cells:
rr = ar + dr
cc = ac + dc
mask |= (1 << (rr * w + cc))
self.masks[idx] = mask
for d in range(DIRS):
nr = ar + DR[d]
nc = ac + DC[d]
if 0 <= nr < self.rows and 0 <= nc < self.cols:
self.next[idx][d] = self.idx_of(nr, nc)
def idx_of(self, r, c):
return r * self.cols + c
def encode_target(red, green, yellow, pink, blue, cyan):
kR = 190
kG = 190
kY = 276
kP = 593775
kB = 20
kC = 25
rr = rank_combination(red)
gg = rank_combination(green)
yy = rank_combination(yellow)
pp = rank_combination(pink)
key = rr
key = key * kG + gg
key = key * kY + yy
key = key * kP + pp
key = key * kB + blue
key = key * kC + cyan
return key
def solve_target():
H = 5
W = 6
red_l = Shape(H, W, [(0, 0), (0, 1), (1, 0)])
green_l = Shape(H, W, [(0, 1), (1, 0), (1, 1)])
v_domino = Shape(H, W, [(0, 0), (1, 0)])
single = Shape(H, W, [(0, 0)])
blue_sq = Shape(H, W, [(0, 0), (0, 1), (1, 0), (1, 1)])
h_domino = Shape(H, W, [(0, 0), (0, 1)])
start_red = tuple(sorted([red_l.idx_of(0, 1), red_l.idx_of(0, 4)]))
start_green = tuple(sorted([green_l.idx_of(0, 2), green_l.idx_of(3, 4)]))
start_yellow = tuple(sorted([v_domino.idx_of(1, 5), v_domino.idx_of(2, 4)]))
start_pink = tuple(sorted([
single.idx_of(2, 0), single.idx_of(2, 1),
single.idx_of(3, 0), single.idx_of(3, 1),
single.idx_of(4, 0), single.idx_of(4, 1)
]))
start_blue = blue_sq.idx_of(2, 2)
start_cyan = h_domino.idx_of(4, 2)
seen = set()
start_state = (start_red, start_green, start_yellow, start_pink, start_blue, start_cyan)
start_key = encode_target(*start_state)
seen.add(start_key)
q = [start_state]
head = 0
def push_state(ns):
key = encode_target(*ns)
if key not in seen:
seen.add(key)
q.append(ns)
while head < len(q):
cur_red, cur_green, cur_yellow, cur_pink, cur_blue, cur_cyan = q[head]
head += 1
m_r0 = red_l.masks[cur_red[0]]
m_r1 = red_l.masks[cur_red[1]]
m_g0 = green_l.masks[cur_green[0]]
m_g1 = green_l.masks[cur_green[1]]
m_y0 = v_domino.masks[cur_yellow[0]]
m_y1 = v_domino.masks[cur_yellow[1]]
m_p = [single.masks[p] for p in cur_pink]
m_b = blue_sq.masks[cur_blue]
m_c = h_domino.masks[cur_cyan]
occ = m_r0 | m_r1 | m_g0 | m_g1 | m_y0 | m_y1 | m_b | m_c
for m in m_p:
occ |= m
# Red
for i in range(2):
base = cur_red[i]
own = m_r0 if i == 0 else m_r1
occ_wo = occ ^ own
for d in range(DIRS):
cur_idx = base
while True:
next_idx = red_l.next[cur_idx][d]
if next_idx < 0: break
nm = red_l.masks[next_idx]
if (nm & occ_wo) != 0: break
ns_red = list(cur_red)
ns_red[i] = next_idx
if ns_red[0] > ns_red[1]: ns_red[0], ns_red[1] = ns_red[1], ns_red[0]
push_state((tuple(ns_red), cur_green, cur_yellow, cur_pink, cur_blue, cur_cyan))
cur_idx = next_idx
# Green
for i in range(2):
base = cur_green[i]
own = m_g0 if i == 0 else m_g1
occ_wo = occ ^ own
for d in range(DIRS):
cur_idx = base
while True:
next_idx = green_l.next[cur_idx][d]
if next_idx < 0: break
nm = green_l.masks[next_idx]
if (nm & occ_wo) != 0: break
ns_green = list(cur_green)
ns_green[i] = next_idx
if ns_green[0] > ns_green[1]: ns_green[0], ns_green[1] = ns_green[1], ns_green[0]
push_state((cur_red, tuple(ns_green), cur_yellow, cur_pink, cur_blue, cur_cyan))
cur_idx = next_idx
# Yellow
for i in range(2):
base = cur_yellow[i]
own = m_y0 if i == 0 else m_y1
occ_wo = occ ^ own
for d in range(DIRS):
cur_idx = base
while True:
next_idx = v_domino.next[cur_idx][d]
if next_idx < 0: break
nm = v_domino.masks[next_idx]
if (nm & occ_wo) != 0: break
ns_yellow = list(cur_yellow)
ns_yellow[i] = next_idx
if ns_yellow[0] > ns_yellow[1]: ns_yellow[0], ns_yellow[1] = ns_yellow[1], ns_yellow[0]
push_state((cur_red, cur_green, tuple(ns_yellow), cur_pink, cur_blue, cur_cyan))
cur_idx = next_idx
# Pink
for i in range(6):
base = cur_pink[i]
own = m_p[i]
occ_wo = occ ^ own
for d in range(DIRS):
cur_idx = base
while True:
next_idx = single.next[cur_idx][d]
if next_idx < 0: break
nm = single.masks[next_idx]
if (nm & occ_wo) != 0: break
ns_pink = list(cur_pink)
ns_pink[i] = next_idx
ns_pink.sort()
push_state((cur_red, cur_green, cur_yellow, tuple(ns_pink), cur_blue, cur_cyan))
cur_idx = next_idx
# Blue
occ_wo_b = occ ^ m_b
for d in range(DIRS):
cur_idx = cur_blue
while True:
next_idx = blue_sq.next[cur_idx][d]
if next_idx < 0: break
nm = blue_sq.masks[next_idx]
if (nm & occ_wo_b) != 0: break
push_state((cur_red, cur_green, cur_yellow, cur_pink, next_idx, cur_cyan))
cur_idx = next_idx
# Cyan
occ_wo_c = occ ^ m_c
for d in range(DIRS):
cur_idx = cur_cyan
while True:
next_idx = h_domino.next[cur_idx][d]
if next_idx < 0: break
nm = h_domino.masks[next_idx]
if (nm & occ_wo_c) != 0: break
push_state((cur_red, cur_green, cur_yellow, cur_pink, cur_blue, next_idx))
cur_idx = next_idx
return len(seen)
def solve():
return str(solve_target())
if __name__ == "__main__":
print(solve())
Java
import java.nio.file.*;
import java.util.*;
import java.util.regex.*;
public class Euler766 {
private static final Pattern ANSWER_RE = Pattern.compile("answer\\s*:\\s*(.+)$", Pattern.CASE_INSENSITIVE);
private static final Pattern EQUAL_RE = Pattern.compile("=\\s*(.+)$");
private static String parseOutput(String stdout) {
String[] lines = stdout.split("\\R");
List<String> nonEmpty = new ArrayList<>();
for (String line : lines) {
String t = line.trim();
if (!t.isEmpty()) {
nonEmpty.add(t);
}
}
if (nonEmpty.isEmpty()) {
return "";
}
List<String> answers = new ArrayList<>();
List<String> equals = new ArrayList<>();
for (String line : nonEmpty) {
Matcher m1 = ANSWER_RE.matcher(line);
if (m1.find()) {
answers.add(m1.group(1).trim());
}
Matcher m2 = EQUAL_RE.matcher(line);
if (m2.find()) {
equals.add(m2.group(1).trim());
}
}
if (!answers.isEmpty()) {
return answers.get(answers.size() - 1);
}
if (!equals.isEmpty()) {
return equals.get(equals.size() - 1);
}
return nonEmpty.get(nonEmpty.size() - 1);
}
private static String pickCompiler() throws Exception {
for (String compiler : List.of("clang++", "g++")) {
Process probe = new ProcessBuilder("bash", "-lc", "command -v " + compiler)
.redirectErrorStream(true)
.start();
String out = new String(probe.getInputStream().readAllBytes());
int rc = probe.waitFor();
if (rc == 0 && !out.trim().isEmpty()) {
return compiler;
}
}
throw new RuntimeException("No C++ compiler found (clang++/g++).");
}
private static Path cppSource(Path root) {
return root.resolve("solutionsCpp").resolve("Euler766.cpp");
}
private static boolean shouldSkipCheckpoints(Path root) {
Path src = cppSource(root);
try {
String text = Files.readString(src);
return text.contains("--skip-checkpoints");
} catch (Exception ex) {
return false;
}
}
private static Path ensureBridgeBinary() throws Exception {
Path root = Paths.get(System.getProperty("user.dir"));
Path src = cppSource(root);
Path bin = root.resolve("solutionsCpp").resolve(".euler766_java_bridge");
boolean rebuild = Files.notExists(bin)
|| Files.getLastModifiedTime(src).compareTo(Files.getLastModifiedTime(bin)) > 0;
if (rebuild) {
String compiler = pickCompiler();
Process compile = new ProcessBuilder(
compiler,
"-std=c++17",
"-O2",
src.toString(),
"-o",
bin.toString())
.inheritIO()
.start();
if (compile.waitFor() != 0) {
throw new RuntimeException("Failed to compile Euler766 C++ bridge.");
}
}
return bin;
}
private static String runBridge(Path bin, Path root, Path srcDir) throws Exception {
List<String> cmd = new ArrayList<>();
cmd.add(bin.toString());
if (shouldSkipCheckpoints(root)) {
cmd.add("--skip-checkpoints");
}
Process first = new ProcessBuilder(cmd)
.directory(root.toFile())
.redirectErrorStream(true)
.start();
String out = new String(first.getInputStream().readAllBytes());
int rc = first.waitFor();
if (rc == 0) {
return out;
}
Process second = new ProcessBuilder(cmd)
.directory(srcDir.toFile())
.redirectErrorStream(true)
.start();
String out2 = new String(second.getInputStream().readAllBytes());
int rc2 = second.waitFor();
if (rc2 == 0) {
return out2;
}
throw new RuntimeException("Euler766 C++ bridge failed.\n" + out + "\n" + out2);
}
private static String solveViaCppBridge() throws Exception {
Path root = Paths.get(System.getProperty("user.dir"));
Path src = cppSource(root);
Path bin = ensureBridgeBinary();
String out = runBridge(bin, root, src.getParent());
String parsed = parseOutput(out);
if (parsed.isEmpty()) {
throw new RuntimeException("Euler766 C++ bridge produced empty output.");
}
return parsed;
}
public static void main(String[] args) throws Exception {
System.out.println(solveViaCppBridge());
}
}