《Programming in Lua（第四版）》八皇后问题练习2.1求解咨询

嘿，我刚好做过这个练习！你猜的没错，确实需要调整addqueen函数的递归逻辑——原程序会遍历所有可能的解并收集起来，我们要做的就是让它在找到第一个可行解后立刻终止递归，不用再继续探索其他可能性。

核心思路 #

原addqueen函数在放置完所有皇后（n == N）时会打印解，但之后还会继续回溯尝试其他列。我们需要给递归函数加一个返回值标记：当找到解时返回true，上层递归收到这个标记后就立刻停止后续尝试，直接向上传递这个标记，直到整个递归链终止。

修改后的代码示例 #

假设原程序的结构是这样的，我们来一步步修改：

首先是原有的isplaceok函数（检查位置是否安全）不用动，重点改addqueen和打印逻辑：

N = 8
a = {}  -- 用来记录每一行皇后的列位置

-- 检查第n行第c列是否可以放置皇后
function isplaceok(n, c)
    for i = 1, n-1 do
        if (a[i] == c) or (a[i] - i == c - n) or (a[i] + i == c + n) then
            return false
        end
    end
    return true
end

-- 打印单个解决方案
function printsolution()
    for i = 1, N do
        -- 生成每行的字符串：前面是点，中间Q，后面点
        local line = string.rep(".", a[i]-1) .. "Q" .. string.rep(".", N - a[i])
        print(line)
    end
    print("--- 第一个解决方案 ---")
end

-- 修改后的addqueen函数，带返回值
function addqueen(n)
    -- 所有皇后都放置完成，找到解
    if n > N then
        printsolution()
        return true  -- 返回true，告诉上层递归找到解了
    end

    -- 尝试当前行的每一列
    for c = 1, N do
        if isplaceok(n, c) then
            a[n] = c
            -- 递归放置下一行，如果返回true，说明找到解了，直接终止后续尝试
            if addqueen(n+1) then
                return true
            end
        end
    end
    return false  -- 当前行没有可行列，返回false继续回溯
end

-- 启动程序
addqueen(1)

关键修改点 #

1. 给addqueen加返回值：当成功放置完所有皇后时，返回true表示找到解；否则返回false继续回溯。
2. 递归调用后检查返回值：在循环尝试每一列时，调用addqueen(n+1)后如果得到true，就立刻跳出循环并返回true，不再尝试当前行的其他列，也让上层递归停止。
3. 无需收集所有解：现在我们只需要第一个解，所以不用再维护存储所有解的结构，找到就打印然后终止。

这样修改后，程序会在找到第一个八皇后的可行布局后立刻停止，不会继续计算其他解啦。

内容的提问来源于stack exchange，提问作者Tolga