मुख्य कंटेंट तक स्किप करें

Sudoku Solver

Ayesha
EditReport

The Sudoku Solver is a classic constraint-satisfaction problem solved using backtracking. The goal is to fill a partially completed 9×9 grid so that every row, column, and 3×3 sub-box contains the digits 1–9 exactly once.

Video Explanation​

Problem Statement​

Given a 9×9 grid partially filled with digits (1–9), fill in the empty cells (represented as 0 or .) such that:

  • Every row contains digits 1–9 with no repetition
  • Every column contains digits 1–9 with no repetition
  • Every 3×3 sub-box contains digits 1–9 with no repetition

Approach​

The backtracking approach works as follows:

  1. Find an empty cell — scan the grid for the next 0
  2. Try digits 1–9 — for each digit, check if placing it is valid
  3. Validity check — ensure the digit doesn't already exist in the same row, column, or 3×3 box
  4. Place and recurse — if valid, place the digit and recurse to the next empty cell
  5. Backtrack — if no digit works, reset the cell to 0 and return false to trigger backtracking

Constraint Check​

A digit d is valid at position (row, col) if:

  • d does not appear in grid[row][*] (same row)
  • d does not appear in grid[*][col] (same column)
  • d does not appear in the 3×3 box starting at (row/3 * 3, col/3 * 3)

Time and Space Complexity​

MetricComplexity
Time (worst case)O(9^m) where m = number of empty cells
SpaceO(m) recursion stack depth

In practice, constraint pruning makes it much faster than the theoretical worst case.

C++ Implementation 💻​

Sudoku Solver - C++ Backtracking
#include <iostream>
#include <vector>
using namespace std;

bool isValid(vector<vector<int>>& board, int row, int col, int num) {
    // Check row — num must not already exist in this row
    for (int j = 0; j < 9; j++) {
        if (board[row][j] == num) return false;
    }

    // Check column — num must not already exist in this column
    for (int i = 0; i < 9; i++) {
        if (board[i][col] == num) return false;
    }

    // Check 3x3 sub-box — find top-left corner of the box
    int boxRow = (row / 3) * 3;
    int boxCol = (col / 3) * 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[boxRow + i][boxCol + j] == num) return false;
        }
    }

    return true; // num is safe to place at (row, col)
}

bool solve(vector<vector<int>>& board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == 0) { // Found an empty cell
                for (int num = 1; num <= 9; num++) {
                    if (isValid(board, i, j, num)) {
                        board[i][j] = num; // Place the digit

                        if (solve(board)) return true; // Recurse

                        board[i][j] = 0; // Backtrack — undo placement
                    }
                }
                return false; // No valid digit found — trigger backtrack
            }
        }
    }
    return true; // No empty cells remain — puzzle solved
}

void printBoard(vector<vector<int>>& board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    vector<vector<int>> 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}
    };

    if (solve(board)) {
        printBoard(board);
    } else {
        cout << "No solution exists" << endl;
    }
    return 0;
}

Python Implementation 🐍​

Sudoku Solver - Python Backtracking
def is_valid(board, row, col, num):
    # Check row
    if num in board[row]:
        return False

    # Check column
    if any(board[i][col] == num for i in range(9)):
        return False

    # Check 3x3 sub-box
    box_row, box_col = (row // 3) * 3, (col // 3) * 3
    for i in range(3):
        for j in range(3):
            if board[box_row + i][box_col + j] == num:
                return False

    return True

def solve(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:  # Empty cell found
                for num in range(1, 10):
                    if is_valid(board, i, j, num):
                        board[i][j] = num  # Place digit

                        if solve(board):
                            return True  # Recurse

                        board[i][j] = 0  # Backtrack
                return False  # No valid digit — backtrack
    return True  # All cells filled

def print_board(board):
    for row in board:
        print(" ".join(map(str, row)))

# Example board (0 = empty)
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]
]

if solve(board):
    print_board(board)
else:
    print("No solution exists")

JavaScript Implementation 🌐​

Sudoku Solver - JavaScript Backtracking
function isValid(board, row, col, num) {
    // Check row
    if (board[row].includes(num)) return false;

    // Check column
    for (let i = 0; i < 9; i++) {
        if (board[i][col] === num) return false;
    }

    // Check 3x3 sub-box
    const boxRow = Math.floor(row / 3) * 3;
    const boxCol = Math.floor(col / 3) * 3;
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            if (board[boxRow + i][boxCol + j] === num) return false;
        }
    }

    return true;
}

function solve(board) {
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] === 0) { // Empty cell
                for (let num = 1; num <= 9; num++) {
                    if (isValid(board, i, j, num)) {
                        board[i][j] = num; // Place digit

                        if (solve(board)) return true; // Recurse

                        board[i][j] = 0; // Backtrack
                    }
                }
                return false; // No valid digit found
            }
        }
    }
    return true; // Solved
}

Backtracking Decision Tree​

Optimizations​

  • Minimum Remaining Values (MRV): Instead of scanning left-to-right, pick the empty cell with the fewest valid candidates first — reduces branching significantly
  • Constraint Propagation: After placing a digit, immediately eliminate it from candidates in the same row, column, and box
  • Naked Singles: If a cell has only one valid candidate, place it immediately without branching

References​

🧠 Quick Quiz

Test Your Understanding

Answer these 3 questions to check what you have learned.

Q1

What is the main topic of this documentation page?

Q2

What should be identified before implementing sudoku solver?

Q3

How is understanding of sudoku solver best checked?

Track Your Progress

Done with this topic? Mark it as complete to track your progress.

Was this page helpful?

💬

Discuss this page

Have a question or spot something confusing in "Sudoku Solver"? Ask below. Backed by GitHub Discussions—maintainers receive system notifications directly.