The OEIS is supported by the many generous donors to the OEIS Foundation.
Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #22 Jul 20 2024 14:46:13
%S 0,1,0,1,1,1,2,2,2,2,3,3,3,3,3,4,4
%N 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.
%C For n large enough, n/60 <= a(n) <= 0.241*n [Glock et al.].
%H I. P. Gent, C. A. Jefferson, and P. W. Nightingale, <a href="https://doi.org/10.1613/jair.5512">Complexity of n-Queens Completion</a>, Journal of Artificial Intelligence Research, 59, 815-848.
%H S. Glock, D. M. Correia, and B. Sudakov, <a href="https://doi.org/10.1007/s40687-022-00335-1">The n-queens completion problem</a>, Res Math Sci, 9 (2022), 41.
%H Hugo M. Nielsen, <a href="https://gist.github.com/dragonoverlord3000/8c9757bd5aeb16d6aa3af6f4a1397810">C implementation</a>
%e There are 2 solutions to the 4-queens problem:
%e . Q . .
%e . . . Q
%e Q . . .
%e . . Q .
%e and
%e . . Q .
%e Q . . .
%e . . . Q
%e . Q . .
%e 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.
%o (C) \\ see github link
%Y Cf. A000170.
%K nonn,more
%O 4,7
%A _Hugo M. Nielsen_, Jun 25 2024