toroidal n-queens problem
he...@magenta.ira.uka.de
For all n<18 there is a solution for the toroidal n-queens problem
if and only if n mod 6 in {1,5} .
For all n with n mod 6 in {1,5} there is a simple solution:
The queens are placed diagonally in a "knight`s move distance".
Now the question:
Is there any solution known for n with n mod 6 not in {1,5} ??!
Remember the classical n-queens problem has a solution for any n>3.
Heinz Braun (e-mail: br...@ira.uka.de)
Richard Lee
Heinz Braun asks:
Answer:
There is NO toroidal solution for n mod 6 not in {1,5}. There are
several independent proofs of this in the literature.
References:
Chandra, A: "Independent Permutations, as Related to a Problem of Moser
and a Theorem of Polya"; in _Journal of Combinatorial Theory_, (A) 16
(1974), p. 111-120.
Hedayat, A: "A Complete Solution to the Existence and Nonexistence of
Knut Vik Designs and Orthogonal Knut Vik Designs"; in _Journal of
Combinatorial Theory_, (A) 22 (1977), p. 331-337.
Klove, T: "The Modular n-Queen Problem:; in _Discrete Mathematics_, 19
(1977), p. 289-291.
Lee, R: _Chessboard Colorings and an Extension of Latin Squares_; MS
Thesis, Univ. of Ill., Urbana, Jul. 1978.
Polya, G: "Uber die 'doppelt-periodischen' Losungen des n-Damen
Problems"; in W. Ahrens _Mathematische Unterhaltungen und Spiele_,
p. 364-374, Tuebner, Leipzig, 1918.
Shapiro, H: _Theoretical Limitations on the Use of Parallel Memories_;
PhD Thesis, Univ. of Ill., Urbana, Dec. 1975.
--
RICHARD LEE rl...@ads.com or ...!{sri-spam | ames}!zodiac!rlee
415-960-7300 ADS, 1500 Plymouth St., Mtn. View CA 94043-1230
Scott Amspoker
>Heinz Braun asks:
>
> For all n<18 there is a solution for the toroidal n-queens problem
> if and only if n mod 6 in {1,5} .
>Answer:
>
>There is NO toroidal solution for n mod 6 not in {1,5}. There are
>several independent proofs of this in the literature.
Folks, I feel *really* stupid - but I don't understand the problem.
I'm familiar with the traditional n-queens problem but not the
"toroidal" version. What special restrictions apply here?
--
Scott Amspoker
Basis International, Albuquerque, NM
(505) 345-5232
unmvax.cs.unm.edu!bbx!bbxsda!scott
Ilan Vardi
For n mod 6 not in {1,5} the maximum number of toroidal queens is n-1 or
n-2 which is proved in a American Math Monthly problem ``superqueens''
with the solution appearing in 1988 or 1989.
For the general queens problem, Igor Rivin and I found the lower bound
2^{n/4} for almost all n for the number of solutions.
There is also Zabih's theorem: The n-queens problem has a solution for n=1.