Detailed mathematical approach

Problem Summary

On an \(n\times n\) board we place exactly one queen in each row. A queen does not attack forever: it attacks vertically and diagonally only up to row distance \(D\), where

$D=n-1-w.$

Let \(Q(n,w)\) be the number of legal placements for weakness parameter \(w\). It is convenient to reparameterize by \(D\) and write \(N(n,D)=Q(n,n-1-D)\). Then the required quantity is

$S(n)=\sum_{w=0}^{n-1}Q(n,w)=\sum_{D=0}^{n-1}N(n,D).$

The endpoint cases clarify the model. When \(D=0\), no queen can reach a different row, so every row may use any of the \(n\) columns and \(N(n,0)=n^n\). When \(D=n-1\), every pair of rows can interact, so we recover the ordinary \(n\)-queens condition.

Mathematical Approach

The decisive observation is that a queen more than \(D\) rows above the current row is irrelevant. Therefore a partial placement is completely summarized by the most recent \(D\) chosen columns.

Step 1: Reparameterize by Attack Depth

Instead of summing directly over \(w\), we solve the fixed-depth problem \(N(n,D)\). This removes one layer of notation and matches the actual row-by-row rule: only row pairs whose distance is at most \(D\) can attack each other.

After computing every \(N(n,D)\) independently, the final answer is the outer sum

$S(n)=\sum_{D=0}^{n-1}N(n,D).$

Step 2: Describe the Local Forbidden Columns

Let \(c_r\in\{0,1,\dots,n-1\}\) denote the column used in row \(r\). A queen already placed in row \(r-d\) affects row \(r\) only when \(1\le d\le D\). In that case it forbids three possibilities:

$c_r=c_{r-d},\qquad c_r=c_{r-d}+d,\qquad c_r=c_{r-d}-d,$

whenever those columns stay inside the board. The first condition is the vertical attack, and the other two are the diagonals. Nothing older than \(D\) rows can matter.

Step 3: Use a Finite-Memory State

After placing the first \(r\) rows, define \(\ell=\min(r,D)\). The future depends only on the tuple

$\sigma_r=(c_r,c_{r-1},\dots,c_{r-\ell+1}).$

Two partial boards with the same tuple \(\sigma_r\) are equivalent for all future choices, because every earlier queen is already more than \(D\) rows away from the next row and can never attack again. This turns the search into dynamic programming on recent-history states.

Step 4: Transition to the Next Row

Suppose the current state is \(\sigma=(a_1,\dots,a_\ell)\), with \(a_1\) the most recent column. The blocked set for the next row is

$B(\sigma)=\bigcup_{d=1}^{\ell}\left(\{a_d\}\cup\{a_d+d\}\cup\{a_d-d\}\right)\cap\{0,1,\dots,n-1\}.$

Every column in \(\{0,1,\dots,n-1\}\setminus B(\sigma)\) is legal. Choosing such a column \(c\) produces the new recent-history tuple obtained by putting \(c\) in front and dropping the oldest remembered column if necessary.

If \(F_r(\sigma)\) denotes the number of partial boards of height \(r\) that lead to state \(\sigma\), then the next layer is obtained by adding \(F_r(\sigma)\) to every legal successor of \(\sigma\).

Step 5: Merge Equal Recent Histories

Many different partial boards collapse to the same recent-history tuple. Once the next-row successors have been generated, equal tuples are merged and their multiplicities are added. This is the key compression step: the algorithm never distinguishes two histories once their last \(D\) columns agree.

The merging is exact because the future attack pattern is determined entirely by the recent tuple, so no information is lost.

Worked Example: \((n,D)=(4,1)\)

When \(D=1\), each row interacts only with the immediately previous row, so the state is just the last column. If the previous column is \(0\), the next row may use only \(2\) or \(3\). If it is \(1\), only \(3\) is legal. If it is \(2\), only \(0\) is legal. If it is \(3\), only \(0\) or \(1\) are legal.

Starting from the first row, the counts of partial boards ending in columns \(0,1,2,3\) evolve as

$\begin{aligned} r=1&:\ (1,1,1,1), &&T_1=4,\\ r=2&:\ (2,1,1,2), &&T_2=6,\\ r=3&:\ (3,2,2,3), &&T_3=10,\\ r=4&:\ (5,3,3,5), &&T_4=16. \end{aligned}$

Hence \(N(4,1)=16\). The same framework also gives \(N(4,0)=4^4=256\), \(N(4,2)=2\), and \(N(4,3)=2\), so

$S(4)=256+16+2+2=276.$

How the Code Works

The C++, Python, and Java implementations all use this finite-memory dynamic program. For a fixed \(D\), they begin with the empty state of multiplicity \(1\), process rows from top to bottom, rebuild the blocked columns from the remembered recent columns, and enumerate every legal next column.

The compiled implementations store the remembered columns in a compact integer representation, using four bits per remembered row, which is sufficient for the target size \(n=14\). After each row, the generated successor states are ordered by their encoded state and equal states are merged by adding their counts.

Once all \(n\) rows have been processed, the counts of the surviving states are summed to obtain \(N(n,D)\). The outer routine repeats this for every \(D=0,1,\dots,n-1\) and adds the results. Because these fixed-\(D\) tasks are independent, the compiled implementations distribute them across worker threads. The Python implementation serves as a thin front end to the same compiled computation.

Complexity Analysis

For fixed \(D\), let \(F_r\) be the number of merged states after row \(r\), and let \(G_r\) be the number of generated successors before merging at the next step. Building the blocked set for one parent state scans at most \(D\) remembered queens, so the transition phase at that row costs \(O(F_rD+G_r)\). The implementations then sort the generated states before merging, which adds \(O(G_r\log G_r)\).

Therefore the total time for one value of \(D\) is

$O\left(\sum_{r=0}^{n-1}\left(F_rD+G_r\log G_r\right)\right),$

and the memory usage is \(O(\max_r G_r)\). A coarse worst-case bound is exponential in \(D\), since there can be up to \(n^D\) recent-history states, but for the required instance \(n=14\) the state merging keeps the frontier manageable enough for a direct computation.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=534
2. Eight queens puzzle: Wikipedia — Eight queens puzzle
3. Dynamic programming: Wikipedia — Dynamic programming
4. Bitwise operation: Wikipedia — Bitwise operation