Solving Sudoku using Backtracking

Introduction

This post is the continuation of the backtracking series. Sudoku can be solved using multiple algorithms based on Neural Networks and Genetic Algorithms by doing exhaustive searches in the solution space. However, here we are focusing on solving Sudoku using backtracking algorithm.

For people who are unaware of the Sudoku puzzle, please check out Wikipedia for details. For a brief description read below:

  • A Sudoku puzzle is a 9 * 9 grid.
  • Few cells in the grid contain random numbers between 1 and 9 (both inclusive)
  • A fully solved Sudoku must contain numbers through 1-9 in each column, each row and in each 3*3 box

The task is to write an algorithm which can solve a Sudoku puzzle  given a incomplete grid. Here is a pictorial representation of a Sudoku puzzle. The left one is unsolved, the right one is solved.Each 3*3 box is distinctly represented here.

Solving Sudoku using Backtracking

Approach

Again! as many backtracking algorithms, this also works on trying solution, rejecting partial solutions and backtracking to try alternate solutions. So let us start with defining what is a safe move?

Defining the Safe Move

  • A safe move is adding a number to one of the cells
  • The number must be between 1 to 9
  • It must not be present in the row
  • It must not be present in the column
  • And the 3*3 box must not contain the same number

If we have to define that in a method, here it is.

The GRID is the complete puzzle, the emptyCell is the cell where we are planning to write the num (the calles makes sure that the num is between 1-9). This method returns false if the number is present in the same row, column or box as the empty cell.

It returns true otherwise.

Defining the Strategy

The strategy is pretty simple

  • Find the next empty cell in the grid
  • If there are no empty cells, the grid is solved, so just print it.
  • Else, test if any of the numbers 1 through 9 can be successfully added at the empty cell.
    • If yes, add the number and recursively solve the remaining grid.
  • When the grid is completely solved, return true.
  • There might be a possibility that we get stuck somewhere down the line and the cells are still empty
    • This is an indication that we made a wrong choice in the past steps
    • Hence, we remove the number from the current empty cell and try the next number in the sequence [1..9]
    • If this fails, we keep removing numbers from the previous cells, which is maintained in the recursion stack.
  • Eventually, if the Sudoku puzzle is a valid puzzle, we will get a solution.

Source Code

As an optimization, you can remember the current emptyCell, so finding the next one wont be a O(N^2) task.

How to invoke this method?

Here is the main method you would need

 

Analysis

The analysis and dry run of this code is similar to the previous posts in the backtracking series. The recursion tree here will branch into 9 branches and at each level the problem size is reduced by 1.

The problem can be designed for a grid size of N*N where N is a perfect square. For such a 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). For details check my previous posts in the Backtracking category. Clearly this is an exponential solution.

Talking about the space complexity, it is just the recursion stack which is used as an auxiliary space. And the recursion 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, the space complexity would be O(M).