Sudoku Solver: Interactive Backtracking Algorithm Visualization

Description

The Sudoku Solver algorithm uses backtracking to solve a 9x9 Sudoku puzzle. The goal is to fill the grid with numbers from 1 to 9, ensuring that each number appears exactly once in each row, column, and 3x3 sub-grid.

How It Works

Start with an incomplete Sudoku grid
Find an empty cell (represented by 0)
Try placing numbers 1-9 in the empty cell
For each number, check if it's valid in the current position:
- Check if the number exists in the current row
- Check if the number exists in the current column
- Check if the number exists in the current 3x3 box
If the number is valid, place it and recursively try to solve the rest of the puzzle
If the recursive call fails, backtrack by removing the number and try the next one
If no number works, return false to trigger backtracking
If all cells are filled, the puzzle is solved

Visualization

Speed:

Enter numbers and click Start to solve

Implementation


def is_valid(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 box
    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_sudoku(board):
    empty = find_empty(board)
    if not empty:
        return True
    
    row, col = empty
    
    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
    
    return False

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


class SudokuSolver {
private:
    bool isValid(vector<vector<int>>& board, int row, int col, int num) {
        // Check row
        for (int x = 0; x < 9; x++) {
            if (board[row][x] == num) return false;
        }
        
        // Check column
        for (int x = 0; x < 9; x++) {
            if (board[x][col] == num) return false;
        }
        
        // Check 3x3 box
        int startRow = row - row % 3;
        int 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;
    }
    
    pair<int, int> findEmpty(vector<vector<int>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == 0) {
                    return {i, j};
                }
            }
        }
        return {-1, -1};
    }
    
public:
    bool solveSudoku(vector<vector<int>>& board) {
        auto empty = findEmpty(board);
        if (empty.first == -1) return true;
        
        int row = empty.first;
        int col = empty.second;
        
        for (int num = 1; num <= 9; num++) {
            if (isValid(board, row, col, num)) {
                board[row][col] = num;
                
                if (solveSudoku(board)) {
                    return true;
                }
                
                board[row][col] = 0;
            }
        }
        
        return false;
    }
};


public class SudokuSolver {
    private bool IsValid(int[,] board, int row, int col, int num) {
        // Check row
        for (int x = 0; x < 9; x++) {
            if (board[row, x] == num) return false;
        }
        
        // Check column
        for (int x = 0; x < 9; x++) {
            if (board[x, col] == num) return false;
        }
        
        // Check 3x3 box
        int startRow = row - row % 3;
        int 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;
    }
    
    private (int row, int col) FindEmpty(int[,] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i, j] == 0) {
                    return (i, j);
                }
            }
        }
        return (-1, -1);
    }
    
    public bool SolveSudoku(int[,] board) {
        var empty = FindEmpty(board);
        if (empty.row == -1) return true;
        
        int row = empty.row;
        int col = empty.col;
        
        for (int num = 1; num <= 9; num++) {
            if (IsValid(board, row, col, num)) {
                board[row, col] = num;
                
                if (SolveSudoku(board)) {
                    return true;
                }
                
                board[row, col] = 0;
            }
        }
        
        return false;
    }
}

Complexity Analysis

Time Complexity

The time complexity of the Sudoku solver is O(9^(n*n)), where n is the size of the board (typically 9). This is because:

For each empty cell, we try numbers 1-9
There can be up to n*n empty cells
For each attempt, we need to validate the move (O(1))
The algorithm backtracks when invalid solutions are found

Space Complexity

The space complexity is O(n*n), where n is the board size. This accounts for:

The recursion stack depth (up to n*n calls)
The board representation itself
No additional significant space requirements

Advantages and Disadvantages

Advantages

Guaranteed to find a solution if one exists
Simple to implement and understand
Memory efficient
Can solve any valid Sudoku puzzle
No pre-processing required

Disadvantages

Exponential time complexity
Can be slow for very difficult puzzles
Not optimal for puzzles with multiple solutions
Performance depends heavily on initial board state
May explore many dead ends before finding solution

Quick Info

Sudoku Solver