Skip to main content
MathOverflow

Return to Question

added OEIS reference, and added new values to table
Source Link
ho boon suan
ho boon suan
  • 667
  • 1
  • 7
  • 16

The $n$ queens problem asks if we can place $n$ queens on an $n\times n$ chessboard such that no two queens attack one another. For example, when $n=8$, here are two solutions (images taken from Wikipedia): Two of the twelve fundamental solutions to the 8 queens problem. The solution on the right has three queens that lie on a line, at positions b3, e4, and h5. (They happen to be evenly spaced here, but that is not necessary in general.) The solution on the left however is such that no three queens lie on a line. No such configurations exist when $n=5,6,7$.

Question. Suppose $n\ge8$. Is there an $n$ queens configuration with no three queens on a line (of any slope whatsoever)?

What is known? Sam Loyd observed in 1897 that Solution 10 above has no three queens on a line. In August 2012, the problem of finding such configurations was posed on HackerRank, and it was quickly determined that solutions exist for $8\le n\le1000$, with many of the fastest programs using the min-conflicts algorithm. In June 2016, Bad_Jim (James Hollis) counted the number of configurations for $n = 9, 11, 13, \dots, 21$. In February 2023, joriki (Felix Pahl) counted configurations for $8\le n\le 16$. The known values are:

\begin{array}{c|cc} n&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&19&21\\\hline \text{s}&0&0&1&0&0&0&1&4&5&12&53&174&555&2344&8968&?&?&?\\ \text{t}&0&0&2&0&0&0&8&32&40&96&410&1392&4416&18752&71486&235056&4285920&94619480\end{array}\begin{array}{c|cc} n&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21\\\hline \text{s}&0&0&1&0&0&0&1&4&5&12&53&174&555&2344&8968&?&?&?&?&?\\ \text{t}&0&0&2&0&0&0&8&32&40&96&410&1392&4416&18752&71486&235056&1001972&4285920&21887710&94619480\end{array}

Here, the first row gives the number of configurations up to symmetries (rotations and reflections), while the second row gives the total number of configurations. (These sequences will be added toThe total count is now on the OEIS; see OEIS soonA365437.) See also exercise 7.2.2.3–502 of Don Knuth’s book The Art of Computer Programming for one way of finding all solutions for given $n$ by treating the problem as a “multiple covering with colors” (MCC) problem (a generalization of the exact cover problem). Finally, I remark on the similarity to problems such as the no-three-in-line problem and the cap set problem — results of Cooper and Solymosi [Annals of Combinatorics 9 (2005), 169–175] imply that no solutions avoiding three queens on a line exist in the case of the toroidal chessboard $(\mathbf Z/p\mathbf Z)^2$ for $p>2$ prime, even though $p$ queen configurations on the toroidal chessboard do exist for $p\ge5$ prime, by a 1918 theorem of Pólya.

The $n$ queens problem asks if we can place $n$ queens on an $n\times n$ chessboard such that no two queens attack one another. For example, when $n=8$, here are two solutions (images taken from Wikipedia): Two of the twelve fundamental solutions to the 8 queens problem. The solution on the right has three queens that lie on a line, at positions b3, e4, and h5. (They happen to be evenly spaced here, but that is not necessary in general.) The solution on the left however is such that no three queens lie on a line. No such configurations exist when $n=5,6,7$.

Question. Suppose $n\ge8$. Is there an $n$ queens configuration with no three queens on a line (of any slope whatsoever)?

What is known? Sam Loyd observed in 1897 that Solution 10 above has no three queens on a line. In August 2012, the problem of finding such configurations was posed on HackerRank, and it was quickly determined that solutions exist for $8\le n\le1000$, with many of the fastest programs using the min-conflicts algorithm. In June 2016, Bad_Jim (James Hollis) counted the number of configurations for $n = 9, 11, 13, \dots, 21$. In February 2023, joriki counted configurations for $8\le n\le 16$. The known values are:

\begin{array}{c|cc} n&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&19&21\\\hline \text{s}&0&0&1&0&0&0&1&4&5&12&53&174&555&2344&8968&?&?&?\\ \text{t}&0&0&2&0&0&0&8&32&40&96&410&1392&4416&18752&71486&235056&4285920&94619480\end{array}

Here, the first row gives the number of configurations up to symmetries (rotations and reflections), while the second row gives the total number of configurations. (These sequences will be added to the OEIS soon.) See also exercise 7.2.2.3–502 of Don Knuth’s book The Art of Computer Programming for one way of finding all solutions for given $n$ by treating the problem as a “multiple covering with colors” (MCC) problem (a generalization of the exact cover problem). Finally, I remark on the similarity to problems such as the no-three-in-line problem and the cap set problem — results of Cooper and Solymosi [Annals of Combinatorics 9 (2005), 169–175] imply that no solutions avoiding three queens on a line exist in the case of the toroidal chessboard $(\mathbf Z/p\mathbf Z)^2$ for $p>2$ prime, even though $p$ queen configurations on the toroidal chessboard do exist for $p\ge5$ prime, by a 1918 theorem of Pólya.

The $n$ queens problem asks if we can place $n$ queens on an $n\times n$ chessboard such that no two queens attack one another. For example, when $n=8$, here are two solutions (images taken from Wikipedia): Two of the twelve fundamental solutions to the 8 queens problem. The solution on the right has three queens that lie on a line, at positions b3, e4, and h5. (They happen to be evenly spaced here, but that is not necessary in general.) The solution on the left however is such that no three queens lie on a line. No such configurations exist when $n=5,6,7$.

Question. Suppose $n\ge8$. Is there an $n$ queens configuration with no three queens on a line (of any slope whatsoever)?

What is known? Sam Loyd observed in 1897 that Solution 10 above has no three queens on a line. In August 2012, the problem of finding such configurations was posed on HackerRank, and it was quickly determined that solutions exist for $8\le n\le1000$, with many of the fastest programs using the min-conflicts algorithm. In June 2016, Bad_Jim (James Hollis) counted the number of configurations for $n = 9, 11, 13, \dots, 21$. In February 2023, joriki (Felix Pahl) counted configurations for $8\le n\le 16$. The known values are:

\begin{array}{c|cc} n&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21\\\hline \text{s}&0&0&1&0&0&0&1&4&5&12&53&174&555&2344&8968&?&?&?&?&?\\ \text{t}&0&0&2&0&0&0&8&32&40&96&410&1392&4416&18752&71486&235056&1001972&4285920&21887710&94619480\end{array}

Here, the first row gives the number of configurations up to symmetries (rotations and reflections), while the second row gives the total number of configurations. (The total count is now on the OEIS; see A365437.) See also exercise 7.2.2.3–502 of Don Knuth’s book The Art of Computer Programming for one way of finding all solutions for given $n$ by treating the problem as a “multiple covering with colors” (MCC) problem (a generalization of the exact cover problem). Finally, I remark on the similarity to problems such as the no-three-in-line problem and the cap set problem — results of Cooper and Solymosi [Annals of Combinatorics 9 (2005), 169–175] imply that no solutions avoiding three queens on a line exist in the case of the toroidal chessboard $(\mathbf Z/p\mathbf Z)^2$ for $p>2$ prime, even though $p$ queen configurations on the toroidal chessboard do exist for $p\ge5$ prime, by a 1918 theorem of Pólya.

edited title
Link
ho boon suan
ho boon suan
  • 667
  • 1
  • 7
  • 16

The $n$-queens queens problem with no three on a line

Source Link
ho boon suan
ho boon suan
  • 667
  • 1
  • 7
  • 16

The $n$-queens problem with no three on a line

The $n$ queens problem asks if we can place $n$ queens on an $n\times n$ chessboard such that no two queens attack one another. For example, when $n=8$, here are two solutions (images taken from Wikipedia): Two of the twelve fundamental solutions to the 8 queens problem. The solution on the right has three queens that lie on a line, at positions b3, e4, and h5. (They happen to be evenly spaced here, but that is not necessary in general.) The solution on the left however is such that no three queens lie on a line. No such configurations exist when $n=5,6,7$.

Question. Suppose $n\ge8$. Is there an $n$ queens configuration with no three queens on a line (of any slope whatsoever)?

What is known? Sam Loyd observed in 1897 that Solution 10 above has no three queens on a line. In August 2012, the problem of finding such configurations was posed on HackerRank, and it was quickly determined that solutions exist for $8\le n\le1000$, with many of the fastest programs using the min-conflicts algorithm. In June 2016, Bad_Jim (James Hollis) counted the number of configurations for $n = 9, 11, 13, \dots, 21$. In February 2023, joriki counted configurations for $8\le n\le 16$. The known values are:

\begin{array}{c|cc} n&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&19&21\\\hline \text{s}&0&0&1&0&0&0&1&4&5&12&53&174&555&2344&8968&?&?&?\\ \text{t}&0&0&2&0&0&0&8&32&40&96&410&1392&4416&18752&71486&235056&4285920&94619480\end{array}

Here, the first row gives the number of configurations up to symmetries (rotations and reflections), while the second row gives the total number of configurations. (These sequences will be added to the OEIS soon.) See also exercise 7.2.2.3–502 of Don Knuth’s book The Art of Computer Programming for one way of finding all solutions for given $n$ by treating the problem as a “multiple covering with colors” (MCC) problem (a generalization of the exact cover problem). Finally, I remark on the similarity to problems such as the no-three-in-line problem and the cap set problem — results of Cooper and Solymosi [Annals of Combinatorics 9 (2005), 169–175] imply that no solutions avoiding three queens on a line exist in the case of the toroidal chessboard $(\mathbf Z/p\mathbf Z)^2$ for $p>2$ prime, even though $p$ queen configurations on the toroidal chessboard do exist for $p\ge5$ prime, by a 1918 theorem of Pólya.