2
$\begingroup$

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:

  1. I create a whitelist of fields where the new piece can be placed (at the beginning it has all fields of the chessboard)
  2. I take the first piece from the list
  3. I place it on the first field I take from whitelist: (1,1)
  4. I update whitelist excluding all fields that are threatened with this piece I placed
  5. 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).
  6. I repeat it until the last piece is placed
  7. 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?

$\endgroup$
  • 3
    $\begingroup$ Welcome to CS.SE! How many solutions are there (for your example 7x7 chessboard with 7 pieces)? $\endgroup$ – D.W. Feb 20 at 2:18
  • 1
    $\begingroup$ You could try sorting the pieces by decreasing order (so place all the queens before any other piece, then all the rooks, etc.). You could also try stopping early if the number of places left on the whitelist is less than the number of pieces remaining to be placed. $\endgroup$ – D.W. Feb 20 at 2:22
  • 1
    $\begingroup$ You could also try checking to see if you've explored this configuration before, where a configuration is the pair of the whitelist and the list of pieces remaining to be placed. If you have, you can reuse results from that prior computation. I don't know whether to expect this to be helpful or not. This is basically a form of memoization. $\endgroup$ – D.W. Feb 20 at 2:24
  • $\begingroup$ There are 3063828 unique combinations if my program is correct. $\endgroup$ – Krzysztof Atłasik Feb 20 at 8:56
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your suggestion with memoization helped me a lot. I checked if my main method is called more than once with the same arguments and it was a case. I backtracked why it was happening and when I fix it, the program ran for ~6 min. Then I added parallel execution and also rewrote the main recursive method, that it was tail-recursive. Not it takes ~2 min. Not bad :) Thanks. $\endgroup$ – Krzysztof Atłasik Feb 21 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.