Chess pieces placement algorithm I've got the following problem:


I've got chessboard with fixed size N x M
I've got list of pieces, like 2 queens, 2 rooks (It can be any piece with exception of pawn).
I need to find every combination where none of the pieces is in a position to take any of the others


For example for chessboard 3 x 3 and 2 rooks and 1 king, possible solutions are:

 |R|        |R|      K| |      | |K
-+-+-      -+-+-     -+-+-    -+-+-
R| |        | |R      | |R    R| | 
-+-+-      -+-+-     -+-+-    -+-+-
 | |K      K| |       |R|      |R| 


What I came out with:


I create a whitelist of fields where the new piece can be placed (at the beginning it has all fields of the chessboard)
I take the first piece from the list
I place it on the first field I take from whitelist: (1,1)
I update whitelist excluding all fields that are threatened with this piece I placed
Here I branch out: I take next piece from the list and call my method recursively on every field from the whitelist (I also need to check, if placing new piece would threat already standing piece).
I repeat it until the last piece is placed
If there are pieces left, but no fields on whitelist I just finish that branch.


I noticed I can calculate results only for first quadrant (fields (1,1),(1,2)(2,1),(2,2) for my example. Rest of the solutions can be received by just mirroring results from the first quadrant.

Problem with my solution is, it's not very fast. For chessboard 7x7 and 7 pieces it takes ~15 minutes to finish. I implemented it with scala. 

Do you have any tips about how can I improve it?
Suppose you're trying to place $Q$ queens, $R$ rooks, $B$ bishops, $N$ knights, and $K$ kings.  Then doing things the way you're doing them now, at least provided the language isn't clever enough to memoize the pure function calls for you, means that you're processing each solution $Q!R!B!N!K!$ times, rather than once, since in a solution containing $Q$ queens you could have placed them in any of $Q!$ different orders, and so forth.

Similar logic also applies to the partial solutions in your call stack.

If you're just trying to place one of each piece then this isn't so bad.  If, on the other hand, you're trying to place 8 queens on an 8 x 8 board, this means each solution gets generated 8! = 40,320 different times.

This is probably the single largest issue you're seeing here.  I tested this out by writing a naive python program, and it was able to do 8 queens on an 8x8 board in considerably less than fifteen minutes running on a single core of my twelve-year-old laptop with 1GB of RAM. 

I'm not particularly familiar with Scala but it's possible you could just keep your existing code but tell it to memoize your function, at least provided it's written as a pure function.

Other optimizations would be to parallelize the analysis (which, again, a functional language like Scala might be able to do near-automatically for you), and to take advantage of the four- or eightfold-symmetry of the problem (depending on whether the board is square or just rectangular) by putting everything into a canonical form.

One last thing to check is that the intermediate data is stored in such a way that you're not having to recalculate anything.  When checking for a blank square, you want a stored list of blank squares you can iterate over.  When checking to see if the piece you just added is threatening something already on the board, you want a stored list of occupied positions to work with.