https://leetcode-cn.com/problems/sudoku-solver/
难度困难936收藏分享切换为英文接收动态反馈
编写一个程序,通过填充空格来解决数独问题。
数独的解法需 遵循如下规则:
1-9
在每一行只能出现一次。1-9
在每一列只能出现一次。1-9
在每一个以粗实线分隔的 3x3
宫内只能出现一次。(请参考示例图)数独部分空格内已填入了数字,空白格用 '.'
表示。
示例:
输入: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]
是一位数字或者 '.'
通过次数97,696提交次数145,663
class Solution { int [][] line = new int[9][9]; int [][] column = new int[9][9]; int [][][] block = new int[3][3][9]; boolean valid = false; List<int[]> blank = new ArrayList<int[]>(); public void solveSudoku(char[][] board) { for(int i=0;i<9;i++) { for(int j=0;j<9;j++) { if(board[i][j]=='.') { blank.add(new int[]{i,j}); } else { int x = board[i][j]-'0'-1; line[i][x] = column[j][x] = block[i/3][j/3][x]=1; } } } dfs(board, 0); } void dfs(char[][] board,int index) { if(index == blank.size()) { valid = true; return; } int[] blank_ = blank.get(index); int i = blank_[0]; int j = blank_[1]; for(int d =0 ;d < 9 && !valid;++d) { if(line[i][d]!=1 && column[j][d]!=1 && block[i/3][j/3][d]!=1) { line[i][d] = column[j][d] = block[i/3][j/3][d] = 1; board[i][j] = (char)(d+'0'+1); dfs(board,index+1); line[i][d] = column[j][d] = block[i/3][j/3][d] = 0; } } } }