%I
%S 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 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 3,5,8,10,12,6,11,2,7,9,4,1,3,5,2,9,12,10
%N 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 kth queen is placed in square (k, T(n, k)).
%C History: In December 2017, work of 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 Solutions for n=48 to n=55 were found by Wolfram Schubert, around 2010, but not entered in the OEIS.
%C 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 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 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 Comments from _Don Knuth_, Jul 23 2019 (Start)
%C (i) Concerning the above question about convergence, note that (a) this is sequence A065188, and (b) such convergence is obvious.
%C (ii) The new 2019 paper by Fischetti and Salvagnin includes solutions for n = 5661, 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 (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 nqueens solution cannot be extended.
%C (iv) Here's an excerpt from a message that Matthias Engelhardt sent me on 30 Oct 2017:
%C > I do not know of a real paper where it is published; up to know, I
%C > thought it is contained in the OEIS (Online encyclopedia of integer
%C > sequences, URL http://oeis.org/A141843), but I detect now that the last
%C > updates are not done! It was Wolfram Schubert who did
%C > the last computations, and I thought he would update the OEIS. The
%C > current entry contains the solutions only to n=47. The result for n=48,
%C > 54 and 55 were computed by him only, the results for n=46, 50, 51, 52,
%C > 53 were computed by him and verified with my completely different program.
%C >
%C > I know I got the results from Wolfram; unfortunately, I cannot find them
%C > directly. Implicitly, they are contained in the big GIF image which I
%C > constructed and which is in the internet under
%C > http://www.nqueens.de/images/firstAlfa.gif. It is linked on my page
%C > http://www.nqueens.de/sub/FirstAlfa.en.html (I detected also that I must
%C > correct a header line there).
%C >
%C > I think I should update the OEIS in the next days.
%C (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 integerprogramming approach, and it's also too hard for my Algorithm X. Maybe a SAT solver would verify it though... .(End)
%H Matthias Engelhardt, <a href="/A141843/b141843.txt">Table of n, a(n) for n = 1..1892</a>, (previous version of Colin Pearson enlarged)
%H Matthias R. Engelhardt, <a href="http://nqueens.de/sub/SearchAlgorithm.en.html">The old nQueens problem</a>
%H 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 Matteo Fischetti, Domenico Salvagnin, <a href="https://arxiv.org/abs/1907.08246">Finding First and MostBeautiful Queens by Integer Programming</a>, arXiv:1907.08246 [cs.DS], 18 Jul 2019.
%H Colin S. Pearson, <a href="http://queens.cspea.co.uk/">CSP Queens  Counting Queenplacements</a>
%H Martin S. Pearson, <a href="http://queens.lyndenlea.info/">Queens On A Chessboard</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Eight_queens_puzzle">Eight Queens Puzzle</a>
%F Lim_{n>infinity} Sum_{k=1..n} T(n,k)*x^k = A065188(x).
%e Triangle begins:
%e n\k [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]
%e [1] 1;
%e [2] 0, 0;
%e [3] 0, 0, 0;
%e [4] 2, 4, 1, 3;
%e [5] 1, 3, 5, 2, 4;
%e [6] 2, 4, 6, 1, 3, 5;
%e [7] 1, 3, 5, 7, 2, 4, 6;
%e [8] 1, 5, 8, 6, 3, 7, 2, 4;
%e [9] 1, 3, 6, 8, 2, 4, 9, 7, 5;
%e [10] 1, 3, 6, 8, 10, 5, 9, 2, 4, 7;
%e [11] 1, 3, 5, 7, 9, 11, 2, 4, 6, 8, 10;
%e [12] 1, 3, 5, 8, 10, 12, 6, 11, 2, 7, 9, 4;
%e [13] ...
%e For n=8 the lexicographically smallest solution for the 8queens problem is 1,5,8,6,3,7,2,4.
%o (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,n3)!*n,n!, ok(numtoperm(n,i))&& return(numtoperm(n,i))); vector(n)} \\ _M. F. Hasler_, Jan 20 2019
%Y Cf. A065188, A140450, A000170.
%K nonn,tabl
%O 1,7
%A _Colin S. Pearson_, Jul 10 2008, Aug 16 2008
%E 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 kth 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 Comments rewritten by _Matthias Engelhardt_, Jan 28 2018
