1
$\begingroup$

Given the position of chess board of two players, we have to find the minimum number of moves (and output them) so that only one player playing continuously and optimally defeat the other one (checkmate).

The assumption is that the other player stops playing after the inputted position and only one player plays from there on.

My initial assumption is that simply bfs might help, but I don't think this should give the minimum number of moves always. Just wondering is this an well known problem? then how to solve it?

  • 1
    BFS will give you the optimal number of moves, but the tree you have to traverse with BFS is going to be huge since you have a lot of possible moves in each steps, at least if there is many pieces left.2012-09-23
  • 2
    BFS will give the minimal number of moves, because it examines all the positions that can be reached in one move, then all the positions that can be reached in two moves, and so on in order.2012-09-23

1 Answers 1