SUDOKU solver in c++

Question 1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define UNASSIGNED 0
#define N 9

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

/* assign values to all unassigned locations for Sudoku solution  
 */
bool SolveSudoku(int grid[N][N])
{
    int row, col;
    if (!FindUnassignedLocation(grid, row, col))
       return true;
    for (int num = 1; num <= 9; num++)
    {
    if (isSafe(grid, row, col, num))
    {
        grid[row][col] = num;
        if (SolveSudoku(grid))
            return true;
        grid[row][col] = UNASSIGNED;
    }
    }
    return false;
}

/* Searches the grid to find an entry that is still unassigned. */
bool FindUnassignedLocation(int grid[N][N], int &row, int &col)
{
    for (row = 0; row < N; row++)
        for (col = 0; col < N; col++)
            if (grid[row][col] == UNASSIGNED)
                return true;
    return false;
}

/* Returns whether any assigned entry n the specified row matches 
   the given number. */
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;
}

/* Returns whether any assigned entry in the specified column matches 
   the given number. */
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;
}

/* Returns whether any assigned entry within the specified 3x3 box matches 
   the given number. */
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;
}

/* Returns whether it will be legal to assign num to the given row,col location. 
 */
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);
}

void printGrid(int grid[N][N])
{
    for (int row = 0; row < N; row++)
    {
        for (int col = 0; col < N; col++)
            cout<<grid[row][col]<<"  ";
        cout<<endl;
    }
}

int main()
{
    int grid[N][N] = {{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}};
    if (SolveSudoku(grid) == true)
        printGrid(grid);
    else
        cout<<"No solution exists"<<endl;
    return 0;
}

Question 2

Here's my code: I think it's the best.

/*
 *  File: Sudoku-Solver.cc
 *
 *  Created On: 12, April 2016
 *      Author: Shlomo Gottlieb
 *
 * Description: This program holds A sudoku board (size: 9*9),
 *              it allows the user to input values that he choices
 *              and finds the first rational solution.
 *              The program also prints the sudoku whether A solution
 *              was found or not.
 *
 */

//========= Includes =========//
#include <iostream>

//========= Using ==========//
using namespace std;

//========= Constants =========//
const int N = 3;            // The size of 1 square in the sudoku.
const int EMPTY = 0;        // A sign for an empty cell.
const int STOP_INPUT = -1;  // A sign for stop get input.

//====== Function Declaration ======//
void input_sud(int sud[][N*N]);
bool fill_sud(int sud[][N*N], int row, int col);
void print_sud(const int sud[][N*N]);
bool is_legal(const int sud[][N*N], int row, int col, int val);
bool is_row_ok(const int row[], int col, int val);
bool is_col_ok(const int sud[][N*N], int row, int col, int val);
bool is_sqr_ok(const int sud[][N*N], int row, int col, int val);

//========== Main ===========//
int main()
{
    int sud[N*N][N*N] = { { EMPTY } };  // The sudoku board.

    input_sud(sud);
    fill_sud(sud, 0, 0);
    print_sud(sud);

    return 0;
}

//======== Input Sudoku ========//
// Gets the input for the sudoku,
// 0 means an empty cell.
void input_sud(int sud[][N*N])
{
    for(int i = 0; i < N*N; i++)
        for(int j = 0; j < N*N; j++)
            cin >> sud[i][j];
}

//======== Fill Sudoku =========//
// Tries to fill-in the given sudoku board
// according to the sudoku rules.
// Returns whether it was possible to solve it or not.
bool fill_sud(int sud[][N*N], int row, int col)
{
    // Points to the row number of the next cell.
    int next_row = (col == N*N - 1) ? row + 1 : row;

    // Points to the column number of the next cell.
    int next_col = (col + 1) % (N*N);

    // If we get here, it means we succeed to solve the sudoku.
    if(row == N*N)  
        return true;

    // Checks if we are allowed to change the value of the current cell.
    // If we're not, then we're moving to the next one.
    if(sud[row][col] != EMPTY)
        return fill_sud(sud, next_row, next_col);

    // We're about to try and find the legal and appropriate value
    // to put in the current cell.
    for(int value = 1; value <= N*N; value++)
    {
        sud[row][col] = value;

        // Checks if 'value' can stay in the current cell,
        // and returns true if it does.
        if(is_legal(sud, row, col, value) && fill_sud(sud, next_row, next_col))
            return true;

        // Trial failed!
        sud[row][col] = EMPTY;
    }

    // None of the values solved the sudoku.
    return false;
}

//======== Print Sudoku ========//
// Prints the sudoku Graphically.
void print_sud(const int sud[][N*N])
{
    for(int i = 0; i < N*N; i++)
    {
        for(int j = 0; j < N*N; j++)
            cout << sud[i][j] << ' ';
        cout << endl;
    }
}

//========== Is Legal ==========//
// Checks and returns whether it's legal
// to put 'val' in A specific cell.
bool is_legal(const int sud[][N*N], int row, int col, int val)
{
    return (is_row_ok(sud[row], col, val) &&
            is_col_ok(sud, row, col, val) &&
            is_sqr_ok(sud, row, col, val));
}

//========= Is Row OK =========//
// Checks and returns whether it's legal
// to put 'val' in A specific row.
bool is_row_ok(const int row[], int col, int val)
{
    for(int i = 0; i < N*N; i++)
        if(i != col && row[i] == val)
            return false;       // Found the same value again!

    return true;
}

//========= Is Column OK =========//
// Checks and returns whether it's legal
// to put 'val' in A specific column.
bool is_col_ok(const int sud[][N*N], int row, int col, int val)
{
    for(int i = 0; i < N*N; i++)
        if(i != row && sud[i][col] == val)
            return false;       // Found the same value again!

    return true;
}

//========= Is Square OK =========//
// Checks and returns whether it's legal
// to put 'val' in A specific square.
bool is_sqr_ok(const int sud[][N*N], int row, int col, int val)
{
    int row_corner = (row / N) * N;
    // Holds the row number of the current square corner cell.

    int col_corner = (col / N) * N;
    // Holds the column number of the current square corner cell.

    for(int i = row_corner; i < (row_corner + N); i++)
        for(int j = col_corner; j < (col_corner + N); j++)
            if((i != row || j != col) && sud[i][j] == val)
                return false;       // Found the same value again!

    return true;
}

Question 3

//here's a pseudo sudoku solver:

#include <iostream> 
#include <cmath>
#include "time.h"
//for(int i=0; i< ++i){}
using namespace std;

int main(){
 int a[9][9]={{0,7,0,0,2,0,1,0,0},
             {6,0,3,0,0,0,0,0,0},
             {2,0,0,3,0,0,5,0,0},
             {0,0,0,0,3,0,0,6,0},
             {0,6,4,7,0,0,0,8,0},
             {0,5,0,0,9,0,0,4,0},
      /*54*/ {0,4,0,0,7,0,9,0,0},
             {0,2,0,0,0,8,0,5,0},
             {0,0,0,0,0,0,0,0,0}};/*this is the grid. I need to use two so that I can use one as a constant reference*/
             
  int a2[9][9]={{0,7,0,0,2,0,1,0,0},
             {6,0,3,0,0,0,0,0,0},
             {2,0,0,3,0,0,5,0,0},
             {0,0,0,0,3,0,0,6,0},
             {0,6,4,7,0,0,0,8,0},
             {0,5,0,0,9,0,0,4,0},
             {0,4,0,0,7,0,9,0,0},
             {0,2,0,0,0,8,0,5,0},
             {0,0,0,0,0,0,0,0,0}}; 
                            
int x=0,y=0,z=0;
int oo=0,o=0,ooo=0,oooo=0; 
 for(int i=0; i<9; ++i)/*this is the double for loop.  to keep track of  the cells*/
 {
 for(int j=0; j<9; ++j)
 { 
 if(!a2[i][j])
 {a://label that if something doesn't work, to restart here.
 ++a[i][j];//increment the number in the cell by 1.
  if(a[i][j]>9)/*if no valid number is found/the number is out of range, execute the if statement.  **This is the backtracking algorithm.***/
{      
             a[i][j]=0;//erase the invalid number.
             --j;if(j<0){--i;j=8;} /*if j equals < 0, j is reset to 8, as the first 9 numbers are easy to find, and if j needs to be reset, there will always be a number in the j equals 8 cell.  The "i" will never be less than zero, if it is a valid puzzle, so the j=8 will only happen after i is > 0.*/ 
    while(a2[i][j]){--j;if(j<0){--i;j=8;}}/*if there was a number present from the beginning, skip it until a variable cell space is found.*/         

  goto a;//jump to a: and increment the current number in the cell by 1.
  } 
 if(j<3){o=0;oo=3;}if(j>2 && j<6){o=3;oo=6;}/*locate the 3X9 grid j is in.*/
 if(j>5){o=6;oo=9;}

 if(i<3){ooo=0;oooo=3;}if(i>2 && i<6){ooo=3;oooo=6;}/*locate the 9X3 grid i is in.*/
 if(i>5){ooo=6;oooo=9;}       
                               
 for(int u=ooo; u<oooo; ++u)/*intersect the 3X9 and 9X3 grids to create a searchable 3X3 grid.*/   
 { 
 for(int p=o; p<oo; ++p)
 {
     
     if(a[u][p]==a[i][j]){++x;if(x>1){x=0;goto a;}}/*if the number is not valid, go to a: and increment the number in the cell by 1.*/
            
  }
  
  }    
 x=0;
  for(int n=0; n<9; ++n)
  {
  if(a[i][j]==a[i][n]){++y; if(y>1){y=0;goto a;}}/*if no valid number is found, goto a: and increment the number in the cell by 1.*/
  }y=0;
  
  for(int m=0; m<9; ++m)
  {
   if(a[i][j]==a[m][j]){++y; if(y>1){y=0;goto a;}}//""     
  } y=0;   

  
  } 
  
  }
  } 

for(int i=0; i<9; ++i)//print the completed puzzle.
{
  for(int j=0; j<9; ++j)
    {
     cout<<a[i][j]<<" ";
    }  
    cout<<endl;//print on the next line after 9 digits are printed.  
}

return 0;
}

//if no valid puzzle is found, the screen hangs.  -  Harjinder




/*random sudokus' can be generated and solved in one program by copying the following code into an editor. hit enter to generate and solve a new puzzle:

//the following works the same way as above except that it is 2 solvers in a continuous while loop

//the first solver, to generate the random puzzle:

#include <iostream> 

using namespace std;

int main(){
 while(1){     
 int a[9][9]={0}, a2[9][9]={0};


 int w=0, x=0,y=0,z=0, yy=0, oo=0,o=0,ooo=0,oooo=0;
 for(int i=0; i<9; ++i)
 {
 for(int j=0; j<9; ++j)
 { 
   if(!a2[i][j])
   {srand(time(0));if(w<5){++w;a[i][j]=rand()%9;}a:++a[i][j];//generate a random number from 0 to 9 and and then increment by 1. 
       
   if(a[i][j]>9)
  { 
             a[i][j]=0; 
             --j;if(j<0){--i;j=8;}
   while(a2[i][j]){--j;if(j<0){--i;j=8;}}


  goto a;
  } 
 if(j<3){o=0;oo=3;}if(j>2 && j<6){o=3;oo=6;}
 if(j>5){o=6;oo=9;}

 if(i<3){ooo=0;oooo=3;}if(i>2 && i<6){ooo=3;oooo=6;}
 if(i>5){ooo=6;oooo=9;}

 for(int u=ooo; u<oooo; ++u)
 {
 for(int p=o; p<oo; ++p)
 {
  if(a[u][p]==a[i][j]){++x;if(x>1){x=0;goto a;}}
  }}
x=0;
 for(int n=0; n<9; ++n)
 {
 if(a[i][j]==a[i][n]){++y; if(y>1){y=0;goto a;}}
 }y=0;

 for(int m=0; m<9; ++m)
 {
 if(a[i][j]==a[m][j]){++y; if(y>1){y=0;goto a;}}
 } y=0;}//if 
 }
  }
  
//the second part below is to add zeros' to the puzzle, and copy the puzzle into the second solver arrays. 
int n=40;//adjusts the amount of empty spaces. works only if landed on non-zero, or else the zero will be counted.
x=0;int xx=0;
o=0;int pp=0,ppp=0;
while(o<n)
{
 
pp=rand()%9;
ppp=rand()%9; 
 a[pp][ppp]=0;  
  pp=rand()%9;
 ppp=rand()%9;    
a[ppp][pp]=0;    

 ++o;
}
for(int i=0; i<9; ++i)
{
for(int j=0; j<9; ++j)
    {
     cout<<a[i][j]<<" ";
     
    }
     cout<<endl;
}
x=0,xx=0;

cout<<endl<<endl;
int a5[9][9]={0}, a6[9][9]={0};x=-1;
for(int i=0; i<9; ++i)
{
for(int j=0; j<9; ++j)
    {
     ++x;
     a5[i][j]=a[i][j];//copy first puzzle with added zeros into the new array.
     
    }
     
}
for(int i=0; i<9; ++i)
{
for(int j=0; j<9; ++j)
    {
     a6[i][j]=a5[i][j];//copy the updated puzzle with zeros, into the constant reference array.
     
    }
     
}

x=0;
////////////////////////////////////////////////////////////////////////
//second solver to solve the zero updated array:
cout<<endl<<endl;
o=0;
y=0,z=0;
oo=0,ooo=0,oooo=0;
for(int i=0; i<9; ++i)
{
for(int j=0; j<9; ++j)
{
if(!a6[i][j])
{c5:
 ++a5[i][j];
  if(a5[i][j]>9)
 {
             a5[i][j]=0;
             --j;if(j<0){--i;j=8;}
    while(a6[i][j]){--j;if(j<0){--i;j=8;}}
     
  goto c5;
  }
 if(j<3){o=0;oo=3;}if(j>2 && j<6){o=3;oo=6;}
 if(j>5){o=6;oo=9;}

 if(i<3){ooo=0;oooo=3;}if(i>2 && i<6){ooo=3;oooo=6;}
 if(i>5){ooo=6;oooo=9;}

 for(int u=ooo; u<oooo; ++u)
 {
 for(int p=o; p<oo; ++p)
 {
  if(a5[u][p]==a5[i][j]){++x;if(x>1){x=0;goto c5;}}
 }}
x=0;
for(int n=0; n<9; ++n)
{
if(a5[i][j]==a5[i][n]){++y; if(y>1){y=0;goto c5;}}
 }y=0;

for(int m=0; m<9; ++m)
{
 if(a5[i][j]==a5[m][j]){++y; if(y>1){y=0;goto c5;}}
 } y=0;} }
 }

for(int i=0; i<9; ++i)
{
for(int j=0; j<9; ++j)
    {
     cout<<a5[i][j]<<" ";
    }
    cout<<endl;
}

cout<<endl;
system("pause");//hit enter to load a new puzzle
}
 
return 0;
} */

Question 4

The answer given above is similar to what a lot of people have posted at several websites like https://www.geeksforgeeks.org/sudoku-backtracking-7/. TBH, those solutions are not intuitive to me when they don't initialize row and col and call it in the FindUnassignedLocation function. I wanted to give it a shot myself with slight help from another answer I found on LeetCode. If it helps anyone, here you go.

// https://www.pramp.com/challenge/O5PGrqGEyKtq9wpgw6XP

#include <iostream>
#include <vector>

using namespace std;

// Print the sudoku
void print(vector<vector<char>> board){
    for(int i = 0; i < board.size(); i++){
        for(int j = 0; j < board[i].size(); j++){
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

// Check if sudoku is all filled up
bool checkIfFilled(vector<vector<char>> board){
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++){
            if(board[i][j] == '.')
                return false;
        }
    }
    return true;
}

// Check if a given number can be inserted at a given position
bool checkIfInsertOkay(vector<vector<char>> board, int x, int y, char num){
    // Check row if num already exists
    for(int j = 0; j < 9; j++){
        if(board[x][j] == num)
            return false;
    }
    // Check column if num already exists
    for(int i = 0; i < 9; i++){
        if(board[i][y] == num)
            return false;
    }
    // Check 3x3 gird if num already exists
    // Find the corners
    // Find i
    if(x < 3)
        x = 0;
    else if(x < 6)
        x = 3;
    else
        x = 6;
    // Find j
    if(y < 3)
        y = 0;
    else if(y < 6)
        y = 3;
    else
        y = 6;
    // Check the 3x3 box
    for(int i = x; i < x+3; i++){
        for(int j = y; j < y+3; j++){
            if(board[i][j] == num)
                return false;
        }
    }
    return true;
}

// Helper function because of const issues
bool sudokuSolveHelper(vector<vector<char>> &board){
    // Base condition - if sudoku gets completely filled
    if(checkIfFilled(board))
        return true;

    // Iterate through the sudoku
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++){
            // If empty space
            if(board[i][j] == '.'){
                for(int k = 1; k <= 9; k++){
                    // Check if char(k) can be inserted at this empty location
                    char ch = '0' + k;
                    if(checkIfInsertOkay(board, i, j, ch)){
                        // Put k in this empty location and check
                        board[i][j] = ch;
                        // Check if done
                        bool flag = sudokuSolveHelper(board);
                        if(flag)
                            return true;
                        else
                            // Else, backtrack by making it empty again
                            board[i][j] = '.';
                    }
                }
                return false;
            }
        }
    }
    return true;
}

// Return true if a correct sudoku can be formed
// Apply backtracking
// Time complexity = O(9^empty spaces)
bool sudokuSolve(vector<vector<char>> &board){
    return sudokuSolveHelper(board);
}

int main() {

    vector<vector<char>> board = {
        {'.','.','.','7','.','.','3','.','1'},
        {'3','.','.','9','.','.','.','.','.'},
        {'.','4','.','3','1','.','2','.','.'},
        {'.','6','.','4','.','.','5','.','.'},
        {'.','.','.','.','.','.','.','.','.'},
        {'.','.','1','.','.','8','.','4','.'},
        {'.','.','6','.','2','1','.','5','.'},
        {'.','.','.','.','.','9','.','.','8'},
        {'8','.','5','.','.','4','.','.','.'}
    };
    print(board);
    bool flag = sudokuSolve(board);
    if(flag){
        cout << "A solution exists as below\n";
        print(board);
    }
    else
        cout << "No solution exists!\n";
    return 0;
}

Question 5

//the following works like the one above accept there is a while loop instead of goto statements:

#include <iostream>
#include <cmath>
#include "time.h"
//for(int i=0; i< ++i){}
using namespace std;

int main(){
int a[9][9]={{2,0,0,0,0,0,0,0,1},
             {0,0,0,9,0,6,0,0,0},
             {0,0,0,8,0,1,7,2,0},
             {9,0,0,3,0,0,0,0,0},
             {0,0,8,0,0,0,2,0,4},
             {0,0,0,0,0,0,0,1,3},
      /*54*/ {1,0,3,0,0,5,0,0,9},
             {0,0,0,0,0,0,0,0,0},
             {0,4,6,2,0,0,0,0,0}};

 int a2[9][9]={{2,0,0,0,0,0,0,0,1},
             {0,0,0,9,0,6,0,0,0},
             {0,0,0,8,0,1,7,2,0},
             {9,0,0,3,0,0,0,0,0},
             {0,0,8,0,0,0,2,0,4},
             {0,0,0,0,0,0,0,1,3},
             {1,0,3,0,0,5,0,0,9},
             {0,0,0,0,0,0,0,0,0},
             {0,4,6,2,0,0,0,0,0}};

 int x=0,y=0,z=0;
 int colPlusThree=0,col=0,row=0,rowPlusThree=0;
  for(int i=0; i<9; ++i)
  {
  for(int j=0; j<9; ++j)
  {z=0;
  if(!a2[i][j])
  {while(z==0){ //the master while loop. loops until a valid number is found.
  ++a[i][j];
  if(a[i][j]>9)
 {
             a[i][j]=0;
             --j;if(j<0){--i;j=8;}
    while(a2[i][j]){--j;if(j<0){--i;j=8;}}

 ++a[i][j];if(a[i][j]>9){--j;}
 }      

if(j<3){col=0;colPlusThree=3;}if(j>2 && j<6){col=3;colPlusThree=6;}
if(j>5){col=6;colPlusThree=9;}

if(i<3){row=0;rowPlusThree=3;}if(i>2 && i<6){row=3;rowPlusThree=6;}
if(i>5){row=6;rowPlusThree=9;}

 for(int u=row; u<rowPlusThree; ++u)
 {
 for(int p=col; p<colPlusThree; ++p)
 {
  if(a[u][p]==a[i][j]){++x;if(x>1){u=rowPlusThree;break;}}
 }}if(x<2){z=1;}else{z=0;}x=0;

for(int n=0; n<9; ++n)
{
if(z==0){y=2;break;}
if(a[i][j]==a[i][n]){++y; if(y>1){break;}}
}if(y<2){z=1;}else{z=0;}y=0;

for(int m=0; m<9; ++m)
{
 if(z==0){y=2;break;}     
 if(a[i][j]==a[m][j]){++y; if(y>1){break;}}
} if(y<2){z=1;}else{z=0;}y=0;}}}}

for(int i=0; i<9; ++i)
{
for(int j=0; j<9; ++j)
    {
     cout<<a[i][j]<<" ";
    }
    cout<<endl;
}

return 0;
}//  -  Harjinder