《Lua 程序设计 第四版》中的八皇后问题
2018-2-6 15:34:59
收藏:0
阅读:117
评论:1
我正在阅读《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) 应该如何修改,使其仅打印第一个可能的解?
虽然我不确定是否完全理解了回溯算法,但我尝试了两种假设,但未能成功实现,所以非常感谢任何帮助。
点赞
评论区的留言会收到邮件通知哦~
推荐文章
- Lua 虚拟机加密load(string.dump(function)) 后执行失败问题如何解决
- 我想创建一个 Nginx 规则,禁止访问
- 如何将两个不同的lua文件合成一个 东西有点长 大佬请耐心看完 我是小白研究几天了都没搞定
- 如何在roblox studio中1:1导入真实世界的地形?
- 求解,lua_resume的第二次调用继续执行协程问题。
- 【上海普陀区】内向猫网络招募【Skynet游戏框架Lua后端程序员】
- SF爱好求教:如何用lua实现游戏内调用数据库函数实现账号密码注册?
- Lua实现网站后台开发
- LUA错误显式返回,社区常见的规约是怎么样的
- lua5.3下载库失败
- 请问如何实现文本框内容和某个网页搜索框内容连接,并把网页输出来的结果反馈到另外一个文本框上
- lua lanes多线程使用
- 一个kv数据库
- openresty 有没有比较轻量的 docker 镜像
- 想问一下,有大佬用过luacurl吗
- 在Lua执行过程中使用Load函数出现问题
- 为什么 neovim 里没有显示一些特殊字符?
- Lua比较两个表的值(不考虑键的顺序)
- 有个lua简单的项目,外包,有意者加微信 liuheng600456详谈,最好在成都
- 如何在 Visual Studio 2022 中运行 Lua 代码?

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