题目
代码分析
递归参数的确定
1,使用的思想就是回溯递归,每放入一个位置就判断一下,如果可以的话,我们就继续递归,不行的话,复原当前位置,换一个数字继续递归。对于二维数组的话,我们的row和col是不断改变的。所以我们的方法参数包括row和col,每一次这个f的时候,需要改变的就是row和col。
2,当然也需要带上char[][] board这个二维数组
3,除了回溯的思想,我们还需要用到hash的概念,因为每放一个数字就要判断它的合法性,如果使用for循环进行判断的话,时间复杂度会很高,所以我们使用hash的思想来降低时间复杂度,需要判断的时间复杂度来自于三个地方
行,列,小方块
使用二维数组这个变形的hash结构
boolean[][] rowUsed=new boolean[row][num] boolean[][] colUsed=new boolean[col][num] boolean[][] smallAreaUsed=new boolean[row/3][col/3][nun]
举个例子,如果我们放入的数字是5,然后所在的行是3,我们的意思就是在第3行数字5有没有出现过,有没有出现过就是使用false和true
初始化
public void solveSudoku(char[][] board) { // 三个布尔数组 表明 行, 列, 还有 3*3 的方格的数字是否被使用过 boolean[][] rowUsed = new boolean[9][10]; boolean[][] colUsed = new boolean[9][10]; boolean[][][] boxUsed = new boolean[3][3][10]; // 初始化 for(int row = 0; row < board.length; row++){ for(int col = 0; col < board[0].length; col++) { int num = board[row][col] - '0'; if(1 <= num && num <= 9){ rowUsed[row][num] = true; colUsed[col][num] = true; boxUsed[row/3][col/3][num] = true; } } } // 递归尝试填充数组 recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, 0, 0); }
递归
递归的大概框架如下
f(char[][] board,int row,int col,三个哈希结构) { //base case //如果是空位置,就要具体的进行递归 //如果不是空位置,就继续递归进入 }
首先是base case,我们就想的极端一点,如果我们进入到最后一个位置的话,表明这个数独已经填充完毕,这样的话就表明数独解开了
if(col == board[0].length){ col = 0; row++; if(row == board.length){ return true; } }
两种情况,一个是最极端的情况,一个是有点极端的情况,对于后者,我们就需要换行操作,如果换行操作导致了是最后一行+1的话,表明就是前者这个最极端的情况。这个就是base case的完成情况
然后就是对于空位置的处理情况,肯定就是一个个的字符进行尝试,尝试成功的话,就进入,如果失败的话,就for循环的下一个位置。如果所有的for循环都不成功,就表明这个数独是无解的就直接return false就可以了。
如果某一个循环的情况是有解的话,我们就可以直接return true,我们来展示一下我们的递归框架
for(循环1----9) { if 看看放数字可不可以,就是使用那三个hash结构进行判断 { 如果可以放的话,我们就放入,然后修改哈希的结构。然后就进行递归了 f(char[][] ,row,col+1,哈希结构) 我们不能直接将这个f返回,只有它返回是true的情况才可以返回,如果是false的话,不能直接返回,因为我们还需要判断其他的情况,也就是使用下个循环的内容。 如果没有返回true的话,表明我们就要进行下一次的循环了,然后就是复原操作 } } 如果所有的情况都不行,表明在当前位置数独是没有解的,我们就直接返回false就可以了
详细代码如下
if(board[row][col]=='.') { for(char c='1';c<='9';c++) { int num=c-'0'; boolean used=!(rowUsed[row][num]||colUsed[col][num]||smallAreaUsed[row/3][col/3][num]); if(used) { board[row][col]=c; rowUsed[row][num]=true; colUsed[col][num]=true; smallAreaUsed[row/3][col/3][num]=true; if(f(board, rowUsed, colUsed, smallAreaUsed, row, col+1)) return true; board[row][col]='.'; rowUsed[row][num]=false; colUsed[col][num]=false; smallAreaUsed[row/3][col/3][num]=false; } } return false; }
如果不是空的话,直接进入下次的循环就可以了
else { return f(board, rowUsed, colUsed, smallAreaUsed, row, col+1); }
代码展示
public static void main(String[] args) { char[][] 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'} }; solveSudoku(board); for(int i=0;i<board.length;i++) { for(int j=0;j<board[0].length;j++) { System.out.print(board[i][j]+" "); } System.out.println(); } } public static void solveSudoku(char[][] board) { //1-----9 boolean[][] rowUsed=new boolean[9][10]; boolean[][] colUsed=new boolean[9][10]; boolean[][][] smallAreaUsed=new boolean[3][3][10]; //init for(int i=0;i<board.length;i++) for(int j=0;j<board[0].length;j++) { if(board[i][j]!='.') { int num=board[i][j]-'0'; rowUsed[i][num]=true; colUsed[j][num]=true; smallAreaUsed[i/3][j/3][num]=true; } } //递归求解 f(board,rowUsed,colUsed,smallAreaUsed,0,0); } public static boolean f(char[][] board, boolean[][] rowUsed, boolean[][] colUsed ,boolean[][][] smallAreaUsed ,int row,int col) { if(col==board[0].length) { col=0; row++; if(row==board.length) { return true; } } if(board[row][col]=='.') { for(char c='1';c<='9';c++) { int num=c-'0'; boolean used=!(rowUsed[row][num]||colUsed[col][num]||smallAreaUsed[row/3][col/3][num]); if(used) { board[row][col]=c; rowUsed[row][num]=true; colUsed[col][num]=true; smallAreaUsed[row/3][col/3][num]=true; if(f(board, rowUsed, colUsed, smallAreaUsed, row, col+1)) return true; board[row][col]='.'; rowUsed[row][num]=false; colUsed[col][num]=false; smallAreaUsed[row/3][col/3][num]=false; } } return false; }else { return f(board, rowUsed, colUsed, smallAreaUsed, row, col+1); } }
学习次数
完成次数 1次 12月25日 星期三