回溯算法

类似穷举搜索，但是发现不满足条件就回溯回退，尝试别的路径。

四皇后问题：

要求横不有两个相同，竖和45°斜也没有。

当无法进行下去时进行回溯。

N皇后是递归+回溯的思想，利用回溯剪枝，减少运算数量。

输入k个皇后，输出满足的情况：

NQueens(k)

{

If k > n then

Output x //如果此时已经进行到最后一行，相当于找到一个可行解

For col = 1 to n do //尝试在每一行放皇后

{

If Place(k,col) then //检验是否可以放下

{

X[k] <- col //在k行col列 放置皇后

NQueens（k+1） //递归到下一行

}

}

}

验证函数：

Place(k,col)

{

For I = 1 to k – 1 do

{

If x[i] == col then

Return false

If x[i] – I == col – k then

Return false

If x[i] + I == col + k then

Return false

}

Return true

}

例如在（4，3），对角线为（2，1），（3，2）

| 1,1 | 1,2 | 1,3 | 1,4 | | 2,1 | 2,2 | 2,3 | 2,4 | | 3,1 | 3,2 | 3,3 | 3,4 | | 4,1 | 4,2 | 4,3 | 4,4 |