Name: PULI DEVI PRASAD
Reg no.: 19111277
Assignment 3: Recursion and Backtracking
Title: Sudoku Solver
Objective:
Practice recursion, backtracking, and constraint satisfaction.
Tasks:
● Implement a Sudoku puzzle solver using backtracking.
● Accept partially filled Sudoku boards as input.
● Display the solved board or indicate if the puzzle is unsolvable.
Implementation:
We use recursion and backtracking to solve the Sudoku puzzle. The algorithm fills empty
cells one by one by trying digits from 1 to 9. For each digit, it checks whether placing it
violates Sudoku rules (row, column, or subgrid constraints). If valid, it proceeds recursively
to solve the next cell. If no digit works, it backtracks and tries a different digit in the
previous cell.
Python Code:
def is_safe(board, row, col, num):
# Check row
for x in range(9):
if board[row][x] == num:
return False
# Check column
for x in range(9):
if board[x][col] == num:
return False
# Check 3x3 subgrid
start_row, start_col = 3 * (row // 3), 3 * (col // 3)
for i in range(3):
for j in range(3):
if board[start_row + i][start_col + j] == num:
return False
return True
def solve_sudoku(board):
for row in range(9):
for col in range(9):
if board[row][col] == 0:
for num in range(1, 10):
if is_safe(board, row, col, num):
board[row][col] = num
if solve_sudoku(board):
return True
board[row][col] = 0
return False
return True
def print_board(board):
for row in board:
print(row)
# Example partially filled Sudoku board (0 represents empty cell)
board = [
[3, 0, 6, 5, 0, 8, 4, 0, 0],
[5, 2, 0, 0, 0, 0, 0, 0, 0],
[0, 8, 7, 0, 0, 0, 0, 3, 1],
[0, 0, 3, 0, 0, 0, 0, 6, 8],
[9, 0, 0, 8, 6, 3, 0, 0, 5],
[0, 5, 0, 0, 9, 0, 6, 0, 0],
[1, 3, 0, 0, 0, 0, 2, 5, 0],
[0, 0, 0, 0, 0, 0, 0, 7, 4],
[0, 0, 5, 2, 0, 6, 3, 0, 0]
]
if solve_sudoku(board):
print_board(board)
else:
print("No solution exists")
