A146303 Number of distinct ways to place queens (even fewer than n) on an n X n chessboard so that no queen is attacking another and that it is not possible to add another queen.

1, 4, 9, 18, 58, 348, 1862, 10188, 57600, 376692, 2640422, 19469324, 151978440, 1258451524, 10963084588, 100087600184

Offset: 1

Author

Paolo Bonzini, Oct 29 2008

Keywords

• hard
• nonn
• more

Comments

In other words, number of maximal independent vertex sets (and minimal vertex covers) in the n X n queen graph. - Eric W. Weisstein, Jun 20 2017

Examples

			The a(2) = 4 solutions are to place a single queen in each of the squares of the chessboard. For n=3, there is a single one-queen solution (placing the queen in b2) and eight two-queen solutions, but no three-queen solution (see A000170).
		

Links

• S. W. Golomb and L. D. Baumert, Backtrack Programming, Journal of the ACM, 4 (2001), 516-524.
• Stefan Kral, C++11 code using OpenMP
• Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
• Eric Weisstein's World of Mathematics, Minimal Vertex Cover
• Eric Weisstein's World of Mathematics, Queen Graph

Crossrefs

Cf. A000170, A146304.

Extensions

a(12)-a(16) from Stefan Kral, Aug 10 2016