I wrote a python script to solve the N Queens puzzle. I made a function which, provided n, will return the first solution it finds for n queens by using backtracking. With a small modification it is possible to make the function find and return all solutions by exhausting the search space. It works well for n between 1 and 23. After 23 it starts to take some time to find a single solution.
I was wondering if it is possible to find a solution with a further constraint by extending the "attack range" of the queen. A queen in chess can attack horizontally, vertically, and on the diagonals. For my modification the queen can also attack the adjacent squares to the left and the right of the diagonal ones. As a consequence of this behavior, each queen must be 4 squares away from the next queen, instead of 3 squares for the normal puzzle.
In the following image, the blue squares are the normal queen range, and the green squares represent the new attack range: New queen attack range.
I made a new function which takes into account this new constraint. However, after running my code, I haven't been able to find any solutions for any number up to 23, and after 24 it takes a lot of time.
So my question is: does anyone know if there is a solution at all for this problem? Which is the smallest number for which there is a solution?
If anyone has done this before, I'm sure their code will be better and faster than mine, but I can provide the code if needed.
Thanks in advance!
With these super queens, you will no longer be able to fit N queens on an NxN board, other than the trivial 1x1 board. One way to see this is that there are 2N-1 diagonals (let's use lower left to upper right) on an NxN board. Each queen will be attacking 3 diagonals, except if they are in the corner they will attack 2 diagonals.
Let's say we have one queen in the corner, occupying 2 diagonals. Then e.g. on an 8x8 board we have 13 diagonals left which can be used by floor(13/3) queens or 4 queens. So at most we could have 5 queens on an 8x8 board. I don't know if this is a tight upper bound.
