51.N皇后
题目
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。
代码
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
//棋盘初始化全为.
char[][] path = new char[n][n];
for(char[] c : path){
Arrays.fill(c,'.');
}
//从第一行开始回溯
backTracking(n,0,path);
return res;
}
public void backTracking(int n,int row,char[][] path){
//row到了最后一行，把path转为List加入res
if(row == n){
List<String> list = new ArrayList<>();
for(char[] c : path){ //获取棋盘的每一行char[]
String s = String.copyValueOf(c); //把char[]转为String
list.add(s);
}
res.add(list); //把path对应的List加入结果集
return;
}
//n个分支代表不同的列取值
for(int col=0; col < n; col++){
//如果此时path[row][col]的棋盘合法
if(judge(row,col,path,n) == true){
path[row][col] = 'Q'; //确定row行的Q
backTracking(n,row+1,path); //回溯row+1行
path[row][col] = '.'; //回溯row行的Q，为下一个列做准备
}
}
}
public boolean judge(int row,int col,char[][] path,int n){
//因为回溯过程中row一值变大，所以不用考虑同一行
//同一列
for(int i=row-1; i >=0; i--){
if(path[i][col] == 'Q'){
return false;
}
}
//45斜对角
for(int i=row-1,j=col-1; i>=0 && j>=0; i--,j--){
if(path[i][j] == 'Q'){
return false;
}
}
//135斜对角
for(int i=row-1,j=col+1; i>=0 && j<=n-1; i--,j++){
if(path[i][j] == 'Q'){
return false;
}
}
return true;
}
}总结
树的每一层row代表棋盘的一行，里面的for循环代表棋盘的一列。row从0开始，当row到达n，说明走出棋盘了，作为叶子节点可以收集结果。
如果某个位置设置为Q,加入棋盘后导致棋盘不合法（同行、同列、同斜线），就要剪枝，但是剪枝是需要知道当前位置的row和col，所以把剪枝写在for循环里面，只有当前位置合法，才修改成Q，然后递归下一行row+1。如果不合法，直接跳过当前col，进入for循环的下一层循环。
判断位置是否合法，需要判断同列、同斜线，其中同斜线有两种情况，不要漏了。而且同一行不用判断，因为每调用一次backTracking，row都+1，相当于row一直向下走不会同一行。
37.解数独
题目
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1：
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] 输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]] 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
代码
class Solution {
public void solveSudoku(char[][] board) {
backTracking(board);
}
public boolean backTracking(char[][] board){
for(int i=0; i < 9; i++){
for(int j=0; j < 9; j++){
//已经填入了数字
if(board[i][j] != '.'){
continue;
}
for(char k = '1'; k <= '9'; k++){
if(judge(i,j,k,board) == true){
board[i][j] = k;
//确定了位置[i][j]，递归下一个位置[i][j+1]
//如果这里没有返回true，说明board[i][j] = k的条件下，下面是没有数独的解的
if(backTracking(board)){
return true;
};
board[i][j] = '.'; //下一个位置[i][j+1]找不到，说明这个k是错误解，要恢复成.,继续判断下一个数组k
}
}
//53,53x的1-9都不行，说明数独无解，直接返回false，会终止
return false;
}
}
//两个for循环走完，还没返回，棋盘已经走完了，得到了唯一解
return true;
}
public boolean judge(int row,int col,char k,char[][] board){
//判断同一行
for(int i = 0; i < 9;i++){
if(board[row][i] == k){
return false;
}
}
//判断同一列
for(int i = 0; i < 9;i++){
if(board[i][col] == k){
return false;
}
}
//判断同一个九宫格
int starti = row / 3 * 3;
int startj = col / 3 * 3;
for(int i = starti; i < starti + 3; i++){
for(int j = startj; j < startj + 3; j++){
if(board[i][j] == k){
return false;
}
}
}
return true;
}
}
总结
两个for循环用于确定9*9棋盘的每一个位置，再用一个for循环确定该位置选[1-9]的哪个数字/
如果数字满足judge条件（不同行不同列不在一个9宫格），board[i][j]确定数字，然后，继续
递归调用棋盘，确定下一个位置的数字board[i][j+1]。
如果backTracking返回值为true说明，找到了数独的唯一解，直接return true，比如4的下面是
可以找到唯一解，后面的5-9就不用再走了，直接返回true.
如果for循环确定该位置选[1-9]的哪个数字的循环结束，还没有返回true，就说明9个数字都不
行，说明在这个情况下该数独就是无解的，需要回溯，比如351x,在for循环确定x的时候，循环结束
还是没有返回true，说明在351x的棋盘下，不会存在正确解了，需要回溯1，继续走352。
如果走棋盘的ij的两个for循环结束，说明棋盘已经走完确定完每一个位置了，直接返回true。
