回溯 皇后 算法笔记_算法笔记_04_回溯

设计思想：

(1)适用：求解搜索问题和优化问题。

(2)搜索空间：数，节点对应部分解向量，可行解在树叶上。

(3)搜索过程：采用系统的方法隐含遍历搜索树。

(4)搜索策略：深度优先，宽度优先，函数优先，宽深结合等。

(5)结点分支判定条件：

满足约束条件----分支扩张解向量

不满足约束条件----回溯到该节点的父节点

经典算法

N皇后

class Solution {

List> res = new ArrayList<>();

List curr = new ArrayList<>();

int[][] tag;

int n;

public List> solveNQueens(int n) {

this.n = n;

tag = new int[n][n];

backtrace(0);

return res;

}

private void backtrace(int level) {

if (level == this.n) {

res.add(new ArrayList<>(curr));

}else{

StringBuilder sb = new StringBuilder();

for (int i = 0; i < this.n; i++) {

if (tag[level][i] == 0) {

addTag(level, i);

sb.append("Q");

int col = i;

while (++col < n) sb.append(".");

} else {

sb.append(".");

continue;

}

curr.add(sb.toString());

backtrace(level + 1);

curr.remove(curr.size() - 1);

removeTag(level, i);

sb = new StringBuilder(sb.substring(0, i));

sb.append(".");

}

}

}

public void addTag(int row, int col) {

int le = row;

while (le < n) tag[le++][col]++;//该列

le = row + 1;

int x = col + 1;

while (le < n && x < n) tag[le++][x++]++;//右下角

le = row + 1;

x = col - 1;

while (le < n && x >= 0) tag[le++][x--]++;//左下角

}

;

public void removeTag(int row, int col) {

int le = row;

while (le < n) tag[le++][col]--;//该列

le = row + 1;

int x = col + 1;

while (le < n && x < n) tag[le++][x++]--;//右下角

le = row + 1;

x = col - 1;

while (le < n && x >= 0) tag[le++][x--]--;//左下角

}

}

总结

以上是生活随笔为你收集整理的回溯 皇后 算法笔记_算法笔记_04_回溯的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。