回溯算法经典题目之N皇后
提到回溯算法那肯定离不开 n 皇后这道算法题，它实在是太经典了。 所谓 n 皇后问题 ，指的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'q' 和 '.' 分别代表了皇后和空位。
输入：n = 4输出：[[.q..,...q,q...,..q.],[..q.,q...,...q,.q..]]解释：4 皇后问题存在两个不同的解法。 我觉得你应该能够结合视频动画和保姆级别的代码注释把这道题目弄清楚。
class solution { // 保存所有符合要求的解 list res = new arraylist(); public list solvenqueens(int n) { // attack 用来表示皇后的攻击范围 int[][] attack = new int[n][n]; // queen 用来记录皇后的位置 char[][] queen = new char[n][n]; // 初始化二维数组 queen 中所有的元素为 '.' for(char[] c : queen) { arrays.fill(c, '.'); } // 初始化二维数组 attack 中所有的元素为 0 // 0 代表没有皇后能攻击得到 // 1 代表出于任意一个皇后的攻击范围内 for(int[] c : attack) { arrays.fill(c, 0); } // 从棋盘的第 0 行第 0 列处理 n 皇后的情况 backtrack(0,n,queen,attack); // 最后，返回所有符合要求的解 return res; } // 很显然，每一行只能放置一个皇后，所以我们每一行每一行的来放置皇后 // k 表示当前处理的行 // n 表示需要放置多少个皇后，同时也代表棋盘的大小为 n * n // queen 用来记录皇后的位置 // attack 用来表示皇后的攻击范围 private void backtrack(int k ,int n , char[][] queen,int[][] attack){ // 如果发现在棋盘的最后一行放置好了皇后，那么就说明找到了一组符合要求的解 if(k == n){ // 由于 queen 为二维字符数组，所以需要转换为字符串数组 list list = new arraylist(); // 遍历二维数组 queen // 取出 queen 的每一行字符数组 c for (char[] c : queen) { // 把字符数组 c 中的所有字符转换为字符串的形式进行拼凑 // 比如 ['.','q','.','.',] // 转换为 '.q..' // 把这个字符串加入到 list 中 list.add(string.copyvalueof(c)); } // list 即为一组符合要求的解，把它加入到结果数组中 res.add(list); // 由于遍历完了所有的行，无需再遍历下去，所以返回 return; } // 每一行只能放置一个皇后 // 并且每一列也只能放置一个皇后 // 所以在 k 行中，从 0 列到 n - 1 列，判断皇后应该放置到哪个位置 for(int i = 0 ; i < n ; i++){ // 如果发现 attack[k][i] == 0 // 说明这个位置不在任何一个皇后的攻击范围内 // 所以可以考虑放置皇后 if(attack[k][i] == 0){ // 如果在 ( k , i ) 位置放置了皇后，那么就需要考虑在 k + 1 行应该怎么放置其它的皇后了 // 由于有可能在( k , i ) 位置放置了皇后之后，在后续的其它行会无法再放置其它的皇后 // 那么就需要回到 ( k , i ) 的状态，考虑能不能在 ( k , i + 1 )的位置放置 // 为了能够回到 ( k , i ) 的状态，所以需要先记录此时的 attack // 使用一个临时的二维数组，深度拷贝 attack // 如果不使用深度拷贝，而是直接使用 int[][] temp = c // 会导致 attack 发生改变是 temp 也会发生改变 // 这样也就无法保存之前的状态了 int[][] temp = new int[n][n]; // 通过两个 for 循环，把 attack 中的所有元素深度拷贝到 temp for(int l = 0 ; l < n ; l++){ for( int m = 0 ; m < n ; m++){ temp[l][m] = attack[l][m]; } } // queen 用来记录皇后的位置 // 那么 ( k , i ) 的位置 queen[k][i] = 'q' queen[k][i] = 'q'; // 由于新放置了一个皇后，所以攻击范围又更多了 // 所以需要更新 attack 数组 // 新放置皇后的坐标为 ( k , i ) ，同样的需要更新它的八个方向 checkqueenattack(k,i,attack); // 如果在 ( k , i ) 位置放置了皇后，那么就需要考虑在 k + 1 行应该怎么放置其它的皇后 // 递归的调用 backtrack 在 k + 1 行放置皇后 backtrack(k + 1,n,queen,attack); // 递归结束后，拿走皇后，恢复 attack 的状态，考虑能不能在 ( k ,i + 1 )的位置放置 attack = temp; // 恢复 queen 的状态，说明此时皇后不放置在( k , i ) 位置 queen[k][i] = '.'; } } } // 坐标 ( x , y) 为皇后所处的位置 // 更新 attack private void checkqueenattack(int x ,int y,int[][] attack){ // 对于每一个坐标 (x,y) 来说，都有上、下、左、右、左上、左下、右上、右下 八个方向 //【左上】的坐标为 (x - 1, y - 1) //【上】的坐标为 (x - 1, y ) //【右上】的坐标为 (x + 1, y + 1) //【左】的坐标为 (x, y + 1) //【右】的坐标为 (x , y - 1) //【左下】的坐标为 (x + 1, y - 1) //【下】的坐标为 (x + 1, y) //【右下】的坐标为 (x + 1, y + 1) // 通过两个一维数组可以表示这八个方向 // dx 表示 x 的方向 int dx[] = { -1 , -1 , -1 , 0 , 0 , 1 , 1 , 1 }; // dy 表示 y 的方向 int dy[] = { -1 , 0 , 1 , -1 , 1 , -1 , 0 , 1 }; // 皇后所处的坐标肯定是皇后能攻击的位置，设置为 1 attack[x][y] = 1; // 以坐标 ( x , y) 为中心，去更新它八个方向的坐标 for(int j = 0 ; j < 8; j++){ // 由内向外的进行更新 for(int i = 1 ; i = 0 && nx = 0 && ny < attack.length){ // 那么这些位置就是在坐标为 （x，y）的皇后的攻击范围内，更新为 1 attack[nx][ny] = 1; } } } }}
一文看懂苹果A14芯片的战略
DPU特征结构系列（二）一种DPU参考设计
与高通合作的华芯通开始量产昇龙4800芯片
AI将信息化推向了新的高度 华为迎来了最好的发展时机
塔吊设备无线监控方案
回溯算法经典题目之N皇后
什么系统这么厉害，可以揭示人的衣服底下的身体的形状和位置
百亿市场的农用无人机竞争多有激烈?
IC设计流程之全定制和半定制
打破垄断局面，比亚迪汽车级LED追赶国际品牌
单片射频收发芯片TRF6901的原理与应用
如何利用树莓派安装Docker和Docker-compose呢？
通过PLC数据采集系统实现智能工厂高效数据管理
Apple iTouch3 电路图赏析
新益昌成功进入了半导体固晶机和锂电池设备领域
xSPI STT-MRAM--EM064LX产品系列的主要优势
边缘人工智能，从传感器融合到深度神经网络
多家企业悄悄推出单晶中镍三元产品 市场热度起升
中国自动驾驶有了好消息！中国无人驾驶进军欧洲环卫第一车
关于那些储存技术的发展之路
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'q' 和 '.' 分别代表了皇后和空位。
输入：n = 4输出：[[.q..,...q,q...,..q.],[..q.,q...,...q,.q..]]解释：4 皇后问题存在两个不同的解法。 我觉得你应该能够结合视频动画和保姆级别的代码注释把这道题目弄清楚。
class solution { // 保存所有符合要求的解 list res = new arraylist(); public list solvenqueens(int n) { // attack 用来表示皇后的攻击范围 int[][] attack = new int[n][n]; // queen 用来记录皇后的位置 char[][] queen = new char[n][n]; // 初始化二维数组 queen 中所有的元素为 '.' for(char[] c : queen) { arrays.fill(c, '.'); } // 初始化二维数组 attack 中所有的元素为 0 // 0 代表没有皇后能攻击得到 // 1 代表出于任意一个皇后的攻击范围内 for(int[] c : attack) { arrays.fill(c, 0); } // 从棋盘的第 0 行第 0 列处理 n 皇后的情况 backtrack(0,n,queen,attack); // 最后，返回所有符合要求的解 return res; } // 很显然，每一行只能放置一个皇后，所以我们每一行每一行的来放置皇后 // k 表示当前处理的行 // n 表示需要放置多少个皇后，同时也代表棋盘的大小为 n * n // queen 用来记录皇后的位置 // attack 用来表示皇后的攻击范围 private void backtrack(int k ,int n , char[][] queen,int[][] attack){ // 如果发现在棋盘的最后一行放置好了皇后，那么就说明找到了一组符合要求的解 if(k == n){ // 由于 queen 为二维字符数组，所以需要转换为字符串数组 list list = new arraylist(); // 遍历二维数组 queen // 取出 queen 的每一行字符数组 c for (char[] c : queen) { // 把字符数组 c 中的所有字符转换为字符串的形式进行拼凑 // 比如 ['.','q','.','.',] // 转换为 '.q..' // 把这个字符串加入到 list 中 list.add(string.copyvalueof(c)); } // list 即为一组符合要求的解，把它加入到结果数组中 res.add(list); // 由于遍历完了所有的行，无需再遍历下去，所以返回 return; } // 每一行只能放置一个皇后 // 并且每一列也只能放置一个皇后 // 所以在 k 行中，从 0 列到 n - 1 列，判断皇后应该放置到哪个位置 for(int i = 0 ; i < n ; i++){ // 如果发现 attack[k][i] == 0 // 说明这个位置不在任何一个皇后的攻击范围内 // 所以可以考虑放置皇后 if(attack[k][i] == 0){ // 如果在 ( k , i ) 位置放置了皇后，那么就需要考虑在 k + 1 行应该怎么放置其它的皇后了 // 由于有可能在( k , i ) 位置放置了皇后之后，在后续的其它行会无法再放置其它的皇后 // 那么就需要回到 ( k , i ) 的状态，考虑能不能在 ( k , i + 1 )的位置放置 // 为了能够回到 ( k , i ) 的状态，所以需要先记录此时的 attack // 使用一个临时的二维数组，深度拷贝 attack // 如果不使用深度拷贝，而是直接使用 int[][] temp = c // 会导致 attack 发生改变是 temp 也会发生改变 // 这样也就无法保存之前的状态了 int[][] temp = new int[n][n]; // 通过两个 for 循环，把 attack 中的所有元素深度拷贝到 temp for(int l = 0 ; l < n ; l++){ for( int m = 0 ; m < n ; m++){ temp[l][m] = attack[l][m]; } } // queen 用来记录皇后的位置 // 那么 ( k , i ) 的位置 queen[k][i] = 'q' queen[k][i] = 'q'; // 由于新放置了一个皇后，所以攻击范围又更多了 // 所以需要更新 attack 数组 // 新放置皇后的坐标为 ( k , i ) ，同样的需要更新它的八个方向 checkqueenattack(k,i,attack); // 如果在 ( k , i ) 位置放置了皇后，那么就需要考虑在 k + 1 行应该怎么放置其它的皇后 // 递归的调用 backtrack 在 k + 1 行放置皇后 backtrack(k + 1,n,queen,attack); // 递归结束后，拿走皇后，恢复 attack 的状态，考虑能不能在 ( k ,i + 1 )的位置放置 attack = temp; // 恢复 queen 的状态，说明此时皇后不放置在( k , i ) 位置 queen[k][i] = '.'; } } } // 坐标 ( x , y) 为皇后所处的位置 // 更新 attack private void checkqueenattack(int x ,int y,int[][] attack){ // 对于每一个坐标 (x,y) 来说，都有上、下、左、右、左上、左下、右上、右下 八个方向 //【左上】的坐标为 (x - 1, y - 1) //【上】的坐标为 (x - 1, y ) //【右上】的坐标为 (x + 1, y + 1) //【左】的坐标为 (x, y + 1) //【右】的坐标为 (x , y - 1) //【左下】的坐标为 (x + 1, y - 1) //【下】的坐标为 (x + 1, y) //【右下】的坐标为 (x + 1, y + 1) // 通过两个一维数组可以表示这八个方向 // dx 表示 x 的方向 int dx[] = { -1 , -1 , -1 , 0 , 0 , 1 , 1 , 1 }; // dy 表示 y 的方向 int dy[] = { -1 , 0 , 1 , -1 , 1 , -1 , 0 , 1 }; // 皇后所处的坐标肯定是皇后能攻击的位置，设置为 1 attack[x][y] = 1; // 以坐标 ( x , y) 为中心，去更新它八个方向的坐标 for(int j = 0 ; j < 8; j++){ // 由内向外的进行更新 for(int i = 1 ; i = 0 && nx = 0 && ny < attack.length){ // 那么这些位置就是在坐标为 （x，y）的皇后的攻击范围内，更新为 1 attack[nx][ny] = 1; } } } }}
一文看懂苹果A14芯片的战略
DPU特征结构系列（二）一种DPU参考设计
与高通合作的华芯通开始量产昇龙4800芯片
AI将信息化推向了新的高度 华为迎来了最好的发展时机
塔吊设备无线监控方案
回溯算法经典题目之N皇后
什么系统这么厉害，可以揭示人的衣服底下的身体的形状和位置
百亿市场的农用无人机竞争多有激烈?
IC设计流程之全定制和半定制
打破垄断局面，比亚迪汽车级LED追赶国际品牌
单片射频收发芯片TRF6901的原理与应用
如何利用树莓派安装Docker和Docker-compose呢？
通过PLC数据采集系统实现智能工厂高效数据管理
Apple iTouch3 电路图赏析
新益昌成功进入了半导体固晶机和锂电池设备领域
xSPI STT-MRAM--EM064LX产品系列的主要优势
边缘人工智能，从传感器融合到深度神经网络
多家企业悄悄推出单晶中镍三元产品 市场热度起升
中国自动驾驶有了好消息！中国无人驾驶进军欧洲环卫第一车
关于那些储存技术的发展之路