A171760 The maximum number of sets of n queens which can be placed on an n X n chessboard such that no queen attacks another queen in the same set.

0, 1, 0, 0, 2, 5, 4, 7, 6, 7, 8, 11, 12, 13, 14, 15, 16, 17

Offset: 0

Author

Howard A. Landman, Dec 17 2009

Keywords

• nonn
• hard
• more

Comments

a(n) is nonzero for n >= 4 (there is always at least one solution to the n-queens problem). a(n) <= n (because n sets of n queens fill up the board). a(n) = n if n = 1 or 5 (mod 6).

a(n) is at least two for all even n >= 4 since a solution and its reflection will fit on the same board. - Charlie Neder, Jul 24 2018

In addition a(18) >= 16 and a(20) = 20. - Benjamin Butin, Dec 11 2023

Examples

			a(4) = 2 because there are only two solutions to the 4-queens problem and they can both fit on the same board:
 0 1 2 0
 2 0 0 1
 1 0 0 2
 0 2 1 0
a(8) = 6 since at least 6 solutions to the 8-queens problem can fit on the same board but 7 solutions can't:
 3 0 5 2 1 6 0 4
 0 1 4 0 5 3 2 6
 4 6 0 1 2 0 5 3
 5 2 3 6 0 4 1 0
 6 4 1 5 0 2 3 0
 2 5 0 3 4 0 6 1
 0 3 2 0 6 1 4 5
 1 0 6 4 3 5 0 2
a(9) = 7
 7 5 6 3 1 . . 2 4
 6 3 . 4 2 7 1 . 5
 . . 2 7 5 6 3 4 1
 4 7 5 1 . 2 . 6 3
 3 1 4 . 6 . 7 5 2
 . 6 . 5 3 4 2 1 7
 2 4 7 6 . 1 5 3 .
 5 . 1 2 7 3 4 . 6
 1 2 3 . 4 5 6 7 .
a(10) = 8
 3 4 2 8 . . 1 7 5 6
 6 . 7 1 5 4 8 2 . 3
 . 1 5 6 7 2 3 4 8 .
 2 8 4 . 3 6 . 5 1 7
 7 . 6 5 1 8 4 3 . 2
 8 3 . 4 2 7 5 . 6 1
 5 6 8 7 . . 2 1 3 4
 4 7 3 . 8 1 . 6 2 5
 . 5 1 2 6 3 7 8 4 .
 1 2 . 3 4 5 6 . 7 8
		

Links

• Benjamin Butin, Solution for a(14) = 14
• Giovanni Resta, A C program for computing a(1)-a(11)

Crossrefs

Cf. A000170.

Extensions

a(6) and known a(7) added by Charlie Neder, Jul 24 2018

a(8)-a(10) and known a(11)-a(13) from Giovanni Resta, Jul 26 2018

a(14) from Benjamin Butin, Nov 07 2023

a(15)-a(17) from Benjamin Butin, Dec 11 2023