Problem Description
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits 1-9 must occur exactly once in each row.
- Each of the digits 1-9 must occur exactly once in each column.
- Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
The '.' character indicates empty cells.
Examples
Input: 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"]] Output: [["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"]]
Python Solution
def solveSudoku(board: List[List[str]]) -> None:
def isValid(num: str, pos: tuple) -> bool:
# Check row
for x in range(9):
if board[pos[0]][x] == num and pos[1] != x:
return False
# Check column
for x in range(9):
if board[x][pos[1]] == num and pos[0] != x:
return False
# Check box
box_x = pos[1] // 3
box_y = pos[0] // 3
for i in range(box_y * 3, box_y * 3 + 3):
for j in range(box_x * 3, box_x * 3 + 3):
if board[i][j] == num and (i,j) != pos:
return False
return True
def solve() -> bool:
for i in range(9):
for j in range(9):
if board[i][j] == ".":
for num in "123456789":
if isValid(num, (i,j)):
board[i][j] = num
if solve():
return True
board[i][j] = "."
return False
return True
solve()Java Solution
class Solution {
public void solveSudoku(char[][] board) {
solve(board);
}
private boolean solve(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (solve(board))
return true;
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, int row, int col, char num) {
for (int x = 0; x < 9; x++) {
if (board[row][x] == num) return false;
}
for (int x = 0; x < 9; x++) {
if (board[x][col] == num) return false;
}
int startRow = row - row % 3, startCol = col - col % 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i + startRow][j + startCol] == num) return false;
}
}
return true;
}
}C++ Solution
class Solution {
public:
void solveSudoku(vector>& board) {
solve(board);
}
private:
bool solve(vector>& board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (solve(board))
return true;
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
bool isValid(vector>& board, int row, int col, char num) {
for (int x = 0; x < 9; x++) {
if (board[row][x] == num) return false;
}
for (int x = 0; x < 9; x++) {
if (board[x][col] == num) return false;
}
int startRow = row - row % 3, startCol = col - col % 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i + startRow][j + startCol] == num) return false;
}
}
return true;
}
}; JavaScript Solution
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solveSudoku = function(board) {
const solve = () => {
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (board[i][j] === '.') {
for (let num = 1; num <= 9; num++) {
const char = num.toString();
if (isValid(i, j, char)) {
board[i][j] = char;
if (solve())
return true;
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
};
const isValid = (row, col, num) => {
for (let x = 0; x < 9; x++) {
if (board[row][x] === num) return false;
}
for (let x = 0; x < 9; x++) {
if (board[x][col] === num) return false;
}
const startRow = Math.floor(row / 3) * 3;
const startCol = Math.floor(col / 3) * 3;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[i + startRow][j + startCol] === num) return false;
}
}
return true;
};
solve();
};C# Solution
public class Solution {
public void SolveSudoku(char[][] board) {
Solve(board);
}
private bool Solve(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (IsValid(board, i, j, c)) {
board[i][j] = c;
if (Solve(board))
return true;
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
private bool IsValid(char[][] board, int row, int col, char num) {
for (int x = 0; x < 9; x++) {
if (board[row][x] == num) return false;
}
for (int x = 0; x < 9; x++) {
if (board[x][col] == num) return false;
}
int startRow = row - row % 3, startCol = col - col % 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i + startRow][j + startCol] == num) return false;
}
}
return true;
}
}Complexity Analysis
- Time Complexity: O(9^(n*n)) where n is the board size (9 in this case)
- Space Complexity: O(n*n) due to recursion stack
Solution Explanation
This solution uses backtracking to solve the Sudoku puzzle. Here's how it works:
- For each empty cell:
- Try placing numbers 1-9
- Check if the number is valid in current position
- If valid, recursively try to solve the rest of the puzzle
- If solution is found, we're done
- If no solution is found, backtrack by removing the number
- The isValid function checks:
- Row constraint: number doesn't exist in current row
- Column constraint: number doesn't exist in current column
- Box constraint: number doesn't exist in current 3x3 box
Key points:
- Uses depth-first search with backtracking
- Modifies the board in-place
- Returns early when a solution is found
- Handles constraints efficiently