#include "sudoku.h"

//-------------------------------------------------------------------------------------------------
// Start here to work on your MP7
//-------------------------------------------------------------------------------------------------
// Partners : slee528, jseo35, taehyun4
// This week's MP is about making a sudoku using a 2-D array functions.
// Each cell contains a number from 1 to 9 and each number can only be appeared only once.
// We used the pseudocode of a typical backtracking algorithm to solve for sudoku puzzle.
// Each function represents specific tasks for successfully using backtracking to solve for parse_sudoku
// and row, col, 3x3, is valid, solve functions present specific areas that programs should implement.

// You are free to declare any private functions if needed.

// Function: is_val_in_row
// Return true if "val" already existed in ith row of array sudoku.
int is_val_in_row(const int val, const int i, const int sudoku[9][9]) {

  assert(i>=0 && i<9);
  int a=0;
  int count=0;
  for(a=0; a<9;a++){
   if(sudoku[i][a]==val)
     count++;
  }
  if (count > 0)
    return 1;
  else
    return 0;
  // END TODO
}

// Function: is_val_in_col
// Return true if "val" already existed in jth column of array sudoku.
int is_val_in_col(const int val, const int j, const int sudoku[9][9]) {

  assert(j>=0 && j<9);
  int a=0;
  int count=0;
  for(a=0; a<9;a++){
   if(sudoku[a][j]==val)
     count++;
  }
  if (count > 0)
    return 1;
  else
    return 0;
  // END TODO
}

// Function: is_val_in_3x3_zone
// Return true if val already existed in the 3x3 zone corresponding to (i, j)
int is_val_in_3x3_zone(const int val, const int i, const int j, const int sudoku[9][9]) {

  assert(i>=0 && i<9);
  int a, b, c, d;
  a = i - i%3;
  b = j - j%3;
  for (c = 0; c< 3; c++){
	  for (d = 0; d< 3; d++){
		  if (sudoku[a+c][b+d] == val)
			  return 1;
    }
  }
  return 0;
  // END TODO
}

// Function: is_val_valid
// Return true if the val is can be filled in the given entry.
int is_val_valid(const int val, const int i, const int j, const int sudoku[9][9]) {

  assert(i>=0 && i<9 && j>=0 && j<9);

  if(!is_val_in_3x3_zone(val, i, j, sudoku) && !is_val_in_col(val, j, sudoku) && !is_val_in_row(val, i, sudoku))
        return 1;

  else
    return 0;
  // END TODO
}

int is_full(int sudoku[9][9])
{
  int a,b;
  for(a=0;a<9;a++)
  {
    for(b=0;b<9;b++)
    {
      if(sudoku[a][b]==0)
      return(0);
    }
  }
  return(1);
}

// Procedure: solve_sudoku
// Solve the given sudoku instance.
int solve_sudoku(int sudoku[9][9]) {

  int a, b, i, j;
  for (a = 0; a<9; a++){
	  for(b = 0; b<9; b++){
		  if (sudoku[a][b] == 0){
           printf("a:%d b:%d\n",a,b);
           i = a;
           j = b;
		  }
    }
  }
  if(is_full(sudoku))
  return(1);

  int num;
  for (num = 1; num <= 9; num++){
	  if (is_val_valid(num, i, j, sudoku)){	//check if number is valid for this cell(i,j)
		  sudoku[i][j] = num;
	    if (solve_sudoku(sudoku)){ //recursive call, solve remaining cells.
		    return 1;
      }
      sudoku[i][j] = 0;
    }
  }
  return 0;
}

// Procedure: print_sudoku
void print_sudoku(int sudoku[9][9])
{
  int i, j;
  for(i=0; i<9; i++) {
    for(j=0; j<9; j++) {
      printf("%2d", sudoku[i][j]);
    }
    printf("\n");
  }
}

// Procedure: parse_sudoku
void parse_sudoku(const char fpath[], int sudoku[9][9]) {
  FILE *reader = fopen(fpath, "r");
  assert(reader != NULL);
  int i, j;
  for(i=0; i<9; i++) {
    for(j=0; j<9; j++) {
      fscanf(reader, "%d", &sudoku[i][j]);
    }
  }
  fclose(reader);
}