八皇后问题

image.png

百度百科说这是回溯算法的经典案例，当时还纠结了一下啥是回溯算法，看了下解释：有冲突解决冲突，没有冲突往前走，无路可走往回退，走到最后是答案。

仔细一想，这不是深度优先+迭代，求出所有的最深路径嘛

算法实现思路（这里用Lua实现）

1. 既然要回溯，首先要判断当前皇后的位置是否合法：

function CheckValid(nRow, nCol)
    for k,v in ipairs(tRow2Col) do
        if v == nCol then
            return false
        end
        if math.abs(nRow - k) == math.abs(nCol - v)then
            return false
        end
    end

    tRow2Col[nRow] = nCol
    return true
end

因为默认从第一行找起，行数不一样，所以这里只判断列和对角线

2. 找到当前行的位置：

function FindPosByRow(nRow)
    if nRow > nCount then
        table.insert(tAllPlace, tRow2Col)  --记录所以排列
    else
        for nCol = 1,nCount do
            if CheckValid(nRow, nCol) then
                FindPosByRow(nRow + 1)
                tRow2Col[nRow] = nil  --去掉记录，以待回溯
            end
        end
    end
end

3. 最后贴上全部代码：

local nCount = 8
local tRow2Col = {}
local tAllPlace = {}

function FindPosByRow(nRow)
    if nRow > nCount then
        table.insert(tAllPlace, tRow2Col)  --记录所以排列
    else
        for nCol = 1,nCount do
            if CheckValid(nRow, nCol) then
                FindPosByRow(nRow + 1)
                tRow2Col[nRow] = nil  --去掉记录，以待回溯
            end
        end
    end
end

function CheckValid(nRow, nCol)
    for k,v in ipairs(tRow2Col) do
        if v == nCol then
            return false
        end
        if math.abs(nRow - k) == math.abs(nCol - v)then
            return false
        end
    end

    tRow2Col[nRow] = nCol
    return true
end

FindPosByRow(1)
print(#tAllPlace)