Theorem 2 (Pólya) — a modular n-Queens solution n-embedded along an m-Queens solution solves (n·m)-Queens
ProvedNQueensComp.NPC.theorem_2modular-n-queensn-queensp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Theorem 2 (Pólya). If is a modular solution to the -Queens problem and is any solution to the -Queens problem, then
is a solution to the -Queens problem, i.e. to the -Queens problem.
In chessboard terms: replace every empty square of an -Queens solution by an empty board and every queen by a modular -Queens solution. The reduction of Definition 10 builds its frame this way from and .
Differences from the source:
- encoding: the n × m-Queens problem → the (n·m)-Queens problem
IsNQueensSol (n * m); reason: the paper's n × m board is the board of size nm (it replaces each square of an m × m board by an n × n board)
Preamble
import Mathlib import Definitions.Def_NQueensComp_NPC_Queens
Formal statement
namespace NQueensComp.NPC
/-- Theorem 2 (Pólya), p. 819: if `Q₁` is a modular solution to the `n`-Queens problem and `Q₂`
is a solution to the `m`-Queens problem, then `Q₁ + nQ₂` is a solution to the `(n·m)`-Queens
problem. -/
theorem theorem_2 (n m : ℕ) (Q₁ Q₂ : Finset Queen) (h₁ : IsModularSol n Q₁)
(h₂ : IsNQueensSol m Q₂) : IsNQueensSol (n * m) (sumSet Q₁ (scaleSet n Q₂)) := by sorry
end NQueensComp.NPC
Source
Gent, Jefferson & Nightingale, Complexity of n-Queens Completion, J. Artif. Intell. Res. 59 (2017), p. 819, Theorem 2 (Bell & Stevens 2009, Thm. 6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.