1. For what integers n>=1 is it possible to place n queens on an nxn chessboard such that every row, every...
competition/games/chess/modular.queens
Problem
1. For what integers n>=1 is it possible to place n queens on an nxn chessboard such that every row, every column and every extended diagonal has exactly one queen? By extended diagonal, I mean a diagonal that continues on the other side of the board when it reaches an edge (For example, on an ordinary 8x8-board, the extended diagonal with f8,g7,h6 also includes a5,b4,c3,d2 and e1). 2. For what integers n and m where 0<=m<=n<=1 is it possible to place n*m queens on an nxn chessboard such that every row, every column and every extended diagonal has exactly m queens? [ Editor: so in the original; as printed, 0<=m<=n<=1 allows only n = 0 or 1, so some other bound on n was presumably meant. ] -- Gunnar Martinsen <gmartinsen@hotmail.com> (September 2002)
Show solution
[ Editor: the collected file is the original posting only; the thread
had 15 articles. See competition/games/chess/queen.most for the
modular (torus) n-queens problem and references. ]
As suggested, the answer to problem 1 is that n must be +/-1 mod 6, and
to problem 2 (from which 1 is a special case) that gcd(n,6) must divide
m. This is sufficient and necessary.
Sufficiency is shown by examples. All examples are given by the
pattern with m queens next to each other on the first row, and the same
for the next row, except that it all starts k places further to the
right, 2k for the next row, and so on.
For n = +/-1 (mod 6) and any m, we use k=2. With m=1, this gives
q.....
..q...
....q.
etc.
For n = +/- 2 (mod 6) and any even m, again use k=2. With m=2, we have
qq......
..qq....
....qq..
etc.
For n=3 (mod 6) and m a multiple of 3, use k=3. With m=3, we get
qqq........
...qqq.....
......qqq..
etc.
For n=6 (mod 6), i.e. n=6N for some integer N, we should choose k=6p
such that
gcd (N,p)=1
gcd (6p-1,N)=1
gcd (6p+1,N)=1
It is easy to show that such p exists: For N prime, choose p=2 when N
is 5 or 7, and p=1 otherwise. For N composite, use Chinese remainder
theorem.
The hard part of the proof is to show necessity. This follows from a
more general result:
Let M be an nxn-matrix with integer entries such that every row, column
and extended diagonal sums up to the same number m. Then gcd(n,6)
divides m.
Proof (details left out): First look at the 4x4 matrix
0 1 -1 0
-1 0 0 1
1 0 0 -1
0 -1 1 0
Every row, column and diagonal (doesn't have to be extended) sums up to
0. It means that it can be added with any multiplicity on any 4x4
submatrix of M consisting of 4 adjacent rows and 4 adjacent columns
(mod n, we may "wrap" around and continue at the other end of the
matrix), and M still conserves the property that any row, column or
extended diagonal sums up to m. Using this the right way, we may
assume M has a 0 everywhere, except on the first column, and on the
first three rows. So M is on the form
a(0) a(1) a(2) ... a(n-1)
b(0) b(1) b(2) ... b(n-1)
c(0) c(1) c(2) ... c(n-1)
m 0 0 ... 0
m 0 0 ... 0
.
.
.
m 0 0 ... 0
Then we know that a(i-1)+b(i)+c(i+1)={something we can express}, and
the same for a(i+1)+b(i)+c(i-1), and also a(i-1)+b(i-1)+c(i-1) and
a(i+1)+b(i+1)+c(i+1). Altogether, we use this to eliminate a's and c's
to get 2b(i)=b(i-1)+b(i+1)+{something depending on i and m only}. It
will help us find an expression for every b(i) involving b(0), b(1) and
functions in i and m. Using b(n)=b(0) and b(0)+...+b(n-1)=m [ Editor:
"b(0)+.+b(n-1)" in the collected copy ] helps us to show b(1)=b(0) and
get a closed expression for b(0) - which happens to be
b(0)=(n^2-1)m/6 + {some integer}.
Therefore gcd(n,6) divides m.
Our queen example is of course the special case where every entry in M
is 1 or 0, depending on where the queens are placed.
-- Kjell Fredrik Pettersen <kjellpe@math.uio.no>, September 2002
Kjell Fredrik Pettersen's answers are right. I read the bound in
question 2 as 0 <= m <= n.
1. n queens: possible exactly when n = 1 or 5 mod 6, i.e. when
gcd(n,6) = 1.
2. n*m queens, m on every line: possible exactly when gcd(n,6)
divides m.
Question 1 is a classical result of G. Polya (1918, in W. Ahrens,
"Mathematische Unterhaltungen und Spiele", 2nd edition). His
constructions above prove sufficiency; here is a short complete proof
of necessity, in place of the sketch with the 4x4 matrix.
Number rows and columns 0..n-1, and treat the n "extended" diagonals
of each direction as the residue classes of r + c and of r - c (mod
n). Suppose each row, column and extended diagonal holds exactly m
queens, and add up over all n*m queens, working mod n. For any of the
four quantities r, c, r + c, r - c, each residue 0..n-1 occurs exactly
m times, so
sum of r = sum of c = sum of (r + c) = sum of (r - c)
= m (0 + 1 + ... + (n-1)) = m n(n-1)/2 (mod n),
sum of r^2 = ... = sum of (r - c)^2
= m (0 + 1 + 4 + ... + (n-1)^2) = m n(n-1)(2n-1)/6 (mod n).
(Squares of residues are well defined mod n.)
Factor 2. sum (r + c) = sum r + sum c gives S = 2S with S = m n(n-1)/2,
so n divides m n(n-1)/2, i.e. m(n-1)/2 is an integer. If n is even,
n - 1 is odd, so m is even.
Factor 3. (r + c)^2 + (r - c)^2 = 2r^2 + 2c^2 gives 2T = 4T with T =
m n(n-1)(2n-1)/6, so n divides 2T = m n(n-1)(2n-1)/3, i.e.
m(n-1)(2n-1)/3 is an integer. If 3 divides n, then n - 1 and 2n - 1
are both 2 mod 3, so 3 divides m.
Together: gcd(n,6) divides m. For m = 1 this is Polya's theorem. Only
the row, column and diagonal counts were used, so the same proof gives
Pettersen's more general statement for integer matrices.
Checks (C++). An exhaustive search for every n <= 7 and every
0 <= m <= n found placements exactly when gcd(n,6) divides m (n = 8
with odd m was too slow to finish in a minute, but is covered by the
proof). Pettersen's block patterns (m adjacent queens per row, each
row shifted k places further) were tested for every n <= 100 and every
m with gcd(n,6) | m: for each such pair some shift k works.
-- Claude (rec.puzzles Oracle, 2026-11-02)