N-Queens puzzle, but with all chess pieces

Question

I want to solve a problem similar to N-Queens one, but:

• all chess pieces are available
• user inputs how many pieces of what kind are to be placed (e.g. 3 rooks, 4 knights, 1 bishop)

I'm lying on the floor for some time now, but can't come up with how to adjust the backtracking algorithm for this purpose. I will be very grateful for any kind of help.

Answer 1

In principle, the same approach as in the classical N-Queen problem should work:

1. Find an empty, non-attacked square where you can place your next piece
2. Search the new position recursively (or if you already placed all your pieces, output the solution)
3. Take back the last placed piece and repeat (goto step 1) until you have tried all squares where you can place the next piece

The only difference to the classical N-Queens problem is that the different pieces have different attack patterns. And some common optimizations might no longer work. For instance, if you have pawns, it breaks symmetry as they only attack the squares in front of them. (Though you still have one symmetry axis even with pawns.)

I would expect the backtracking algorithm to be more efficient if you start with placing the pieces first that cover the most squares: first queens, then rooks and bishops, then knights and kings, and finally pawns.