Sudoku is a popular puzzle game where you fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids (also known as regions or boxes) contains all of the digits from 1 to 9 without repetition.
Now, let’s implement a Sudoku Solver using a Backtracking algorithm in C++.
Sudoku Solver Algorithm
The Backtracking algorithm for solving Sudoku works like this:
1. Find an empty cell in the Sudoku grid.
2. Try all numbers from 1 to 9 (N) in that cell.
3. Check if the number is valid (i.e. number is not present in the same row, column, or 3x3 subgrid).
4. If the number is valid, recursively try to fill the next empty cell.
5. If all cells are filled, we have found a solution. If not, we backtrack and try the next number.
Code Implementation
//
// main.cpp
// Sudoku Solver
//
// Created on 24/04/24.
//
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool isSafe(vector<vector<int>>& board, int row, int col, int num, int N) {
// Check row and column
for (int i = 0; i < N; i++) {
if (board[row][i] == num || board[i][col] == num) {
return false;
}
}
// Check subgrid
int sqrtN = sqrt(N);
int startRow = row - (row % sqrtN);
int startCol = col - (col % sqrtN);
for (int i = 0; i < sqrtN; i++) {
for (int j = 0; j < sqrtN; j++) {
if (board[i + startRow][j + startCol] == num) {
return false;
}
}
}
return true;
}
bool solveSudoku(vector<vector<int>>& board, int N) {
int row = -1, col = -1;
// Find an empty cell
bool foundEmpty = false;
for (row = 0; row < N; row++) {
for (col = 0; col < N; col++) {
if (board[row][col] == 0) {
foundEmpty = true;
break;
}
}
if (foundEmpty) {
break;
}
}
// If there is no empty cell left, Sudoku is solved
if (!foundEmpty) {
return true;
}
// Try numbers from 1 to N
for (int num = 1; num <= N; num++) {
if (isSafe(board, row, col, num, N)) {
board[row][col] = num;
// Recur to fill next cell
if (solveSudoku(board, N)) {
return true;
}
// If not a valid solution, backtrack
board[row][col] = 0;
}
}
return false; // No solution
}
void printSudoku(vector<vector<int>>& board, int N) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << board[i][j] << " ";
}
cout << endl;
}
}
int main() {
int N = 9; // Size of Sudoku grid
// Define the Sudoku grid (N x N), '0' represents empty cells
vector<vector<int>> board = {
{5, 0, 0, 6, 0, 0, 0, 0, 0},
{8, 2, 7, 5, 0, 0, 0, 0, 0},
{6, 0, 0, 8, 3, 1, 0, 0, 5},
{0, 0, 2, 4, 0, 0, 0, 8, 7},
{0, 0, 0, 0, 0, 0, 4, 0, 2},
{0, 0, 4, 0, 0, 8, 0, 0, 6},
{0, 9, 0, 1, 0, 7, 0, 0, 0},
{2, 1, 0, 0, 0, 6, 7, 0, 0},
{0, 5, 3, 0, 0, 0, 0, 0, 9}
};
if (solveSudoku(board, N)) {
cout << "Solved Sudoku:" << endl << endl;
printSudoku(board, N);
} else {
cout << "No solution exists." << endl;
}
return 0;
}
Output
Solved Sudoku:
5 3 1 6 7 2 9 4 8
8 2 7 5 4 9 6 3 1
6 4 9 8 3 1 2 7 5
9 6 2 4 1 5 3 8 7
1 8 5 7 6 3 4 9 2
3 7 4 9 2 8 5 1 6
4 9 6 1 5 7 8 2 3
2 1 8 3 9 6 7 5 4
7 5 3 2 8 4 1 6 9
Working of the code
- The
isSafe() function checks if it is safe to place a numbernumat positionboard[row][col]by checking the row, column, and each subgrid. - The
solveSudoku() function recursively solves the Sudoku puzzle by trying numbers from 1 to N and backtracking if a solution is not valid. Intuition behind inner or sub grid calculations,startRow = row - (row % sqrtN), could be understood from:startRow = (row / sqrtN) * sqrtN
let’s consider the example of 9×9 grid (sqrtN is 3) for the sub-grid calculations:startRow = (row / sqrtN) * sqrtN,
will result in startRow having values as 0 for rows (0-2), 3 for rows (3-5) and, 6 for rows (6-8).
Also, we know that startRow is the additive factor used for rows for sub-grid correctness calculations. Similarly, startCol is the additive factor for the columns.
Note: This code works for all the values of N. However, for large values of N, it may take too long to finish, particularly for sparse grids. Also, you’ll need to tweak the code for values of N that are not perfect squares. This is because of the variable dimensions of sub-grids.
Time complexity: O(NN*N), N x N is the size of the grid.
Auxiliary Space: O(N2)
Explanation
Time complexity
O(N(N*N)), for every cell (number of cells is N*N), there are N possible options, hence this time complexity.
Space complexity
O(N2), to store the N x N Sudoku grid