login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)). 5

%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 k-th 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 = 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 (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 (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 integer-programming 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 Most-Beautiful 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 Queen-placements</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 8-queens 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,n-3)!*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 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 Comments rewritten by _Matthias Engelhardt_, Jan 28 2018

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 24 23:25 EDT 2021. Contains 346273 sequences. (Running on oeis4.)