Sudoku originally called Number Place
is a logic-based,combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 subgrids that compose the grid (also called "boxes", "blocks", or "regions") contain all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.
Here we have implemented how a sudoku can be solved
#include<bits/stdc++.h>
using namespace std;
// UNASSIGNED is used for empty cells in sudoku grid
#define UNASSIGNED 0
// N is used for the size of Sudoku grid.
// Size will be NxN
#define N 9
class Solution
{
public:
//Function to find a solved Sudoku.
bool isSafe(int grid[N][N], int row, int col, int num) {
for (int i = 0; i < 9; i++) {
if (grid[row][i] == num) {
return false;
}
}
for (int i = 0; i < 9; i++) {
if (grid[i][col] == num) {
return false;
}
}
int startRow = row - (row % 3);
int startCol = col - (col % 3);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (grid[startRow + i][startCol + j] == num) {
return false;
}
}
}
return true;
}
bool SolveSudoku(int grid[N][N])
{
// Your code here
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == 0) {
for (int n = 1; n <= 9; n++) {
if (isSafe(grid, i, j, n) == true) {
grid[i][j] = n;
if (SolveSudoku(grid)) {
return true;
}
else {
grid[i][j] = 0;
}
}
}
return false;
}
}
}
return true;
}
//Function to print grids of the Sudoku.
void printGrid (int grid[N][N])
{
// Your code here
if (SolveSudoku(grid)) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << grid[i][j] << " ";
}
}
}
}
};
int main() {
int t;
cin >> t;
while (t--)
{
int grid[N][N];
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
cin >> grid[i][j];
Solution ob;
if (ob.SolveSudoku(grid) == true)
ob.printGrid(grid);
else
cout << "No solution exists";
cout << endl;
}
return 0;
}