回溯和国际象棋

Question

有N*N个棋盘，里面已经出现了一些黑棋。找到您需要投入该领域的最少白色皇后，以便它们可以击败所有黑色数字。使用回溯算法。

首先，我将所有可能的皇后放在它们至少可以击败某些东西的位置。那我应该如何决定女王是否进入最终解决方案？

Answer 1

在递归伪代码中：

minQueensNeeded = ∞
procedure placeQueens():
  if all black pieces are under attack:
    minQueensNeeded = min(minQueensNeeded, number of queens on the board)
  else:
    for each black piece B that is not under attack:
      for each square S from which B can be captured:
        place a queen at S
        placeQueens()
        remove the queen at S

注意它会多次访问相同的情况，因为皇后可以任意排列。这不会影响答案，但对性能来说不是很好。您可以通过仅将新皇后放在阅读顺序中最后一个皇后之后的方块上来修复它。

回溯和国际象棋

Backtracking and chess

algorithm

chess

backtracking