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.
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.