Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

program for sudoku puzzle generator and solver

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
nikhilpurwant

Joined: 15 Nov 2005
Posts: 1
:

Items
PostPosted: Tue Nov 15, 2005 5:26 pm    Post subject: program for sudoku puzzle generator and solver Reply with quote

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
Back to top
View user's profile Send private message Send e-mail
dom

Joined: 10 Nov 2005
Posts: 42
:

Items
PostPosted: Wed Nov 16, 2005 12:54 pm    Post subject: Reply with quote

Any chance you could edit your post, highlight the sourcecode and click the Code button in the edit window? It's difficult to read when all the tabs are removed...

[EDIT]Cheers Mate![/EDIT]
_________________
Orangeminds Sudoku
http://www.orangeminds.com/sudoku/
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron