Coders Packet

Solving Sudoku using Backtracking and Recursion in C++

By G Ganga Jathin

This project is focused on Developing the code to solve the sudoku puzzles by using the backtracking and recursion algorithms in C++ language to find the correct solution

Objective:- Solve the given Sudoku puzzle and display its solution.

 

Input:- Our input will be a 2-dimensional array of 9x9 matrix of sudoku where the missing numbers are replaced by 0 and given as input for the code

int main()
{
    cout << "Hello Welcome to Sudoku Solver \nPlease enter the Sudoku you want us to solve, input the blank boxes as 0" << endl;
  int sudoku[N][N];
  for(int i = 0;i < N;i++)for(int j = 0;j < N;j++)cin >> sudoku[i][j];
  if (Solver(sudoku) == true)printGrid(sudoku);
  else cout << "No solution exists" << endl;
  return 0;
}

 

Main Idea:- 

The main idea of the code is that we first search missing numbers row by row and then try to fill a suitable number which is not repeated in a row or a column and then try to find all permutation where there is a potential solution and is not breaking any rules of sudoku and then return that particular solution.

Step 1 - Finding missing numbers

We can find missing numbers easily as our input contains 0 for missing numbers

bool missinglocation(int sudoku[N][N],int& row, int& col)
{
  for (row = 0; row < N; row++)
    for (col = 0; col < N; col++)
      if (sudoku[row][col] == missing)
        return true;
  return false;
}

 

Here we iterate through the 9 x 9 matrix and we update the values of row and col with the missing spot and return once we find a missing spot to fill.

Here the row and col are taken as reference variables so the update made here is updated permanently in the program.

Step 2 - Finding a suitable number to fill the missing spot

Here we iterate through numbers from 1 to 9 and check whether any given number is suitable for the missing spot and then we recursively iterate this procedure to get all types of permutations that fills the missing spot without any repetition.

bool Solver(int sudoku[N][N])
{
  int row, col;
  if (!missinglocation(sudoku, row, col))return true;
  for (int num = 1; num <= 9; num++)
  {
    if (check(sudoku, row, col, num))
    {
      sudoku[row][col] = num;
      if (Solver(sudoku))
        return true;
      sudoku[row][col] = missing;
    }
  }
  return false;
}

 

Step 3 - Checking whether the number is suitable to fill the spot

Here We first check if the current number is repeated first by row then by column then by the box. If all the conditions are satisfied then the number is ready to fill the missing spot

bool Checkrow(int sudoku[N][N], int row, int num)
{
  for (int col = 0; col < N; col++)
    if (sudoku[row][col] == num)
      return true;
  return false;
}
bool Checkcol(int sudoku[N][N], int col, int num)
{
  for (int row = 0; row < N; row++)
    if (sudoku[row][col] == num)
      return true;
  return false;
}
bool Checkbox(int sudoku[N][N], int boxStartRow,
      int boxStartCol, int num)
{
  for (int row = 0; row < 3; row++)
    for (int col = 0; col < 3; col++)
      if (sudoku[row + boxStartRow]
          [col + boxStartCol] ==
                  num)
        return true;
  return false;
}
bool check(int sudoku[N][N], int row,
      int col, int num)
{
  return !Checkrow(sudoku, row, num)
    && !Checkcol(sudoku, col, num)
    && !Checkbox(sudoku, row - row % 3,
            col - col % 3, num)
    && sudoku[row][col] == missing;
}

Here Checkrow and Checkcol check for any repetition of the numbers in row-wise and column-wise respectively and Checkbox checks within the 3 x 3 grid. The boxStartRow and boxStartCol are the variables that give us the index of the starting element in the box of the sudoku and we iterate the subset 3 x 3 matrix to check if there is any repetition for the given number

Step 4 - Print the updated solution for the given sudoku

finally we print the final solution of the sudoku puzzle

Output: -

Here is the test case I used for my code. This test case is rated as expert level difficulty.

And here is the output of my code,

 

How to use it?
1) Download and extract the zip file and open it in the C++ IDE of your choice

2) Compile and Run the source code

3) Enter the incomplete Sudoku in the Command Prompt.

The Solution for the given sudoku is displayed

Download project

Reviews Report

Submitted by G Ganga Jathin (GangaJathin)

Download packets of source code on Coders Packet