[Community Puzzle] n Queens

Puzzles
#1

https://www.codingame.com/training/hard/n-queens

Send your feedback or ask for help here!

#2

4 posts were merged into an existing topic: [Community Puzzles] n Queens

#3

Just starting to try hands on the n-Queens puzzle and found that for a 4x4 board, the solution could be more than 2 as shown in the first test case.
Q . . .
. . Q .
. . . Q
. Q . .
How about this one? And it has rotation and mirrors as extra solutions as well.
Is it true?

#4

What about the queens in line 2 and 3, that can attack each other?

#5

Oh yeah, it was a misconception on my side. Diagonals of length 3 or 2 are also diagonals needing to avoid.
Thanks

#6

Looking for advice on how to make my algorithm run faster. Currently taking about 1.5 seconds to solve for 10 queens, but I time out at 11. Takes a little over 5 seconds for 11 queens when I run on my local machine.

[Community Puzzle] n Queens
#7

I don’t know what language you use but basically the main factor of optimisation will be the exploration strategy.
There are two ways to do your backtracking:

  • for each row, choose a column for the queen
  • for each queen, choose its 2 coordinates

One of the two options is significantly faster, so there’s that.

Then there are implementations details. The less information you carry, the best.
The most efficient way to store a state of the board is to use bitboard.
For the 11*11 board, you can theoretically store the whole board in one single 121 bits integer (if your language allow that, else you have to slice it into several ints).
You can precalc the “mask” of every possible queen position, and then checking for a valid position can be done only with the & bitwise operator, which is pretty cool.
Ultimately, you don’t even need to carry the information of the queens placements, you can just carry the information of the “combined mask”.

And you can memoize the number of different boards for a given “combined mask” and the number of queens already placed.

With all those optimisations, I could compute n=13 within the CG time limit.

1 Like
#8

Thanks, I will look into bitboards. I am currently using lists in python, and choosing a column for the queen for each row.

#9

I’m using Python too.
Python is a nice language for bitboard cause the integers automatically scale so you never have to wonder about the size.