Sudoku Solver
Write a program to solve a Sudoku puzzle. The program should take a 2D array representing the puzzle as input, where empty cells are represented by 0. The program should fill in the empty cells with numbers from 1 to 9 such that each row, column, and 3x3 sub-grid contains each number exactly once.
Constraints:
- The input puzzle is a 9x9 2D array
- The input puzzle contains numbers from 0 to 9
- The input puzzle is valid (i.e., it is possible to solve it)
Examples:
Input: [[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,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]]
Explanation: The program fills in the empty cells with numbers from 1 to 9 such that each row, column, and 3x3 sub-grid contains each number exactly once.
Solutions
Backtracking
The backtracking approach is used to solve the Sudoku puzzle. The program tries to fill in the empty cells with numbers from 1 to 9. If a number is valid (i.e., it does not appear in the same row, column, or 3x3 sub-grid), the program recursively tries to fill in the rest of the puzzle. If it is not possible to fill in the rest of the puzzle, the program backtracks and tries a different number.
def solve_sudoku(board):
def is_valid(board, row, col, num):
for i in range(9):
if board[row][i] == num:
return False
for i in range(9):
if board[i][col] == num:
return False
start_row = row - row % 3
start_col = col - col % 3
for i in range(3):
for j in range(3):
if board[i + start_row][j + start_col] == num:
return False
return True
def solve(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1, 10):
if is_valid(board, i, j, num):
board[i][j] = num
if solve(board):
return True
board[i][j] = 0
return False
return True
solve(board)Follow-up:
How would you optimize the solution to solve larger Sudoku puzzles?
