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 New, unsolved
New entry, edited from material collected for the archive and not yet in a released version.
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
No solution was found in the collected postings.
[ 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