首页 > 代码库 > 【leetcode刷题笔记】Sudoku Solver
【leetcode刷题笔记】Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character ‘.‘.
You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.
题解：递归。在每个空位上尝试放置0~9的数，然后递归的解决剩下的空位。
单独写一个判断board目前(x,y)处的数是否合法的函数 public boolean isValidSudoku(char[][] board,int x,int y) ，它就只用检查跟(x,y)同行，同列和同一个九宫格的元素是否和board[x][y]有重复即可。（其实在九宫格中只用判断4个和(x,y)不同行列的元素，因为和(x,y)同行列的我们已经判断过了）。
代码如下：
1 public class Solution { 2 public boolean isValidSudoku(char[][] board,int x,int y) { 3 //check for row x 4 for(int i = 0;i < 9;i++) 5 if(i!=y && board[x][i] == board[x][y]) 6 return false; 7 8 //check for column y 9 for(int i = 0;i < 9;i++)10 if(i!= x &&board[i][y] == board[x][y])11 return false;12 13 //check for the 3*3 square (x,y) belongs to14 for(int i = 3 * (x/3);i<3*(x/3)+3;i++){15 for(int j = 3*(y/3);j<3*(y/3)+3;j++){16 if(i!=x && j != y && board[i][j] == board[x][y] )17 return false;18 }19 }20 21 return true;22 }23 24 private boolean solveSudokuRecur(char[][] board){25 for(int i = 0;i < 9;i++){26 for(int j = 0;j < 9;j++){27 if(board[i][j] != ‘.‘)28 continue;29 for(int k = 1;k <= 9;k++){30 board[i][j] = (char)(k + ‘0‘);31 if(isValidSudoku(board,i,j) && solveSudokuRecur(board))32 return true;33 board[i][j] = ‘.‘;34 }35 return false;36 }37 }38 return true;39 }40 public void solveSudoku(char[][] board) {41 solveSudokuRecur(board);42 }43 }
注意之前做过的Valid Sudoku这道题是判断整个数独是否合法，而不是单独某个位置(x,y)是否合法，它需要遍历整个数独，所以这段代码不能拿来用了。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。