《Lua 程序设计 第四版》中的八皇后问题

我正在阅读《Lua 程序设计 第四版》,但我已经被第二章插曲“八皇后问题”第一个练习题难住了。

示例代码如下:

N = 8 -- 棋盘大小

-- 检查位置 (n, c) 是否受到攻击
function isplaceok (a, 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 (a)
    for i = 1, N do                 -- 对于每行
        for j = 1, N do             -- 对于每列
            -- 输出“X”或“-”,并添加一个空格
            io.write(a[i] == j and "X" or "-", " ")
        end
        io.write("\n")
    end
    io.write("\n")
end

-- 将 1~N 个皇后添加到棋盘 'a' 中
function addqueen (a, n)
    if n > N then -- 所有皇后都已放置?
        printsolution(a)
    else -- 尝试放置第 n 个皇后
        for c = 1, N do
            if isplaceok(a, n, c) then
                a[n] = c -- 将第 n 个皇后放置在第 c 列
                addqueen(a, n + 1)
            end
        end
    end
end

-- 运行程序
addqueen({}, 1)

代码有很详细的注释,但在第一个问题方面我无法回答:

练习 2.1:修改八皇后程序的代码,使其在打印第一个解后停止运行。

在程序结束时,a 包含了所有可能的解;我无法确定 addqueen (n, c) 应该如何修改,使 a 仅包含一个可能的解,或者 printsolution (a) 应该如何修改,使其仅打印第一个可能的解?

虽然我不确定是否完全理解了回溯算法,但我尝试了两种假设,但未能成功实现,所以非常感谢任何帮助。

点赞
用户1442917
用户1442917

在程序的末尾,a包含了所有可能的解决方案。

就我理解来看,a从未包含过所有可能的解决方案;它要么包含了一个完整的解决方案,要么包含了一个算法正在处理的不完整/不正确的方案。该算法的编写方式有效地枚举了可能的解决方案,并在尽早发现冲突的情况下跳过那些产生冲突的方案(例如,如果第一和第二个皇后在同一条线上,那么将移动第二个皇后而不会检查其他皇后的位置,因为它们无论如何都不会满足解决方案)。

因此,要在打印第一个解决方案后停止,您可以在printsolution(a)行后直接添加os.exit()

2018-02-06 18:41:26