网站建设框架都有哪些内容,html5国内网站建设,手机图片编辑,英文专业的网站设计思路#xff1a; N皇后问题要求在一个nn的棋盘上放置n个皇后#xff0c;使得它们不能相互攻击。皇后可以攻击同一行、同一列#xff0c;以及两个对角线方向上的其他皇后。解决这个问题意味着找到所有可能的棋盘配置#xff0c;每个配置都符合上述条件。
1、初始化数据结构…
思路 N皇后问题要求在一个n×n的棋盘上放置n个皇后使得它们不能相互攻击。皇后可以攻击同一行、同一列以及两个对角线方向上的其他皇后。解决这个问题意味着找到所有可能的棋盘配置每个配置都符合上述条件。
1、初始化数据结构
使用一个整型数组record来记录每个皇后的位置。其中record[i] j表示第i行的皇后位于第j列。使用一个列表list来收集所有有效的棋盘配置。
2. 递归和回溯
利用递归函数遍历棋盘的所有可能状态对每一行尝试放置一个皇后并通过回溯方法探索所有可能的解决方案
递归函数定义创建一个递归函数process2(i, record, n, list)其中i代表当前行record用于记录皇后位置n为棋盘大小list用于存储所有合法的棋盘配置。终止条件当当前行i等于n时表示所有行都已经成功放置了皇后。此时根据record数组生成一个棋盘配置加入到解决方案列表list中。
3. 验证放置是否有效
在递归中对于每一行的每一列检查放置皇后是否合法
列冲突确保没有其他皇后在同一列。对角线冲突确保没有其他皇后在两个可能的对角线上。 这可以通过检查当前尝试放置的列的索引与之前每行皇后列的索引的差的绝对值是否等于行的差的绝对值来实现。
4. 生成棋盘配置
每当找到一个有效的皇后布局后需要将其转换为棋盘的字符串表示形式
对于record中的每个元素表示列位置构造一个字符串其中Q表示皇后的位置而.表示空位。
5. 回溯
每次尝试放置一个皇后后进入下一行继续尝试。如果发现当前行的某个列位置导致无法找到有效配置则回溯到上一行改变皇后的位置然后再次尝试。通过逐行递归和回溯可以探索棋盘的所有可能状态直到找到所有有效的解决方案。
通过这种结合递归与回溯的方法N皇后问题可以被系统地解决所有可能的棋盘配置都会被找到并记录。
class Solution {// 主函数用于解决n皇后问题接收棋盘大小n返回所有合法的棋盘配置public ListListString solveNQueens(int n) {if (n 1) {return new ArrayList(); // 如果n小于1直接返回空列表因为没有可行的棋盘配置}int[] record new int[n]; // 创建数组记录每一行皇后的列位置ListListString list new ArrayList(); // 存储所有有效的棋盘配置process2(0, record, n, list); // 从第0行开始递归处理放置皇后return list; // 返回所有找到的棋盘配置}// 递归函数用于处理从第i行开始的皇后放置private void process2(int i, int[] record, int n, ListListString list) {if (i n) { // 如果已经处理完所有行ListString childList new ArrayList(); // 创建一个新的列表存储当前棋盘的一种配置for (int index 0; index record.length; index) { // 遍历每一行int num record[index]; // 获取当前行皇后的列位置StringBuilder builder new StringBuilder(); // 使用StringBuilder构建每一行的字符串表示for (int j 0; j n; j) { // 遍历每一列if (j num) {builder.append(Q); // 如果当前列是皇后的位置添加Q} else {builder.append(.); // 否则添加.}}childList.add(builder.toString()); // 将构建好的字符串加入到当前棋盘配置中}list.add(childList); // 将当前配置添加到解决方案列表中} else {// 尝试在当前行i放置皇后的所有可能列for (int j 0; j n; j) {if (isValid(record, i, j)) { // 检查在第i行的第j列放置皇后是否有效record[i] j; // 如果有效记录这个位置process2(i 1, record, n, list); // 递归处理下一行}}}}// 检查在第i行的第j列放置皇后是否会导致冲突public static boolean isValid(int[] record, int i, int j) {for (int k 0; k i; k) { // 检查之前的每一行// 判断列冲突和对角线冲突if (j record[k] || Math.abs(record[k] - j) Math.abs(i - k)) { return false; // 如果有冲突返回false}}return true; // 如果没有冲突返回true}
}
