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

Question

我目前正在阅读《Lua 编程》第四版，并且已经陷入了“第 2 章插曲：八皇后谜题”的第一个练习。

示例代码如下：

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)应该修改以便仅打印第一个可能的解决方案？

尽管我不确定完全理解回溯，但我尝试实现这两个假设但没有成功，所以任何帮助将不胜感激。

Answer 1

在这个程序的最后，a包含了所有可能的解决方案

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

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