八皇后问题

【背景】

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

【回溯法】

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。

【思路】

首先，每一行和每一列中只能有一个皇后。

然后，往棋盘上放皇后，从第一个位置开始遍历，找到一个可以放皇后的位置后，按同方法放下一个皇后;
如果所有位置都不能放皇后，说明上一个皇后的位置不能满足需求;
那么就要回溯到上一个皇后，把她往后挪一个位置，重新检查设置后面皇后的位置。

【回溯法解法】

--来自《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 
            io.write(a[i]==j and "X" or "-", " ")
        end
        io.write("\n")
    end
    io.write("\n")
end

--把从'n'到'N'的所有皇后放在棋盘'a'上
function addqueen(a, n)
    if n > N then
        printsolution(a)
    else
        for c=1,N do 
            if isplaceok(a,n,c) then
                --把第n个皇后放在列c
                a[n] = c    
                addqueen(a, n+1)
            end
        end
    end
end

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

【指定个数】

上面的程序会输出所有解法(共92种），如何使其在输出指定个数的解后停止运行呢。

sum = 0
needCount = 1

--修改一下addqueen函数就好
function addqueen(a, n)
    if sum == needCount then
        return
    end

    if n > N then
        printsolution(a)
        sum = sum + 1
    else
        for c=1,N do 
            if isplaceok(a,n,c) then
                a[n] = c    
                addqueen(a, n+1)
            end
        end
    end
end

【全排列法解法】

解决八皇后问题的另一种方式是，先生成1-8之间的所有排列，然后依次遍历这些排列，检查每一个排列是否是八皇后问题的有效解。

N = 8

visit = {}
temp = {}
res = {}

function dfs(index, n)
    if index > n then
        local arr = {}
        for i=1,n do 
            table.insert(arr, temp[i])
        end
        table.insert(res, arr)
    else 
        for i=1,n do 
            if visit[i] == nil or visit[i] == false then
                visit[i] = true
                temp[index] = i 
                dfs(index+1,n)
                visit[i] = false
            end
        end
    end
end

--生成1-8之间的所有排列（8! = 40320种）
dfs(1, N)

function isplaceok2(arr)
    for i=1,#arr-1 do
        for j=i+1,#arr do
            if math.abs(j-i)==math.abs(arr[j]-arr[i]) then
                return false
            end     
        end
    end
    return true
end

--遍历结果，检查是否是八皇后问题的有效解
--剩下的res即是有效解
for i=#res,1,-1 do
    if not isplaceok2(res[i]) then
        table.remove(res, i)
    end
end

【后记】

在知乎上看到了如何用C++在10行内写出八皇后？ 感叹一下真是人才济济。