How should N queens be placed on an N x N board to leave the maximum number of unattacked vacant squares?
competition/games/chess/queens.unattacked New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
How should N queens be placed on an N x N board to leave the maximum number of unattacked vacant squares? -- Mario Velucchi <velucchi@cli.di.unipi.it>
Show solution
FOR ME, THIS IS THE BEST CHESS-PUZZLE
by Mario VELUCCHI - Friday 22 September 1995
* Placing N Queens on an order-N board to leave a maximum number of
unattacked vacant cells.
- For N=8: Free = 11
7 DIFFERENT SOLUTIONS
by Johan CLAES, Mario VELUCCHI - [~C] 1995
[in the GARDNER's reference only 6 different solutions]
======================
THERE ARE THE CONJECTURED VALUES of Free(Qn), and empirical probability
(based on personal tests) [in expansion]
N Free Prob.
1 0 100%
2 0 "
3 0 "
4 1 "
5 3 "
6 5 "
7 7 "
8 11 99%
9 18 >90%
10 22 "
11 30 "
12 36 "
13 47 "
14 56 85%
15 72 "
16 82 70%
17 97 70%
18 111 50%
19 132 65%
20 145 "
21 170 "
22 186 65%
23 216 "
24 240 50%
25 260 65%
26 290 "
27 324 50%
28 360 65%
29 381 50%
30 420 "
>30 others dispositions 50/65%
======================
ROLL -
The authors of these proposed values of Free(Qn) are:
N=1 Free=0 obvious
N=2 Free=0 obvious
N=3 Free=0 obvious
N=4 Free=1 in Martin GARDNER 'Wheels, Life and Other Mathematical
Amusements' [Editor: "Amusement" in the original]
Freeman 1983
N=5 Free=3 in Martin GARDNER, ibid
N=6 Free=5 in Martin GARDNER, ibid
N=7 Free=7 in Martin GARDNER, ibid
N=8 Free=11 in Walter William Rouse BALL 'Mathematical Recreations and
Problems' Macmillan 1892
N=9 Free=18 Diego BRACAMONTE (Argentina) in 'El Acertijo' 1994
N=10 Free=22 in Martin GARDNER, ibid
N=11 Free=30 Rodolfo KURCHAN (Argentina) in 'El Acertijo' 1994
Mario VELUCCHI (Italy) - [C] 1995 [other solution]
N=12 Free=36 in Martin GARDNER, ibid
N=13 Free=47 Johan CLAES (Belgium) - [C] 1995
Mario VELUCCHI - [C] 1995 [separately]
N=14 Free=56 Hector SAN SEGUNDO (Argentina) in 'El Acertijo' 1995
[queens in one corner]
Mario VELUCCHI - [C] 1995 [queens in the four corners]
N=15 Free=72 Johan CLAES - [C] 1995
Mario VELUCCHI - [C] 1995 [separately]
N=16 Free=82 Johan CLAES - [C] 1995
N=17 Free=97 Johan CLAES, Mario VELUCCHI - [~C] 1995
N>17 every by Johan CLAES, Mario VELUCCHI, Miyoshi NAGAI (Japan) - [C] 1995
[C] - Computer Research [~C] - Computer and Human Research
======================
Different Solutions [in expansion]
by Johan CLAES, Mario VELUCCHI, Miyoshi NAGAI - [~C] 1995
N Free #
4 1 25
5 3 1
6 5 3
7 7 38
8 11 7
9 18 1
10 22 1
11 30 2
12 36 7
13 47 1
... ... ...
======================
Generalisation:
* K Queens on an order-N board
Table (best known solutions) for:
1 <= N <= 30 , 1 <= K <= (N*N) [in expansion]
by Johan CLAES, Mario VELUCCHI - [~C] 1995
Free(K, N) = free squares for K Queens in order-N board
Free(1, N) = N^2-3*N+2
Free(2, N) = N^2-5*N+7
Free(3, N) =? N^2-6*N+9
Free(4, N) =? N^2-6*N+8 for N even [Editor: "pair" in the original];
otherwise: Free(4, N) =? N^2-6*N+9
Free(>4, N) = approximate formulas
Free(N, N) = lower bound or approximate formula
by Johan CLAES, Mario VELUCCHI - 1995
[ =? it is for: NEAR ]
======================
references:
1) 'El Acertijo' Argentinean magazine of Recreational Mathematics
2) 'KONWAKAI NEWS' Japanese magazine of Recreational Mathematics
3) Private communications by Hector SAN SEGUNDO (Argentina)
4) Private communications by Johan CLAES (Belgium)
5) Private communications by Martin GARDNER (USA)
6) Private communications by Ronald L. GRAHAM (USA)
7) Private communications by Stephen [Editor: "Sthefenson" in the original] HEDETNIEMI (USA)
8) Private communications by Toshi Junk KATO (Japan)
9) My (Mario VELUCCHI - Italy) papers
-- Mario Velucchi <velucchi@cli.di.unipi.it>
[ Editor: Velucchi's revised text (last updated 19 June 1996), mailed to
the math-fun list in October 1996 and forwarded to Chris Cole. It was
sent quoted-printable; it is decoded here, and accented letters are
decoded from the PC character set. ]
###############################################################################
This Text File is Public Domain. This is available in INTERNET.
http://www.cli.di.unipi.it/~velucchi/queens.txt
This is for review/abstract in journals and magazines in all the World.
I am available for more technical details.
IF YOU PRINT THIS FILE OR REFERENCE ON, WRITE ME PLEASE.
###############################################################################
FOR ME, THIS IS THE BEST CHESS-PUZZLE
by Mario VELUCCHI
[Project Beginning: May 1995 - Last Up-Dated: 19 June 1996]
NON-Dominating Queens Problem
- Placing N Queens on an order-N board to leave a maximum number of unattacked vacant cells.
N Free(N) Prob.
1 0 100% Sure
2 0 "
3 0 "
4 1 "
5 3 "
6 5 "
7 7 "
8 11 "
9 18 "
10 22 "
11 30 "
12 36 "
13 47 "
14 56 "
15 72 "
16 82 "
17 97 probable
18 111 "
19 132 "
20 145 "
21 170 "
22 186 "
23 216 "
24 240 "
25 260 "
26 290 "
27 324 "
28 360 "
29 381 "
30 420 "
>30 others dispositions probables
[Notation: Free[N] = Maximum Known for unattacked vacant cells if i place N queens in order-N board]
======================
ROLL -
The first authors of these proposed values of Free(N) are:
N= 1 Free= 0 obvious
N= 2 Free= 0 obvious
N= 3 Free= 0 obvious
N= 4 Free= 1 in Stephen AINLEY, 1977 and Martin GARDNER, 1983 (reprint of previous Scientific American articles)
N= 5 Free= 3 in Stephen AINLEY and M. GARDNER, ibid
N= 6 Free= 5 in Stephen AINLEY and M. GARDNER, ibid
N= 7 Free= 7 in Stephen AINLEY and M. GARDNER, ibid
N= 8 Free= 11 in Walter William Rouse BALL 'Mathematical Recreations and Problems' Macmillan 1892
N= 9 Free= 18 Diego BRACAMONTE (Argentina) in 'El Acertijo' 1993
N=10 Free= 22 in Stephen AINLEY and M. GARDNER, ibid
N=11 Free= 30 Rodolfo KURCHAN (Argentina) in 'El Acertijo' 1993
Mario VELUCCHI (Italy) - [C] 1995 [new solution]
N=12 Free= 36 in Stephen AINLEY and M. GARDNER, ibid
N=13 Free= 47 Johan CLAES (Belgium), Mario VELUCCHI - [C] 1995
N=14 Free= 56 in Stephen AINLEY, ibid
Mario VELUCCHI - [C] 1995 [new solution]
N=15 Free= 72 Johan CLAES, Mario VELUCCHI - [C] 1995
N=16 Free= 82 Johan CLAES, Mario VELUCCHI - [C] 1995
N=17 Free= 97 Johan CLAES, Mario VELUCCHI - [~C] 1995
N=18 Free=111 in Stephen AINLEY, ibid
N=19 Free=132 in Stephen AINLEY, ibid
N=20 Free=145 Johan CLAES, Mario VELUCCHI - [C] 1995
N=21 Free=170 Johan CLAES, Mario VELUCCHI - [C] 1995
N=22 Free=186 in Stephen AINLEY, ibid
N>22 every by Johan CLAES, Mario VELUCCHI, Miyoshi NAGAI (Japan) - [C] 1995
[Notation: [C] - Computer Research; [~C] - Computer and Human Research]
======================
Different Solutions [in increase]
by Johan CLAES, Mario VELUCCHI, Miyoshi NAGAI - [C] 1995
N Free # Prob.
4 1 25 100% Sure
5 3 1 "
6 5 3 "
7 7 38 "
8 11 7 "
9 18 1 "
10 22 1 "
11 30 2 "
12 36 7 "
13 47 1 "
14 56 4 "
15 72 3 "
16 82 1 "
17 97 >=1
18 111 >=1
.. ... ...
for N <= 8 the first reference is by Bernd SCHWARZKOPF (Germany) in 'Die Schwalbe' [C] 1982
======================
Generalisation:
K Queens on an order-N board
- Table Free(K,N) (best known solutions) for:
1 <= N <= 30
only for Max K-Queens near equal to Free(K,N)
in Stephen AINLEY, ibid
1 <= N <= 10 1 <= K <= (N)
incomplete
by Hiroshi OKUNO (Japan) in Martin GARDNER, ibid [C]
1 <= N <= 8 1 <= K <= (N*N)
best/number of solutions
by Bernd SCHWARZKOPF in 'Die Schwalbe' [C] 1982
1 <= N <= 30 1 <= K <= (N*N) [in increase]
best/number of solutions
by Johan CLAES, Mario VELUCCHI - [C] 1995
- Formulas and Bounds [in progress]
by Johan CLAES, Mario VELUCCHI 1995
Free(K, N) = 0 for N^2-3*N+3 <= K <= N^2
Free(K, N) = 1 for N^2-5*N+8 <= K <= N^2-3*N+2 ...
this is obvious because i have:
Free(1, N) = N^2-3*N+2
Free(2, N) = N^2-5*N+7
Free(3, N) =? N^2-6*N+9
Free(4, N) =? N^2-6*N+8 for N pair; otherwise: Free(4, N) =? N^2-6*N+9
...
Free(>4, N) = others approximate formulas
- Lower, Upper Bounds and Approximate Formulas for Free(N, N), the proposed problem [in progress]
by Johan CLAES, Mario VELUCCHI, Gustavo PIÑEIRO 1995
...
- Others theoretical considerations, conjectures and theorems [in progress]
by Johan CLAES, Mario VELUCCHI, Gustavo PIÑEIRO 1995
...
[Notation: Free(K, N) = free squares for K Queens in order-N board]
======================
References/Acknowledgements:
1. Walter William Rouse BALL 'Mathematical Recreations and Problems' Macmillan 1892
2. Stephen AINLEY 'Mathematical Puzzles' G.Bell & Sons Ltd, UK 1977
3. Martin GARDNER 'Wheels, Life and Other Mathematical Amusements' Freeman 1983
I. 'Jouer Jeux Mathématiques' (French journal specific on Recreational Mathematics)
II. 'mathematical digest' (South African magazine)
III. 'springaren' (Swedish journal specific on Chess Problems)
IV. 'Technology Review - MIT Students special edition' Allan J. GOTTLIEB's Puzzle Corner (USA)
V. 'Die Schwalbe' (German journal specific on Chess Problems)
VI. 'El Acertijo' (Argentinean journal specific on Recreational Mathematics)
VII. 'KONWAKAI NEWS' (Japanese journal specific on Recreational Mathematics)
VIII. 'SHARADA' (Russian journal specific on Recreational Mathematics)
IX. 'Scientific American' Martin GARDNER's Mathematical Games Column (USA)
a. Personal communications by Allan J. GOTTLIEB (USA)
b. Personal communications by Bernd SCHWARZKOPF (Germany)
c. Personal communications by Dario URI (Italy)
d. Personal communications by Gustavo PIÑEIRO (Argentina)
e. Personal communications by Hèctor SAN SEGUNDO (Argentina)
f. Personal communications by J.H. WEBB (South Africa)
g. Personal communications by Johan CLAES (Belgium)
h. Personal communications by Martin GARDNER (USA)
i. Personal communications by Michel CRITON(France)
j. Personal communications by Miyoshi NAGAI (Japan)
k. Personal communications by Ronald L. GRAHAM (USA)
l. Personal communications by Stephen HEDETNIEMI (USA)
m. Personal communications by Toshi Junk KATO (Japan)
n. Personal communications by Vladimir N. RIBINSKY (Russia)
o. My papers (Mario VELUCCHI - Italy)
======================
Mario VELUCCHI
Via Emilia, 106
I-56121 Pisa - ITALY
e-mail: velucchi@cli.di.unipi.it
http://www.cli.di.unipi.it//~velucchi/intro.html
======================
Two nice DIAGRAMS (very small selection):
...
...
+ - + + + + - -
+ - + + + - - -
+ + + + + - - +
Q + Q + + + + +
Q + + + + + + +
Q + + + Q + + +
+ + + + + + - -
+ + Q Q Q + + +
8 : free = 11
+ Q + + + + Q +
Q + Q + + + Q +
+ Q + + + + + +
+ + + + + - + -
+ + + + - + + -
+ + + - + - + -
Q Q + + + + + +
+ + + - - - + -
8 : free = 11
...
-- Mario Velucchi <velucchi@cli.di.unipi.it>