Write Algorithm for Soduku

Question

Accepted Answer

Algorithm to solve Sudoku puzzle

Create a 9x9 grid to represent the puzzle
Fill in known numbers
For each empty cell, try numbers 1-9 until a valid number is found
Backtrack if no valid number can be found
Repeat until all cells are filled

Accepted Answer

Let's see the logic part first,

1. There are some empty cells so, our first goal is to find them. for simplicity make those empty cells as zero (0).
2. when we find all empty cells and fill them with zeroes, we have to check that numbers ranging from 1 to 9 are valid for that particular row or column.
3. Place a valid number and recursively call the function to fill another empty cell
4. Backtracking, If a number leads to a dead-end or cannot lead to a solution the algorithm backtracks to the previous cell and tries the next possible number.
Now, let's try to code it:

def is_valid(board, row, col, num):
# Check if the number is already present in the row
    if num in board[row]:
        return False
    
    # Check if the number is already present in the column
    if num in [board[i][col] for i in range(9)]:
        return False
    
    # Check if the number is already present in the 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):
    empty_cell = find_empty_cell(board)
    if not empty_cell:
        return True  # Puzzle solved
    
    row, col = empty_cell
    for num in range(1, 10):
        if is_valid(board, row, col, num):
            board[row][col] = num
            if solve_sudoku(board):
                return True
            board[row][col] = 0  # Backtrack
    
    return False  # No solution found

def find_empty_cell(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i, j)
    return None

# Example usage
board = [
    [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]
]

solve_sudoku(board)
for row in board:
    print(row)

Write Algorithm for Soduku

Top Altimetrik Python Developer interview questions & answers

Popular interview questions of Python Developer