回溯算法part06 算法
今日任务：
● 51. N皇后
● 37. 解数独
1.leetcode 51. N皇后
https://leetcode.cn/problems/n-queens/description/文章来源：https://www.toymoban.com/news/detail-802783.html
class Solution {
//存储结果
List<List<String>> result=new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
//存放一个棋盘,一个棋盘是一个二维数组
char[][] chessboard=new char[n][n];
//将棋盘填满逗点
for(char[] c:chessboard){
Arrays.fill(c,'.');
}
backrtacing(chessboard,n,0);//棋盘，多深，当前行（深度）
return result;
//n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，
//并且使皇后彼此之间不能相互攻击。
//皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子
}
public void backrtacing(char[][] chessboard,int n,int row){
//确定终止条件，如果此时深度已经为n了
if(row==n){
//将棋盘（二维数组）加进结果（二维集合）中
//将棋盘二维数组转成一维集合
//调用函数
result.add(Array2List(chessboard));
return;
}
//进行判断棋盘二维数组的每一个一维（控制横向）
for(int i=0;i<n;i++){
//第一行第一个元素表示是c[row][i]//row控制整体深度，第几行//i控制横向，哪一个元素
//要放皇后前，先检查这个位置的元素合不合法
if(isValid(row,i,n,chessboard)){
//合法了我们就放
chessboard[row][i]='Q';
//接着看接下来一层的一维，因为前一个一维已经处理好放不放n皇后了
backrtacing(chessboard,n,row+1);
//进行回溯
chessboard[row][i]='.';//前面函数调用完已经处理加不加进去了
//然后进行下一次
}
}
}
//将二维数组转成一维集合
public List Array2List(char[][] chessboard){
List<String> list=new ArrayList<>();
for(char[] c:chessboard){
list.add(String.copyValueOf(c));
}
return list;
}
//判断是不是有效的棋盘位置
public boolean isValid(int row, int col, int n, char[][] chessboard) {
// 检查列
for (int i=0; i<row; ++i) { // 相当于剪枝
if (chessboard[i][col] == 'Q') {
return false;
}
}
// 检查45度对角线
for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
// 检查135度对角线
for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
return true;
}
}
2.leetcode 37. 解数独
https://leetcode.cn/problems/sudoku-solver/description/文章来源地址https://www.toymoban.com/news/detail-802783.html
class Solution {
public void solveSudoku(char[][] board) {
//没有返回值
backtracing(board);
}
public boolean backtracing(char[][] board){
//遍历数独的一维横行(遍历行)
for(int i=0;i<board.length;i++){
//遍历列
for(int j=0;j<board.length;j++){
//如果遇到是数字的元素位置就跳过
if(board[i][j]!='.'){
continue;
}
//遇到不是数字元素的位置，也就是遇到逗点了，需要填充数字
for(char k='1';k<='9';k++){
//判断该位置是不是合法的,合法才可以加入数字
if(isValidSudoku(i,j,k,board)){
board[i][j]=k;
//开始递归
if(backtracing(board)){//如果有合适的直接返回
return true;
}
//进行回溯
board[i][j]='.';
}
}
//9个数字都试完了还不行，直接返回false
return false;
}
}
//遍历完没有返回false,说明找到了合适棋盘位置了
return true;
}
//判断棋盘是否合法
private boolean isValidSudoku(int row, int col, char val, char[][] board){
// 同行是否重复
for (int i = 0; i < 9; i++){
if (board[row][i] == val){
return false;
}
}
// 同列是否重复
for (int j = 0; j < 9; j++){
if (board[j][col] == val){
return false;
}
}
// 9宫格里是否重复
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++){
for (int j = startCol; j < startCol + 3; j++){
if (board[i][j] == val){
return false;
}
}
}
return true;
}
}
到了这里，关于回溯算法part06 算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
