please HELPPP: data Structure / use for c++ Make modifications to your solution
ID: 3845998 • Letter: P
Question
please HELPPP: data Structure / use for c++
Make modifications to your solution to Sudoku I that
1) defines grids of "arbitrary" size.
9 x 9 grids are possible
16 x 16 grids are possible
25 x 25 grids are possible
...
The criterion that must be met is that the grid dimension be a perfect square
attach sudoku solution:
Source.cpp
#include <iostream>
#include <string>
#include "Sudoku.h"
using namespace std;
int main()
{
int g[][9] =
{
{6,0,3,0,2,0,0,9,0},
{0,0,0,0,5,0,0,8,0},
{0,2,0,4,0,7,0,0,1},
{0,0,6,0,1,4,3,0,0},
{0,0,0,0,8,0,0,5,6},
{0,4,0,6,0,3,2,0,0},
{8,0,0,2,0,0,0,0,7},
{0,1,0,0,7,5,8,0,0},
{0,3,0,0,0,6,1,0,5}
};
Sudoku sudoku1;
sudoku1.printSudokuGrid();
sudoku1.solveSudoku();
cout << endl;
sudoku1.printSudokuGrid();
cout << endl;
Sudoku sudoku2(g);
sudoku2.solveSudoku();
sudoku2.printSudokuGrid();
cout << endl;
sudoku2.solveSudoku();
sudoku2.printSudokuGrid();
cout << endl;
system("pause");
return 0;
}
Sudoku.cpp
#include <iostream>
#include <string>
#include "sudoku.h"
using namespace std;
Sudoku::Sudoku(void)
{
initializeSudokuGrid();
}
Sudoku::Sudoku(int g[][9])
{
initializeSudokuGrid(g);
}
void Sudoku::initializeSudokuGrid()
{
for(int row = 0; row < 9; row++)
for(int col = 0; col < 9; col++)
grid[row][col] = 0;
}
void Sudoku::initializeSudokuGrid(int g[][9])
{
for(int row = 0; row < 9; row++)
for(int col = 0; col < 9; col++)
grid[row][col] = g[row][col];
}
void Sudoku::printSudokuGrid()
{
for(int row = 0; row < 9; row++)
{
for(int col = 0; col < 9; col++)
cout << grid[row][col];
cout << endl;
}
}
bool Sudoku::solveSudoku()
{
int row = 0, col = 0;
if(findEmptyGridSlot(row, col))
{
for(int num = 1; num <= 9; num++)
{
if(canPlaceNum(row, col, num))
{
grid[row][col] = num;
if(solveSudoku())
return true;
grid[row][col] = 0;
}
}
return false;
}
else
return true;
}
bool Sudoku::findEmptyGridSlot(int &row, int &col)
{
for (row = 0; row < 9; row++)
for (col = 0; col < 9; col++)
if (grid[row][col] == 0)
return true;
row = -1;
col = -1;
return false;
}
bool Sudoku::canPlaceNum(int row, int col, int num)
{
return !numAlreadyInRow(row, num) &&
!numAlreadyInCol(col, num)&&
!numAlreadyInBox(row, col, num);
}
bool Sudoku::numAlreadyInRow(int row, int num)
{
for(int col = 0; col < 9; col++)
if(grid[row][col] == num) return true;
return false;
}
bool Sudoku::numAlreadyInCol(int col, int num)
{
for (int row = 0; row < 9; row++)
if (grid[row][col] == num) return true;
return false;
}
bool Sudoku::numAlreadyInBox(int smallGridRow, int smallGridCol, int num)
{
int beginSmallGridRow = smallGridRow - smallGridRow % 3;
int endSmallGridRow = beginSmallGridRow + 3;
int beginSmallGridCol = smallGridCol - smallGridCol % 3;
int endSmallGridCol = beginSmallGridCol + 3;
for (int row = beginSmallGridRow; row < endSmallGridRow; row++)
for (int col = beginSmallGridCol; col < endSmallGridCol; col++)
if (grid[row][col] == num)
return true;
return false;
}
Sudoku.h
#pragma once
/* notes
sudoku()
default constructor
precondition : none
postcondition: grid is initialized to 0
sudoku(g[][9])
1-parameter constructor
precondition : g satisfies sudoku grid restrictions
postcondition: grid = g
void initialiizeSudokuGrid()
interactive function to prompt the user to specify the number of the partially filled grid
precondition : none
postcondition: grid is initialized to the number specified by the user
void initializeSudokuGrid(int g[][9])
function to initialize grid to g
precondition: g satisties sudoku grid restrictions
postcondition: grid = g
void printSudokuGrid()
function to print the sudoku
bool solveSudoku()
function to solve thesukoku problem
precondition : none
postcondition: if a solution exists, 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
precondition : row and col refer to a grid slot
postcondition: returns true if grid[row][col] = 0, otherwise it returns false
bool canPlaceNum(int row, int col, int num)
function to determine if num can be placed in grid[row][col]
precondition : row and col refer to a grid slot
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][]
precondition : row refers to a grid row and num is an integer inclusively between 1 and 9
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][]
precondition : col refers to a grid column and num is an integer inclusively between 1 and 9
postcondition: returns true if num is in grid[][col], otherwise it returns false
bool numAlreadyInBox(int smallGridRow, int smallGridCol, int num)
function to determine if num is in the small grid that contains grid[smallGridRow][smallGridCol]
precondition : smallGridRow and smallGridCol refer to a grid slot, num is an integer inclusively between 1 and 9
postcondition: returns true if num is in small grid, otherwise it returns false
*/
class Sudoku
{
public:
Sudoku();
Sudoku(int g[][9]);
void initializeSudokuGrid();
void initializeSudokuGrid(int g[][9]);
void printSudokuGrid();
bool solveSudoku();
bool findEmptyGridSlot(int &row, int &col);
bool canPlaceNum(int row, int col, int num);
bool numAlreadyInRow(int row, int num);
bool numAlreadyInCol(int col, int num);
bool numAlreadyInBox(int smallGridRow, int smallGridCol, int num);
private:
int grid[9][9];
};
Explanation / Answer
Source.cpp
#include <iostream>
#include <string>
#include "Sudoku.h"
using namespace std;
int main()
{
int g[][9] =
{
{6,0,3,0,2,0,0,9,0},
{0,0,0,0,5,0,0,8,0},
{0,2,0,4,0,7,0,0,1},
{0,0,6,0,1,4,3,0,0},
{0,0,0,0,8,0,0,5,6},
{0,4,0,6,0,3,2,0,0},
{8,0,0,2,0,0,0,0,7},
{0,1,0,0,7,5,8,0,0},
{0,3,0,0,0,6,1,0,5}
};
Sudoku sudoku1;
sudoku1.printSudokuGrid();
sudoku1.solveSudoku();
cout << endl;
sudoku1.printSudokuGrid();
cout << endl;
Sudoku sudoku2(g);
sudoku2.solveSudoku();
sudoku2.printSudokuGrid();
cout << endl;
sudoku2.solveSudoku();
sudoku2.printSudokuGrid();
cout << endl;
system("pause");
return 0;
}
Sudoku.cpp
#include <iostream>
#include <string>
#include "sudoku.h"
using namespace std;
Sudoku::Sudoku(void)
{
initializeSudokuGrid();
}
Sudoku::Sudoku(int g[][9])
{
initializeSudokuGrid(g);
}
void Sudoku::initializeSudokuGrid()
{
for(int row = 0; row < 9; row++)
for(int col = 0; col < 9; col++)
grid[row][col] = 0;
}
void Sudoku::initializeSudokuGrid(int g[][9])
{
for(int row = 0; row < 9; row++)
for(int col = 0; col < 9; col++)
grid[row][col] = g[row][col];
}
void Sudoku::printSudokuGrid()
{
for(int row = 0; row < 9; row++)
{
for(int col = 0; col < 9; col++)
cout << grid[row][col];
cout << endl;
}
}
bool Sudoku::solveSudoku()
{
int row = 0, col = 0;
if(findEmptyGridSlot(row, col))
{
for(int num = 1; num <= 9; num++)
{
if(canPlaceNum(row, col, num))
{
grid[row][col] = num;
if(solveSudoku())
return true;
grid[row][col] = 0;
}
}
return false;
}
else
return true;
}
bool Sudoku::findEmptyGridSlot(int &row, int &col)
{
for (row = 0; row < 9; row++)
for (col = 0; col < 9; col++)
if (grid[row][col] == 0)
return true;
row = -1;
col = -1;
return false;
}
bool Sudoku::canPlaceNum(int row, int col, int num)
{
return !numAlreadyInRow(row, num) &&
!numAlreadyInCol(col, num)&&
!numAlreadyInBox(row, col, num);
}
bool Sudoku::numAlreadyInRow(int row, int num)
{
for(int col = 0; col < 9; col++)
if(grid[row][col] == num) return true;
return false;
}
bool Sudoku::numAlreadyInCol(int col, int num)
{
for (int row = 0; row < 9; row++)
if (grid[row][col] == num) return true;
return false;
}
bool Sudoku::numAlreadyInBox(int smallGridRow, int smallGridCol, int num)
{
int beginSmallGridRow = smallGridRow - smallGridRow % 3;
int endSmallGridRow = beginSmallGridRow + 3;
int beginSmallGridCol = smallGridCol - smallGridCol % 3;
int endSmallGridCol = beginSmallGridCol + 3;
for (int row = beginSmallGridRow; row < endSmallGridRow; row++)
for (int col = beginSmallGridCol; col < endSmallGridCol; col++)
if (grid[row][col] == num)
return true;
return false;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.