6

Sudoku Solver Using C++ [Easy Guide]

 2 years ago
source link: https://www.journaldev.com/60419/sudoku-solver-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

In this article, we will learn to implement a Sudoku Solver using C++. This is a perfect example of a recursion and backtracking algorithm. Have you ever tried to solve a 9×9 Sudoku puzzle? If yes, then you must be tempted to look at the algorithm behind finding the solution. Haven’t heard of Sudoku? Don’t worry, we have got everybody covered here. We’ll start only after introducing you all to the basics of Sudoku. What are you waiting for? Let’s get started.

What Is Sudoku?

A Sudoku puzzle is a grid of size N x N, where N is a perfect square. Some of the numbers in the grid are already filled, your task is to fill the remaining cells by following a set of rules which are listed below.

  • There must not be any repeating character in any row
  • Same goes for every column
  • In addition to that, every grid is further divided into smaller grids for side square_root(N)
    • Each of the smaller grids must not have repeating number.
  • For every value of N, you can only insert number in the range [1, N]
    • Suppose that the value of N is 9, then you must insert the numbers in the range [1, 9]

Alright, enough of rules, and we are ready to rock. Let’s look at the interesting algorithm behind this puzzle.

9.6....2.4..36819.35.4.....2.9.8.5.1..3.4....671.9.328.3...1.76..2856..9.5....8.3Sudoku Puzzle

Sudoku Solver Concept

  • We will start by finding an empty cell
  • Once we are at an empty cell, we have N options for each cell. In this case, we have 9 options for each cell
  • We will try to place each valid choice into the empty cell
  • Now we will make a recursive call on the remaining grid
    • If this recursive call returns true, then it implies that the solution for current value of the empty cell exists
    • Otherwise, we will change the value and try again
  • To check for duplicate in the same column or the same row, we can simply iterate linearly. But the question is how to check for duplicates in smaller grids?
  • How do we iterate over the subgrids?
  • We can iterate over the subgrid if we have its starting point coordinates.
  • And if you do some maths, you will find that the starting coordinates for the subgrid are
    • Sx = (i/square_root(N)) * square_root(N)
    • Sy = (j/square_root(N)) * square_root(N)

C++ Code To Demonstrate The Algorithm

#include <iostream>
#include <cmath>
using namespace std;
bool canPlace(int mat[][9], int i, int j, int n, int number)
{
// check for the row and the column
for(int x = 0; x < n; x++)
{
if(mat[x][j] == number || mat[i][x] == number)
{
return false;
}
}
// for subgrid
int rn = sqrt(n);
int sx = (i / rn) * rn;
int sy = (j / rn) * rn;
for(int x = sx; x < sx + rn; x++)
{
for(int y = sy; y < sy + rn; y++)
{
if(mat[x][y] == number)
{
return false;
}
}
}
// otherwise, return true
return true;
}
bool solveSudoku(int mat[][9], int i, int j, int n)
{
// base case
// we've solved all the rows and now we're
// standing at the last cell of the grid
if(i == n)
{
// print the matrix
cout << "Solution to this Sudoku Puzzle is:" << endl;
for(int a = 0; a < n; a++)
{
for(int b = 0; b < n; b++)
{
cout << mat[a][b] << " ";
}
cout << endl;
}
// and return success
return true;
}
// Case: Row end --> shift to the next row
if(j == n)
return solveSudoku(mat, i + 1, 0, n);
// skip the prefilled cells
if(mat[i][j] != 0)
solveSudoku(mat, i, j + 1, n);
// recursive case
// Case: Empty Cell
// We will try all the possible options
// until we find the solution
for(int number = 1; number <= n; number++)
{
// the canPlace function would check
// for the feasability of placing
// a specific number at any position
if(canPlace(mat, i, j, n, number))
{
mat[i][j] = number;
bool couldWeSolve = solveSudoku(mat, i, j + 1, n);
if(couldWeSolve == true)
{
return true;
}
}
}
// backtrack here
mat[i][j] = 0;
return false;
}
int main()
{
int mat[9][9] =
{
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};
solveSudoku(mat, 0, 0, 9);
return 0;
}
Can Place FunctionCan Place Function
Algorithm To Solve SudokuAlgorithm To Solve Sudoku
Driver FunctionDriver Function

Output

Sudoku OutputSudoku Output

Conclusion

In this article, we learned to implement Sudoku Solver Using C++. Though the algorithm was a little complex, we ended up coding it and running it over a sample grid. That’s all for today, thanks for reading.

Further Readings

To learn more about recursion or backtracking, you can refer to the following websites

https://www.journaldev.com/56918/0-1-knapsack-using-cpp

https://www.journaldev.com/58739/tiling-problem-dynamic-programming-cpp


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK