Problem 534: Weak Queens

Problem 534 source code

C++

#include <cstdint>
#include <iomanip>
#include <iostream>
#include <atomic>
#include <algorithm>
#include <thread>
#include <vector>

namespace {

using u64 = std::uint64_t;
using u128 = __uint128_t;

u64 count_configurations(int n, int D) {
    // Place exactly one queen per row. A queen attacks vertically/diagonally only up to D rows away.
    // Row-by-row DP with state = last D columns (4 bits each, most recent at LSB).
    const u64 all_cols = (n == 64) ? ~0ULL : ((1ULL << n) - 1ULL);
    const u64 mask = (D == 0) ? 0ULL : ((1ULL << (4 * D)) - 1ULL);

    struct Node {
        u64 state;
        u64 ways;
    };

    std::vector<Node> dp, next, generated;
    dp.reserve(1 << 18);
    next.reserve(1 << 18);
    generated.reserve(1 << 20);
    dp.push_back(Node{0ULL, 1ULL});

    for (int row = 0; row < n; ++row) {
        generated.clear();
        const int len = (row < D) ? row : D;
        for (const Node& node : dp) {
            const u64 state = node.state;
            const u64 ways = node.ways;
            u64 blocked = 0;
            for (int dist = 1; dist <= len; ++dist) {
                const int c_prev = static_cast<int>((state >> (4 * (dist - 1))) & 0xFULL);
                blocked |= 1ULL << c_prev;
                const int c1 = c_prev + dist;
                const int c2 = c_prev - dist;
                if (c1 >= 0 && c1 < n) {
                    blocked |= 1ULL << c1;
                }
                if (c2 >= 0 && c2 < n) {
                    blocked |= 1ULL << c2;
                }
            }
            u64 avail = all_cols & ~blocked;
            while (avail) {
                const int col = __builtin_ctzll(avail);
                avail &= (avail - 1);
                const u64 ns = (((state << 4) | static_cast<u64>(col)) & mask);
                generated.push_back(Node{ns, ways});
            }
        }

        std::sort(generated.begin(), generated.end(),
                  [](const Node& a, const Node& b) { return a.state < b.state; });
        next.clear();
        next.reserve(generated.size());
        for (const Node& g : generated) {
            if (!next.empty() && next.back().state == g.state) {
                next.back().ways += g.ways;
            } else {
                next.push_back(g);
            }
        }

        dp.swap(next);
    }

    u128 total = 0;
    for (const Node& node : dp) {
        total += static_cast<u128>(node.ways);
    }
    return static_cast<u64>(total);
}

u64 S(int n) {
    unsigned threads = std::thread::hardware_concurrency();
    if (threads == 0) {
        threads = 8;
    }
    threads = std::min<unsigned>(threads, static_cast<unsigned>(n));

    std::atomic<int> next_w{0};
    std::vector<u128> partial(threads, 0);
    std::vector<std::thread> workers;
    workers.reserve(threads);

    for (unsigned tid = 0; tid < threads; ++tid) {
        workers.emplace_back([&, tid]() {
            u128 local = 0;
            while (true) {
                const int w = next_w.fetch_add(1, std::memory_order_relaxed);
                if (w >= n) {
                    break;
                }
                const int D = (n - 1) - w;
                local += static_cast<u128>(count_configurations(n, D));
            }
            partial[tid] = local;
        });
    }
    for (auto& t : workers) {
        t.join();
    }

    u128 sum = 0;
    for (u128 v : partial) {
        sum += v;
    }

    return static_cast<u64>(sum);
}

bool run_checkpoints() {
    if (count_configurations(4, 3) != 2ULL) {  // w=0 => D=3
        std::cerr << "Checkpoint failed: Q(4,0)\n";
        return false;
    }
    if (count_configurations(4, 1) != 16ULL) {  // w=2 => D=1
        std::cerr << "Checkpoint failed: Q(4,2)\n";
        return false;
    }
    if (count_configurations(4, 0) != 256ULL) {  // w=3 => D=0
        std::cerr << "Checkpoint failed: Q(4,3)\n";
        return false;
    }
    if (S(4) != 276ULL) {
        std::cerr << "Checkpoint failed: S(4)\n";
        return false;
    }
    if (S(5) != 3347ULL) {
        std::cerr << "Checkpoint failed: S(5)\n";
        return false;
    }
    return true;
}

}  // namespace

int main() {
    if (!run_checkpoints()) {
        return 1;
    }
    std::cout << S(14) << '\n';
    return 0;
}

Python

from __future__ import annotations

import re
import shutil
import subprocess
from pathlib import Path

ANSWER_RE = re.compile(r"answer\s*:\s*(.+)$", re.IGNORECASE)
EQUAL_RE = re.compile(r"=\s*(.+)$")


def parse_output(stdout: str) -> str:
    lines = [line.strip() for line in stdout.splitlines() if line.strip()]
    if not lines:
        return ""
    answers = []
    equals = []
    for line in lines:
        m1 = ANSWER_RE.search(line)
        if m1:
            answers.append(m1.group(1).strip())
        m2 = EQUAL_RE.search(line)
        if m2:
            equals.append(m2.group(1).strip())
    if answers:
        return answers[-1]
    if equals:
        return equals[-1]
    return lines[-1]


def should_skip_cpp_checkpoints(src: Path) -> bool:
    try:
        text = src.read_text(encoding="utf-8", errors="ignore")
    except OSError:
        return False
    return "--skip-checkpoints" in text


def run_cpp(binary: Path, src: Path, root: Path) -> str:
    cmd = [str(binary)]
    if should_skip_cpp_checkpoints(src):
        cmd.append("--skip-checkpoints")

    try:
        return subprocess.check_output(cmd, text=True, cwd=root)
    except subprocess.CalledProcessError:
        return subprocess.check_output(cmd, text=True, cwd=src.parent)


def solve() -> str:
    problem_id = __file__.split("Euler")[-1].split(".")[0]
    root = Path(__file__).resolve().parent.parent
    src = root / "solutionsCpp" / f"Euler{problem_id}.cpp"
    binary = root / "solutionsCpp" / f".euler{problem_id}_py_bridge"

    if not binary.exists() or src.stat().st_mtime > binary.stat().st_mtime:
        compiler = shutil.which("clang++") or shutil.which("g++")
        if not compiler:
            raise RuntimeError("No C++ compiler found (clang++/g++).")
        subprocess.check_call([compiler, "-std=c++17", "-O2", str(src), "-o", str(binary)])

    output = run_cpp(binary=binary, src=src, root=root)
    parsed = parse_output(output)
    if not parsed:
        raise RuntimeError(f"Euler{problem_id} bridge produced empty output.")
    return parsed


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

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

public class Euler534 {
    static class Node implements Comparable<Node> {
        long state;
        long ways;

        Node(long state, long ways) {
            this.state = state;
            this.ways = ways;
        }

        @Override
        public int compareTo(Node o) {
            return Long.compare(this.state, o.state);
        }
    }

    static long countConfigurations(int n, int D) {
        long allCols = (n == 64) ? ~0L : ((1L << n) - 1L);
        long mask = (D == 0) ? 0L : ((1L << (4 * D)) - 1L);

        List<Node> dp = new ArrayList<>();
        dp.add(new Node(0L, 1L));

        List<Node> generated = new ArrayList<>(1 << 20);
        List<Node> next = new ArrayList<>(1 << 18);

        for (int row = 0; row < n; row++) {
            generated.clear();
            int len = Math.min(row, D);

            for (Node node : dp) {
                long state = node.state;
                long ways = node.ways;
                long blocked = 0;

                for (int dist = 1; dist <= len; dist++) {
                    int cPrev = (int) ((state >> (4 * (dist - 1))) & 0xFL);
                    blocked |= (1L << cPrev);
                    int c1 = cPrev + dist;
                    int c2 = cPrev - dist;
                    if (c1 >= 0 && c1 < n) {
                        blocked |= (1L << c1);
                    }
                    if (c2 >= 0 && c2 < n) {
                        blocked |= (1L << c2);
                    }
                }

                long avail = allCols & ~blocked;
                while (avail != 0) {
                    long lsB = avail & -avail;
                    int col = Long.numberOfTrailingZeros(lsB);
                    avail &= (avail - 1);
                    long ns = ((state << 4) | col) & mask;
                    generated.add(new Node(ns, ways));
                }
            }

            Collections.sort(generated);
            next.clear();
            for (Node g : generated) {
                if (!next.isEmpty() && next.get(next.size() - 1).state == g.state) {
                    next.get(next.size() - 1).ways += g.ways;
                } else {
                    next.add(new Node(g.state, g.ways));
                }
            }

            List<Node> temp = dp;
            dp = next;
            next = temp;
        }

        long total = 0;
        for (Node node : dp) {
            total += node.ways;
        }
        return total;
    }

    public static String solve() {
        int n = 14;
        int numThreads = Runtime.getRuntime().availableProcessors();
        if (numThreads == 0)
            numThreads = 8;
        numThreads = Math.min(numThreads, n);

        AtomicInteger nextW = new AtomicInteger(0);
        long[] partial = new long[numThreads];
        Thread[] workers = new Thread[numThreads];

        for (int tid = 0; tid < numThreads; tid++) {
            final int threadId = tid;
            workers[tid] = new Thread(() -> {
                long local = 0;
                while (true) {
                    int w = nextW.getAndIncrement();
                    if (w >= n)
                        break;
                    int D = (n - 1) - w;
                    local += countConfigurations(n, D);
                }
                partial[threadId] = local;
            });
            workers[tid].start();
        }

        for (int tid = 0; tid < numThreads; tid++) {
            try {
                workers[tid].join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        long sum = 0;
        for (long v : partial) {
            sum += v;
        }

        return Long.toString(sum);
    }

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