Lua 八皇後問題

1.什麼是八皇後問題？

八皇後問題是一個以國際象棋為背景的問題：如何能夠在8×8 的國際象棋棋盤上放置八個皇後，使得任何一個皇後都無法直接吃掉其他的皇後。不知道你們玩過國際象棋沒有。皇後在國際象棋中是非常重要的棋子，因為她的移動範圍很廣，比車，和象都要廣，可以橫豎走，斜着也可以走，一般死掉皇後，基本就輸了。因為每一行都有8種可能，是以一共可能解是8*8*8*8*8*8*8*8是以要想人工在棋盤上擺出八個皇後的所有解，還是蠻難的一件事情。

2.用Lua來解這個問題solution

用什麼語言解不是重點，主要我最近在看《​

​Programming in lua​

​》這書，書中給出了答案，感覺寫的比較好。第一眼看起來還蠻難的，又是遞歸！

local N = 8
-- 判斷從第1行開始直到目前給定的行，列是否有沖突的皇後
-- 比如一個解{3, 7, 2, 1, 8, 6, 5, 4}, 在判斷第4行，第一列是否合法是， isPlaceOK(a, 4, 1)
-- 我們就發現它是與第三行的2有"斜着"沖突 
local function isPlaceOK(a,row,column)
   for i = 1, row - 1 do
      if(a[i] == column) or                      --相同列
       (a[i] - i == column - row) or        --斜着沖突， 方向是\
      (a[i] + i == column + row) then  --斜着沖突， 方向是/
      return false
     end
   end
   return true
end

-- 列印一個解
-- 我們這裡的解是放在一個table中，類似{3, 7, 2, 1, 8, 6, 5, 4}
local 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

--核心方法，獨立解釋
local function addQueen(a, row)
   if row > N then
     printSolution(a)
   else
     for column = 1, N do
       if isPlaceOK(a, row, column) then
        a[row] = column
       addQueen(a, row + 1)
      end
     end
   end
end



addQueen({}, 1)--從第一行開始求解      

3.程式輸出

4.解釋下addQueen這個函數