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

[navyTensor]

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	?