Problem 424: Kakuro
View on Project EulerProject Euler Problem 424 Solution
EulerSolve provides an optimized solution for Project Euler Problem 424, Kakuro, with C++, Python, Java, and a step-by-step mathematical explanation.
Problem Summary Each puzzle is a Kakuro grid whose clue sums are written with letters \(A,\dots,J\) instead of decimal digits. The same bijection between those ten letters and the ten digits \(0,\dots,9\) is used everywhere in the puzzle, so solving one grid means recovering a single global permutation of the digits. Every white cell contains a value from \(1\) to \(9\), digits may not repeat inside one horizontal or vertical run, and each run must add up to the number represented by its clue. After a puzzle is solved, the digits assigned to \(A,B,\dots,J\) are concatenated in that order to form one encrypted 10-digit number. The Project Euler task asks for the sum of those encrypted values over the full dataset. Mathematical Approach 1. Variables and Global Constraints Let \(L_0,\dots,L_9\) denote the digits assigned to the ten letters. They satisfy $$L_i\in\{0,\dots,9\},\qquad L_i\neq L_j \text{ for } i\neq j.$$ For each white cell \(c\), introduce a cell variable \(x_c\in\{1,\dots,9\}\). If that cell is labelled by letter \(i\), then the cell and the letter must agree: $$x_c=L_i.$$ This already yields useful pruning. Letters may use \(0\), but white cells may not, so every letter that appears in a white cell is immediately restricted to \(\{1,\dots,9\}\). 2....
Detailed mathematical approach
Problem Summary
Each puzzle is a Kakuro grid whose clue sums are written with letters \(A,\dots,J\) instead of decimal digits. The same bijection between those ten letters and the ten digits \(0,\dots,9\) is used everywhere in the puzzle, so solving one grid means recovering a single global permutation of the digits. Every white cell contains a value from \(1\) to \(9\), digits may not repeat inside one horizontal or vertical run, and each run must add up to the number represented by its clue.
After a puzzle is solved, the digits assigned to \(A,B,\dots,J\) are concatenated in that order to form one encrypted 10-digit number. The Project Euler task asks for the sum of those encrypted values over the full dataset.
Mathematical Approach
1. Variables and Global Constraints
Let \(L_0,\dots,L_9\) denote the digits assigned to the ten letters. They satisfy
$$L_i\in\{0,\dots,9\},\qquad L_i\neq L_j \text{ for } i\neq j.$$
For each white cell \(c\), introduce a cell variable \(x_c\in\{1,\dots,9\}\). If that cell is labelled by letter \(i\), then the cell and the letter must agree:
$$x_c=L_i.$$
This already yields useful pruning. Letters may use \(0\), but white cells may not, so every letter that appears in a white cell is immediately restricted to \(\{1,\dots,9\}\).
2. Runs as Ordered Distinct-Digit Tuples
A Kakuro run is an ordered list \(R=(c_1,\dots,c_\ell)\) of consecutive white cells. For a run of length \(\ell\) and sum \(s\), the relevant object is the set
$$\mathcal T_{\ell,s}=\left\{(d_1,\dots,d_\ell)\in\{1,\dots,9\}^\ell:\sum_{j=1}^{\ell} d_j=s,\ d_u\neq d_v \text{ for } u\neq v\right\}.$$
The order matters, because \((1,2,3)\) and \((3,2,1)\) fill different cells. The implementation therefore precomputes all ordered tuples for every \(\ell\le 9\) and every achievable sum \(s\le 45\). The total size of this library is
$$\sum_{\ell=1}^{9}\frac{9!}{(9-\ell)!}=986409,$$
which is large enough to power strong propagation, but still a fixed constant for this problem.
3. Decoding One-Letter and Two-Letter Clues
If a clue contains one letter \(a\), its numeric value is simply
$$s=L_a.$$
If a clue contains two letters \(ab\), it is read as a decimal number:
$$s=10L_a+L_b,\qquad L_a\neq 0.$$
Because a Kakuro run built from distinct digits \(1,\dots,9\) can never exceed \(45\), only clue sums in \([0,45]\) are relevant. That gives immediate pruning on clue letters before search. The solver also treats repeated two-letter clues such as \(aa\) correctly; in that case the sum has the form \(s=11L_a\).
4. Constraint Propagation on a Run
During solving, each cell and each letter has a current domain \(D(\cdot)\). For a fixed run \(R=(c_1,\dots,c_\ell)\), one first computes the set of currently allowed sums. For a one-letter clue \(a\), this is
$$S_R=\{d\in D(a): 0\le d\le 9\}.$$
For a two-letter clue \(ab\), it is
$$S_R=\{10u+v:\ u\in D(a),\ v\in D(b),\ 10u+v\le 45\}.$$
A tuple \((d_1,\dots,d_\ell)\in \mathcal T_{\ell,s}\) is feasible exactly when every coordinate matches the current domain of its cell:
$$d_j\in D(c_j)\qquad\text{for all }j=1,\dots,\ell.$$
Let \(\mathcal F_R\) be the set of all feasible tuples over all allowed sums. Then each cell can be pruned by projection:
$$D(c_j)\leftarrow D(c_j)\cap \{d_j:(d_1,\dots,d_\ell)\in \mathcal F_R\}.$$
If no feasible tuple survives, the current branch is inconsistent and can be abandoned immediately.
The same information is projected back to the clue letters. A one-letter clue keeps only digits that still occur as valid run sums. A two-letter clue keeps only digit pairs whose decimal value \(10u+v\) still occurs among feasible sums. This two-way filtering between clue digits and run digits is the main reason the search tree stays small.
5. Global All-Different Pruning
The ten letters must form a permutation of \(0,\dots,9\). Instead of a heavy general matching algorithm, the implementation repeatedly applies two light but effective reductions.
First, if a letter is already fixed to one digit, that digit is removed from all other letter domains. Second, if a digit appears in only one remaining letter domain, that letter is forced to take it. In constraint-programming language these are singleton elimination and hidden-single detection for the global all-different condition.
6. Search Strategy and Final Value
Propagation often solves most of a puzzle by itself. When it does not, the solver chooses the unresolved variable with minimum remaining domain size, considering both letters and white cells, and branches on its candidate digits. After each tentative assignment, the full propagation cycle runs again. This is the standard minimum-remaining-values heuristic combined with depth-first search.
Once all letters are fixed, the encrypted value of one puzzle is
$$E=\sum_{i=0}^{9} L_i\,10^{9-i}.$$
The required answer is the sum of \(E\) over all puzzles in the input.
How the Code Works
The C++, Python, and Java implementations all follow the same pipeline. They parse one puzzle into white cells, letter-labelled white cells, and horizontal or vertical runs. Next they build the tuple tables \(\mathcal T_{\ell,s}\), initialize each letter with domain \(\{0,\dots,9\}\), and initialize each white cell with domain \(\{1,\dots,9\}\).
The propagation loop alternates between three ideas: linking letter domains to labelled cells, pruning the global letter permutation, and scanning each run against the precomputed tuple tables. If propagation no longer changes anything and the puzzle is still incomplete, the implementation branches on the smallest non-singleton domain and recurses. The three language versions differ only in syntax; algorithmically they are the same solver.
Complexity Analysis
The worst-case complexity remains exponential, because Kakuro solving with a global digit substitution still requires backtracking in difficult cases. However, the expensive combinatorial structure is mostly front-loaded into a constant-size precomputation. For this problem the tuple library has fixed size \(986409\), so it does not grow with the number of puzzles.
If a run has length \(\ell\), one propagation pass examines at most the tuples attached to sums that are still allowed by its clue. A rough upper bound for one pass over that run is
$$O\left(\sum_{s\in S_R} |\mathcal T_{\ell,s}|\,\ell\right).$$
The overall runtime is therefore dominated by the number of search nodes that survive propagation. In practice, tuple filtering, clue back-projection, all-different pruning, and MRV branching reduce that number sharply. Memory usage is linear in the current puzzle state plus the fixed tuple table.
References
- Problem page: https://projecteuler.net/problem=424
- Kakuro overview: Wikipedia - Kakuro
- Constraint satisfaction problem: Wikipedia - Constraint satisfaction problem
- Variable ordering heuristics: Wikipedia - Variable and value ordering heuristics
- Global constraints in constraint programming: Wikipedia - Constraint programming
Problem 424 source code
C++
#include <algorithm>
#include <array>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
namespace {
using u16 = std::uint16_t;
using u64 = std::uint64_t;
constexpr int LETTERS = 10;
constexpr int MAX_LEN = 9;
constexpr int MAX_SUM = 45;
constexpr u16 LETTER_MASK = (1u << LETTERS) - 1u; // digits 0..9
constexpr u16 CELL_MASK = LETTER_MASK & ~1u; // digits 1..9
struct Options {
std::string file = "solutionsCpp/p424_kakuro200.txt";
bool run_checkpoints = true;
};
struct Run {
std::vector<int> cells;
std::array<int, 2> clue_letters{};
int clue_len = 0; // 1 or 2
};
struct Puzzle {
int n = 0;
std::vector<int> white_index; // n*n -> white id or -1
std::vector<int> cell_letter; // white id -> letter id or -1
std::vector<Run> runs;
};
struct State {
std::array<u16, LETTERS> letter_dom{};
std::vector<u16> cell_dom;
};
std::array<std::array<std::vector<u64>, MAX_SUM + 1>, MAX_LEN + 1> tuple_codes;
bool parse_arguments(int argc, char** argv, Options& options) {
for (int i = 1; i < argc; ++i) {
const std::string arg(argv[i]);
if (arg == "--skip-checkpoints") {
options.run_checkpoints = false;
continue;
}
if (arg.rfind("--file=", 0U) == 0U) {
options.file = arg.substr(7);
continue;
}
std::cerr << "Unknown argument: " << arg << '\n';
return false;
}
return !options.file.empty();
}
inline int popcount(u16 x) {
return __builtin_popcount(static_cast<unsigned>(x));
}
inline bool is_single(u16 x) {
return x != 0 && (x & (x - 1u)) == 0;
}
inline int single_value(u16 x) {
return __builtin_ctz(static_cast<unsigned>(x));
}
void gen_tuples(int len, int pos, int used_mask, int sum, u64 code) {
if (pos == len) {
tuple_codes[len][sum].push_back(code);
return;
}
for (int d = 1; d <= 9; ++d) {
if (used_mask & (1 << d)) {
continue;
}
gen_tuples(len, pos + 1, used_mask | (1 << d), sum + d, code | (static_cast<u64>(d) << (4 * pos)));
}
}
void prepare_tuples() {
for (int len = 1; len <= MAX_LEN; ++len) {
gen_tuples(len, 0, 0, 0, 0);
}
}
std::vector<std::string> split_csv(const std::string& line) {
std::vector<std::string> out;
std::string cur;
cur.reserve(16);
int depth = 0;
for (char ch : line) {
if (ch == ',' && depth == 0) {
out.push_back(cur);
cur.clear();
} else if (ch != ' ' && ch != '\r' && ch != '\n' && ch != '\t') {
cur.push_back(ch);
if (ch == '(') {
++depth;
} else if (ch == ')') {
--depth;
}
}
}
out.push_back(cur);
return out;
}
int letter_id(char ch) {
if (ch < 'A' || ch > 'J') {
return -1;
}
return ch - 'A';
}
bool is_white_token(const std::string& tok) {
if (tok == "O") {
return true;
}
return tok.size() == 1 && letter_id(tok[0]) != -1;
}
std::vector<std::string> split_by_comma_inside(const std::string& s) {
std::vector<std::string> out;
std::string cur;
for (char ch : s) {
if (ch == ',') {
out.push_back(cur);
cur.clear();
} else {
cur.push_back(ch);
}
}
if (!cur.empty()) {
out.push_back(cur);
}
return out;
}
bool parse_puzzle_line(const std::string& line, Puzzle& puzzle) {
const std::vector<std::string> tokens = split_csv(line);
if (tokens.empty()) {
return false;
}
int n = 0;
try {
n = std::stoi(tokens[0]);
} catch (...) {
return false;
}
if (n <= 0 || static_cast<int>(tokens.size()) != 1 + n * n) {
return false;
}
std::vector<std::string> grid(tokens.begin() + 1, tokens.end());
puzzle.n = n;
puzzle.white_index.assign(static_cast<std::size_t>(n * n), -1);
puzzle.cell_letter.clear();
puzzle.runs.clear();
int white_count = 0;
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
const std::string& tok = grid[static_cast<std::size_t>(r * n + c)];
if (!is_white_token(tok)) {
continue;
}
puzzle.white_index[static_cast<std::size_t>(r * n + c)] = white_count++;
if (tok == "O") {
puzzle.cell_letter.push_back(-1);
} else {
puzzle.cell_letter.push_back(letter_id(tok[0]));
}
}
}
auto add_run = [&](int r, int c, bool horizontal, const std::string& clue_str) {
Run run;
run.clue_len = static_cast<int>(clue_str.size());
if (run.clue_len < 1 || run.clue_len > 2) {
return;
}
run.clue_letters[0] = letter_id(clue_str[0]);
run.clue_letters[1] = (run.clue_len == 2 ? letter_id(clue_str[1]) : -1);
if (run.clue_letters[0] < 0 || (run.clue_len == 2 && run.clue_letters[1] < 0)) {
return;
}
if (horizontal) {
for (int cc = c + 1; cc < n; ++cc) {
const int idx = puzzle.white_index[static_cast<std::size_t>(r * n + cc)];
if (idx < 0) {
break;
}
run.cells.push_back(idx);
}
} else {
for (int rr = r + 1; rr < n; ++rr) {
const int idx = puzzle.white_index[static_cast<std::size_t>(rr * n + c)];
if (idx < 0) {
break;
}
run.cells.push_back(idx);
}
}
if (!run.cells.empty()) {
puzzle.runs.push_back(std::move(run));
}
};
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
const std::string& tok = grid[static_cast<std::size_t>(r * n + c)];
if (tok.size() < 2 || tok.front() != '(' || tok.back() != ')') {
continue;
}
const std::string inside = tok.substr(1, tok.size() - 2);
const std::vector<std::string> parts = split_by_comma_inside(inside);
for (const std::string& part : parts) {
if (part.size() < 2) {
return false;
}
if (part[0] == 'h') {
add_run(r, c, true, part.substr(1));
} else if (part[0] == 'v') {
add_run(r, c, false, part.substr(1));
} else {
return false;
}
}
}
}
return true;
}
bool load_puzzles(const std::string& file, std::vector<Puzzle>& puzzles) {
std::ifstream in(file);
if (!in) {
return false;
}
puzzles.clear();
std::string line;
while (std::getline(in, line)) {
if (line.empty()) {
continue;
}
Puzzle p;
if (!parse_puzzle_line(line, p)) {
return false;
}
puzzles.push_back(std::move(p));
}
return !puzzles.empty();
}
bool propagate_links(const Puzzle& puzzle, State& st, bool& changed) {
for (std::size_t i = 0; i < puzzle.cell_letter.size(); ++i) {
const int letter = puzzle.cell_letter[i];
if (letter < 0) {
continue;
}
const u16 allowed = static_cast<u16>(st.letter_dom[letter] & CELL_MASK);
u16 cdom = st.cell_dom[i];
u16 ndom = static_cast<u16>(cdom & allowed);
if (ndom == 0) {
return false;
}
if (ndom != cdom) {
st.cell_dom[i] = ndom;
changed = true;
}
u16 ldom = st.letter_dom[letter];
u16 nldom = static_cast<u16>(ldom & ndom);
if (nldom == 0) {
return false;
}
if (nldom != ldom) {
st.letter_dom[letter] = nldom;
changed = true;
}
}
return true;
}
bool propagate_all_diff_letters(State& st, bool& changed) {
bool local_changed = true;
while (local_changed) {
local_changed = false;
for (int i = 0; i < LETTERS; ++i) {
if (st.letter_dom[i] == 0) {
return false;
}
}
u16 assigned_mask = 0;
for (int i = 0; i < LETTERS; ++i) {
if (is_single(st.letter_dom[i])) {
assigned_mask |= st.letter_dom[i];
}
}
for (int i = 0; i < LETTERS; ++i) {
if (is_single(st.letter_dom[i])) {
continue;
}
u16 ndom = static_cast<u16>(st.letter_dom[i] & ~assigned_mask);
if (ndom == 0) {
return false;
}
if (ndom != st.letter_dom[i]) {
st.letter_dom[i] = ndom;
local_changed = true;
changed = true;
}
}
for (int d = 0; d <= 9; ++d) {
const u16 bit = static_cast<u16>(1u << d);
int count = 0;
int where = -1;
for (int i = 0; i < LETTERS; ++i) {
if (st.letter_dom[i] & bit) {
++count;
where = i;
}
}
if (count == 0) {
return false;
}
if (count == 1 && st.letter_dom[where] != bit) {
st.letter_dom[where] = bit;
local_changed = true;
changed = true;
}
}
}
return true;
}
bool propagate_run(const Run& run, State& st, bool& changed) {
const int len = static_cast<int>(run.cells.size());
if (len <= 0 || len > MAX_LEN) {
return false;
}
const int a = run.clue_letters[0];
const int b = run.clue_letters[1];
if (run.clue_len == 2) {
u16 dom_a = st.letter_dom[a];
u16 ndom_a = static_cast<u16>(dom_a & ~1u); // no leading zero in two-digit sum.
if (ndom_a == 0) {
return false;
}
if (ndom_a != dom_a) {
st.letter_dom[a] = ndom_a;
changed = true;
}
}
std::array<bool, MAX_SUM + 1> sum_allowed{};
if (run.clue_len == 1) {
const u16 dom = st.letter_dom[a];
for (int d = 0; d <= 9; ++d) {
if ((dom >> d) & 1u) {
sum_allowed[d] = true;
}
}
} else {
const u16 dom_a = st.letter_dom[a];
const u16 dom_b = st.letter_dom[b];
for (int da = 0; da <= 9; ++da) {
if (!((dom_a >> da) & 1u)) {
continue;
}
for (int db = 0; db <= 9; ++db) {
if (!((dom_b >> db) & 1u)) {
continue;
}
const int s = 10 * da + db;
if (s <= MAX_SUM) {
sum_allowed[s] = true;
}
}
}
}
std::array<u16, MAX_LEN> union_masks{};
std::array<bool, MAX_SUM + 1> sum_valid{};
bool any_tuple = false;
for (int s = 0; s <= MAX_SUM; ++s) {
if (!sum_allowed[s]) {
continue;
}
const auto& tuples = tuple_codes[len][s];
if (tuples.empty()) {
continue;
}
bool any_for_sum = false;
for (u64 code : tuples) {
bool ok = true;
for (int pos = 0; pos < len; ++pos) {
const int d = static_cast<int>((code >> (4 * pos)) & 0xFULL);
const u16 bit = static_cast<u16>(1u << d);
if ((st.cell_dom[static_cast<std::size_t>(run.cells[pos])] & bit) == 0) {
ok = false;
break;
}
}
if (!ok) {
continue;
}
any_for_sum = true;
any_tuple = true;
for (int pos = 0; pos < len; ++pos) {
const int d = static_cast<int>((code >> (4 * pos)) & 0xFULL);
union_masks[static_cast<std::size_t>(pos)] |= static_cast<u16>(1u << d);
}
}
if (any_for_sum) {
sum_valid[s] = true;
}
}
if (!any_tuple) {
return false;
}
for (int pos = 0; pos < len; ++pos) {
const int cid = run.cells[pos];
const u16 ndom = static_cast<u16>(st.cell_dom[static_cast<std::size_t>(cid)] & union_masks[static_cast<std::size_t>(pos)]);
if (ndom == 0) {
return false;
}
if (ndom != st.cell_dom[static_cast<std::size_t>(cid)]) {
st.cell_dom[static_cast<std::size_t>(cid)] = ndom;
changed = true;
}
}
if (run.clue_len == 1) {
u16 allowed = 0;
for (int s = 0; s <= 9; ++s) {
if (sum_valid[s]) {
allowed |= static_cast<u16>(1u << s);
}
}
const u16 ndom = static_cast<u16>(st.letter_dom[a] & allowed);
if (ndom == 0) {
return false;
}
if (ndom != st.letter_dom[a]) {
st.letter_dom[a] = ndom;
changed = true;
}
} else if (a == b) {
u16 allowed = 0;
for (int d = 0; d <= 9; ++d) {
const int s = 11 * d;
if (s <= MAX_SUM && sum_valid[s]) {
allowed |= static_cast<u16>(1u << d);
}
}
allowed = static_cast<u16>(allowed & ~1u);
const u16 ndom = static_cast<u16>(st.letter_dom[a] & allowed);
if (ndom == 0) {
return false;
}
if (ndom != st.letter_dom[a]) {
st.letter_dom[a] = ndom;
changed = true;
}
} else {
u16 allowed_a = 0;
u16 allowed_b = 0;
const u16 dom_a = st.letter_dom[a];
const u16 dom_b = st.letter_dom[b];
for (int da = 0; da <= 9; ++da) {
if (!((dom_a >> da) & 1u)) {
continue;
}
for (int db = 0; db <= 9; ++db) {
if (!((dom_b >> db) & 1u)) {
continue;
}
const int s = 10 * da + db;
if (s <= MAX_SUM && sum_valid[s]) {
allowed_a |= static_cast<u16>(1u << da);
allowed_b |= static_cast<u16>(1u << db);
}
}
}
allowed_a = static_cast<u16>(allowed_a & ~1u);
const u16 ndom_a = static_cast<u16>(st.letter_dom[a] & allowed_a);
const u16 ndom_b = static_cast<u16>(st.letter_dom[b] & allowed_b);
if (ndom_a == 0 || ndom_b == 0) {
return false;
}
if (ndom_a != st.letter_dom[a]) {
st.letter_dom[a] = ndom_a;
changed = true;
}
if (ndom_b != st.letter_dom[b]) {
st.letter_dom[b] = ndom_b;
changed = true;
}
}
return true;
}
bool propagate(const Puzzle& puzzle, State& st) {
while (true) {
bool changed = false;
if (!propagate_links(puzzle, st, changed)) {
return false;
}
if (!propagate_all_diff_letters(st, changed)) {
return false;
}
if (!propagate_links(puzzle, st, changed)) {
return false;
}
for (const Run& run : puzzle.runs) {
if (!propagate_run(run, st, changed)) {
return false;
}
}
if (!changed) {
break;
}
}
return true;
}
bool solved(const State& st) {
for (int i = 0; i < LETTERS; ++i) {
if (!is_single(st.letter_dom[i])) {
return false;
}
}
for (u16 dom : st.cell_dom) {
if (!is_single(dom)) {
return false;
}
}
return true;
}
struct Choice {
bool is_letter = true;
int idx = -1;
u16 dom = 0;
int size = 1000;
};
Choice choose_variable(const State& st) {
Choice best;
for (int i = 0; i < LETTERS; ++i) {
const int sz = popcount(st.letter_dom[i]);
if (sz > 1 && sz < best.size) {
best = {true, i, st.letter_dom[i], sz};
}
}
for (int i = 0; i < static_cast<int>(st.cell_dom.size()); ++i) {
const int sz = popcount(st.cell_dom[static_cast<std::size_t>(i)]);
if (sz > 1 && sz < best.size) {
best = {false, i, st.cell_dom[static_cast<std::size_t>(i)], sz};
}
}
return best;
}
bool dfs_solve(const Puzzle& puzzle, State& st) {
if (!propagate(puzzle, st)) {
return false;
}
if (solved(st)) {
return true;
}
const Choice choice = choose_variable(st);
if (choice.idx < 0) {
return false;
}
for (int d = 0; d <= 9; ++d) {
const u16 bit = static_cast<u16>(1u << d);
if ((choice.dom & bit) == 0) {
continue;
}
State next = st;
if (choice.is_letter) {
next.letter_dom[static_cast<std::size_t>(choice.idx)] = bit;
} else {
next.cell_dom[static_cast<std::size_t>(choice.idx)] = bit;
}
if (dfs_solve(puzzle, next)) {
st = std::move(next);
return true;
}
}
return false;
}
bool solve_puzzle(const Puzzle& puzzle, u64& encrypted_value) {
State st;
st.letter_dom.fill(LETTER_MASK);
st.cell_dom.assign(puzzle.cell_letter.size(), CELL_MASK);
if (!dfs_solve(puzzle, st)) {
return false;
}
encrypted_value = 0ULL;
for (int i = 0; i < LETTERS; ++i) {
encrypted_value = encrypted_value * 10ULL + static_cast<u64>(single_value(st.letter_dom[i]));
}
return true;
}
bool run_checkpoints(const std::vector<Puzzle>& puzzles) {
if (puzzles.empty()) {
std::cerr << "Checkpoint failed: no puzzles loaded\n";
return false;
}
u64 first_value = 0ULL;
if (!solve_puzzle(puzzles[0], first_value)) {
std::cerr << "Checkpoint failed: first puzzle unsolved\n";
return false;
}
if (first_value != 8426039571ULL) {
std::cerr << "Checkpoint failed: first puzzle encrypted value\n";
return false;
}
return true;
}
} // namespace
int main(int argc, char** argv) {
Options options;
if (!parse_arguments(argc, argv, options)) {
return 1;
}
prepare_tuples();
std::vector<Puzzle> puzzles;
if (!load_puzzles(options.file, puzzles)) {
std::cerr << "Failed to load puzzle file: " << options.file << '\n';
return 2;
}
if (options.run_checkpoints && !run_checkpoints(puzzles)) {
return 3;
}
u64 total = 0ULL;
for (const Puzzle& puzzle : puzzles) {
u64 value = 0ULL;
if (!solve_puzzle(puzzle, value)) {
std::cerr << "Failed to solve a puzzle\n";
return 4;
}
total += value;
}
std::cout << total << '\n';
return 0;
}
Python
def solve():
import os
path = os.path.join(os.path.dirname(os.path.dirname(__file__)), "solutionsCpp", "p424_kakuro200.txt")
if not os.path.exists(path):
path = "solutionsCpp/p424_kakuro200.txt"
MAX_SUM = 45; CELL_MASK = 0x3FE # bits 1-9
# Generate valid tuples
tc = [[[] for _ in range(MAX_SUM+1)] for _ in range(10)]
def gen(l,p,u,s,c):
if p==l: tc[l][s].append(c); return
for d in range(1,10):
if u&(1<<d): continue
gen(l,p+1,u|(1<<d),s+d,c|(d<<(4*p)))
for l in range(1,10): gen(l,0,0,0,0)
def lid(ch): return ord(ch)-ord('A') if 'A'<=ch<='J' else -1
def iswt(t): return t=='O' or (len(t)==1 and lid(t[0])>=0)
def parse(line):
toks = []; cur=''; depth=0
for ch in line.strip():
if ch==',' and depth==0: toks.append(cur); cur=''
elif ch not in ' \t\r\n': cur+=ch; depth+=(ch=='(')-(ch==')')
toks.append(cur)
n=int(toks[0]); grid=toks[1:]
wi=[-1]*(n*n); cl=[]; wc=0
for r in range(n):
for c in range(n):
t=grid[r*n+c]
if not iswt(t): continue
wi[r*n+c]=wc; wc+=1; cl.append(lid(t[0]) if t!='O' else -1)
runs=[]
for r in range(n):
for c in range(n):
t=grid[r*n+c]
if len(t)<2 or t[0]!='(' or t[-1]!=')': continue
ins=t[1:-1]; parts=ins.split(',')
for part in parts:
h=part[0]=='h'; cs=part[1:]
clen=len(cs); cl0=lid(cs[0]); cl1=lid(cs[1]) if clen==2 else -1
cells=[]
if h:
for cc in range(c+1,n):
idx=wi[r*n+cc]
if idx<0: break
cells.append(idx)
else:
for rr in range(r+1,n):
idx=wi[rr*n+c]
if idx<0: break
cells.append(idx)
if cells: runs.append((cells,cl0,cl1,clen))
return n,wi,cl,runs
def solve_puzzle(puz):
n,wi,cl,runs=puz; NC=len(cl)
ld=[0x3FF]*10; cd=[CELL_MASK]*NC
def prop():
while True:
ch=False
for i in range(NC):
lt=cl[i]
if lt<0: continue
al=ld[lt]&CELL_MASK; nd=cd[i]&al
if nd==0: return False
if nd!=cd[i]: cd[i]=nd; ch=True
nl=ld[lt]&nd
if nl==0: return False
if nl!=ld[lt]: ld[lt]=nl; ch=True
# alldiff
asgn=0
for i in range(10):
if ld[i]==0: return False
if ld[i]&(ld[i]-1)==0: asgn|=ld[i]
for i in range(10):
if ld[i]&(ld[i]-1)==0: continue
nd=ld[i]&~asgn
if nd==0: return False
if nd!=ld[i]: ld[i]=nd; ch=True
for d in range(10):
bit=1<<d; cnt=0; where=-1
for i in range(10):
if ld[i]&bit: cnt+=1; where=i
if cnt==0: return False
if cnt==1 and ld[where]!=bit: ld[where]=bit; ch=True
# runs
for cells,a,b,clen in runs:
ln=len(cells)
if clen==2:
nd=ld[a]&~1
if nd==0: return False
if nd!=ld[a]: ld[a]=nd; ch=True
sa=[False]*(MAX_SUM+1)
if clen==1:
for d in range(10):
if (ld[a]>>d)&1: sa[d]=True
else:
for da in range(10):
if not (ld[a]>>da)&1: continue
for db in range(10):
if (ld[b]>>db)&1:
s=10*da+db
if s<=MAX_SUM: sa[s]=True
um=[0]*ln; sv=[False]*(MAX_SUM+1); at=False
for s in range(MAX_SUM+1):
if not sa[s]: continue
for code in tc[ln][s]:
ok=True
for p in range(ln):
d=(code>>(4*p))&0xF
if not (cd[cells[p]]>>(d))&1: ok=False; break
if not ok: continue
at=True; sv[s]=True
for p in range(ln): um[p]|=1<<((code>>(4*p))&0xF)
if not at: return False
for p in range(ln):
cid=cells[p]; nd=cd[cid]&um[p]
if nd==0: return False
if nd!=cd[cid]: cd[cid]=nd; ch=True
if clen==1:
al2=0
for s in range(10):
if sv[s]: al2|=1<<s
nd=ld[a]&al2
if nd==0: return False
if nd!=ld[a]: ld[a]=nd; ch=True
elif a==b:
al2=0
for d in range(10):
s=11*d
if s<=MAX_SUM and sv[s]: al2|=1<<d
al2&=~1; nd=ld[a]&al2
if nd==0: return False
if nd!=ld[a]: ld[a]=nd; ch=True
else:
aa=ab=0
for da in range(10):
if not (ld[a]>>da)&1: continue
for db in range(10):
if not (ld[b]>>db)&1: continue
s=10*da+db
if s<=MAX_SUM and sv[s]: aa|=1<<da; ab|=1<<db
aa&=~1; na=ld[a]&aa; nb=ld[b]&ab
if na==0 or nb==0: return False
if na!=ld[a]: ld[a]=na; ch=True
if nb!=ld[b]: ld[b]=nb; ch=True
if not ch: break
return True
def solved():
return all(d&(d-1)==0 and d!=0 for d in ld) and all(d&(d-1)==0 and d!=0 for d in cd)
def dfs():
if not prop(): return False
if solved(): return True
best_sz=100; best_is_l=True; best_i=-1; best_d=0
for i in range(10):
sz=bin(ld[i]).count('1')
if sz>1 and sz<best_sz: best_sz=sz; best_is_l=True; best_i=i; best_d=ld[i]
for i in range(NC):
sz=bin(cd[i]).count('1')
if sz>1 and sz<best_sz: best_sz=sz; best_is_l=False; best_i=i; best_d=cd[i]
if best_i<0: return False
sld=ld[:]; scd=cd[:]
for d in range(10):
if not (best_d>>d)&1: continue
ld[:]=sld[:]; cd[:]=scd[:]
if best_is_l: ld[best_i]=1<<d
else: cd[best_i]=1<<d
if dfs(): return True
ld[:]=sld; cd[:]=scd; return False
if not dfs(): return 0
v=0
for i in range(10): v=v*10+(ld[i]).bit_length()-1
return v
with open(path) as f: lines=f.readlines()
total=0
for line in lines:
line=line.strip()
if not line: continue
total+=solve_puzzle(parse(line))
return str(total)
if __name__=='__main__':
print(solve())
Java
import java.io.BufferedReader;
import java.io.FileReader;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Euler424 {
static final int LETTERS = 10;
static final int MAX_LEN = 9;
static final int MAX_SUM = 45;
static final int LETTER_MASK = (1 << LETTERS) - 1;
static final int CELL_MASK = LETTER_MASK & ~1;
@SuppressWarnings("unchecked")
static List<Long>[][] tupleCodes = new List[MAX_LEN + 1][MAX_SUM + 1];
static {
for (int i = 0; i <= MAX_LEN; i++) {
for (int j = 0; j <= MAX_SUM; j++) {
tupleCodes[i][j] = new ArrayList<>();
}
}
}
static int popcount(int x) {
return Integer.bitCount(x);
}
static boolean isSingle(int x) {
return x != 0 && (x & (x - 1)) == 0;
}
static int singleValue(int x) {
return Integer.numberOfTrailingZeros(x);
}
static void genTuples(int len, int pos, int usedMask, int sum, long code) {
if (pos == len) {
tupleCodes[len][sum].add(code);
return;
}
for (int d = 1; d <= 9; d++) {
if ((usedMask & (1 << d)) != 0)
continue;
genTuples(len, pos + 1, usedMask | (1 << d), sum + d, code | ((long) d << (4 * pos)));
}
}
static void prepareTuples() {
if (!tupleCodes[1][1].isEmpty())
return;
for (int len = 1; len <= MAX_LEN; len++) {
genTuples(len, 0, 0, 0, 0L);
}
}
static class Run {
List<Integer> cells = new ArrayList<>();
int[] clueLetters = new int[2];
int clueLen = 0;
}
static class Puzzle {
int n = 0;
int[] whiteIndex;
List<Integer> cellLetter = new ArrayList<>();
List<Run> runs = new ArrayList<>();
}
static class State {
int[] letterDom = new int[LETTERS];
int[] cellDom;
State(int size) {
Arrays.fill(letterDom, LETTER_MASK);
cellDom = new int[size];
Arrays.fill(cellDom, CELL_MASK);
}
State copy() {
State n = new State(this.cellDom.length);
System.arraycopy(this.letterDom, 0, n.letterDom, 0, LETTERS);
System.arraycopy(this.cellDom, 0, n.cellDom, 0, this.cellDom.length);
return n;
}
}
static List<String> splitCsv(String line) {
List<String> out = new ArrayList<>();
StringBuilder cur = new StringBuilder();
int depth = 0;
for (char ch : line.toCharArray()) {
if (ch == ',' && depth == 0) {
out.add(cur.toString());
cur.setLength(0);
} else if (ch != ' ' && ch != '\r' && ch != '\n' && ch != '\t') {
cur.append(ch);
if (ch == '(')
depth++;
else if (ch == ')')
depth--;
}
}
out.add(cur.toString());
return out;
}
static int letterId(char ch) {
if (ch >= 'A' && ch <= 'J')
return ch - 'A';
return -1;
}
static boolean isWhiteToken(String tok) {
if (tok.equals("O"))
return true;
return tok.length() == 1 && letterId(tok.charAt(0)) != -1;
}
static Puzzle parsePuzzleLine(String line) {
List<String> tokens = splitCsv(line);
if (tokens.isEmpty())
return null;
int n = 0;
try {
n = Integer.parseInt(tokens.get(0));
} catch (Exception e) {
return null;
}
if (n <= 0 || tokens.size() != 1 + n * n)
return null;
List<String> grid = tokens.subList(1, tokens.size());
Puzzle puzzle = new Puzzle();
puzzle.n = n;
puzzle.whiteIndex = new int[n * n];
Arrays.fill(puzzle.whiteIndex, -1);
int whiteCount = 0;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
String tok = grid.get(r * n + c);
if (!isWhiteToken(tok))
continue;
puzzle.whiteIndex[r * n + c] = whiteCount++;
if (tok.equals("O"))
puzzle.cellLetter.add(-1);
else
puzzle.cellLetter.add(letterId(tok.charAt(0)));
}
}
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
String tok = grid.get(r * n + c);
if (tok.length() < 2 || tok.charAt(0) != '(' || tok.charAt(tok.length() - 1) != ')')
continue;
String inside = tok.substring(1, tok.length() - 1);
String[] parts = inside.split(",");
for (String part : parts) {
if (part.length() < 2)
return null;
boolean horiz = part.charAt(0) == 'h';
if (!horiz && part.charAt(0) != 'v')
return null;
String clueStr = part.substring(1);
Run run = new Run();
run.clueLen = clueStr.length();
if (run.clueLen < 1 || run.clueLen > 2)
continue;
run.clueLetters[0] = letterId(clueStr.charAt(0));
run.clueLetters[1] = run.clueLen == 2 ? letterId(clueStr.charAt(1)) : -1;
if (run.clueLetters[0] < 0 || (run.clueLen == 2 && run.clueLetters[1] < 0))
continue;
if (horiz) {
for (int cc = c + 1; cc < n; cc++) {
int idx = puzzle.whiteIndex[r * n + cc];
if (idx < 0)
break;
run.cells.add(idx);
}
} else {
for (int rr = r + 1; rr < n; rr++) {
int idx = puzzle.whiteIndex[rr * n + c];
if (idx < 0)
break;
run.cells.add(idx);
}
}
if (!run.cells.isEmpty())
puzzle.runs.add(run);
}
}
}
return puzzle;
}
static List<Puzzle> loadPuzzles(String filepath) {
List<Puzzle> puzzles = new ArrayList<>();
try (BufferedReader br = new BufferedReader(new FileReader(filepath))) {
String line;
while ((line = br.readLine()) != null) {
line = line.trim();
if (line.isEmpty())
continue;
Puzzle p = parsePuzzleLine(line);
if (p != null)
puzzles.add(p);
}
} catch (Exception e) {
// Error handling ignored to fallback
}
return puzzles;
}
static class PropResult {
boolean ok, changed;
PropResult(boolean o, boolean c) {
ok = o;
changed = c;
}
}
static PropResult propagateLinks(Puzzle puzzle, State st) {
boolean changed = false;
int sz = puzzle.cellLetter.size();
for (int i = 0; i < sz; i++) {
int letter = puzzle.cellLetter.get(i);
if (letter < 0)
continue;
int allowed = st.letterDom[letter] & CELL_MASK;
int cdom = st.cellDom[i];
int ndom = cdom & allowed;
if (ndom == 0)
return new PropResult(false, changed);
if (ndom != cdom) {
st.cellDom[i] = ndom;
changed = true;
}
int ldom = st.letterDom[letter];
int nldom = ldom & ndom;
if (nldom == 0)
return new PropResult(false, changed);
if (nldom != ldom) {
st.letterDom[letter] = nldom;
changed = true;
}
}
return new PropResult(true, changed);
}
static PropResult propagateAllDiffLetters(State st) {
boolean changed = false;
boolean localChanged = true;
while (localChanged) {
localChanged = false;
for (int i = 0; i < LETTERS; i++) {
if (st.letterDom[i] == 0)
return new PropResult(false, changed);
}
int assignedMask = 0;
for (int i = 0; i < LETTERS; i++) {
if (isSingle(st.letterDom[i]))
assignedMask |= st.letterDom[i];
}
for (int i = 0; i < LETTERS; i++) {
if (isSingle(st.letterDom[i]))
continue;
int ndom = st.letterDom[i] & ~assignedMask;
if (ndom == 0)
return new PropResult(false, changed);
if (ndom != st.letterDom[i]) {
st.letterDom[i] = ndom;
localChanged = true;
changed = true;
}
}
for (int d = 0; d <= 9; d++) {
int bit = 1 << d;
int count = 0;
int where = -1;
for (int i = 0; i < LETTERS; i++) {
if ((st.letterDom[i] & bit) != 0) {
count++;
where = i;
}
}
if (count == 0)
return new PropResult(false, changed);
if (count == 1 && st.letterDom[where] != bit) {
st.letterDom[where] = bit;
localChanged = true;
changed = true;
}
}
}
return new PropResult(true, changed);
}
static PropResult propagateRun(Run run, State st) {
boolean changed = false;
int len = run.cells.size();
if (len <= 0 || len > MAX_LEN)
return new PropResult(false, changed);
int a = run.clueLetters[0];
int b = run.clueLetters[1];
if (run.clueLen == 2) {
int domA = st.letterDom[a];
int ndomA = domA & ~1;
if (ndomA == 0)
return new PropResult(false, changed);
if (ndomA != domA) {
st.letterDom[a] = ndomA;
changed = true;
}
}
boolean[] sumAllowed = new boolean[MAX_SUM + 1];
if (run.clueLen == 1) {
int dom = st.letterDom[a];
for (int d = 0; d <= 9; d++) {
if (((dom >> d) & 1) != 0)
sumAllowed[d] = true;
}
} else {
int domA = st.letterDom[a];
int domB = st.letterDom[b];
for (int da = 0; da <= 9; da++) {
if (((domA >> da) & 1) == 0)
continue;
for (int db = 0; db <= 9; db++) {
if (((domB >> db) & 1) == 0)
continue;
int s = 10 * da + db;
if (s <= MAX_SUM)
sumAllowed[s] = true;
}
}
}
int[] unionMasks = new int[MAX_LEN];
boolean[] sumValid = new boolean[MAX_SUM + 1];
boolean anyTuple = false;
for (int s = 0; s <= MAX_SUM; s++) {
if (!sumAllowed[s])
continue;
List<Long> tuples = tupleCodes[len][s];
if (tuples.isEmpty())
continue;
boolean anyForSum = false;
for (long code : tuples) {
boolean ok = true;
for (int pos = 0; pos < len; pos++) {
int d = (int) ((code >> (4 * pos)) & 0xF);
int bit = 1 << d;
if ((st.cellDom[run.cells.get(pos)] & bit) == 0) {
ok = false;
break;
}
}
if (!ok)
continue;
anyForSum = true;
anyTuple = true;
for (int pos = 0; pos < len; pos++) {
int d = (int) ((code >> (4 * pos)) & 0xF);
unionMasks[pos] |= (1 << d);
}
}
if (anyForSum)
sumValid[s] = true;
}
if (!anyTuple)
return new PropResult(false, changed);
for (int pos = 0; pos < len; pos++) {
int cid = run.cells.get(pos);
int ndom = st.cellDom[cid] & unionMasks[pos];
if (ndom == 0)
return new PropResult(false, changed);
if (ndom != st.cellDom[cid]) {
st.cellDom[cid] = ndom;
changed = true;
}
}
if (run.clueLen == 1) {
int allowed = 0;
for (int s = 0; s <= 9; s++) {
if (sumValid[s])
allowed |= (1 << s);
}
int ndom = st.letterDom[a] & allowed;
if (ndom == 0)
return new PropResult(false, changed);
if (ndom != st.letterDom[a]) {
st.letterDom[a] = ndom;
changed = true;
}
} else if (a == b) {
int allowed = 0;
for (int d = 0; d <= 9; d++) {
int s = 11 * d;
if (s <= MAX_SUM && sumValid[s])
allowed |= (1 << d);
}
allowed &= ~1;
int ndom = st.letterDom[a] & allowed;
if (ndom == 0)
return new PropResult(false, changed);
if (ndom != st.letterDom[a]) {
st.letterDom[a] = ndom;
changed = true;
}
} else {
int allowedA = 0, allowedB = 0;
int domA = st.letterDom[a], domB = st.letterDom[b];
for (int da = 0; da <= 9; da++) {
if (((domA >> da) & 1) == 0)
continue;
for (int db = 0; db <= 9; db++) {
if (((domB >> db) & 1) == 0)
continue;
int s = 10 * da + db;
if (s <= MAX_SUM && sumValid[s]) {
allowedA |= (1 << da);
allowedB |= (1 << db);
}
}
}
allowedA &= ~1;
int ndomA = st.letterDom[a] & allowedA;
int ndomB = st.letterDom[b] & allowedB;
if (ndomA == 0 || ndomB == 0)
return new PropResult(false, changed);
if (ndomA != st.letterDom[a]) {
st.letterDom[a] = ndomA;
changed = true;
}
if (ndomB != st.letterDom[b]) {
st.letterDom[b] = ndomB;
changed = true;
}
}
return new PropResult(true, changed);
}
static boolean propagate(Puzzle puzzle, State st) {
while (true) {
boolean globallyChanged = false;
PropResult r1 = propagateLinks(puzzle, st);
if (!r1.ok)
return false;
if (r1.changed)
globallyChanged = true;
PropResult r2 = propagateAllDiffLetters(st);
if (!r2.ok)
return false;
if (r2.changed)
globallyChanged = true;
PropResult r3 = propagateLinks(puzzle, st);
if (!r3.ok)
return false;
if (r3.changed)
globallyChanged = true;
for (Run run : puzzle.runs) {
PropResult r4 = propagateRun(run, st);
if (!r4.ok)
return false;
if (r4.changed)
globallyChanged = true;
}
if (!globallyChanged)
break;
}
return true;
}
static boolean solved(State st) {
for (int i = 0; i < LETTERS; i++) {
if (!isSingle(st.letterDom[i]))
return false;
}
for (int dom : st.cellDom) {
if (!isSingle(dom))
return false;
}
return true;
}
static class Choice {
boolean isLetter = true;
int idx = -1;
int dom = 0;
int size = 1000;
}
static Choice chooseVariable(State st) {
Choice best = new Choice();
for (int i = 0; i < LETTERS; i++) {
int sz = popcount(st.letterDom[i]);
if (sz > 1 && sz < best.size) {
best.isLetter = true;
best.idx = i;
best.dom = st.letterDom[i];
best.size = sz;
}
}
for (int i = 0; i < st.cellDom.length; i++) {
int sz = popcount(st.cellDom[i]);
if (sz > 1 && sz < best.size) {
best.isLetter = false;
best.idx = i;
best.dom = st.cellDom[i];
best.size = sz;
}
}
return best;
}
static boolean dfsSolve(Puzzle puzzle, State st) {
if (!propagate(puzzle, st))
return false;
if (solved(st))
return true;
Choice choice = chooseVariable(st);
if (choice.idx < 0)
return false;
for (int d = 0; d <= 9; d++) {
int bit = 1 << d;
if ((choice.dom & bit) == 0)
continue;
State next = st.copy();
if (choice.isLetter)
next.letterDom[choice.idx] = bit;
else
next.cellDom[choice.idx] = bit;
if (dfsSolve(puzzle, next)) {
System.arraycopy(next.letterDom, 0, st.letterDom, 0, LETTERS);
System.arraycopy(next.cellDom, 0, st.cellDom, 0, st.cellDom.length);
return true;
}
}
return false;
}
static long solvePuzzle(Puzzle puzzle) {
State st = new State(puzzle.cellLetter.size());
if (!dfsSolve(puzzle, st))
return -1;
long encryptedValue = 0;
for (int i = 0; i < LETTERS; i++) {
encryptedValue = encryptedValue * 10 + singleValue(st.letterDom[i]);
}
return encryptedValue;
}
static String solve() {
prepareTuples();
String file = "p424_kakuro200.txt";
List<Puzzle> puzzles = loadPuzzles(file);
if (puzzles.isEmpty()) {
file = "solutionsCpp/p424_kakuro200.txt";
puzzles = loadPuzzles(file);
}
long total = 0;
for (Puzzle p : puzzles) {
long val = solvePuzzle(p);
if (val >= 0)
total += val;
}
return Long.toString(total);
}
public static void main(String[] args) {
System.out.println(solve());
}
}