Day29代码随想录(1刷) 回溯

本文主要是介绍Day29代码随想录(1刷) 回溯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

• 1 <= n <= 9

 状态：完成

思路：还是用回溯去解决这个问题，一行就是一个树层，每个树层先判断在这个位置上符不符合要求然后再进入下一层，就这样子到最后一层为止，把结果装进result数组里面。

class Solution {List<List<String>> result=new ArrayList<>();List<String> list=new LinkedList<>();int Q_num=0;public List<List<String>> solveNQueens(int n) {char[] arr=new char[n];Arrays.fill(arr,'.');for(int i=0;i<n;i++){list.add(String.valueOf(arr));}backstracking(0,0,n);return result;}public void backstracking(int x,int y,int n){if(Q_num==n){result.add(new LinkedList(list));return;}String temp=list.get(y);for(int i=x;i<n;i++){boolean flag=isVaild(i,y,n);System.out.println(i+" "+y+" "+flag+" "+list);if(flag){Q_num++;list.set(y,temp.substring(0,i)+"Q"+temp.substring(i+1,n));backstracking(0,y+1,n);list.set(y,temp.substring(0,i)+"."+temp.substring(i+1,n));Q_num--;}}}public boolean isVaild(int x,int y,int n){//列判断for(int i=0;i<n;i++){String temp=list.get(i);if(temp.charAt(x)=='Q') return false;}//行判断String temp=list.get(y);for(int i=0;i<n;i++){if(temp.charAt(i)=='Q') return false;}//斜线判断int startLeft_x=x;int startLeft_y=y;while(startLeft_x>0&&startLeft_y>0){startLeft_x--;startLeft_y--;}int startRight_x=x;int startRight_y=y;while(startRight_x<n-1&&startRight_y>0){startRight_x++;startRight_y--;}while(startLeft_x>=0&&startLeft_y>=0&&startLeft_x<n&&startLeft_y<n){String a=list.get(startLeft_y);if(a.charAt(startLeft_x)=='Q') return false;startLeft_x++;startLeft_y++;}while(startRight_x>=0&&startRight_y<n){String a=list.get(startRight_y);if(a.charAt(startRight_x)=='Q') return false;startRight_x--;startRight_y++;}return true;}
}

 37. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 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"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 '.'
• 题目数据 保证 输入数独仅有一个解

状态：完成

思路：这里我自己写是用了暴力的递归的方式去解决问题的，就是判断合不合适合适就填进去不合适就继续下个数，一个格子一个格子的去找的，carl那种二维递归就是一行一行地确定的，每次回溯都用两个for循环。

class Solution {List<List<Integer>> list=new ArrayList<>();public void solveSudoku(char[][] board) {for(int i=0;i<9;i++){for(int k=0;k<9;k++){if(board[i][k]=='.'){ArrayList<Integer> temp= new ArrayList<>();temp.add(i);temp.add(k);list.add(temp);}}}System.out.println(backstracking(board,0));}public boolean backstracking(char[][] board,int index){if(index==list.size()) return true;List<Integer> temp=list.get(index);int x=temp.get(0);int y=temp.get(1);for(int i=1;i<=9;i++){if(isVaild(x,y,i,board)){board[x][y]=(char)(i+48);System.out.println(x+" "+y+" "+(char)(i+48));if(backstracking(board,index+1)) return true;board[x][y]='.';}}return false;}public boolean isVaild(int x,int y,int value,char[][] board){//9宫格检索int start_x=(x/3)*3;int start_y=(y/3)*3;for(int i=0;i<3;i++){for(int k=0;k<3;k++){if(board[start_x+i][start_y+k]!='.')if(Integer.valueOf(String.valueOf(board[start_x+i][start_y+k]))==value){return false;}}}//行for(int i=0;i<9;i++){if(board[i][y]!='.')if(Integer.valueOf(String.valueOf(board[i][y]))==value){return false;}}//列for(int i=0;i<9;i++){if(board[x][i]!='.')if(Integer.valueOf(String.valueOf(board[x][i]))==value){return false;}}return true;}
}

 感想：终于刷完回溯了，继续进步，贪心出发。

这篇关于Day29代码随想录(1刷) 回溯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---