cp's OEIS Frontend

A141843 Triangular array T(n,k) (n >= 1, 1 <= k <= n) read by rows: row n gives the lexicographically earliest solution to the n queens problem, or n zeros if no solution exists. The k-th queen is placed in square (k, T(n, k)).

%I A141843 #99 Jun 01 2024 12:00:07
%S A141843 1,0,0,0,0,0,2,4,1,3,1,3,5,2,4,2,4,6,1,3,5,1,3,5,7,2,4,6,1,5,8,6,3,7,
%T A141843 2,4,1,3,6,8,2,4,9,7,5,1,3,6,8,10,5,9,2,4,7,1,3,5,7,9,11,2,4,6,8,10,1,
%U A141843 3,5,8,10,12,6,11,2,7,9,4,1,3,5,2,9,12,10
%N A141843 Triangular array T(n,k) (n >= 1, 1 <= k <= n) read by rows: row n gives the lexicographically earliest solution to the n queens problem, or n zeros if no solution exists. The k-th queen is placed in square (k, T(n, k)).
%C A141843 History: In December 2017, Matteo Fischetti and Domenico Salvagnin, using Integer Linear Programming (ILP), found solutions for n=56 to n=61; they also found solutions for higher n, but not in contiguous sequence.
%C A141843 Solutions for n=48 to n=55 were found by Wolfram Schubert, around 2010, but not entered in the OEIS.
%C A141843 Entries for board size 46 X 46 (a new solution) and for board size 47 X 47 (already known to Colin Pearson) were added to this sequence in November 2011.
%C A141843 The solution for the 46 X 46 board was discovered by _Matthias Engelhardt_ on Apr 30 2011, the solution for the 47 X 47 board by _Colin S. Pearson_ on Jan 09 2008.
%C A141843 Is it known that the rows converge to (1, 3, 5, 2, 4, 9, 11, 13, 15, 6, 8, 19, 7, 22, 10, 25, 27, 29, 31, ...) ? - _M. F. Hasler_, Jan 20 2019.
%C A141843 Comments from _Don Knuth_, Jul 23 2019: (Start)
%C A141843 (i) Concerning the above question about convergence, note that (a) this is sequence A065188, and (b) such convergence is obvious.
%C A141843 (ii) The new 2019 paper by Fischetti and Salvagnin includes solutions for n = 56-61, 63, 65, 67. 69. 71, 73, 77, 79, 85. 91. 93, 97, 101, 103, 109, 115; so the first unknown case is currently n=62.
%C A141843 (iii) I think this sequence (A141843) ought to be the "archival repository" for progress on this problem (I mean, the lexicographically first solutions to the n queens problem). However, it does not yet include Schubert's previously known solutions for n between 48 and 55. Somebody should now add the Fischetti/Salvagnin results too. Each of these is a significant benchmark example, because it's not easy to prove that a partial n-queens solution cannot be extended.
%C A141843 (iv) Here's an excerpt from a message that Matthias Engelhardt sent me on 30 Oct 2017:
%C A141843 > I do not know of a real paper where it is published; up to know, I
%C A141843 > thought it is contained in the OEIS (Online encyclopedia of integer
%C A141843 > sequences, URL http://oeis.org/A141843), but I detect now that the last
%C A141843 > updates are not done! It was Wolfram Schubert who did
%C A141843 > the last computations, and I thought he would update the OEIS. The
%C A141843 > current entry contains the solutions only to n=47. The result for n=48,
%C A141843 > 54 and 55 were computed by him only, the results for n=46, 50, 51, 52,
%C A141843 > 53 were computed by him and verified with my completely different program.
%C A141843 >
%C A141843 > I know I got the results from Wolfram; unfortunately, I cannot find them
%C A141843 > directly. Implicitly, they are contained in the big GIF image which I
%C A141843 > constructed and which is in the internet under
%C A141843 > http://www.nqueens.de/images/firstAlfa.gif. It is linked on my page
%C A141843 > http://www.nqueens.de/sub/FirstAlfa.en.html (I detected also that I must
%C A141843 > correct a header line there).
%C A141843 >
%C A141843 > I think I should update the OEIS in the next days.
%C A141843 (v) Schubert's result for n=48 hasn't been verified independently, as far as I know. It was too hard for Fischetti and Salvagnin's integer-programming approach, and it's also too hard for my Algorithm X. Maybe a SAT solver would verify it though... .(End)
%H A141843 Matthias Engelhardt, <a href="/A141843/b141843.txt">Table of n, a(n) for n = 1..1892</a> (previous version of Colin Pearson enlarged)
%H A141843 Matthias R. Engelhardt, <a href="http://nqueens.de/sub/SearchAlgorithm.en.html">The old nQueens problem</a>.
%H A141843 Matteo Fischetti, Domenico Salvagnin, <a href="https://www.researchgate.net/publication/322508723_Chasing_First_Queens_by_Integer_Programming">Chasing First Queens by Integer Programming</a>, 2018.
%H A141843 Matteo Fischetti, Domenico Salvagnin, <a href="https://arxiv.org/abs/1907.08246">Finding First and Most-Beautiful Queens by Integer Programming</a>, arXiv:1907.08246 [cs.DS], 18 Jul 2019.
%H A141843 Colin S. Pearson, <a href="http://queens.cspea.co.uk/">CSP Queens - Counting Queen-placements</a>.
%H A141843 Martin S. Pearson, <a href="http://queens.lyndenlea.info/">Queens On A Chessboard</a>.
%H A141843 Wikipedia, <a href="http://en.wikipedia.org/wiki/Eight_queens_puzzle">Eight Queens Puzzle</a>.
%F A141843 Limit_{n->oo} Sum_{k=1..n} T(n,k)*x^k = A065188(x).
%e A141843 Triangle begins:
%e A141843 n\k  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]  [10] [11] [12]
%e A141843 [1]  1;
%e A141843 [2]  0,   0;
%e A141843 [3]  0,   0,   0;
%e A141843 [4]  2,   4,   1,   3;
%e A141843 [5]  1,   3,   5,   2,   4;
%e A141843 [6]  2,   4,   6,   1,   3,   5;
%e A141843 [7]  1,   3,   5,   7,   2,   4,   6;
%e A141843 [8]  1,   5,   8,   6,   3,   7,   2,   4;
%e A141843 [9]  1,   3,   6,   8,   2,   4,   9,   7,   5;
%e A141843 [10] 1,   3,   6,   8,   10,  5,   9,   2,   4,   7;
%e A141843 [11] 1,   3,   5,   7,   9,   11,  2,   4,   6,   8,   10;
%e A141843 [12] 1,   3,   5,   8,   10,  12,  6,   11,  2,   7,   9,   4;
%e A141843 [13] ...
%e A141843 For n=8, the lexicographically smallest solution for the 8-queens problem is 1,5,8,6,3,7,2,4.
%o A141843 (PARI) row(n)={my(ok(p,a,d)=!for(j=1,n, bittest(d,p[j]-j+n)&& return; bittest(a,p[j]+j)&& return; d+=1<<(p[j]-j+n); a+=1<<(p[j]+j))); for(i=if(n>2,n-3)!*n,n!, ok(numtoperm(n,i))&& return(numtoperm(n,i))); vector(n)} \\ _M. F. Hasler_, Jan 20 2019
%Y A141843 Cf. A065188, A140450, A000170.
%K A141843 nonn,tabl
%O A141843 1,7
%A A141843 _Colin S. Pearson_, Jul 10 2008, Aug 16 2008
%E A141843 We extended this sequence by adding new terms 1036 to 1128 relating to two further puzzle solutions, for board size 46 X 46 (a new solution) and for board size 47 X 47. Given that the k-th queen is placed in square (k, a(n, k)), we have added the terms (1, a(46, 1)) to (47, a(47, 47)). - _Colin S. Pearson_, Nov 04 2011
%E A141843 Comments rewritten by _Matthias Engelhardt_, Jan 28 2018