[challenge]: Exact contraction of the tensor network representation of the N-queens problem

Released by

Hai-Jun Liao, Institute of Physics, Chinese Academy of Sciences

Contact email

navyphysics@iphy.ac.cn

Method

PEPS Based Algorithm

Challenge issue

Exact tensor-network contraction for the N-queens counting problem — can we reach N = 28?

A combinatorial count you can actually contract

The N-queens problem — place $N$ non-attacking queens on an $N \times N$ board — is one of the oldest problems in discrete mathematics. The exact count $Q(N)$ grows super-exponentially. The current frontier $N = 27$ was reached by massively parallel FPGA backtracking (Preußer & Engelhardt, 2017); GPU solvers have since reproduced $Q(27)$. $Q(28)$ is unknown — and Azuma et al. (2018) estimate that even improved FPGA hardware would need further gains to make $N=28$ tractable.

Liu, Liao, and Wang (arXiv:2605.10326v2, Sec. VI) encode the constraints as an exact tensor network: each site carries a rank-8 tensor $C$ with bond dimension $D=2$ on four channels (row, column, two diagonals) and only 17 nonzero elements. Contracting the full $N \times N$ network yields $Q(N)$ with no statistical noise. This challenge: strictly contract that network — with CTMRG, boundary MPS/MPO, or any exact TN method — and see whether $N=28$ is reachable.

Why a tensor network?

Each queen constraint (at most one per row/column/diagonal) is a matrix product operator with $D=2$. At every lattice site, four constraint lines meet, producing the sparse local tensor $C$. The solution count is one number:

$$
Q(N) = \langle \Psi \mid (|0\rangle+|1\rangle)^{\otimes N^2} \rangle
$$

equivalently a row-by-row transfer matrix contraction $Q(N)=\langle v_f \mid T^N \mid v_0 \rangle$.

The twist: $T$ is nilpotent ($T^{N+1}=0$). All eigenvalues vanish; $Q(N)$ lives in the finite power $T^N$, not a dominant spectral mode. Standard infinite-size methods (DMRG, VUMPS, CTMRG) target $\lambda_{\max}$ — the wrong object here. Finite-$N$ exact contraction is the natural route, but bond dimension grows exponentially. The open question is whether improved TN algorithms can beat the current combinatorial frontier at $N=27$.

The core of the challenge

Build an exact (no bond-dimension truncation) contraction for the Sec. VI construction and compute $Q(N)$ for as large $N$ as possible. The headline target:

$$
\boxed{Q(28) = \ ?}
$$

with cross-checks against known values (OEIS A000170). A valid solver must first reproduce several benchmarks — at minimum $Q(8)=92$, $Q(16)=14{,}772{,}512$, $Q(20)=39{,}029{,}188{,}884$, and $Q(27)=234{,}907{,}967{,}154{,}122{,}528$.

Load-bearing requirements:

• Follow the Sec. VI network (tensors B/C, boundary vectors $v_0=(1,0), v_1=(0,1), v_2=(1,1) $). Equivalent reformulations are fine if exactness is proved.
• Contraction must be strictly exact — truncation that changes the count does not count.
• Report runtime and memory scaling; identify the bottleneck that limits $N$.

Goal

1. Implement exact TN contraction for the N-queens network of Liu et al. (Sec. VI).
2. Validate against known $Q(N)$ for $N \le 27$ (OEIS A000170).
3. Push to $N=28$ if feasible; otherwise report the largest $N$ reached and why the next step fails.

Why this leads to research output

• Combinatorial milestone. $Q(28)$ would be the first exact count beyond the FPGA/GPU record at $N=27$, via an independent physics/tensor-network route — a qualitatively different algorithm from carry-chain backtracking.
• Nilpotent transfer matrices. Most TN methods assume a largest eigenvalue; N-queens is a rare counterexample where the answer is in $T^N$, not $\lambda_{\max}^N$. Scaling to $N=28$ forces new algorithmic ideas.
• Benchmark for stat-mech combinatorics. Exact $Q(N)$ from TN contraction complements the Monte Carlo thermodynamic route in the same paper (Simkin constant $\gamma$) with noise-free integers.

Acceptance / deliverables

• Documented exact TN contraction code following Sec. VI.
• Reproduction of at least four benchmark values from OEIS A000170 (including $Q(27)$).
• $Q(28)$ if reached; otherwise largest $N$ achieved with a clear complexity analysis.
• Short report: method, scaling, and comparison with FPGA/GPU backtracking solvers.
• Code submitted as a PR against the harness.

Background & references

Tensor network contraction methods

• Z.-Y. Liu, H.-J. Liao, L. Wang, Statistical mechanics of the N-queens problem, arXiv:2605.10326v2 (2026), Sec. VI; code: https://github.com/LiuZY613/nqueen-lattice-gas
• F. Pan, H. Gu, P. Springer, X. Li, Parallelizing Large-Scale Tensor Network Contraction on Multiple GPUs, arXiv:2606.01852 (2026) — multi-GPU algorithms for exact TN contraction; relevant infrastructure for scaling the N-queens network to large $N$.
• T. Xiang, Density Matrix and Tensor Network Renormalization (Cambridge, 2024)

FPGA exact enumeration (current computational frontier)

• T. B. Preußer, B. Nägel, R. G. Spallek, Putting Queens in Carry Chains, TU Dresden (2009) — distributed FPGA backtracking; first computation of $Q(26) = 22{,}317{,}699{,}616{,}364{,}044$.
• T. B. Preußer, M. R. Engelhardt, Putting Queens in Carry Chains, No. 27, J. Signal Process. Syst. 88, 185–201 (2017), https://doi.org/10.1007/s11265-016-1176-8 — exploits $D_4$ symmetry and carry-chain logic; $Q(27) = 234{,}907{,}967{,}154{,}122{,}528$ (year-long distributed FPGA run). Code & logs: https://github.com/preusser/q27
• Y. Azuma, H. Sakagami, K. Kise, An Efficient Parallel Hardware Scheme for Solving the N-Queens Problem, IEEE MCSoC (2018), pp. 16–22 — improved FPGA solver (2.58× over Preußer & Engelhardt); explicitly targets $N=28$ as future work.

GPU exact enumeration

• G. Yao, Y. Li, High-performance N-queens solver on GPU, arXiv:2511.12009 (2025) — independent reproduction of $Q(27)$ via parallel DFS.

Known counts

• OEIS A000170: https://oeis.org/A000170

Known values (OEIS A000170):

$N$	$Q(N)$
8	92
16	14,772,512
20	39,029,188,884
25	2,207,893,435,360
26	22,317,699,616,364,044
27	234,907,967,154,122,528
28	?

Start with Sec. VI of Liu et al. and the linked nqueen-lattice-gas code; no file or test entry point is named in this issue. Build an exact, untruncated contraction and validate it against OEIS A000170, including the listed Q(27) benchmark. Done means documented code, scaling results, and Q(28) if feasible, or the largest completed N with a complexity analysis.