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?