编程中的八皇后问题——Lua编程第四版

Question

我目前正在阅读《Lua编程第四版》，但在"第二章插曲：八皇后问题"的第一个练习中就遇到了困难。

以下是示例代码:

N = 8 -- board size

-- check whether position (n, c) is free from attacks
function isplaceok (a, n ,c)
    for i = 1, n - 1 do -- for each queen already placed
        if (a[i] == c) or           -- same column?
        (a[i] - i == c - n) or      -- same diagonal?
        (a[i] + i == c + n) then    -- same diagonal?
            return false -- place can be attacked
        end
    end
    return true -- no attacks; place is OK
end

-- print a board
function printsolution (a)
    for i = 1, N do                 -- for each row
        for j = 1, N do             -- and for each column
            -- write "X" or "-" plus a space
            io.write(a[i] == j and "X" or "-", " ")
        end
        io.write("\n")
    end
    io.write("\n")
end

-- add to board 'a' all queens from 'n' to 'N'
function addqueen (a, n)
    if n > N then -- all queens have been placed?
        printsolution(a)
    else -- try to place n-th queen
        for c = 1, N do
            if isplaceok(a, n, c) then
                a[n] = c -- place n-th queen at column 'c'
                addqueen(a, n + 1)
            end
        end
    end
end

-- run the program
addqueen({}, 1)

代码已经有相当详细的注释，书中也有明确的说明，但我无法回答第一个问题：

练习 2.1：修改八皇后程序，使其在打印第一个解后停止。

在程序的末尾，数组a包含所有可能的解；我不确定是否应该修改addqueen（n，c）函数，使数组a仅包含一个可能的解，或者是否应该修改printsolution（a）函数，使其仅打印第一个可能的解？

虽然我并不确定是否完全理解回溯算法，但我尝试了两种假设都没有成功地实现，因此任何帮助将不胜感激。

- Tolga

---

你尝试了什么？可以给我们一些代码吗，这样我们可以更容易地帮助您吗？ - Feathercrown

基本上，我尝试修改两个函数的for循环条件。此外，我认为我没有正确的回溯思维图像；确切地说，我不理解a的最终状态——它是一个表格吗？ - Tolga

@Tolga - 数组 a 在每个新解决方案中都会被重写。 a 不保存先前的解决方案。 它只是长度为8的数组。 它不是表格的表格。 - Egor Skriptunoff

亲爱的Egor，感谢您的澄清；下面的答案详细阐述了这一点，并为我提供了解决方案。不过，我仍然需要一些解释：如果您认为您可以帮助我，请查看我刚刚提交的评论。 :) - Tolga

Answer 1

在程序结束时，a包含所有可能的解决方案。

据我理解，解决方案中a永远不包含所有可能的解决方案；它要么包含一个完整的解决方案，要么包含一个算法正在处理的不完整/不正确的解决方案。该算法以一种简单的方式编写，枚举可能的解决方案并尽早跳过生成冲突的解决方案（例如，如果第一和第二皇后在同一行上，则第二个皇后将被移动而不检查其他皇后的位置，因为它们无论如何都不满足解决方案）。

因此，要在打印第一个解决方案后停止，您可以在printsolution(a)行后简单地添加os.exit()。

- Paul Kulchenko

---

亲爱的保罗，非常感谢你的帮助，它确实有效！不过我还是有点困惑：为什么单次调用 addqueen({}, 1) 可以生成多个解决方案而不需要在其定义中使用 os.exit()？这是否等同于 while true do addqueen({}, 1) end？此外，我们如何确定这些不同的解决方案是不同的排列，并且在没有 os.exit() 的情况下打破循环的边缘条件是什么？ - Tolga

@Tolga - 这实际上是一种深度优先搜索，因此它会生成所有的解决方案。 - Egor Skriptunoff

Answer 2

清单1是实现需求的一种替代方案。 用（1），（2）和（3）分别注释的三行是对书中原始实现和问题列表中列出的实现的修改。 通过这些修改，如果函数返回true，则找到了解决方案，并且a包含解决方案。

-- Listing 1
function addqueen (a, n)
  if n > N then    -- all queens have been placed?
    return true  -- (1)
  else  -- try to place n-th queen
    for c = 1, N do
      if isplaceok(a, n, c) then
        a[n] = c    -- place n-th queen at column 'c'
        if addqueen(a, n + 1) then return true end  -- (2)
      end
    end
    return false -- (3)
  end
end

-- run the program
a = {1}
if not addqueen(a, 2) then print("failed") end
printsolution(a)

a = {1, 4}
if not addqueen(a, 3) then print("failed") end
printsolution(a)

让我从书中的Exercise 2.2开始，根据我之前向他人解释“回溯”算法的经验，这可能有助于更好地理解原始实现和我的修改。

Exercise 2.2要求首先生成所有可能的排列。一个直观而简单的解决方案在清单2中，它使用嵌套的for循环生成所有排列，并在最内层循环中逐个验证它们。虽然它满足了Exercise 2.2的要求，但代码看起来笨拙。此外，它是针对8x8棋盘硬编码的。

-- Listing 2
local function allsolutions (a)
  -- generate all possible permutations
  for c1 = 1, N do
    a[1] = c1
    for c2 = 1, N do
      a[2] = c2
      for c3 = 1, N do
        a[3] = c3
        for c4 = 1, N do
          a[4] = c4
          for c5 = 1, N do
            a[5] = c5
            for c6 = 1, N do
              a[6] = c6
              for c7 = 1, N do
                a[7] = c7
                for c8 = 1, N do
                  a[8] = c8
                  -- validate the permutation
                  local valid
                  for r = 2, N do  -- start from 2nd row
                    valid = isplaceok(a, r, a[r])
                    if not valid then break end
                  end
                  if valid then printsolution(a) end
                end
              end
            end
          end
        end
      end
    end
  end
end

-- run the program
allsolutions({})

当N = 8时，列表3等同于列表2。else-end块中的for循环执行了列表2中嵌套的所有for循环的功能。使用递归调用使代码不仅紧凑，而且灵活，即它能够解决NxN棋盘和具有预设行的棋盘。然而，递归调用有时会导致混乱。希望列表2中的代码能够帮助。

-- Listing 3
local function addqueen (a, n)
  n = n or 1
  if n > N then
    -- verify the permutation
    local valid
    for r = 2, N do  -- start from 2nd row
      valid = isplaceok(a, r, a[r])
      if not valid then break end
    end
    if valid then printsolution(a) end
  else
    -- generate all possible permutations
    for c = 1, N do
      a[n] = c
      addqueen(a, n + 1)
    end
  end
end

-- run the program
addqueen({})     -- empty board, equivalent allsolutions({})
addqueen({1}, 2) -- a queen in 1st row and 1st column

将清单3中的代码与原始实现进行比较，不同之处在于它在所有八个皇后都放置在棋盘上之后进行验证，而原始实现在每次添加皇后时都会进行验证，并且如果新添加的皇后导致冲突，则不会继续到下一行。这就是“回溯”所做的事情，即它进行“暴力”搜索，一旦找到一个不会导致解决方案的节点，它就会放弃该搜索分支，并且必须到达搜索树的叶子以确定它是一个有效的解决方案。

回到清单1中的修改。

(1) 当函数达到此点时，它到达了搜索树的叶子，并找到了一个有效的解决方案，因此让它返回true表示成功。

(2) 这是停止函数进一步搜索的点。在原始实现中，for循环会继续进行，而不管递归调用发生了什么。使用修改(1)，如果找到解决方案，则递归调用返回true，函数需要停止并传播成功信号；否则，它将继续for循环，搜索其他可能的解决方案。

(3) 这是函数完成for循环后返回的点。使用修改(1)和(2)，当函数到达此点时，意味着它未能找到解决方案，因此让它明确地返回false表示失败。

- xmartin

---

亲爱的 @xmartin，抱歉回复晚了，感谢您花时间撰写如此完整详细的解释，对我非常有帮助！ - Tolga

@Tolga，很高兴知道它有所帮助。 :-) - xmartin