/*
 * CSE 303, Autumn 2006, Assignment 3, Problem 1
 *
 * You must modify this program as described in the assignment.
 */ 

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>

/*
 * Recursively solve the given Soduku puzzle by guessing 
 * values for the current cell and continuing on to guess 
 * remaining cells. Return true when the puzzle is solved. 
 *
 * The first call to this function 
 * should be for row=0 and col=0.  The function will
 * proceed through each column in a row before moving
 * to the next row. If col>8, then wrap around to the 
 * next row. If row>8 (after wraping to the next row)
 * the then assume that the puzzle has been solved and
 * return true.
 *
 * A value of zero in a cell means that a choice has not 
 * yet been made for that cell.
 *
 */
bool solve(int puzzle[][9], int row, int col) {
  // Handle wrap-around of arguments
  if (col > 8) {
    col = 0;
    row = row + 1;
  }
  if (row > 8)
    return true;


  // If this cell has already been set, go to next
  if (puzzle[row][col] != 0) {
      return solve(puzzle,row,col+1);
  }

  // Find a number that is not present in this row/column
  // and attemt to solve the puzzle with that choice
  int guess, i;
  for (guess=1; guess<=9; guess++) {

    // Check to see if this guess is valid
    bool found = false;
    for (i=0; i<9; i++) {
      // Does this guess appear anywhere else in this row?
      if (puzzle[row][i] == guess) {
	found = true;
	break;
      }
      // Does this guess appear anywhere else in this column?
      if (puzzle[i][col] == guess) {
	found = true;
	break;
      }
      // Does this guess appear anywhere else in this 3x3 box?
      int boxRow = (row/3)*3;
      int boxCol = (col/3)*3;
      if (puzzle[boxRow+(i/3)][boxCol+(i%3)] == guess) {
	found = true;
	break;
      }
    }

    // Put this guess in the puzzle and attempt to solve the rest
    if (found) {
      continue;
    } else {
      puzzle[row][col] = guess;
      if (solve(puzzle,row,col+1))
	return true;
      else 
	continue;
    }
  }

  // If we get here, then we can't solve. Give up.
  puzzle[row][col] = 0;
  return false;
}


int main(int argc, char *argv[]) {

  int puzzle[9][9];    // The puzzle data structure
  int i;               // Iteration variable
  

  // Read in the puzzle
  for (i=0; i<9; i++) {
    
    if (i%3 == 0)
      scanf("-------------------------\n");
    
    int matches = scanf("| %d %d %d | %d %d %d | %d %d %d |\n",
			&puzzle[i][0], &puzzle[i][1], &puzzle[i][2], 
			&puzzle[i][3], &puzzle[i][4], &puzzle[i][5], 
			&puzzle[i][6], &puzzle[i][7], &puzzle[i][8]);
    
    if (matches != 9) {
      fprintf(stderr, "%s: input not in expected format\n",argv[0]);
      return 1;
    }
  }

  // Solve the puzzle
  solve(puzzle,0,0);
  
  // Print a message with today's time
  time_t  today = time(NULL);
  char message[] = "Soduku: XXX XXX XX XX:XX:XX XXXX";
  memcpy(message+8, ctime(&today), 24);
  puts(message);
  
  // Read in the puzzle
  for (i=0; i<9; i++) {
    if (i%3 == 0)
      printf("-------------------------\n");
    printf("| %d %d %d | %d %d %d | %d %d %d |\n",
	   puzzle[i][0], puzzle[i][1], puzzle[i][2], 
	   puzzle[i][3], puzzle[i][4], puzzle[i][5], 
	   puzzle[i][6], puzzle[i][7], puzzle[i][8]);    
  }
  printf("-------------------------\n");
  
  return 0;
}