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
Offset: 4
Examples
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.
Links
- 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
Crossrefs
Cf. A000170.
Programs
-
C
\\ see github link
Comments