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,2

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

Links

Table of n, a(n) for n=1..16.

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

Example

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).

Crossrefs

Cf. A000170, A146304.

Sequence in context: A074896 A015713 A049198 * A344999 A203205 A330375

Adjacent sequences: A146300 A146301 A146302 * A146304 A146305 A146306

Keyword

hard,nonn,more

Author

Paolo Bonzini, Oct 29 2008

Extensions

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

Status

approved