Question

Data Structure

using C++ Complete and test the Sudoku problem

main.cpp

#include <iostream>
#include <cmath>
#include "sudoku.h"

using namespace std;

int main()
{
cout << "See Programming Exercise 18." << endl;
}

sudoku.cpp

#include <iostream>
#include "sudoku.h"

using namespace std;

sudoku::sudoku()
{
cout << "Write the definition. ." << endl;
}

sudoku::sudoku(int g[][9])
{
cout << "Write the definition." << endl;
}

void sudoku::initializeSudokuGrid()
{
cout << "Write the definition." << endl;
}

void sudoku::initializeSudokuGrid(int g[][9])
{
cout << "Write the definition. " << endl;
}

void sudoku::printSudokuGrid()
{
cout << "Write the definition." << endl;
}

bool sudoku::solveSudoku()
{
int row, col;

if (findEmptyGridSlot(row, col))
{   
for (int num = 1; num <= 9; num++)
{   
if (canPlaceNum(row, col, num))
{
grid[row][col] = num;
if (solveSudoku()) //recursive call
return true;
grid[row][col] = 0; //backtrack
}
}
return false;
}
else
return true; //there are no empty slots
}

bool sudoku::findEmptyGridSlot(int &row, int &col)
{
cout << "Write the definition."<< endl;
}

bool sudoku::canPlaceNum(int row, int col, int num)
{
cout << "Write the definition."<< endl;
}

bool sudoku::numAlreadyInRow(int row, int num)
{
cout << "Write the definition." << endl;
}

bool sudoku::numAlreadyInCol(int col, int num)
{
cout << "Write the definition." << endl;
}

bool sudoku::numAlreadyInBox(int smallGridRow, int smallGridCol,
int num)
{
cout << "Write the definition." << endl;
}

sudoku.h

//***************************************************************
// D.S. Malik
//
// This class specifies the functions to solve a sudoku problem.
//***************************************************************

class sudoku
{
public:
sudoku();
//default constructor
//Postcondition: grid is initialized to 0

sudoku(int g[][9]);
//constructor
//Postcondition: grid = g

void initializeSudokuGrid();
//Function to promt the user to specify the numbers of the
//partially filled grid.
//Postcondition: grid is initialized to the numbers
// specified by the user.

void initializeSudokuGrid(int g[][9]);
//Function to initialize grid to g
//Postcondition: grid = g;

void printSudokuGrid();
//Function to print the sudoku grid.

bool solveSudoku();
//Funtion to solve the sudoku problem.
//Postcondition: If a solution exits, it returns true,
// otherwise it returns false.
bool findEmptyGridSlot(int &row, int &col);
//Function to determine if the grid slot specified by
//row and col is empty.
//Postcondition: Returns true if grid[row][col] = 0;

bool canPlaceNum(int row, int col, int num);
//Function to determine if num can be placed in
//grid[row][col]
//Postcondition: Returns true if num can be placed in
// grid[row][col], otherwise it returns false.

bool numAlreadyInRow(int row, int num);
//Function to determine if num is in grid[row][]
//Postcondition: Returns true if num is in grid[row][],
// otherwise it returns false.

bool numAlreadyInCol(int col, int num);
//Function to determine if num is in grid[row][]
//Postcondition: Returns true if num is in grid[row][],
// otherwise it returns false.

bool numAlreadyInBox(int smallGridRow, int smallGridCol,
int num);
//Function to determine if num is in the small grid
//Postcondition: Returns true if num is in small grid,
// otherwise it returns false.

private:
int grid[9][9];
};

Answer 1

Here is my solution for the soduko problem with the tested output

#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);
}
 
/* print grid  */
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;
    }
}
 
/* Main */
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;
}

Here is the output:

Hope this helps:).If you still have any doubt , feel free to discuss it in the comment sections.