8皇后问题
解题思路: 这是一个N*N的棋盘(矩阵),从第1行开始尝试每个列位置是否可行(第1行的任何列位置肯定是可行的),如果有可行的位置则尝试下一行,如果尝试的行数大于N,那么说明已经获得了一个解,这时打印此解,并再逆向往回推看还有没有其它解。如果当前行没有可行的位置则从上一行的下一个位置开始,重复这样的检查逻辑。
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
-- 从第1行开始直到N
addqueen({}, 1)