Solving Sudoku in C++


Sudoku has been a popular tea time puzzle for many years. It is considered to be a brain practice to solve this puzzle manually. This tutorial demonstrates how to solve a sudoku using recursive backtracking in C++.


Introduction


Sudoku is a game in which the player has to fill in numbers in blank spaces based on the given numbers initially. There is only one unique solution, so each blank space has a unique number that is to be filled. There are given set of rules which decides if a number filled in a blank space is absolutely wrong.


Basic Rule of Sudoku


The basic rule for deciding if a number is definitely wrong at a given position is follows :

  • The given number should not be present in the row of the given position
  • The given number should not be present in the column of the given position
  • The given number should not be present in the box of the given position


Naive Approach


The naive, brute-force approach for this problem is obvious. Try putting all possible combinations of numbers in the black spaces until a valid combination is obtained. Of course, this solution will work but will take exponential time to complete.


Recursive Backtracking


We can optimize the above naive solution by exploiting some rules of Sudoku. If we observe, while putting a number at a blank position, we can decide there and then if that number is not valid to be put at that position. This will help to reduce un-necessary calculations and thus will improve our time complexity.

bool SolveSudoku2(int grid[N][N], int i, int j)

{

if (j == N) {

return true;

}

bool isValid ;

if (grid[i][j]>0)

{

if (i < N-1)

isValid = SolveSudoku2(grid,i+1,j) ;

else

isValid = SolveSudoku2(grid,0,j+1) ;

return isValid ;

}

for (int cnt = 1; cnt < 10; cnt++) {

if(isSafe(grid,i,j,cnt))

{

grid[i][j] = cnt;

if (i < N-1)

isValid = SolveSudoku2(grid,i+1,j) ;

else

isValid = SolveSudoku2(grid,0,j+1) ;

if (isValid)

return true ;

}

}

grid[i][j] = 0;

return false ;

}


The isSafe function


bool UsedInRow(int grid[N][N], int row, int num)

{

for (int col = 0; col < N; col++)

if (grid[row][col] == num)

return true;

return false;

}

bool UsedInCol(int grid[N][N], int col, int num)

{

for (int row = 0; row < N; row++)

if (grid[row][col] == num)

return true;

return false;

}

bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num)

{

for (int row = 0; row < 3; row++)

for (int col = 0; col < 3; col++)

if (grid[row+boxStartRow][col+boxStartCol] == num)

return true;

return false;

}

bool isSafe(int grid[N][N], int row, int col, int num)

{

return !UsedInRow(grid, row, num) &&

!UsedInCol(grid, col, num) &&

!UsedInBox(grid, row - row%3 , col - col%3, num);

}

Rohan Raja

Recently graduated, majoring in Mathematics and Computing from IIT Kharagpur, Rohan is a technology enthusiast and passionate programmer. Likes to apply Mathematics and Artificial Intelligence to devise creative solutions to common problems.