Sudoku Solver

This page explains Java solution to problem Sudoku Solver using Backtracking.

Problem Statement

Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character ..

Example 1:

Input: A Sudoku Puzzle

Sudoku Puzzle Input

Output: It's Solution number marked in Red

Sudoku Puzzle Output

Solution

If you have any suggestions in below code, please create a pull request by clicking here.

package com.vc.hard;

class SudokuSolver {
    public void solveSudoku(char[][] board) {
        solve(board);
    }

    private boolean solve(char[][] board) {
        for(int row = 0; row < 9; row++) {
            for(int col = 0; col < 9; col++) {
                if(board[row][col] == '.') {
                    for(char num = '1'; num <= '9'; num++) {
                        if(isValid(board, row, col, num)) {
                            board[row][col] = num;
                            if(solve(board)) return true;
                            else board[row][col] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int row, int col, char num) {
        int blkRow = (row / 3) * 3, blkCol = (col / 3) * 3;
        for(int i = 0; i < 9; i++) {
            if(board[i][col] == num) return false;
            if(board[row][i] == num) return false;
            if(board[blkRow + i / 3][blkCol + i % 3] == num) return false;
        }
        return true;
    }
}

Time Complexity

O(9!)9
For single Row there are 9 possibilities for first cell
8 possibilities for second cell
7 possibilities for third cell and so ....
So total there are 9! operations to fill in one row


There are 9 Rows in Sudoku, so total number of operations will be 9!9

Space Complexity

O(9 * 9) For storing 9 * 9 Grid