N+1 queens algorithm

Question

I'm looking to improve the speed of my algorithm to calculate the number of solutions to the N+1 queens problem (place N+1 queens on a NxN chessboard with 1 pawn). I'm basically using brute-force combined with backtracking, I first place a pawn on a random location on the board (without the edges and corners of the square without edges) and after that I just start to place queens using backtracking. This method is easy, but also slow. What algorithms would be faster?

I was thinking of first placing a pawn and 4 queens on each side of the pawn, but I'm not sure that it would improve the calculation speed.

Answer 1

As you are looking to count all the solutions of the problem, placing the pawn first on a random position will not do. You will have to place the pawn on each position. I believe the best algorithm here is backtracking, but still you can do some optimizations. In the n-queen problem an improtant bit is to take advantage of the symmetry of solutions, so I guess you can do this here as well. Having a solution, all of its 4 rotatations and their mirror images are also solutions.

Answer 2

Your own suggestion sounds correct as it starts with the basic constraint that any solution needs to satisfy, rather than verifying that after the fact for each candidate solution.

For exhaustive search problems, the biggest speedoff usually comes when you implement an early exit rule: as soon as one queen attacks another, you do not place any more queens, and proceed to a new square for the last queen. This will greatly reduce the search space compared to the exhaustive search where you only check mutually attacks when all pieces have been placed on the board.

The pawn position on an NxN board can be reduced to the inner (N-2)x(N-2) subboard, and you can use the 8-fold rotation/mirror symmetry to reduce that even further to one of the octants of that inner square.