八皇后单解和全解递归算法(Lua实现)

单解递归算法

local file = io.open('output.txt', 'w')

io.output(file)


local N = 8

local a = {}  

local times = 0


local function is_place_ok(n, c) -- n >=1 and n <= 8
for i = 1, n - 1 do
if (a[i] == c) or (math.abs(a[i] - c) == math.abs(n - i)) then
return false
end
end
return true
end



local function show()
    times = times + 1
io.write('Times ', times, '\n')
for i = 1, N do
for j = 1, N do 
if a[i] == j then
io.write('X ')
else 
io.write('- ')
end
end
io.write('\n')
end
end



local function add_queen(n)
if n > N then
        show()
else

while (a[n] <= N)
do
if is_place_ok(n, a[n]) then
break
end
            a[n] = a[n] + 1
end

if a[n] <= N then
            a[n + 1] = 1
            add_queen(n + 1)
else

-- 回溯
            n = n - 1
            a[n] = a[n] + 1
            add_queen(n)
end
end
end


local function init()
for i = 1, N do
        a[i] = 1    -- lua 中index从1开始
end
end


init();
add_queen(1)

io.close()

全解递归算法

local file = io.open('output.txt', 'w')

io.output(file)


local N = 8

local a = {}  

local times = 0


local function is_place_ok(n, c) -- n >=1 and n <= 8
for i = 1, n - 1 do
if (a[i] == c) or (math.abs(a[i] - c) == math.abs(n - i)) then
return false
end
end
return true
end



local function show()
    times = times + 1
io.write('Times ', times, '\n')
for i = 1, N do
for j = 1, N do 
if a[i] == j then
io.write('X ')
else 
io.write('- ')
end
end
io.write('\n')
end
end



local function add_queen(n)
if n > N then
        show()
else
for c = 1, N do
if is_place_ok(n, c) then
                a[n] = c
                add_queen(n + 1)
end
end 
end
end


local function init()   
for i = 1, N do
        a[i] = 1  -- lua 中index从1开始
end
end


init();
add_queen(1)

io.close()