最近在看PiL3，今天在做習(xí)題的時候遇見了八皇后問題，當(dāng)時示例代碼并沒有仔細看，等到寫的時候發(fā)現(xiàn)老是有問題。后來去查了下八皇后問題的描述，發(fā)現(xiàn)自己雖然知道這個問題很久了卻沒有真正理解過，真為自己汗顏。

八皇后問題

以下資料來自WikiPedia:

八皇后問題是一個以國際象棋為背景的問題：如何能夠在8×8的國際象棋棋盤上放置八個皇后，使得任何一個皇后都無法直接吃掉其他的皇后？為了達到此目的，任兩個皇后都不能處于同一條橫行、縱行或斜線上。八皇后問題可以推廣為更一般的n皇后擺放問題：這時棋盤的大小變?yōu)閚×n，而皇后個數(shù)也變成n。當(dāng)且僅當(dāng)n = 1或n ≥ 4時問題有解。

一個簡單的遞歸算法

這個算法來自于PiL3中，我在做習(xí)題的時候?qū)⑵渥约簩崿F(xiàn)了一遍，思路是一樣的,下面介紹一下。
首先定義了2個全局變量,N表示棋盤的大小，solved代表問題是否已解決。
printBoard用來打印當(dāng)前棋盤，皇后用X表示，空格用-表示。
validPos的作用是判斷當(dāng)前棋盤上能否在n行pos列上放置新棋子。

addQueen是算法的核心函數(shù)，也是被遞歸調(diào)用的函數(shù)。board代表當(dāng)前的棋盤,n表示當(dāng)前放置棋子的行數(shù)。
當(dāng)n大于N時表明當(dāng)前棋盤已經(jīng)有解了，直接打印即可。
當(dāng)n小于N時，嘗試當(dāng)前行n上在pos列放置棋子，如果位置合適則在棋盤上記錄該棋子，并繼續(xù)在下一行添加新棋子(調(diào)用addQueen(board,n+1))。如果不合適，則舍棄當(dāng)前棋盤，不再遞歸調(diào)用自身，我一開始沒有仔細看這里，導(dǎo)致我沒理解這個解法如何只對符合規(guī)則的棋盤繼續(xù)求解。

總結(jié)：與最常用最容易想到的回溯法相比，遞歸的方法顯得簡單粗暴，不過代碼也確實簡單了不少。

Lua實現(xiàn)如下:

local N=8
local solved=false
local function printBoard(board)
    if solved then
        return
    end
    for i=1, N do
        for j=1, N do
            io.write(board[i]==j and "X" or "-", " ")
        end
        io.write("\n")
    end
    io.write("\n")
    solved = true
end
local function validPos(board, row, pos)
    for i=1, row-1 do
        if (board[i] == pos) or
            (row-i == math.abs(pos - board[i])) then
            return false
        end
    end
    return true
end

local function addQueen(board, n)
    if n>N then
        printBoard(board)
    else
        for pos=1, N do
            if validPos(board, n, pos) then
                board[n]=pos
                addQueen(board, n+1)
            end
        end
    end
end

addQueen({},1)