#include <stdlib.h>
#include <time.h>
#include <iostream>
#include "generator.h"

using namespace std;


/*Prints the grid with white spaces for unassigned cells and double-line
* delimitations for regions
*/
void print(){
     for ( int i=0; i<SIZE; i++ ){

         if ( i == 0 )
           cout<<"======================================="<<endl;        
        
        for( int j=0; j<SIZE; j++ ){
             if ( j==0 )
                cout<<"|| ";
            
             if ( grid[i][j].value != 0 ){
                  cout<<grid[i][j].value<<" |";
             }
             else{
                  cout<<"  |";
             }  
            
             if( j==SIZE-1 )
                 cout<<"|"<<endl;
             else
                 cout<<" ";
        }
        
        if ( (i+1)%3 == 0 )
           cout<<"======================================="<<endl;    
        else
            cout<<"---------------------------------------"<<endl;
     }
}


/* Checks whether the grid is correctly solved or not */
bool check(){
    
     /*For current row/column/region keep an array with the assigned values
       Examples: tempv[2] is 1 if value "3" was assigned to the current column
                 temps[3] is 0 if value "4" was not assigned to the current region */            
     int temph[SIZE] = {0};
     int tempv[SIZE] = {0};
     int temps[SIZE] = {0};
    
     for ( int i =0; i<SIZE; i++ ){
         for ( int j=0; j<SIZE; j++ ){
            
             //If cell has no value assigned yet
             if ( grid[i][j].value == 0 )
                return false;
            
             /* Check if all cells in a row have a value assigned*/
             if ( temph[grid[i][j].value - 1] != 0 )
                 return false;
             else
                 temph[grid[i][j].value - 1] = 1;
                
             if ( grid[j][i].value == 0 )
                return false;
            
             /* Check if all cells in a column have a value assigned*/
             if ( tempv[grid[j][i].value - 1] != 0 )
                 return false;
             else
                 tempv[grid[j][i].value - 1] = 1;
                                  
             if ( grid[(i/3)*3+j/3][(j%3)+3*(i%3)].value == 0 )
                return false;
                

             /* Check if all cells in a region have a value assigned*/
             if ( temps[grid[(i/3)*3+j/3][(j%3)+3*(i%3)].value - 1] != 0 )
                 return false;
             else
                 temps[grid[(i/3)*3+j/3][(j%3)+3*(i%3)].value - 1] = 1;
         }
        
         //Next row/column/region : reset arrays
         for ( int k=0; k<SIZE; k++ ){
             temph[k] = 0;
             tempv[k] = 0;
             temps[k] = 0;
         }
     }
    
     return true;
}


void solve(){

}

int main(int argc, char* argv[]){
    
    if ( argc < 2 ){
         cout<<"Usage : <executable_name> <guess_values_number>"<<endl;
         return -1;
    }

    /* Initialize random generator */
    /* If you just want a pseudo-random distr. for debugging purposes you may comment this line out */
    srand( time(NULL) );
    
    /* Initialize the grid structures */
    init();
    
    /* Generate solution */
    generator();
    
    /* Hide numbers from the solution to generate initial grid */
    hide(atoi(argv[1]));
    
    cout<<endl;
    
    cout<<"Initial grid : "<<endl<<endl;
    
    /* Print the initial grid to be solved */
    print();
    
    cout<<endl;
    
    /* Solve the grid */
    solve();
    
    /* Print the solution if one was found */
    if (check()){
          cout<<"Solved grid : "<<endl<<endl;
          print();
          cout<<endl;
    }

    return 0;
}

#include <stdlib.h>
#include <math.h>
#include "generator.h"

/* Two-dimensional array of cells*/
cell grid[SIZE][SIZE];

/* Initialize all the cells;
* No number assigned, so "value" is "0" for all
* The number of value possibilities is maximum : 9
* Initialize the list of possible values that the cell can take : 1-9
*/
void init(){
     for ( int i=0; i<SIZE; i++ ){
        for( int j=0; j<SIZE; j++ ){
             cell tcell;
             tcell.value = 0;            
             grid[i][j] = tcell;            
        }
     }
}

/* Start with a solution and "hide" a random number "no" of values from the grid */
void hide(int no){
    
     for ( int i=1; i<=no; i++ ){
        
         /* Randomly generate a position in the grid */
         int x = rand()%SIZE;
         int y = rand()%SIZE;
        
         int done = false;
        
         /* If the current cell was already hidden, repeat until we find a visible one */
         while(!done){
             if ( grid[x][y].value != 0 ){
                  done = true;
                  grid[x][y].value = 0;
             }
             else{
                  x = (rand()+x)%SIZE;
                  y = (rand()+y)%SIZE;
             }
          }
        
        
     }
}

/* Randomly generate a list of values 1-9 which we assign to the top-left region */
void generateFirstRegion(){
    
     int temp[SIZE] = {0};
    
     for ( int i=0; i<SIZE; i++ ){
        
         int crt_digit = rand()%SIZE;
        
         while ( temp[crt_digit] != 0 ){
               crt_digit = (crt_digit+rand())%SIZE;
         }
        
         temp[crt_digit] = 1;        
         grid[i/3][i%3].value = crt_digit + 1;
     }
}

/* Generate a region on the right side of a already generated one by rotating the
*  values of rows
*  Example: 1 2 3              4 5 6
            4 5 6    becomes   7 8 9
            7 8 9              1 2 3
*/
void generateHorizontalRegion(int x,int y){    
     for ( int i=0; i<SIZE; i++ ){
         grid[i/3+3*y][i%3+3*x].value = grid[(i/3+x)%3+3*y][i%3].value;
     }    
}

/* Generate a region underneath the top-left one by rotating the values of the columns
*  Example: 1 2 3
            4 5 6
            7 8 9
            
            becomes
            
            2 3 1
            5 6 4
            8 9 7
*/
void generateVerticalRegion(int x){
     for ( int i=0; i<SIZE; i++){
         grid[i/3+3*x][i%3].value = grid[i/3][(i+x)%3].value;
     }
}

/* Generator function; the result is represented by a solution grid */
void generator(){
    
    generateFirstRegion();
    
    generateHorizontalRegion(1,0);
    generateHorizontalRegion(2,0);
        
    generateVerticalRegion(1);
  
    generateHorizontalRegion(1,1);
    generateHorizontalRegion(2,1);
  
    generateVerticalRegion(2);
      
    generateHorizontalRegion(1,2);
    generateHorizontalRegion(2,2);
}

const int SIZE = 9;

/* Structure defining a cell in the grid */
struct cell{
       unsigned short value; //value assigned to this cell (0 if no value assigned)
};

/* declaration  of global variable grid */
extern cell grid[SIZE][SIZE];



/* Initialize all the cells;
* No number assigned, so "value" is "0" for all
* The number of value possibilities is maximum : 9
* Initialize the list of possible values that the cell can take : 1-9
*/
void init();

/* Start with a solution and "hide" a random number "no" of values from the grid */
void hide(int no);


/* Randomly generate a list of values 1-9 which we assign to the top-left region */
void generateFirstRegion();

/* Generate a region on the right side of a already generated one by rotating the
*  values of rows
*  Example: 1 2 3              4 5 6
            4 5 6    becomes   7 8 9
            7 8 9              1 2 3
*/
void generateHorizontalRegion(int x,int y);

/* Generate a region underneath the top-left one by rotating the values of the columns
*  Example: 1 2 3
            4 5 6
            7 8 9
            
            becomes
            
            2 3 1
            5 6 4
            8 9 7
*/
void generateVerticalRegion(int x);

/* Generator function; the result is represented by a solution grid */
void generator();

// returns row number with exactly one missing cell in the row.  Returns -1 if none exist yet.
int FindRowReadyToSolve ();

// returns column number with exactly one missing cell in column.  Returns -1 if none exist yet
int FindColumnReadyToSolve ();

// returns true if there is a box ready to be solved.  row and column are set to upper left corner of box.
// returns false otherwise
bool FindBoxReadyToSolve (int& row, int& column);

// given a row with eight entries, fills in missing entry
void Solve Row (int row);

// given a column with eight entries, fills in missing entry
void SolveColumn (int column);

// given a box with eight entries, fills in missing entry
// row and column are upper left coordinates of box
void SolveBox (int row, int column);

// Traverses columns, rows, and boxes for duplicates.  Returns false if
// illegal entry exists, true otherwise
bool CheckIf Legal ();