Queen Problem: Torsten Sillke, 01.01.96 -------------- The n-queen problem: Let Q(n) be number of permutations of 1..n, which satisfy (*) sigma(i) - i != sigma(j) - j for all i != j (**) sigma(i) + i != sigma(j) + j for all i != j The conditions (*) and (**) avoid two on a diagonal The n-semiqueen problem: Let S(n) be number of permutations of 1..n, which satisfies (*) sigma(i) - i != sigma(j) - j for all i != j. The modular n-queen problem: Let M(n) be number of permutations of 1..n, which satisfy (*) sigma(i) - i != sigma(j) - j (modulo n) for all i != j (**) sigma(i) + i != sigma(j) + j (modulo n) for all i != j The conditions (*) and (**) avoid two on a diagonal Example: a modular 5-queen solution . . . o . o . . . . . . o . . . . . . o . o . . . The best known upper bound is: Q(n) <= S(n) <= n!. The best known lower bound is: S(n) >= Q(n) >= polynomial(n) Question: --------- - Construct a exponential lower bound. - Find a nontrivial upper bound. Remark: The expected number of solutions for the independent diagonal heuristic is: E(Q(n)) = n! / exp(n). References: - Ilan Vardi // ilan@leland.Stanford.EDU (ilan vardi) Computational Recreations in Mathematica - Ilan Vardi AMM 1995 (bounds for semi-queens) - T. Klove, Disc. Math. 19 (1977) 289-291, 36 (1981) 33-48 (modular-queens) -------------------------------------------------------------------------------- Subject: Re: 8 chess queens Date: 15 Sep 1997 12:32:36 -0400 From: rhoads@necturus.rutgers.edu (Glenn Rhoads) Organization: Rutgers University LCSR Newsgroups: alt.brain.teasers, rec.puzzles # unique n #solutions solutions * ********** ********* 1 1 1 2 0 0 3 0 0 4 2 1 5 10 2 6 4 1 7 40 6 8 92 12 9 352 46 10 724 92 11 2,680 341 12 14,200 1,787 13 73,712 9,233 14 365,596 45,752 15 2,279,184 285,053 16 14,772,512 1,846,955 17 95,815,104 11,977,939 18 666,090,624 83,263,591 19 4,968,057,848 20 39,029,188,884 -- Glenn C. Rhoads http://eden.rutgers.edu/~rhoads/ Rutgers University Phone: (908) 445-4634 ext.23 Dept. of Computer Science email: rhoads@paul.rutgers.edu Piscataway, NJ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Date: 2 Sep 1998 09:50:15 GMT From: qscgz@aol.com (QSCGZ) Organization: AOL Bertelsmann Online GmbH & Co. KG http://www.germany.aol.com Newsgroups: rec.puzzles here is the generalization for those, who want to try other colored queens puzzles: let q(q_1,...,q_c;n) ["colored queens numbers"] be the number of different(=nonsymmetric) ways to place q_i queens of color i [i=1 to c] on a n*n-chessboard such that no two queens of different colors attack each other. then we have: q(4,5,6;8)=4 q(1,1,1,1,1,1,1,1;8)=12 q(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1;21)=39333324973 q(7,13;8)=1 q(9,10;8)=3 q(3,5;5)=1 q(1,1;8)=248 q(2,3,4,5;8)=0 ... additions or references (or corrections ?) are welcome - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Date: 27 May 2000 11:27:01 GMT From: qscgz@aol.com (QSCGZ) Organization: AOL http://www.aol.com Newsgroups: rec.puzzles Glenn C. Rhoads wrote: >..In the following table, Q(n) is the total number of solutions >and R(n) is the number of solutions where rotations and reflections >are considered the same. I haven't seen independent confirmation >of the last 3 or 4 values of R(n) > >(use fixed font to see the columns lined up nicely) > > > n Q(n) R(n) > * **** **** > 1 1 1 > 2 0 0 > 3 0 0 > 4 2 1 > 5 10 2 > 6 4 1 > 7 40 6 > 8 92 12 > 9 352 46 >10 724 92 >11 2,680 341 >12 14,200 1,787 >13 73,712 9,233 >14 365,596 45,752 >15 2,279,184 285,053 >16 14,772,512 1,846,955 >17 95,815,104 11,977,939 >18 666,090,624 83,263,591 >19 4,968,057,848 621,012,754 >20 39,029,188,884 that's correct so far. It continues : 20 4,878,666,808 21 314,666,222,712 39,333,324,973 22 2,691,008,701,644 336,376,244,042 23 24,233,937,684,440 3,029,242,658,210 24 ? It's easy to obtain R(n) from Q(n) and vice versa by Polya's Theorem , since symmetric-solution counts are much easier to obtain : upto ~35 (2-fold-symmetry) and ~55 (4-fold-symmetry). --qscgz