#include
#include
using namespace std;
bool isafe(int grid[][9], int i, int j, int n, int number)
{
// check for row and colunm
for (int l = 0; l < n; l++) {
if (grid[l][j] == number || grid[i][l] == number) {
return false;
}
}
// check for inner grid
int rn = sqrt(n);
int sx = (i / rn) * rn;
int sy = (j / rn) * rn;
for (int k = sx; k < sx + rn; k++) {
for (int p = sy; p < sy + rn; p++) {
if (grid[k][p] == number) {
return false;
}
}
}
return true;
}
bool sudukosolver(int grid[][9], int i, int j, int n)
{
// base case if reaches end
if (i == n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << grid[i][j] << " ";
}
cout << endl;
}
cout << endl;
return true;
}
// base case if j reaches end of row
if (j == n) {
return sudukosolver(grid, i + 1, 0, n);
}
**
if i write the above condition without returning it
solution keeps on printing on screen infinitely so what difference does returning function and calling function makes ( this is suduko solver code)
if (j == n) {
return sudukosolver(grid, i + 1, 0, n);
}
vs
if (j == n) {
sudukosolver(grid, i + 1, 0, n);
}
**
// if value in grid is all ready there skip it
if (grid[i][j] != 0) {
return sudukosolver(grid, i, j + 1, n);
}
for (int number = 1; number <= n; ++number) {
if (isafe(grid, i, j, n, number)) {
grid[i][j] = number;
bool couldwesolve = sudukosolver(grid, i, j + 1, n);
if (couldwesolve == true) {
return true;
}
// if we cant solve we have to backtrack
}
}
// backtrack hear
grid[i][j] = 0;
return false;
}
int main(int argc, char const* argv[])
{
int grid[9][9] = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 }, { 5, 2, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 8, 7, 0, 0, 0, 0, 3, 1 }, { 0, 0, 3, 0, 1, 0, 0, 8, 0 },
{ 9, 0, 0, 8, 6, 3, 0, 0, 5 }, { 0, 5, 0, 0, 9, 0, 6, 0, 0 },
{ 1, 3, 0, 0, 0, 0, 2, 5, 0 }, { 0, 0, 0, 0, 0, 0, 0, 7, 4 },
{ 0, 0, 5, 2, 0, 6, 3, 0, 0 } };
sudukosolver(grid, 0, 0, 9);
return 0;
}