Declare a data structure to represent a Sudoko puzzle, write some functions to r
ID: 662600 • Letter: D
Question
Declare a data structure to represent a Sudoko puzzle, write some functions to read Sudoko puzzle from keyboard/file, check if a proposed solution follows the Sudoku rules against duplicating values in a row, column, or outlined 3 x 3 square. You can also write another function which can list the possible values for each empty cell according to Sudoku rules. If needed, we will discuss Sudoko rules in the class. So instead of asking you to write a program that can solve a Sudoko puzzle, which will be hard, you are asked to write a program that can do some of the simple things mentioned above. Specifically, your program must do the followings:
Declare a minimum size data structure to store the values of a Sudoko puzzle (suppose empty cells will have the value of 0 while the other cells will have values from 1 to 9).
Then ask user if he/she wants to enter data for a sudoku puzzle or a sudoku solution. Suppose user enters 1 to enter a puzzle; or 2 to enter a solution to be checked.
Write/call a function that asks user to enter the values for a Sudoku puzzle or solution and saves these values into the data structure you declared in the previous item. User is expected to enter a number between 0 and 9 for each cell in case of a puzzle. Zero is for empty cells, 1-9 are for other cells. In case of a solution, user is expected to enter only the values between 1 and 9. Your program should reject invalid values. [Note: I am sure you are wondering if you have to enter 82 values by hand. Unfortunately, yes :( until we learn how to read data files in ch3. But there is another option: you develop your program as if you will read the values from keyboard. But when you are running the program, the operating system
Explanation / Answer
this is 9x9
#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;
}
------------------------------------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.