Colin S. Pearson - cp's OEIS frontend

User: Colin S. Pearson

Colin S. Pearson has authored 2 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)).

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, 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, 3, 5, 8, 10, 12, 6, 11, 2, 7, 9, 4, 1, 3, 5, 2, 9, 12, 10

Offset: 1

Colin S. Pearson, Jul 10 2008, Aug 16 2008

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.
Solutions for n=48 to n=55 were found by Wolfram Schubert, around 2010, but not entered in the OEIS.
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.
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.
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.
Comments from Don Knuth, Jul 23 2019: (Start)
(i) Concerning the above question about convergence, note that (a) this is sequence A065188, and (b) such convergence is obvious.
(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.
(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.
(iv) Here's an excerpt from a message that Matthias Engelhardt sent me on 30 Oct 2017:
> I do not know of a real paper where it is published; up to know, I
> thought it is contained in the OEIS (Online encyclopedia of integer
> sequences, URL http://oeis.org/A141843), but I detect now that the last
> updates are not done! It was Wolfram Schubert who did
> the last computations, and I thought he would update the OEIS. The
> current entry contains the solutions only to n=47. The result for n=48,
> 54 and 55 were computed by him only, the results for n=46, 50, 51, 52,
> 53 were computed by him and verified with my completely different program.
>
> I know I got the results from Wolfram; unfortunately, I cannot find them
> directly. Implicitly, they are contained in the big GIF image which I
> constructed and which is in the internet under
> http://www.nqueens.de/images/firstAlfa.gif. It is linked on my page
> http://www.nqueens.de/sub/FirstAlfa.en.html (I detected also that I must
> correct a header line there).
>
> I think I should update the OEIS in the next days.
(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)

			Triangle begins:
n\k  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]  [10] [11] [12]
[1]  1;
[2]  0,   0;
[3]  0,   0,   0;
[4]  2,   4,   1,   3;
[5]  1,   3,   5,   2,   4;
[6]  2,   4,   6,   1,   3,   5;
[7]  1,   3,   5,   7,   2,   4,   6;
[8]  1,   5,   8,   6,   3,   7,   2,   4;
[9]  1,   3,   6,   8,   2,   4,   9,   7,   5;
[10] 1,   3,   6,   8,   10,  5,   9,   2,   4,   7;
[11] 1,   3,   5,   7,   9,   11,  2,   4,   6,   8,   10;
[12] 1,   3,   5,   8,   10,  12,  6,   11,  2,   7,   9,   4;
[13] ...
For n=8, the lexicographically smallest solution for the 8-queens problem is 1,5,8,6,3,7,2,4.

Matthias Engelhardt, Table of n, a(n) for n = 1..1892 (previous version of Colin Pearson enlarged)
Matthias R. Engelhardt, The old nQueens problem.
Matteo Fischetti, Domenico Salvagnin, Chasing First Queens by Integer Programming, 2018.
Matteo Fischetti, Domenico Salvagnin, Finding First and Most-Beautiful Queens by Integer Programming, arXiv:1907.08246 [cs.DS], 18 Jul 2019.
Colin S. Pearson, CSP Queens - Counting Queen-placements.
Martin S. Pearson, Queens On A Chessboard.
Wikipedia, Eight Queens Puzzle.

Cf. A065188, A140450, A000170.

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

Limit_{n->oo} Sum_{k=1..n} T(n,k)*x^k = A065188(x).

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

Comments rewritten by Matthias Engelhardt, Jan 28 2018

A140450 The count of how many queens must be placed tentatively onto a board while seeking a first solution to the "N-Queens on an N x N chessboard" puzzle.

Original entry on oeis.org

1, 6, 18, 26, 15, 171, 42, 876, 333, 975, 517, 3066, 1365, 26495, 20280, 160712, 91222, 743229, 48184, 3992510, 179592, 38217905, 584591, 9878316, 1216775, 10339849, 12263400, 84175966, 44434525, 1692888135, 408773285, 2799725104, 4618568460

Offset: 1

Colin S. Pearson and Martin S. Pearson, Jun 26 2008, Jun 30 2008, Jul 03 2008, Jul 31 2008, Aug 16 2008

nonn

The term a(4) with the value 26 is the count for a board size of 4 squares by 4 squares. The highest term so far a(45) is the count for a board of 45 squares by 45 squares.

This whole sequence refers only to the number of queen pieces placed tentatively on a board in the hunt for the FIRST POSSIBLE solution for each board size. This sequence makes no reference to queen placements needed to hunt for subsequent solutions that are possible for board sizes above 3x3.

			Using a simple, mechanical and naive "one queen at a time" algorithm (in other words, a computer-friendly algorithm), in order to place 4 non-clashing queens on a simple board of 4 x 4 squares, we will need to place a tentative new queen 26 times before we discover the first combination that allows all queens to sit unchallenged. For a board size of 5 x 5 we will need to place tentative new queens just 15 times before we discover the first combination of 5 unchallenged queens. In this extended and corrected sequence, those figures "26" and "15" are the values of terms a(4) and a(5) above.

CSP Queens - Counting Queen-placements http://queens.cspea.co.uk/

Colin S. Pearson, Table of n, a(n) for n = 1..45 [Corrected Jul 31 2008]
Colin S. Pearson, CSP Queens - Counting Queen-placements
Martin S. Pearson, Queens On A Chessboard
Wikipedia, Eight Queens puzzle

Cf. A000170 = Number of ways of placing n nonattacking queens on n X n board; A002562 = Number of ways of placing n nonattacking queens on n X n board (symmetric solutions count only once); A141843 = Triangular array of lexicographically earliest solutions to the n queens problem.

Edited by Colin S Pearson to update the URL for Martin S Pearson's website Colin S. Pearson, Mar 25 2009

cp's OEIS Frontend

User: Colin S. Pearson

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)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions