| nikhilpurwant
| Joined: 15 Nov 2005 | Posts: 1 | : | | Items |
|
Posted: Tue Nov 15, 2005 5:26 pm Post subject: program for sudoku puzzle generator and solver |
|
|
here is a C source code which creates a valid (9*9; 9 rows 9 columns ) sudoku puzzle and also reveals its answer there are three difficulty levels provided viz. simple medium and hard. it is possible to write a puzzle / answer to a file all the functions are documented explaining the logic
the program is compilable with both ms windows ( borland tc compiler ) and linux ( gcc ). just remove ( comment the line #define LINUX ) when working in windows output format of this program is as usual same as some of the progs posted previously here for the logic it is explained within the file itself with every function documented.
SAVE IT AS SUDOKU.C preferably NOT .cpp
Code: |
/****************************************************************************
A Program For SuDoKu Puzzle Generation
Program Was Compiled With Borland TC version 3.0
and Borland C++ 5.5.1 for Win32 and gcc v 4.0.1
copyright(c): Nikhil Purwant.(nikhilpurwant@yahoo.com)
date : 28/10/2005
|---|---|---|
| 4 | 2 | 1 |
|---|---|---|
| 7 | 8 | 9 | =>single 3*3 cell in the SuDoku ( containing 1-9 unique numbers )
|---|---|---|
| 6 | 3 | 5 |
|---|---|---|
___________________
|_|_|_|_|_|_|_|_|_|
|_|1|_|_|2|_|_|3|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|4|_|_|5|_|_|6|_| => sudoku cells 1-9 each is a 3*3 subcell like shown above
|_|_|_|_|_|_|_|_|_| also no row or column of complete sudoku(9*9) contain repeated
|_|_|_|_|_|_|_|_|_| elements and strictly contain element from 1to9
|_|7|_|_|8|_|_|9|_|
|_|_|_|_|_|_|_|_|_|
*****************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define LINUX //COMMENT THIS LINE IF YOU ARE PROGRAMMING IN MS WINDOWS ENV (TC)
#ifndef LINUX
#include<conio.h>
#endif
int check_this_in_a_col(int matrix[9][9],int col,int maxindex,int element);
int is_this_in_3by3cell(int value,int filled[9]);
void initialise_filled_to_0(int filled[9]);
int make_a_new_cell(int matrix[9][9],int rl,int rh,int cl,int ch,int how2check);
int find_dup(int matrix[9][9],int i,int j,int array[9]);
int check_cell(int matrix[9][9],int rl,int rh,int cl,int ch);
void actual_thing_from_matrix(int matrix[9][9],int level);
void print_it(int mat[9][9],int to_file);
void print_both(int mat[9][9],int result[9][9],int to_file);
void sudoku(int mat[9][9],int filled[9]);
int main()
{
int filled[9],matrix[9][9],what2do;
#ifndef LINUX
clrscr();
#else
printf("\033[2J"); //clrscr() emulation in linux
printf("\033[""0"";""0""f");
#endif
while(1)
{
sudoku(matrix,filled);
}
} //end main
/*this function checks if the 3*3 cell contains
unique numbers between 1-9 for first (initial)3*3 cell*/
int is_this_in_3by3cell(int value,int filled[9])
{
int i;
for(i=0;i<9;i++)
{
if(filled[i]==value)
return 0;
}
for(i=0;i<9;i++)
{
if(filled[i]==0)
{
filled[i]=value;
break ;
}
}
return 1;
}//end func
//initialises filled[] array to zero
void initialise_filled_to_0(int filled[9])
{
int i;
for (i=0;i<9;i++)
filled[i]=0;
}
//This function Checks the occurance of a number in a column specified
//and returns 0 if the element is present
int check_this_in_a_col(int matrix[9][9],int col,int maxindex,int element)
{
int i,j;
if(element==0)
return 0;
for(i=0;i<maxindex;i++)
{
if (matrix[i][col]==element)
return 0;
}
return 1;
}
//This function Checks the occurance of a number in a row specified
//and returns 0 if the element is present
int check_this_in_a_row(int matrix[9][9],int row,int maxindex,int element)
{
int i,j;
if(element==0)
return 0;
for(i=0;i<maxindex;i++)
{
if (matrix[row][i]==element)
return 0;
}
return 1;
}
/*This function creates a new 3*3 cell with unique numbers from 1->9
and also calls functions check_this_in_a_row() and check_this_in_a_col()
so as to find if the element exists in the row or column of SuDoku
yet generated the option how2check specifies while creating a cell (3*3)
whether only horizontal check is to be done ( reqd for cell2 and cell3)
or only vertical(reqd for cell 4 and cell 7) or both checks to be done
(cells 5,6,8,9)
*/
int make_a_new_cell(int matrix[9][9],int rl,int rh,int cl,int ch,int how2check)
{
int i,j,presentcol=0,ii;
int available_elements[9]={1,2,3,4,5,6,7,8,9};
int value;
int max_lim=0,breakflag=0;
switch(how2check)
{
case 1:
do{
for(i=rl;i<rh;i++)
{
for(j=cl;j<ch;j++)
{
do{
value=rand()%9;
max_lim++;
if(max_lim>30)
{
breakflag=1;
break;
}
}while(check_this_in_a_row(matrix,i,j,available_elements[value])==0);
if(breakflag==1)
{
return 0;
}
matrix[i][j]=available_elements[value];
max_lim=0;
}//for j
}//for i
}while (check_cell(matrix,rl,rh,cl,ch)==0);
break;
case 2:
do{
for(i=rl;i<rh;i++)
{
for(j=cl;j<ch;j++)
{
do{
value=rand()%9;
max_lim++;
if(max_lim>30)
{
breakflag=1;
break;
}
}while(check_this_in_a_col(matrix,presentcol+j,i,available_elements[value])==0);
if(breakflag==1)
{
return 0;
}
matrix[i][j]=available_elements[value];
max_lim=0;
}//for j
}//for i
}while (check_cell(matrix,rl,rh,cl,ch)==0);
break;
case 3:
do{
for(i=rl;i<rh;i++)
{
for(j=cl;j<ch;j++)
{
do{
value=rand()%9;
max_lim++;
if(max_lim>30)
{
breakflag=1;
break;
}
}while(check_this_in_a_col(matrix,presentcol+j,i,available_elements[value])==0||check_this_in_a_row(matrix,i,j,available_elements[value])==0);
if(breakflag==1)
{
return 0;
}
matrix[i][j]=available_elements[value];
max_lim=0;
}//for j
}//for i
}while (check_cell(matrix,rl,rh,cl,ch)==0);
break;
}
return 1;
}
/*
This function Creates The Sudoku Puzzle by removing the elements from the 9*9
matrix ( VALID SUDOKU CREATED BY FUNCTION sudoku() please refer it first)
Based upon the difficulty level for simple sudoku value of level
passed is = 7 the expression (rand()%9 < 7) evaluate true more number
of times than if level were to be 5 hence less no of elements are left
blank in simple level similarly in difficult sudoku value of level passed = 3
hence more elements will be left blank
*/
void actual_thing_from_matrix(int matrix[9][9],int level)
{
int i,j,whatdo,what2do;
int dummymat[9][9];
#ifdef LINUX
time_t t;
srand((unsigned) time(&t));
#else
randomize(); //randomizes otherwise random and rand always give same op on each run
#endif
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if((rand()%9)<level)
dummymat[i][j]=matrix[i][j]; //** creation of puzzle
else
dummymat[i][j]=0;
}
}
printf("\n HERE IS THE SUDOKU\n");
printf("\n\t|---|---|---|---|---|---|---|---|---|\n");
print_it(dummymat,0);
do{
printf("\n\n1.Reveal The Answer Of This SuDoKu\n2.Write the Sudoku Puzzle to file\n3.New SuDoKu\n4.Exit\nEnter your choice::->");
scanf("%d",&whatdo);
switch(whatdo)
{
case 1:
printf("\n\t ***************SOLVED SUDOKU******************* \n");
print_both(dummymat,matrix,0);
printf("\n1.Write The Answer To File\n2.Continue Creating SuDoKus \n3.exit\nEnter your choice::->");
scanf("%d",&what2do);
switch(what2do)
{
case 1:
print_both(dummymat,matrix,1);
break;
case 2:
return;
case 3:
exit(0);
break;
default:
printf("\nWrong Choice");getc(stdin);
exit(0);
break;
} //end inner switch
break;
case 2:
print_it(dummymat,1);
break;
case 3:
return;
case 4:
exit(0);
}
}while(whatdo!=3);
}
// This Function Prints SUDOKU PUZZLE
void print_it(int mat[9][9],int to_file)
{
int i,j;
FILE *fp;
char filename[20];
if(to_file==1)
{
printf("\n Save Puzzle as ( Enter filename ) :->");
scanf("%s",filename);
fp=fopen(filename,"w");
if(fp==NULL)
{
printf("\n Cannot Open File (%s)",filename);
getc(stdin);
exit(1);
}
fprintf(fp," SUDOKU PUZZLE TO SOLVE \n");
fprintf(fp,"\n\t|---|---|---|---|---|---|---|---|---|\n");
}
for(i=0;i<9;i++)
{
printf("\t");
if(to_file==1)
fprintf(fp,"\t");
for(j=0;j<9;j++)
{
if(mat[i][j]!=0)
{printf("| %d ",mat[i][j]);if(to_file==1) fprintf(fp,"| %d ",mat[i][j]);}
else
{printf("| ");if(to_file==1) fprintf(fp,"| ");}
if(j==8)
{printf("|");if(to_file==1)fprintf(fp,"|");}
}
{ printf("\n\t|---|---|---|---|---|---|---|---|---|\n");if (to_file==1) fprintf(fp,"\n\t|---|---|---|---|---|---|---|---|---|\n");}
}
if(to_file==1)
{
printf("\n SuDoKu Puzzle Saved in \"%s\"",filename);
fclose(fp);
}
fflush(stdin);
//flushall();
}
//This Function Checks For Whether NO of elements in a 3*3 cell are from 1-9
//and not repeated
int check_cell(int matrix[9][9],int rl,int rh,int cl,int ch)
{
int i,j;
int this_array[9]={1,2,3,4,5,6,7,8,9};
for(i=rl;i<rh;i++)
{
for(j=cl;j<ch;j++)
{
if(matrix[i][j]==0)
return 0;
if(find_dup(matrix,i,j,this_array)==0)
return 0;
}
}
return 1;
}
//finds duplicate element within a cell
int find_dup(int matrix[9][9],int i,int j,int array[9])
{
if(array[matrix[i][j]-1]!=0)
array[matrix[i][j]-1]=0;
else
{
return 0;
}
return 1;
}
//This Function Prints Both Puzzle And Solved Answer
void print_both(int mat[9][9],int result[9][9],int to_file)
{
int i,j,mixed[9][18];
char filename[20];
FILE *fp;
if(to_file==1)
{
printf("\n Save The Answer As ( Enter Filename ) :");
scanf("%s",filename);
fp=fopen(filename,"w");
if(fp==NULL)
{
printf("\n Can't Open File " );
getc(stdin);
exit(1);
}
fprintf(fp,"\n The SuDoKu Puzzle And Solved SuDoKu are Here \n");
}
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
mixed[i][j]=mat[i][j];
mixed[i][j+9]=result[i][j];
}
}
if(to_file==1)
{fprintf(fp,"\n \t ORIGINAL SUDOKU SOLVED SUDOKU\n\n\t");
fprintf(fp,"|-|-|-|-|-|-|-|-|-| |-|-|-|-|-|-|-|-|-|\n\t");
}
printf("\n \t ORIGINAL SUDOKU SOLVED SUDOKU\n\n\t");
printf("|-|-|-|-|-|-|-|-|-| |-|-|-|-|-|-|-|-|-|\n\t");
for(i=0;i<9;i++)
{
for(j=0;j<18;j++)
{
if(j==9)
{printf("\t\t\t ");if(to_file==1)fprintf(fp,"\t\t\t ");}
if(mixed[i][j]!=0)
{printf("|%d",mixed[i][j]);if (to_file==1)fprintf(fp,"|%d",mixed[i][j]); }
else
{printf("| ");if(to_file==1) fprintf(fp,"| ");}
if(j==17||j==8)
{
printf("|");
if(to_file==1)
fprintf(fp,"|");
}
}
printf("\n\t|-|-|-|-|-|-|-|-|-| |-|-|-|-|-|-|-|-|-|\n\t");
if(to_file==1)
fprintf(fp,"\n\t|-|-|-|-|-|-|-|-|-| |-|-|-|-|-|-|-|-|-|\n\t");
}
if(to_file==1)
{
printf("\n Sudoku (Puzzle AND Answer) Successfully saved to File \"%s\"\n",filename) ;
fclose(fp);
}
fflush(stdin);
//flushall();
}
/*
Creates A valid SuDoku i.e. A 9*9 matrix with every row and column have
elements from 1-9 and no row and col has any no repeated also every
3*3 cell consists of elements from 1-9 and not repeated
also do-while loops make the cells to be recreated if a conflict is found
(in row col or in 3*3 cell of the sudoku) i.e backtracking if a row col or 3*3cell
conflict is found
*/
void sudoku(int matrix[9][9],int filled[9])
{
int i,j,value,level;
#ifdef LINUX
time_t t;
srand((unsigned) time(&t));
#else
randomize(); //randomizes otherwise random and rand always give same op on each run
#endif
initialise_filled_to_0(filled);
for (i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
do{
value=rand()%9+1;//random numbers between 0->(9-1) are produced so we add 1 since we want 1to9
}while(is_this_in_3by3cell(value,filled)==0);
matrix[i][j]=value;
}
}
printf("\n *SuDoKu Creation* Enter the difficulty level required:\n1.simple\n2.medium\n3.hard\nEnter your choice::->");
scanf("%d",&level);
do{
make_a_new_cell(matrix,0,3,3,6,1);
}while(make_a_new_cell(matrix,0,3,6,9,1)==0);
do{
make_a_new_cell(matrix,3,6,0,3,2);
make_a_new_cell(matrix,3,6,3,6,3);
}while(make_a_new_cell(matrix,3,6,6,9,3)==0);
do
{
do
{
make_a_new_cell(matrix,6,9,0,3,2);
}while(make_a_new_cell(matrix,6,9,3,6,3)==0);
}while(make_a_new_cell(matrix,6,9,6,9,3)==0);
switch(level)
{
case 1:
actual_thing_from_matrix(matrix,7);
break;
case 2:
actual_thing_from_matrix(matrix,5);
break;
case 3:
actual_thing_from_matrix(matrix,3);
break;
default:
printf("\n you entered wrong choice(%d) ",level);
getc(stdin);
exit(0);
}
}
|
_________________ say what you wanna say do what you wanna do coz those who matter do not mind and those who mind do not matter
Last edited by nikhilpurwant on Fri Dec 02, 2005 6:35 pm; edited 7 times in total |
|