Sudoku Solver
给一个2d数组, 是一个数独, 求解决数独问题.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
public class Solution { public void solveSudoku(char[][] board) { ArrayList<Integer> empty = new ArrayList<Integer>(); for(int i = 0 ; i < board.length; i++) { for(int j = 0 ; j < board[0].length; j++) { if(board[i][j] == '.') empty.add(i*9+j); } } int len = empty.size(); dfs(empty,len,board,0); } public boolean dfs(ArrayList<Integer> empty, int len, char[][] board, int cur) { if(cur == len){ return true; } int index = empty.get(cur); int row = index / 9; int col = index % 9; for(int v = 1; v <= 9; v++) { if(isValid(board, v, row, col)){ board[row][col] = (char)(v+'0'); if(dfs(empty,len,board,cur+1)) return true; board[row][col] = '.'; } } return false; } public boolean isValid(char[][] board, int v, int row, int col) { for(int i = 0 ; i < 9; i++ ){ if(board[row][i] == v + '0') return false; if(board[i][col] == v + '0') return false; int r = 3*(row/3) + (i/3); int c = 3*(col/3) + (i%3); if(board[r][c] == v + '0') return false; } return true; } } |