求解八皇后问题

什么是八皇后问题

国际相棋中，棋盘是8 * 8的，皇后这个棋子的攻击范围是跟她的同一列、同一行、同一对角。

Q Q  //同一行会给攻击到

Q   //同一列会给攻击到
Q

Q   //对角也会给攻击到
  Q

那么，为了世界和平，怎么摆放8个皇后在棋盘上而不让她们能够互相攻击呢？

这就是八皇后问题。

问题的约束条件

为了满足“互不攻击”的条件，必须同时满足以下四个约束：

1. 行约束：不能有两个皇后在同一行。
2. 列约束：不能有两个皇后在同一列。
3. 主对角线约束：不能有两个皇后在同一条主对角线（左上到右下）上。 在一条主对角线上的所有格子，其 行号 - 列号 的值是相等的。 例如：格子(1,2), (2,3), (3,4) 都在 行-列 = -1 这条对角线上。
4. 副对角线约束：不能有两个皇后在同一条副对角线（右上到左下）上。 在一条副对角线上的所有格子，其 行号 + 列号 的值是相等的。 例如：格子(1,3), (2,2), (3,1) 都在 行+列 = 4 这条对角线上。

什么是回溯法

回溯法是一种通过试错来寻找问题解决方案的算法。它一步一步地构建解决方案，当发现当前步骤不能得到一个正确的最终解时，它将撤销（回溯） 最近的部分决策，并尝试下一个可能的选项。

你可以把回溯法想象成走迷宫：

1. 你沿着一条路一直走。
2. 如果走到死胡同（发现当前选择无效），你就掉头（回溯） 回到上一个岔路口。
3. 然后选择另一条你没走过的路继续尝试。
4. 重复这个过程，直到找到出口

用回溯法解决8皇后问题

我们将利用“一行一后”的规则，把问题转化为：在第1行到第8行，依次为每一行的一个皇后选择一列，并确保不违反列约束和对角线约束。

我们用一个数组a来记录解决方案，a[i] = j 表示第 i 行的皇后放在第 j 列。

逐步推演（重点看回溯过程）：

从第1行开始

• 皇后放在第1列， a[1] = 1

[1, -, -, -, -, -, -, -]

进入第2行

• 皇后放在同一列（2,1），不行
• 皇后放在(2, 2)，也不行
• 皇后放在(2,3)，ok！

[1, 3, -, -, -, -, -, -]

进入第3行

• 第一列（3,1），不行
• 放在（3,2），也不行，和上一个皇后打架了
• 放在（3,3），也不行，和上一个皇后同一列
• 放在（3,4），ok！

[1, 3, 4, -, -, -, -, -]

一直到遇到冲突

• 假设我们按照这个方式一直放置到了第5行，棋盘状态为 [1, 3, 4, 2, 5, X, -, -]。
• 当我们尝试为第6行（i=6）的皇后找位置时，发现从第1列到第8列所有位置都与前几行的皇后冲突。
• 这说明，第5行皇后的位置选择，导致了一条死路。

让我们回溯！

• 算法意识到在第6行无路可走。
• 它撤销第6行的选择（即不放置任何皇后）。
• 回溯到第5行。
• 它撤销第5行当前的选择（比如之前放在第4列），然后尝试将第5行的皇后放到第4列之后的位置（例如第5列、第6列...）。
• 如果第5行所有列都试过了都不行，说明问题出在更前面，它会继续回溯到第4行，改变第4行皇后的位置，然后重新尝试第5行、第6行...

通过这种“前进-检查-失败-回溯-再尝试”的机制，算法能够系统地搜索整个解空间，并最终找到所有满足条件的解。

Lua代码实现

-- lua解决八皇后问题
-- from the book <programing in lua>

N = 8

-- a是数组，n是行，c是列
function isplaceok(a, n, c)
  -- lua中的for循环是从expr1数值执行到expr2
  -- 对于这里而言就是i = 1一直到 i = n - 1
  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)
  -- every row
  for i = 1, N do
    -- every col
    for j = 1, N do
      io.write(a[i] == j and "X" or "-", " ")
    end
    io.write("\n")
  end
  io.write("\n")
end


-- put the queen into a
function addqueen(a, n)
  --是否所有queen都已经落位了
  if n > N then
    --如果是那就打印出棋盘
    printsolution(a)
  else
    for c = 1, N do
      if isplaceok(a, n, c) then
        a[n] = c
        --这里开始递归
        addqueen(a, n + 1)
      end
    end
  end
end

-- run
addqueen({}, 1)