An Exact 2-Body Transfer Matrix Formulation and Telescoping Boundary Framework for the Non-Attacking Queens Problem

The exact enumeration of non-attacking queen configurations on an N × N board (Q(N ), OEIS A000170) has historically been approached via various search strategies. Instead of searching for completed non-attacking boards, in this work we approach the problem by specifically calculating the number of boards eliminated from contention whenever a queen is placed. The sets of boards eliminated by potential attacking pairs and invalid combinations are tracked according to values in Pascal’s triangle, which permits analysis of eliminations based on each square’s symmetry orbit. Recognizing that no square can be attacked by more than two other non-attacking queens, we invoke the Pigeonhole Principle to prove that diagonal collisions of non-attacking queens are strictly a pairwise 2-body interaction. Using the Hockey-Stick (Chu-Shih-chieh) identity on the eliminations recorded in Pascal’s Triangle, we demonstrate that the eliminations for any single square can be represented as a signed 2-sparse boundary pair, which yields a closed-form recurrence for each partial configuration capacity. Finally, we formulate the global counting problem as a contracted trace of rank-contracting transfer matrices over a compressed D4-symmetric state space, verifying the exactness of the formulation against ground-truth benchmarks for both even and odd board dimensions. AI Disclosure: Formal mathematical notation, proof layout (Theorem 1, Lemma 2), and Transfer-Matrix derivations were conducted with the analytical assistance of Google Gemini (Large Language Model), as detailed in the paper's Generative AI Disclosure statement.