- N皇后问题概述
- N皇后问题java代码解析
- 调用函数
- 回溯算法
- 判断选择
要想解决n皇后问题，首先要明白什么是n皇后问题。
在本篇文章中，借助 leetcode 51.N皇后问题 进行解析。
N皇后问题题目：
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
由上述题目的描述，简而言之，就是：
在一个棋盘上，一个皇后（棋子）的 同一列、同一行、以皇后为中心的两条对角线 都不能有任何棋子，求所有可能的情况，这就是N皇后问题。
N皇后问题java代码解析由于我使用了回溯法解决了N皇后问题，所以本篇文章详细讲述如何用回溯法解决n皇后问题。
本文仅仅代表作者的思路，可能有大佬的思路更好一些，欢迎大家发表想法。
在阅读本文之前，建议大家首先了解回溯法，本文会尽量让大家了解回溯法的解题技巧。
首先，N皇后问题的回溯代码大致可以分为调用函数（这里就不使用java方法的概念了，感觉函数更顺口一点）、回溯算法、判断选择三个方法。
调用函数顾名思义，调用函数就是调用回溯算法解决问题的函数，该函数篇幅很短，主要用于定义路径、调用回溯函数、返回结果三个作用。
class Solution {
//res表示result，保存最后的结果
List> res = new ArrayList<>();
//调用函数
public List> solveNQueens(int n) {
//记录正确的结果
ArrayList track = new ArrayList<>();
//回溯算法
backtrack(n, 0, track);
//返回结果
return res;
}
}
解释两点：
- 返回类型为List
类型，如：
[“.Q…”,“…Q”,“Q…”,“…Q.”]，这就是一个棋盘，一个正确的结果。 - 记录正确的结果时，我使用了List
而不是List ，是因为将 ‘.’ 修改为 ‘Q’ 时，StringBuilder 更简单一点。
public void backtrack(int n, int row, Listtrack) { //触发结束条件 if(track.size() == n) { List list = chg(track); res.add(list); return; } StringBuilder sb = new StringBuilder(); for(int i = 0;i < n;i++) { sb.append("."); } for(int i = 0;i < n;i++) { //排除不合法的选择 if(!isValid(n, track, row, i)) { continue; } //做选择 sb.setCharAt(i, 'Q'); track.add(sb); //进入下一层决策树 backtrack(n, row + 1, track); //取消选择 sb.setCharAt(i, '.'); track.remove(track.size() - 1); } }
分析：
//触发结束条件
if(track.size() == n) {
List list = chg(track);
res.add(list);
return;
}
这是回溯算法必须要有的，如果没有条件，那么回溯算法将会一直递归；n皇后问题的条件是：
当 n * n 大的棋盘上放置了 n 个皇后时，这种情况正确，递归结束并加入最终结果中。（chg函数是将 List 类型转换为 List 类型）
//sb 是棋盘中的某一行。
StringBuilder sb = new StringBuilder();
//进行初始化（“.”表示没有放棋子）
for(int i = 0;i < n;i++) {
sb.append(".");
}
//从第 0 列开始，第 n 列结束
for(int i = 0;i < n;i++) {
//排除不合法的选择
if(!isValid(n, track, row, i)) {
continue;
}
//尝试（尝试将第 row 行的第 i 列放置皇后）
sb.setCharAt(i, 'Q');
track.add(sb);
//进入下一层决策树（进入下一行继续尝试）
backtrack(n, row + 1, track);
//取消选择（将皇后取消，并删除该行）
sb.setCharAt(i, '.');
track.remove(track.size() - 1);
}
判断选择
public static boolean isValid(int n, Listtrack, int row, int col) { //检查列中是否有皇后互相冲突 for(int i = 0;i < row;i++) { //如果上方有‘Q’，不能放置，返回结果false。 if(track.get(i).charAt(col) == 'Q') { return false; } } //检查右上方是否有皇后互相冲突 for(int i = row - 1, j = col + 1;i >= 0 && j < n;i--, j++) { if(track.get(i).charAt(j) == 'Q') { return false; } } //检查左上方是否有皇后互相冲突 for(int i = row - 1, j = col - 1;i >= 0 && j >= 0;i--, j--) { if(track.get(i).charAt(j) == 'Q') { return false; } } return true; } //将 List 转换为 List ，可能多此一举，看看就好 public static List chg(List track) { List list = new ArrayList<>(); for(int i = 0;i < track.size();i++) { list.add(new String(track.get(i))); } return list; }
到这里，n皇后的 java 代码部分就结束了。回溯题目大同小异，这里放一下 backtrack 的大致框架：
public static void backtrack(int n, Listtrack) { //触发结束条件（结束递归） if(......) { //向结果中添加一种解决方案 res.add(list); //返回 return; } for(int i = 0;i < n;i++) { //排除不合法的选择 if(...) { continue; } //做选择 track.add(...); //进入下一层决策树 backtrack(n, track); //取消选择 track.remove(track.size() - 1); } }
大致框架就这样子，但是要根据实际情况灵活变通。
至此，n 皇后问题就解决啦，感谢观看！
