Project Euler

Weak Queens

A weak queen on a chessboard attacks only the 8 adjacent squares (like a king). Let f(n) be the number of ways to place n non-attacking weak queens on an n x n board with exactly one queen per row....

Source sync Apr 19, 2026

Problem #0534

Level Level 27

Solved By 371

Languages C++, Python

Answer 11726115562784664

Length 315 words

dynamic_programminglinear_algebragraph

The classical eight queens puzzle is the well known problem of placing eight chess queens on an $8 \times 8$ chessboard so that no two queens threaten each other. Allowing configurations to reappear in rotated or mirrored form, a total of $92$ distinct configurations can be found for eight queens. The general case asks for the number of distinct ways of placing $n$ queens on an $n \times n$ board, e.g. you can find $2$ distinct configurations for $n=4$.

Let’s define a weak queen on an $n \times n$ board to be a piece which can move any number of squares if moved horizontally, but a maximum of $n - 1 - w$ squares if moved vertically or diagonally, $0 \le w < n$ being the "weakness factor". For example, a weak queen on an $n \times n$ board with a weakness factor of $w=1$ located in the bottom row will not be able to threaten any square in the top row as the weak queen would need to move $n - 1$ squares vertically or diagonally to get there, but may only move $n - 2$ squares in these directions. In contrast, the weak queen is not handicapped horizontally, thus threatening every square in its own row, independently from its current position in that row.

Let $Q(n,w)$ be the number of ways $n$ weak queens with weakness factor $w$ can be placed on an $n \times n$ board so that no two queens threaten each other. It can be shown, for example, that $Q(4,0)=2$, $Q(4,2)=16$ and $Q(4,3)=256$.

Let $S(n)=\displaystyle \sum _{w=0}^{n-1} Q(n,w)$.

Let $S(n)=\displaystyle \sum _{w=0}^{n-1} Q(n,w)$

Find $S(14)$.

Problem 534: Weak Queens

Mathematical Foundation

Theorem 1 (Reduction to Constrained Permutations). A placement of $n$ non-attacking weak queens, one per row, on an $n \times n$ board is valid if and only if the column assignment $\sigma \in S_n$ satisfies $|\sigma(i) - \sigma(i+1)| \ge 2$ for all $1 \le i \le n - 1$ .

Proof. Since there is exactly one queen per row, the column assignments $\sigma(1), \ldots, \sigma(n)$ must be distinct, forming a permutation. A weak queen in row $i$ , column $\sigma(i)$ attacks the 8 cells at Chebyshev distance 1. Two queens in rows $i$ and $j$ can attack each other only if $|i - j| \le 1$ and $|\sigma(i) - \sigma(j)| \le 1$ . Since queens are in distinct rows, the only potentially attacking pairs are in consecutive rows $i$ and $i+1$ , requiring $|\sigma(i) - \sigma(i+1)| \le 1$ . The non-attacking condition is therefore $|\sigma(i) - \sigma(i+1)| \ge 2$ for all consecutive $i$ . $\square$

Theorem 2 (Bitmask DP Correctness). Define $\mathrm{dp}[\mathrm{mask}][c]$ as the number of ways to fill $|\mathrm{mask}|$ rows using column set $\mathrm{mask}$ , with the last queen in column $c \in \mathrm{mask}$ . Then

f(n) = \sum_{c=0}^{n-1} \mathrm{dp}[2^n - 1][c]

where the recurrence is

\mathrm{dp}[\mathrm{mask} \cup \{c\}][c] \mathrel{+}= \mathrm{dp}[\mathrm{mask}][c'] \quad \text{for all } c \notin \mathrm{mask},\; |c - c'| \ge 2.

Proof. The DP state captures exactly the information needed: which columns have been used (the bitmask ensures the permutation property) and which column was most recently placed (needed to enforce the $|\sigma(i) - \sigma(i+1)| \ge 2$ constraint). The base case assigns $\mathrm{dp}[\{c\}][c] = 1$ for each column $c$ . Each transition extends a valid partial placement by one row. By induction on $|\mathrm{mask}|$ , $\mathrm{dp}[\mathrm{mask}][c]$ counts all valid partial placements of $|\mathrm{mask}|$ queens using columns $\mathrm{mask}$ with the last in column $c$ . Summing over all $c$ when $\mathrm{mask} = 2^n - 1$ gives $f(n)$ . $\square$

Editorial

A weak queen attacks only adjacent squares (king moves). Place n non-attacking weak queens on an n x n board, one per row. Constraint: queens in adjacent rows must be >= 2 columns apart. Compute sum_{n=1}^{12} f(n) using bitmask DP.

Pseudocode

    if n == 1: return 1
    if n <= 3: return 0

    dp[mask][last_col] = count of valid placements
    dp = map from (mask, col) -> integer, initially 0
    For c from 0 to n-1:
        dp[(1 << c, c)] = 1

    For row from 1 to n-1:
        new_dp = empty map
        For each each (mask, prev_c) in dp with popcount(mask) == row:
            For c from 0 to n-1:
                If mask & (1 << c) != 0 then continue
                If |c - prev_c| < 2 then continue
                new_dp[(mask | (1 << c), c)] += dp[(mask, prev_c)]
        merge new_dp into dp

    Return sum of dp[(2^n - 1, c)] for all c

    Return sum of F(n) for n = 1 to 12

Complexity Analysis

Time: $O(n^2 \cdot 2^n)$ per value of $n$ . For each of the $O(n \cdot 2^n)$ states, we try $O(n)$ transitions. For $n = 12$ : $12^2 \cdot 2^{12} = 589{,}824$ operations. Summing over $n = 1, \ldots, 12$ is dominated by the $n = 12$ term.
Space: $O(n \cdot 2^n)$ for the DP table. For $n = 12$ : $12 \cdot 4096 = 49{,}152$ entries.

Answer

\boxed{11726115562784664}

C++ project_euler/problem_534/solution.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

/*
 * Problem 534: Weak Queens
 *
 * Place n non-attacking weak queens (king-move attacks only) on n x n board.
 * One queen per row. Queens in adjacent rows must differ by >= 2 columns.
 *
 * Bitmask DP: dp[mask][last_col] = count of ways.
 * Time: O(n^2 * 2^n).
 */

ll f(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;

    int total_masks = 1 << n;
    // dp[mask][last_col]
    vector<vector<ll>> dp(total_masks, vector<ll>(n, 0));

    // Row 0: place queen in any column
    for (int c = 0; c < n; c++) {
        dp[1 << c][c] = 1;
    }

    for (int row = 1; row < n; row++) {
        vector<vector<ll>> new_dp(total_masks, vector<ll>(n, 0));
        for (int mask = 0; mask < total_masks; mask++) {
            if (__builtin_popcount(mask) != row) continue;
            for (int prev_c = 0; prev_c < n; prev_c++) {
                if (dp[mask][prev_c] == 0) continue;
                for (int c = 0; c < n; c++) {
                    if (mask & (1 << c)) continue;
                    if (abs(c - prev_c) < 2) continue;
                    new_dp[mask | (1 << c)][c] += dp[mask][prev_c];
                }
            }
        }
        for (int mask = 0; mask < total_masks; mask++) {
            for (int c = 0; c < n; c++) {
                dp[mask][c] += new_dp[mask][c];
            }
        }
    }

    int full = (1 << n) - 1;
    ll result = 0;
    for (int c = 0; c < n; c++) {
        result += dp[full][c];
    }
    return result;
}

int main() {
    ll total = 0;
    for (int n = 1; n <= 12; n++) {
        ll val = f(n);
        printf("f(%d) = %lld\n", n, val);
        total += val;
    }
    printf("Sum = %lld\n", total);
    assert(total == 3884);
    cout << total << endl;
    return 0;
}

Python project_euler/problem_534/solution.py

"""
Problem 534: Weak Queens

A weak queen attacks only adjacent squares (king moves).
Place n non-attacking weak queens on an n x n board, one per row.
Constraint: queens in adjacent rows must be >= 2 columns apart.

Compute sum_{n=1}^{12} f(n) using bitmask DP.
"""

from collections import defaultdict

# --- Method 1: Bitmask DP ---
def f_bitmask(n: int):
    """Count placements via bitmask DP. O(n^2 * 2^n)."""
    if n == 0:
        return 0
    # dp[(mask, last_col)] = count
    dp = defaultdict(int)
    for c in range(n):
        dp[(1 << c, c)] = 1

    for row in range(1, n):
        new_dp = defaultdict(int)
        for (mask, prev_c), count in dp.items():
            if bin(mask).count('1') != row:
                continue
            for c in range(n):
                if mask & (1 << c):
                    continue
                if abs(c - prev_c) < 2:
                    continue
                new_dp[(mask | (1 << c), c)] += count
        for key, val in new_dp.items():
            dp[key] += val

    full_mask = (1 << n) - 1
    return sum(v for (mask, _), v in dp.items() if mask == full_mask)

# --- Method 2: Backtracking (verification) ---
def f_backtrack(n: int):
    """Count placements via backtracking."""
    count = [0]
    cols = []

    def solve(row):
        if row == n:
            count[0] += 1
            return
        for c in range(n):
            if c in cols:
                continue
            if row > 0 and abs(c - cols[-1]) < 2:
                continue
            cols.append(c)
            solve(row + 1)
            cols.pop()

    solve(0)
    return count[0]

# --- Compute and verify ---
results = {}
for n in range(1, 13):
    val = f_bitmask(n)
    results[n] = val
    if n <= 9:
        assert val == f_backtrack(n), f"Mismatch at n={n}: {val} vs {f_backtrack(n)}"
    print(f"f({n}) = {val}")

total = sum(results.values())
print(f"Sum = {total}")
assert total == 3884, f"Expected 3884, got {total}"