# 37. Sudoku Solver      • Time: NP-Complete
• Space: $O(1)$
  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 class Solution { public: void solveSudoku(vector>& board) { solve(board, 0); } private: bool solve(vector>& board, int s) { if (s == 81) return true; const int i = s / 9; const int j = s % 9; if (board[i][j] != '.') return solve(board, s + 1); for (char c = '1'; c <= '9'; ++c) if (isValid(board, i, j, c)) { board[i][j] = c; if (solve(board, s + 1)) return true; board[i][j] = '.'; } return false; } bool isValid(vector>& board, int row, int col, char c) { for (int i = 0; i < 9; ++i) if (board[i][col] == c || board[row][i] == c || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; return true; } }; 
  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 class Solution { public void solveSudoku(char[][] board) { dfs(board, 0); } private boolean dfs(char[][] board, int s) { if (s == 81) return true; final int i = s / 9; final int j = s % 9; if (board[i][j] != '.') return dfs(board, s + 1); for (char c = '1'; c <= '9'; ++c) if (isValid(board, i, j, c)) { board[i][j] = c; if (dfs(board, s + 1)) return true; board[i][j] = '.'; } return false; } private boolean isValid(char[][] board, int row, int col, char c) { for (int i = 0; i < 9; ++i) if (board[i][col] == c || board[row][i] == c || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; return true; } } 
  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 class Solution: def solveSudoku(self, board: List[List[str]]) -> None: def isValid(row: int, col: int, c: str) -> bool: for i in range(9): if board[i][col] == c or \ board[row][i] == c or \ board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == c: return False return True def solve(s: int) -> bool: if s == 81: return True i = s // 9 j = s % 9 if board[i][j] != '.': return solve(s + 1) for c in string.digits[1:]: if isValid(i, j, c): board[i][j] = c if solve(s + 1): return True board[i][j] = '.' return False solve(0)