题目描述
回溯算法经典思路
- 寻找路径。
- 根据路径，每个节点做出选择，继续向下寻找。
- 撤销选择。
算法框架
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
回溯算法解决N皇后问题
/**
* @description:
* @author: lilang
* @version:
* @modified By:1170370113@qq.com
*/
public class ListSolution {
//定义返回节点位置
List<List<String>> solutions = new ArrayList<List<String>>();
public List<List<String>> solveNQueens(int n) {
// 初始化皇后棋盘 初始值设置为‘.’
char[][] board = new char[n][n];
for (int i = 0; i < board.length; i++) {
Arrays.fill(board[i], '.');
}
//对棋盘进行逐行遍历，这也是题目中所说的路径方向
backtrack(board, 0);
return solutions;
}
/**
* 棋盘回溯
* @param board 动态赋值过的棋盘
* @param row 遍历的当前行数
*/
void backtrack(char[][] board, int row) {
/**
* 说明已经可以终止循环，已经到达最后一行了
*
*/
if (row == board.length) {
solutions.add(array2List(board));
return;
}
/**
* 对每一行的元素进行检测
*/
for (int col = 0; col < board[row].length; col++) {
/**
* 判断是否满足皇后要求
*/
if (findIsValid(board, row, col)) {
//如果满足，选择当前位置变为皇后
board[row][col] = 'Q';
//向下继续执行
backtrack(board, row + 1);
//撤销当前选择
board[row][col] = '.';
}
}
}
private boolean findIsValid(char[][] board, int row, int col) {
// 检查列是否有皇后互相冲突
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q')
return false;
}
// 检查右上方是否有皇后互相冲突
for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; ) {
if (board[i][j] == 'Q') {
return false;
}
i--;
j++;
}
// 检查左上方是否有皇后互相冲突
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; ) {
if (board[i][j] == 'Q') {
return false;
}
i--;
j--;
}
return true;
}
private List<String> array2List(char[][] board) {
List<String> res = new LinkedList<>();
for (char[] i : board) {
StringBuffer sb = new StringBuffer();
for (char j : i) {
sb.append(j);
}
res.add(sb.toString());
}
return res;
}
}
