#include <stdio.h>
//Super-Duper Sodoku square generator
//Finds every legal solution for every 9x9 square
//Will make billions upon billions of squares
//so hopefully you have stupid amounts of time and disk space!

//Written by Derrick Williams - adw@derrickwilliams.com

//Released to public domain 2006 so have at it.



void build_tree();
unsigned long count=0;

void print_square(int square[9][9]){
     int row,column;
     for(row=0;row<9;row++){
       for(column=0;column<9;column++){
           printf("%d",square[row][column]);
       }
       printf("\n");
     }
   printf("\n");
}


//Support code used to make sure a square was legal when testing 
//generation code. Use this routine if you change code and want to
//see if you're still generating correct squares.
void check_legal(int square[9][9]){

   int used[10];

   int x,y,z;

   //horizontal rows
   for(y=0;y<9;y++){
     for(z=0;z<10;z++){
       used[z]=z;
     }
     for(x=0;x<9;x++){
       if(used[square[y][x]]==0){
         printf("NOT LEGAL! LINE %d\n",x);
         print_square(square);
	 return;
       }else{
         used[square[y][x]]=0;
       }
     }
   }

   //vertical rows
   for(y=0;y<9;y++){
     for(z=0;z<10;z++){
       used[z]=z;
     }
     for(x=0;x<9;x++){
       if(used[square[x][y]]==0){
         printf("NOT LEGAL! LINE %d\n",x);
         print_square(square);
	 return;
       }else{
         used[square[x][y]]=0;
       }
     }
   }
}

//permute the tree
void permute_tree(int square[9][9],int line,int allowable[9][9]){

     int x1,x2,x3,x4,x5,x6,x7,x8,x9;

     for(x1=0;x1<9;x1++){
        if(allowable[0][x1]!=0){
	  for(x2=0;x2<9;x2++){
            if(allowable[1][x2]!=0 && x2!=x1){
	      for(x3=0;x3<9;x3++){
               if(allowable[2][x3]!=0 && x3!=x2 && x3!=x1){
	         for(x4=0;x4<9;x4++){
                  if(allowable[3][x4]!=0 && x4!=x3 && x4!=x2 && x4!=x1){
	            for(x5=0;x5<9;x5++){
                      if(allowable[4][x5]!=0 && x5!=x4 && x5!=x3 && x5!=x2 && x5!=x1){
	                for(x6=0;x6<9;x6++){
                         if(allowable[5][x6]!=0 && x6!=x5 && x6!=x4 && x6!=x3 && x6!=x2 && x6!=x1){
	                   for(x7=0;x7<9;x7++){
                            if(allowable[6][x7]!=0 && x7!=x6 && x7!=x5 && x7!=x4 && x7!=x3 && x7!=x2 && x7!=x1){
	                     for(x8=0;x8<9;x8++){
                              if(allowable[7][x8]!=0 && x8!=x7 && x8!=x6 && x8!=x5 && x8!=x4 && x8!=x3 && x8!=x2 && x8!=x1){
	                       for(x9=0;x9<9;x9++){
                                if(allowable[8][x9]!=0 && x9!=x8 && x9!=x7 && x9!=x6 && x9!=x5 && x9!=x4 && x9!=x3 && x9!=x2 && x9!=x1){

                                   square[line][0]=x1+1;
                                   square[line][1]=x2+1;
                                   square[line][2]=x3+1;
                                   square[line][3]=x4+1;
                                   square[line][4]=x5+1;
                                   square[line][5]=x6+1;
                                   square[line][6]=x7+1;
                                   square[line][7]=x8+1;
                                   square[line][8]=x9+1;
				   build_tree(square,line+1);

				   if(line==8){ 
			          //	Uncomment this line to check 
				  //	if your square is legal if
				  //	you're testing code. 
                                  //    check_legal(square);
				        count++;
			                printf("Puzzle Solution #%d\n",count);
                                        print_square(square);
                                   }

				}
			       }
			      }
			     }
			    }
			   }
			 }
			}
		      }
		    }
		  }
		 }
	       }
	      }
	    }
	  }
	}
     }
}

//build a line on the tree
void build_tree(int square[9][9],int line){

	int row;
	int column;
	int group_row;
	int group_col;
	int group_col_end;
	

	int allowable[9][9]={{1,2,3,4,5,6,7,8,9},
	 		     {1,2,3,4,5,6,7,8,9},
			     {1,2,3,4,5,6,7,8,9},
                             {1,2,3,4,5,6,7,8,9},
			     {1,2,3,4,5,6,7,8,9},
                             {1,2,3,4,5,6,7,8,9},
			     {1,2,3,4,5,6,7,8,9},
			     {1,2,3,4,5,6,7,8,9},
			     {1,2,3,4,5,6,7,8,9}};

	//blank out the existing values from the stream from above
	//and from the group it is in
	if(line>=3){
	  for(row=0;row<line;row++){
	   for(column=0;column<9;column++){
	        allowable[column][square[row][column]-1]=0;
	   }
	  }
	}

	//blank out values from group, if row is not at the top line of a group
	if(line%3!=0){

	   group_row=line/3;
	   for(column=0;column<9;column++){
             for(row=group_row*3;row<line;row++){
		group_col_end=(column/3)*3+3;
	        for(group_col=(column/3)*3;group_col<group_col_end;group_col++){
	          allowable[column][square[row][group_col]-1]=0;
		}
	     }
	   }


	}

	permute_tree(square,line,allowable);

}


main(){

	int x;
	int square[9][9]={{0,0,0,0,0,0,0,0,0},
	 		  {0,0,0,0,0,0,0,0,0},
			  {0,0,0,0,0,0,0,0,0},
                          {0,0,0,0,0,0,0,0,0},
			  {0,0,0,0,0,0,0,0,0},
                          {0,0,0,0,0,0,0,0,0},
			  {0,0,0,0,0,0,0,0,0},
			  {0,0,0,0,0,0,0,0,0},
			  {0,0,0,0,0,0,0,0,0}};

	printf("SODOKU 3000 SQUARE GENERATOR - processing...\n");

	for(x=0;x<9;x++){
		square[0][x]=x+1;
	}	
	
	//initialize the second line

	build_tree(square,1);	

	printf("Finished processing - final count is %d\n",count);
	
}