/* 
   SUDOKU SOLVER test version

   The meaning of this program is to solve suduko's.
   This program is distrubuted under the GNU GPL.
   Written by Bjarke Bondo Andersen
*/

/* For standard functions */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

/*
 * Take a pointer to a sudoku array as input. Also input where in the
 * soduku to start. Return 0 if sudoku is done, else erturn 1.
 */
int solve(int sudoku[9][9], int x_axis, int y_axis) {
  int new_sudoku[9][9]={0};
  int value, done;
  memcpy(new_sudoku,sudoku,324); /* 81 * 4 = 324 */
  value=sudoku[y_axis][x_axis];
  if(value!=0) {
    if(x_axis<8) x_axis++;
    else if(y_axis<8) {
      y_axis++;
      x_axis=0;
    }
    else {
      printf("\nHere goes the solution:\n\n");
      if(!printsudoku(new_sudoku)) {
        fprintf(stderr,"Error printing solution\n");
        exit(1);
      }
      exit(0);
    }
    return(solve(new_sudoku,x_axis,y_axis));
  }
  do { /* first do */
    do { /* second do */
      if(++value>9) return(1);
    } while(checknumber(new_sudoku,x_axis,y_axis,value)); /* second do */
    new_sudoku[y_axis][x_axis]=value;
    if(x_axis<8) x_axis++;
    else if(y_axis<8) {
      y_axis++;
      x_axis=0;
    }
    else {
      printf("\nHere goes the solution:\n\n");
      if(!printsudoku(new_sudoku)) {
        fprintf(stderr,"Error printing solution\n");
        exit(1);
      }
      exit(0);
    }
    if(solve(new_sudoku,x_axis,y_axis)) {
      done=0;
      if(x_axis>0) x_axis--;
      else if(y_axis>0) {
        y_axis--;
        x_axis=7;
      }
      else return(1);
    } /* if solve() */
    else done=1;
  } while(!done); /* first do */
  return(0);
}

/* Return 1 if number_to_check is found on row, on line or in cube. Else return 0 */
int checknumber(int sudoku[9][9], int x_cordinat, int y_cordinat, int number_to_check) {
  int x,y;
  /* check if number_to_check exists on x_cordinat */
  for(x=x_cordinat,y=0;y<8;y++) {
    if(sudoku[y][x]==number_to_check) {
      return(1);
    }

  }
  /* check if number_to_check exists on y_cordinat */
  for(x=0,y=y_cordinat;x<8;x++) {
    if(sudoku[y][x]==number_to_check) {
      return(1);
    }

  }
  /* check if number exists in cube */
  x=x_cordinat-x_cordinat%3;
  y=y_cordinat-y_cordinat%3;
  while(y<y_cordinat-y_cordinat%3+3) {
    while(x<x_cordinat-x_cordinat%3+3) {
      if(sudoku[y][x]==number_to_check) return(1);
      x++;
    } /* x while loop */
    y++;
    x=x_cordinat-x_cordinat%3;
  } /* y while loop */
  return(0);
}

/* 
   The meaning of this function is to read the sudoku input file
   into the sudoku 2D array with -1 meaning unknown. 
   It returns 1 on succes or 0 on failure. Failure could be fault 
   by errors in input file or by no file found.
*/
int readinputfile(int sudoku[9][9], char *input_file_name) {
  int x,y,ch;
  FILE *stream;
  if((stream=fopen(input_file_name,"r"))==NULL) {
    fprintf(stderr,"Error reading \"%s\" into buffer\n",input_file_name);
    exit(1);
  }
  for(y=0;y<9;y++) {
    for(x=0;x<9;) {
      if(isdigit((char)(ch=fgetc(stream)))) {
	sudoku[y][x]=ch-48; /* make it an int */
        x++;
      }
      else if(isspace(ch));
      else if(ch==EOF) {
        fprintf(stderr,"\"%s\" ends too early\n",input_file_name);
        exit(1);
      }
      else
        fprintf(stderr,"Don't understand \"%c\" in \"%s\", skipping\n",(char)ch,input_file_name);
    } /* x foor loop */
  } /* y foor loop */
  fclose(stream);
  return(1);
}

/*
   Print the contens of the sudoku 2D array and return 1 if no errors
   occured.
*/
int printsudoku(int sudoku[9][9]) {
  int x,y;
  putchar('\n');
  for(y=0;y<9;y++) {
    for(x=0;x<9;x++) {
      printf("%i", sudoku[y][x]);
      putchar(' ');
      if(x%3==2)
        printf("  ");
      if(x==8)
        putchar('\n');
    } /* x foor loop */
    if(y%3==2)
      putchar('\n');
  } /* y foor loop */
  return(1);
}

/* Print a message about how to use this program */
void helpmsg(void) {
  puts("As the first and only argument, give the path to a file contaning\n\
the sudoku that you want to solve. What's inside the file can look\n\
like this (but only the number of digits matters):\n\n\
008 020 100\n\
702 093 506\n\
000 806 234\n\
\n\
001 000 859\n\
600 084 300\n\
500 000 062\n\
\n\
050 200 013\n\
000 001 905\n\
016 000 000\n\nHere, zero means \"unknown\".");
}

/* 
   Take a filename as only argument. The file must be plain ASCII, 
   consisting of only numbers, with 0 (zero) meaning "don't 
   know what's here". An example could be like this:
   ====================> Starting here
008 020 100
702 093 506
000 806 234

001 000 859
600 084 300
500 000 062

050 200 013
000 001 905
016 000 000
   ====================> Ending here
*/
int main(int argc, char *argv[]) {
  int sudoku[9][9]={0};
  if(argc!=2) {
    helpmsg();
    exit(1);
  }
  if(!readinputfile(sudoku,argv[1])) {
    fprintf(stderr,"Error loading \"%s\"\n", argv[1]);
    exit(1);
  }

  if(solve(sudoku,0,0)) {
    printf("%s can not be solved\n", argv[1]);
    exit(1);
  }

  /* The solution is now stored in sudoku */

  printf("Here goes the solution:\n");
  if(!printsudoku(sudoku)) {
    fprintf(stderr,"Error printing solution\n");
    exit(1);
  }
  return(0);
}