A374013 - OEIS

A374013

n-queens completion threshold. The maximum number such that placing a(n) or fewer mutually non-attacking queens on an n X n chessboard is always completeable to a full n-queen configuration.

0, 1, 0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4

(list; graph; refs; listen; history; text; internal format)

OFFSET

4,7

COMMENTS

For n large enough, n/60 <= a(n) <= 0.241*n [Glock et al.].

LINKS

Table of n, a(n) for n=4..20.

I. P. Gent, C. A. Jefferson, and P. W. Nightingale, Complexity of n-Queens Completion, Journal of Artificial Intelligence Research, 59, 815-848.

S. Glock, D. M. Correia, and B. Sudakov, The n-queens completion problem, Res Math Sci, 9 (2022), 41.

Hugo M. Nielsen, C implementation

EXAMPLE

There are 2 solutions to the 4-queens problem:

. Q . .

. . . Q

Q . . .

. . Q .

and

. . Q .

Q . . .

. . . Q

. Q . .

Neither of these has a queen in the upper left corner, so placing a queen here will definitely make the configuration non-completable, while placing no queens is completable, see the two examples.

PROG

CROSSREFS

Cf. A000170.

Sequence in context: A165116 A111656 A165118 * A342882 A025423 A284263

Adjacent sequences: A374010 A374011 A374012 * A374014 A374015 A374016

KEYWORD

nonn,more

AUTHOR

Hugo M. Nielsen, Jun 25 2024

STATUS

approved