[leetcode] Sudoku solver

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 44 45 46 47 48 49 50 51 52 53 54 55 56

public class Solution { public void solveSudoku(char[][] board) { dfs(board, 0, 0); } private boolean dfs(char[][] board, int row, int col){ if (row >= 9) return true; int nextCol = (col+1)%9; int nextRow = row+(col+1)/9; if (board[row][col] != '.') return dfs(board, nextRow, nextCol); else{ for (int i = 0; i < 9; i++){ board[row][col] = (char)(i+'1'); if (isValid(board, row, col) && dfs(board, nextRow, nextCol)) return true; board[row][col] = '.'; } } return false; } private boolean isValid(char[][] board, int row, int col){ boolean lookup[] = new boolean[9]; //check row for (int i = 0; i < 9; i ++){ if (board[row][i] != '.'){ int index = board[row][i] - '0' -1; if (lookup[index]) return false; lookup[index] = true; } } //check column lookup = new boolean[9]; for (int i = 0; i < 9; i++){ if (board[i][col] != '.'){ int index = board[i][col] - '0' - 1; if(lookup[index]) return false; lookup[index] = true; } } //check box int startingRow = (row/3)*3; int startingCol = (col/3)*3; lookup = new boolean[9]; for (int i = startingRow; i < startingRow+3; i++){ for (int j = startingCol; j < startingCol+3; j++){ if (board[i][j] != '.'){ int index = board[i][j] - '0' - 1; if (lookup[index]) return false; lookup[index] = true; } } } return true; } }