# N Queens Problem

## Short introduction

More information on the eight queens problem is available on Wikipedia.

Is it possible to place eight chess queens on a chessboard so that no two queens attack?

Queens attack pieces on both diagonals and in the same column and row. Below is one possible placement for a chessboard with 15 × 15 squares. No one is under attack. I wonder what kind of representation does this placement have in the head of a chess grandmaster?

👑 | ||||||||||||||

👑 | ||||||||||||||

👑 | ||||||||||||||

👑 | ||||||||||||||

👑 | ||||||||||||||

👑 | ||||||||||||||

👑 | ||||||||||||||

👑 | ||||||||||||||

👑 | ||||||||||||||

👑 | ||||||||||||||

👑 | ||||||||||||||

👑 | ||||||||||||||

👑 | ||||||||||||||

👑 | ||||||||||||||

👑 |

## Recursive enumeration of placing *N* queens in Python

I am not interested in a program that will try all possible placements and count those that satisfy the condition.

Given a partial placement, is there a fast way to figure out which rows, columns and diagonals are being attacked?

Turns out there is a fast check. Queen at position (*i*,*j*) sits on four lines.
Vertical, horizontal, *y* = *x* + *c* and *y* = − *x* + *c*. Replacing *x* and *y* by
*i* and *j* we get four numbers that can be used to index an array:

*j*=*c*_{1},*i*=*c*_{2},*i*+*j*=*c*_{3},*i*−*j*=*c*_{4}.

### Program 0

```
= int(input())
N = [0]*N, [0]*N*2, [0]*N*2
Y, D1, D2 = 0
CNT def place(i: int = 0):
global CNT
if i >= N:
+= 1
CNT return
for j in range(N):
if Y[j] + D1[i+j] + D2[i-j]:
continue
=D1[i+j]=D2[i-j]=1
Y[j]+1)
place(i=D1[i+j]=D2[i-j]=0
Y[j]
place()print(CNT)
```

Program above prints the correct count that is listed on
OEIS. Calculating the number of all possible queen
placements for numbers bigger than 15 is too slow for me. It is nice that the
program is always looking at one placement. After the attempt to place the rest
of the queens – `place(i+1)`

, the arrays can be cleared and next `j`

column can
be tried for placement.

Note that Python lists work with negative indices (`i-j`

is negative in many
cases).

Printing all of the placements is also possible:

### Program 0 with prints

```
= int(input())
N = [0]*N, [0]*N*2, [0]*N*2
Y, D1, D2 = 0
CNT = [['0']*N for _ in range(N)]
S def place(i: int = 0):
if i >= N:
global CNT
+= 1
CNT print('\n'.join(''.join(s) for s in S),
='\n\n')
endreturn
for j in range(N):
if Y[j] or D1[i+j] or D2[i-j]: continue
=D1[i+j]=D2[i-j]=1
Y[j]='1'
S[i][j]+1)
place(i='0'
S[i][j]=D1[i+j]=D2[i-j]=0
Y[j]
place()print(CNT)
```

👑 | |||||

👑 | |||||

👑 | |||||

👑 | |||||

👑 | |||||

👑 |

👑 | |||||

👑 | |||||

👑 | |||||

👑 | |||||

👑 | |||||

👑 |

👑 | |||||

👑 | |||||

👑 | |||||

👑 | |||||

👑 | |||||

👑 |

👑 | |||||

👑 | |||||

👑 | |||||

👑 | |||||

👑 | |||||

👑 |

## Recursive enumeration of placing *N* queens in C++

Python is a bit slow. Doing the same implementation in C++ should allow me to see some bigger numbers. In the grand scheme of things, the constant factor is negligible.

### Program 1

```
#include <bits/stdc++.h>
using namespace std;
int N;
<int, 40> Y, D1, D2;
arrayint CNT= 0;
() {
main>> N;
cin
<void(int)> place= [&](int i) {
functionif(i >= N) ++CNT;
else
for(int j= 0; j < N; ++j) {
if(Y[j] + D1[i + j] + D2[i - j + N]) continue;
[j]= D1[i + j]= D2[i - j + N]= 1;
Y(i + 1);
place[j]= D1[i + j]= D2[i - j + N]= 0;
Y}
};
(0);
place<< CNT << endl;
cout }
```

Program above for *N* = 15 takes ~ 5% of time of the Python program (3.1s /
64.2s). It is a line by line translation of the Python program. Unfortunately,
negative indices are not supported so “`+ N`

” needs to be carefully added.

## Recursive enumeration with bits in C++

The current world record for calculating the number of all possible placements
was done for *N* = 27. [PrEn17]
It should be possible to use something other than an array of *O*(*N*) elements
because I cannot hope to beat that record with my personal machine. In this
case the zeros and ones fit inside a 64-bit integer (there are ~ *N* × 2
diagonals).

Instead of tracking the same `Y`

, `D1`

and `D2`

in bits, it is possible to
apply bit tricks to make things even more efficient:

`X & -X`

gives the lowest set bit and allows going only through free columns one by one,`rotr(D1, c`

_{1}`)`

allows marking diagonals for next row by rotating bits by one to right,`rotl(D2, c`

_{2}`)`

allows marking opposite diagonals for next row by rotating bits by one to left.

I recommend checking [Rich97] that is particular for this
problem, [Warr13] that goes through various bit tricks in detail or
very nice and detailed list that is available at this
link. Enumeration of
subsets of size *k* is one I remember using at some point.

### Program 2

```
#include <bits/stdc++.h>
using namespace std;
using ull= unsigned long long;
;
ull N, D1, D2;
ull Y= 0;
ull CNT() {
main>> N;
cin = ~(~0 << N);
ull ALL= D1= D2= ~0;
Y&= ALL;
Y<void()> place= [&]() {
functionif(Y == 0) ++CNT;
else
for(ull cols= Y & D1 & D2, c= cols & -cols; cols;
^= c, c= cols & -cols) {
cols= Y, d1= D1, d2= D2;
ull y^= c, D1^= c, D2^= c;
Y= rotl(D1, 1), D2= rotr(D2, 1);
D1();
place= y, D1= d1, D2= d2;
Y}
};
();
place<< CNT << endl;
cout }
```

Program above for *N* = 16 takes ~ 30% of the execution time of the first C++
program (6.2s / 21.6s). This is a nice improvement. Interesting note, removing
`int i`

from the arguments of function `place`

shaves off `1`

second.

## Symmetry breaking: Do not enumerate placements that mirror another

It is evident that placing a queen in the first half of the first row results
in placements that mirror those where queen is placed in the second half. For
odd *N*, previous observation holds except when queen is placed in the middle
square as illustrated in first figure). When queen is in the middle
of the first row, then placing a queen in the first half of the second row
results in placements that mirror those where queen is placed in the second
half (of the second row).

Previous program can simply be edited to include the restrictions and decrease
execution time. The `CNT`

is multiplied by `2`

at the end:

### Program 3

```
#include <bits/stdc++.h>
using namespace std;
using ull= unsigned long long;
;
ull N, D1, D2;
ull Y= 0;
ull CNT, MID;
ull ALL
template <bool R> ull init(ull x) { return R ? x & (ALL << (N / 2)) : x; }
template <bool R1= false, bool R2= false> void place() {
for(ull c, cols= init<R1>(Y & D1 & D2); cols; cols^= c) {
= cols & -cols;
c= Y, d1= D1, d2= D2;
ull y^= c, D1^= c, D2^= c;
Y= rotl(D1, 1), D2= rotr(D2, 1);
D1+= Y == 0;
CNT&&c == MID ? place<true>() : place();
R2 = y, D1= d1, D2= d2;
Y}
}
() {
main>> N;
cin = ~(~0 << N);
ALL= D1= D2= ~0;
Y&= ALL;
Y= 1 << (N / 2);
MID% 2 ? place<true, true>() : place<true>();
N << CNT + CNT << endl;
cout }
```

I have extracted the function and added two template arguments. First argument
`R1`

indicates if the first row will be restricted. Second one `R2`

indicates
if check for the middle in the first row is made and then the second row
restricted in the recursive call. For *N* = 17 this program takes ~ 45% of the
execution time of the previous C++ program (19.8s / 43.4s). If `template`

code is replaced by simple checks for odd *N* and `MID`

, then the execution
takes ~ 3% more time. I moved `c= cols & -cols`

from `for`

iteration
expression to the body of the loop and this improved the runtime by ~ 3%.

## Conclusion and further improvements

First time I enumerated all placements for *N* 👸👸🏻👸🏼👸🏽👸🏾👸🏿 was decade ago, in
Scala. It was slow and complicated. I wanted to
revisit the problem and try to write code as simply as possible. That is the
reason for commas, global variables, monstrous mutability and non-ISO C++.

Additional symmetries like rotation give more ways to cut off the search space. This was the case with mirroring where search space was cut by a factor of two. Current search happens row by row, from first to last. This cannot support avoiding search trees that will discover the rotation of the same placement.

It looks like counting A033148 might be easier for
large *N*. Might be related to solutions where queens sit on a line. Instead of
enumerating, trying to find the minimum number of queens that attack all
unoccupied squares looks like a fruitful venture too.

N | Program 0 | Program 1 | Program 2 | Program 3 |
---|---|---|---|---|

10 | 32 | 2 | 2 | 2 |

11 | 104 | 5 | 2 | 2 |

12 | 506 | 15 | 6 | 3 |

13 | 2893 | 80 | 27 | 13 |

14 | 17560 | 481 | 152 | 70 |

15 | 103095 | 3092 | 958 | 431 |

16 | – | 21318 | 6347 | 2868 |

17 | – | 154662 | 44037 | 19828 |

18 | – | – | 326972 | 149369 |

Given the current trend of execution time in table, I can expect the
count for *N* = 27 to appear after 300 years. Interestingly the number of
placements for *N* = 27 is 234907967154122528 and it fits into a 64-bit integer,
so I do not even have to change the program and start using
`_m128i`

.

To make my page even less interesting for the Google Search Engine I am going to add a bunch of emojis and tables here with 20 placements for board size 7 × 7 – output of program 3 (yes, HTML output).

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 | ||||||

👑 |

# Bibliography

*Journal of Signal Processing Systems*Bd. 88, Springer (2017), Nr. 2, S. 185–201

*Backtracking algorithms in MCPL using bit patterns and recursion*: Citeseer, 1997

*Hacker’s delight*: Pearson Education, 2013