Sudoku Solver

Difficulty: Hard

Asked in: Amazon, Google, Microsoft

What is Sudoku?

Sudoku is a number-placement puzzle where the objective is to fill a square grid of size ’n’ with numbers between 1 to ’n’. The numbers must be placed so that each column, each row, and each of the sub-grids (if any) contains all of the numbers from 1 to ‘n’.

The most common Sudoku puzzles use a 9x9 grid. The grids are partially filled (with hints) to ensure a solution can be reached.

Understanding the Problem

Problem Description: You are given a Sudoku puzzle and you need to fill the empty cells without violating any rules.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 3x3 sub-boxes of the grid.

Problem Note:

The given board contains only digits 1–9 and the character '.'.

• You may assume that the given Sudoku puzzle will have a unique solution.
• The given board size is always 9x9.
• Empty cells are indicated by the character ‘ . ‘

Example Input: A given sudoku puzzle

Output: Solution numbers are marked in red.

You may first try to solve the problem here.

What is Backtracking?

Backtracking is an algorithm for finding all (or some) of the solutions to a problem that incrementally builds candidates to the solution(s). As soon as it determines that a candidate cannot possibly lead to a valid solution, it abandons the candidate. Backtracking is all about choices and consequences.

You may further read about backtracking from here.

Backtracking Solution

We will now create a Sudoku solver using backtracking by encoding our problem, goal, and constraints in a step-by-step algorithm.

A brute force algorithm visits the empty cells in sequential order, filling in digits sequentially, or backtracking when no digit can be filled without violating any rule.

Initially, the program would solve the puzzle by placing the digit “1” in the first empty cell and checking if it is allowed to be there. If there are no violations (checking row, column and box constraints) then the algorithm advances to the next cell and places a “1” in that cell. When checking for violations, if it is discovered that the “1” is not allowed, the value is changed to “2”. If a cell is discovered where none of the 9 digits is allowed, then the algorithm leaves that cell blank and moves back to the previous cell. The value in that cell is then incremented by one. This is repeated until an allowed value in the last empty cell is discovered.

If we try to draw the recursion tree then each step will branch into 9 branches and at each level, the problem size is reduced by 1.

Visualization of the above example using backtracking

Solution steps

1. Make a list of all the empty spots.
2. Select a spot and place a number, between 1 and 9, in it and validate the subgrids. Subgrids are the horizontal row, vertical column, and the 3x3 grid associated with that spot.
3. If any of the constraints fail, abandon that solution by backtracking to the previous state and repeat step 2 with the next number. Otherwise, check if the goal is reached.
4. If a solution is found, stop searching. Otherwise, repeat steps 2 to 4

However, there are various different techniques to solve this problem that you may read from here.

Pseudo Code

// Driver function
void solveSudoku(char[][] board) {
    solve(board)
}

// Utility function
bool solve(char[][] board) {
    for (int r = 0 to r < 9) {
        for (int c = 0 to c < 9) {
            if (board[r][c] == '.') {
                for (char d = '1'; d <= '9'; d++) {
                    if (isValid(board, r, c, d)) {
                        board[r][c] = d
                        if (solve(board)) 
                            return true
                        board[r][c] = '.'
                    }
                }
                return false
            }
        } 
    }
    return true
}

bool isValid(char[][] board, int r, int c, char d) {
    for (int row = 0 to row < 9)
        if (board[row][c] == d) 
            return false
    for (int col = 0 to col < 9)
        if (board[r][col] == d)
            return false;
    for (int row = (r / 3) * 3 to row < (r / 3 + 1) * 3)
        for (int col = (c / 3) * 3 to col < (c / 3 + 1) * 3)
            if (board[row][col] == d) 
                return false
    return true
}

Complexity Analysis

Time Complexity: O(n ^ m) where n is the number of possibilities for each square (i.e., 9 in classic Sudoku) and m is the number of spaces that are blank.

The problem can be designed for a grid size of N*N where N is a perfect square. For such an N, let M = N*N, the recurrence equation can be written as

T(M) = 9*T(M-1) + O(1)

where T(N) is the running time of the solution for a problem size of N. Solving this recurrence will yield, O(9^M).

Explanation: This can be seen by working backwards from only a single empty spot. If there is only one empty spot, then you have n possibilities and you must work through all of them in the worst case. If there are two empty spots, then you must work through n possibilities for the first spot and n possibilities for the second spot for each of the possibilities for the first spot. If there are three spots, then you must work through n possibilities for the first spot. Each of those possibilities will yield a puzzle with two empty spots that now have n² possibilities.

You may also say that this algorithm performs a depth-first search through the possible solutions. Each level of the graph represents the choices for a single square. The depth of the graph is the number of squares that need to be filled. With a branching factor of n and a depth of m, finding a solution in the graph has a worst-case performance of O(n ^ m).

Space complexity: it’s the recursion stack that is used as an auxiliary space which is N*N step deep. Remember we need to fill in 81 cells in a 9*9 sudoku and at each level, only one cell is filled. So, space complexity would be O(M).

Critical Ideas to Think

• Why does each step will branch 9 branches?
• Can you roughly draw the recursion tree for sample input?
• Analyze the recurrence relation described in time complexity.
• Do you think that there would be different approaches to solve this problem besides backtracking?
• Why we are resetting boarch[r][c] with ‘ . ’ in the solve function described in pseudocode?
• What is the time complexity of isValid function?
• What changes will you make in the above pseudo-code to solve sudoku of NxN besides of 9x9?
• What could be the maximum value of N for which the pseudo-code might exceed the running time of 1 sec for a single processor system?

Suggested Problems to Solve

• N Queens Problem
• Word Break Problem
• Remove Invalid Parenthesis
• Match a pattern and string using regular expression
• Find Path from corner cell to middle cell in a maze
• M Coloring Problem
• Rat in a Maze
• Print all permutations of a given string

If you have any more approaches or you find an error/bug in the above solutions, please comment down below.

Happy Coding! Enjoy Algorithms!