Problem: Sudoku Sudoku is a 9x9 grid divided into smaller 3x3 boxes (also called
ID: 3570576 • Letter: P
Question
Problem: Sudoku
Sudoku is a 9x9 grid divided into smaller 3x3 boxes (also called regions). Some cells, called fixed cells, are pre-polulated with numbers from 1 to 9. See the figure below.
The objective is to fill the empty cells- the free cells - with numbers from 1 to 9 so that every row, every column and every 3x3 region contains the numbers 1 to 9 exactly once.
There are 9 rows, 9 columns and 9 regions to consider in the solution of the problem.
Considering the board as a matrix, the board translates to a 9x9 array, with row 0 at the top and row 8 at the bottom, column 0 on the left, column 8 on the right, and the 9 regions are the 3x3 blocks centered around the matrix elements {1,1}, {1,4}, {1,7};{4,1},{4,4},{4,7};{7,1},{7,4},and {7,7}.
Your programming task will be to:
Your internal representations of the board is required to be a two-dimensional array. The board depicted in the figure above would be stored as:
short int initialBoard[][] ={ { 9, 5, 2, 0, 0, 0, 0, 0, 1},
{ 0, 4, 0, 0, 2, 0, 0, 0, 0},
{ 0, 0, 0, 7, 0, 3, 4, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0, 0, 9},
{ 0, 2, 9, 3, 0, 8, 5, 1, 0},
{ 6, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 8, 1, 0, 6, 0, 0, 0},
{ 0, 0, 0, 0, 7, 0, 0, 8, 0},
{ 5, 0, 0, 0, 0, 0, 7, 3, 6} };
The algorithm to search for a solution should be to:
The search moves forward and backward continuously until one of the following two cases arises:
Input Files:
The board is to be input from a file containing 9 rows of 9 numbers. The number '0' is used to indicate a blank cell. If the file does not contain a valid board, your program should display an error message and terminate.
The contents of the file which represent the board in the figure above would be:
9 5 2 0 0 0 0 0 1
0 4 0 0 2 0 0 0 0
0 0 0 7 0 3 4 0 0
0 0 0 0 0 0 0 0 9
0 2 9 3 0 8 5 1 0
6 0 0 0 0 0 0 0 0
0 0 8 1 0 6 0 0 0
0 0 0 0 7 0 0 8 0
5 0 0 0 0 0 7 3 6
Output to the console
The output of a valid board to the console should include borders using dashes, plus, equal and pipe characters. Plus characters denote the corners, columns are separated by the pipe character (|) and rows are separated by a line of dashes, and regions are set apart vertically by '=', and horizonatally by pipe's interleaved in the dashes.Out put must be look like this:
Implementation Requirements
Your program is required to implement three boolean functions to be used for evaluating if a value assigned to a free cell is valid: isValidRow, isValidColumn, and isValidBlock. The return type of these functions must be boolean. The input parameters are up to you.
Again, your implementation must be well commented, properly indented, and use good variable names.
Explanation / Answer
#include<iostream>
using namespace std;
int su_in[9][9]={
0,0,7 ,0,0,0 ,4,0,6,
8,0,0 ,4,0,0 ,1,7,0,
0,0,0 ,3,0,0 ,9,0,5,
0,0,0 ,7,0,5 ,0,0,8,
0,0,0 ,0,0,0 ,0,0,0,
4,0,0 ,2,0,8 ,0,0,0,
7,0,4 ,0,0,3 ,0,0,0,
0,5,2 ,0,0,1 ,0,0,9,
1,0,8 ,0,0,0 ,6,0,0
};
int su_out[9][9];/*={
5,3,7 ,9,1,2 ,4,8,6,
8,2,9 ,4,5,6 ,1,7,3,
6,4,1 ,3,8,7 ,9,2,5,
9,1,3 ,7,4,5 ,2,6,8,
2,8,6 ,1,3,9 ,7,5,4,
4,7,5 ,2,6,8 ,3,9,1,
7,6,4 ,8,9,3 ,5,1,2,
3,5,2 ,6,7,1 ,8,4,9,
1,9,8 ,5,2,4 ,6,3,7
};*/
struct chance{
int poss[9];
};
int box_validate(int,int,int);
void read(int);
void display(int);
int validate(int);
int solve();
int main()
{
int i,j,row,get_res=2;
enum {input=1,output};
cout<<"enter the sudoku: use 0 if the colum is empty: ";
// for(i=0; i<9; i++){
// read(i);
// }
cout<<" THE ENTERED SU-DO-CU IS: ";
display(input);
get_res=validate(input);
if(get_res==0)
cout<<"valid input! ";
else if(get_res==1)
cout<<"invalid input! ";
// display(input);
for(i=0; i<9; i++)
for(j=0; j<9; j++)
su_out[i][j]=su_in[i][j];
// display(output);
get_res=validate(output);
if(get_res==0){
cout<<"valid solution! "; display(output);}
// else if(get_res==1)
// cout<<"invalid sudoku! ";
if(solve()==0) display(output);
else cout<<"not solved buddy!! ";
}
void read(int row) // function to read the SU-DO-CU
{
unsigned num,i;
cout<<"enter the row:'"<<row+1<<"' ";
for(i=0; i<9; i++)
{
cin>>num;
if(num<0||num>9)
cout<<"error! invalid input: enter a number < or = 9 and > or = 0 ";
else
su_in[row][i]=num;
}
}
void display(int sudoku) // function to display the SU-DO-CU
{
unsigned i,j;
for(i=0;i<9; i++)
{
if(i%3==0)
cout<<" ------------------------- ";
cout<<" ";
for(j=0; j<9; j++)
{
if(j%3==0)
cout<<"| ";
// if(su[i][j]==0)
// cout<<"_ ";
// else
if(sudoku==1)
cout<<su_in[i][j]<<" ";
else if(sudoku==2)
cout<<su_out[i][j]<<" ";
if(j==8)
cout<<"|";
}
cout<<" ";
if(i==8)
cout<<" ------------------------- ";
}
}
int validate(int sudoku) // function to validate the input SU-DO-CU
{
unsigned i,j,k,n,count=0;
//..........................row validation
for(i=0; i<9; i++)
for(j=0; j<9; j++)
for(k=0;k<9;k++)
{
if(sudoku==1 && k!=j && su_in[i][j]!=0)
{
if(su_in[i][j]==su_in[i][k])
return 1;
}
else if(sudoku==2 && k!=j )
{
if(su_out[i][j]==su_out[i][k])
return 1;
}
}
//..................................colume validation
for(i=0; i<9; i++)
for(j=0; j<9; j++)
for(k=0; k<9; k++)
{
if(sudoku==1 && k!=j && su_in[j][i]!=0)
{
if(su_in[j][i]==su_in[k][i])
return 1;
}
else if(sudoku==2 && k!=i )
{
if(su_out[j][i]==su_out[j][k])
return 1;
}
}
// each box validating.......................
for(i=0; i<=6; i=i+3)
for(j=0; j<=6; j=j+3)
{
if(box_validate(i,j,sudoku)==1)
return 1;
}
// sum validation for output....
if(sudoku==2)
{
for(i=0; i<9; i++)
for(j=0; j<9; j++)
count=count+su_out[i][j];
if(count!=405) return 1;
}
return 0;
}
int box_validate(int i,int j,int sudoku)
{
unsigned k=j,n=i;
int temp_i=i,temp_j=j,temp_k=k, temp_n=n;
for(i=temp_i; i<temp_i+3; i++)
for(j=temp_j; j<temp_j+3; j++)
for(k=temp_k; k<temp_k+3; k++)
{
if(sudoku==1 && k!=j && su_in[i][j]!=0)
{
if(su_in[i][j]==su_in[i][k])
return 1;
for(n=temp_n; n<temp_n+3; n++)
{
if(sudoku==1 && su_in[i][j]!=0)
if(k==j && n==i)
;else
if(su_in[i][j]==su_in[n][k])
return 1;
}
}
if(sudoku==2 && k!=j )
{
if(su_out[i][j]==su_out[i][k])
return 1;
for(n=temp_n; n<temp_n+3; n++)
{
if(sudoku==1 )
if(k==j && n==i)
;else
if(su_out[i][j]==su_out[n][k])
return 1;
}
}
}
return 0;
}
int solve()
{
unsigned i,j,k,m,n,x;
struct chance cell[9][9];
for(i=0; i<9; i++)
for(j=0; j<9; j++)
if(su_in[i][j]==0)
for(k=0;k<9; k++)
cell[i][j].poss[k]=k+1;
/*
for(i=0; i<9; i++)
for(j=0; j<9; j++)
if(su_in[i][j]==0)
for(k=0;k<9; k++)
{ su_out[i][j]=cell[i][j].poss[k]=k+1;
su_out[i][j]=cell[i][j].poss[k];
for(m=0; m<9; m++)
for(n=0; n<9; n++)
for(x=1; x<=9; x++)
{ if(x!=k+1)
cell[m][n].poss[x]==x;
if(validate(2)==0)
return 0;
}
}*/
for(i=0; i<9; i++)
for(j=0; j<9; j++)
if(su_in[i][j]==0)
while (validate(2)==0)
{
for(k=0;k<9; k++)
{ su_out[i][j]=k+1;
for(m=i+1; m <9 ; m++)
for(n=0; n <9 ; n++)
for(x=1; x<=9; x++)
{ su_out[m][n]=x;
if(validate(2)==0)
return 0;
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.