回溯和象棋

Question

有一个国际象棋场N * N，其中已经出现了一些黑色的数字。找到您需要放置在字段中的最少的白皇后，以便他们可以击败所有黑人。使用backtrack算法。

首先，我将所有可能的女王置于可以击败至少某些东西的位置。那我该如何决定皇后区是否最终解决？

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

请注意，它将多次访问相同的情况，因为皇后可以任意排列。您可以通过仅在阅读顺序中位于最后一个皇后之后的正方形上放置新皇后来解决此问题。