recursion - 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)

代码的注释很详细，这本书也很明确，但我无法回答第一个问题:

Exercise 2.1: Modify the eight-queen program so that it stops after printing the first solution.

在这个程序结束时，a包含所有可能的解决方案；我不知道是不是 addqueen (n, c)应该修改为 a仅包含一种可能的解决方案或如果 printsolution (a)应该修改，以便它只打印第一个可能的解决方案？

尽管我不确定是否完全理解回溯，但我试图实现这两个假设但没有成功，因此非常感谢任何帮助。

Answer 1

At the end of this program, a contains all possible solutions

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

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