來自《Lua程式與設計》第二節- 八皇后問題
輸出所有解的解法
書中提供的源代碼，加注了自己的注釋，
N = 8
--[[
N為棋盤規模
a為一維陣列，保存第i個皇后所在的列數
]]
-- 檢查是否可以將第n個皇后放在第n行第c列（前n-1行的皇后已經放好）
function isplaceok(a,n,c)
-- 檢查前n-1個皇后是否與(n,c)位置沖突
for i = 1, n - 1, 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
io.write(a[i] == j and "X" or "-", " ")
end
io.write("\n")
end
io.write("\n")
end
-- 已經找到前n-1皇后的位置
-- 存放于a中
-- 尋找第n個皇后可擺放的位置
function addqueen(a,n)
if n > N then
printsolution(a)
return true
else
-- 逐列檢查能否擺放第n個皇后
for c = 1, N do
if isplaceok(a, n, c) then
a[n] = c
if addqueen(a, n+1) then
return true
end
end
end
end
end
-- 啟動方式
addqueen({}, 1)
書后練習
1. 修改八皇后問題的程式，使其在輸出第一個解后即停止運行，
修改addqueen函式即可，
-- 已經找到前n-1皇后的位置
-- 存放于a中
-- 尋找第n個皇后可擺放的位置
function addqueen(a,n)
if n > N then
printsolution(a)
return true
else
-- 逐列檢查能否擺放第n個皇后
for c = 1, N do
if isplaceok(a, n, c) then
a[n] = c
if addqueen(a, n+1) then
return true
end
end
end
end
end
2. 解決八皇后問題的另一種方式是，先生成1-8之間的所有排列，然后依次遍歷這些排列，檢查每一個排列是否是八皇后問題的有效解，請使用這種方法修改程式并對比性能差異，
一定是原本的方法效率更高…1-8之間的所有排列一共有8的8次冪個，檢查每個排列是否合法又是O(n^2)的復雜度，效率會很低，只看isplaceok函式呼叫次數的話，原來的方法一共呼叫isplaceok函式876次，生成所有排列的方法生成了8的8次冪個排列，每個排列呼叫isplaceok的次數最少1次，最多8次，整體也在5千萬次以上，
實際測了一下，用的在線編輯器，直接爆掉了，又重新用本地的lua跑了一下，呼叫isplaceok的次數為50889536次，（媽呀）
N = 8
--[[
N為棋盤規模
a為一維陣列，保存第i個皇后所在的列數
]]
count = 0
-- 檢查是否可以將第n個皇后放在第n行第c列（前n-1行的皇后已經放好）
function isplaceok(a,n,c)
count = count + 1
-- 檢查前n-1個皇后是否與(n,c)位置沖突
for i = 1, n - 1, 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
io.write(a[i] == j and "X" or "-", " ")
end
io.write("\n")
end
io.write("\n")
end
-- 已經放置前n-1皇后
-- 存放于a中
-- 放置第n個皇后
function addqueen(arrays, a, n)
if n > N then
table.insert(arrays, a)
else
-- 逐列檢查能否擺放第n個皇后
for c = 1, N do
local b = {}
for k, v in pairs(a) do
b[k] = v
end
b[n] = c
addqueen(arrays, b, n+1)
end
end
end
function getsolution()
local posibles = {}
addqueen(posibles, {}, 1)
for _, v in pairs(posibles) do
local ok = true
for i = 1, N do
ok = isplaceok(v, i, v[i])
if not ok then
break
end
end
if ok then
printsolution(v)
end
end
end
-- 啟動方式
getsolution()
io.write("\n",count)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/93571.html
標籤：其他
上一篇：資料結構與演算法概念