/* 
   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

   Note that some of the comments may be invalid, as
   this is only a Beta.
*/

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

#define HEADLINE "C Sudoku Solver"

/*
 * 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 {
      if(!printsudoku(new_sudoku)) {
        attrset(COLOR_PAIR(2));
        mvprintw(LINES-2,2,"Error printing solution");
        endwin();
        exit(1);
      }
      endwin();
      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 {
      if(!printsudoku(new_sudoku)) {
        attrset(COLOR_PAIR(2));
        mvprintw(LINES-2,2,"Error printing solution");
        endwin();
        exit(1);
      }
      endwin();
      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 readinput(int sudoku[9][9]) {
  int x,y,ch,x_axis,y_axis;
  x_axis=5;
  y_axis=5;
  attrset(COLOR_PAIR(2));
  mvprintw(3,2,"Enter a sudoku (use zero for unknown value):");
  move(5,5);
  for(y=0;y<9;y++) {
    for(x=0;x<9;) {
      if(isdigit((char)(ch=getch()))) {
        sudoku[y][x]=ch-48; /* make it an int */
        mvprintw(y_axis,x_axis,"%c",(char)ch);
        x_axis+=2;
        if(x%3==2)
          x_axis+=2;
        if(x==8){
          x_axis=5;
          y_axis++;
        }
        x++;
      }
      else if(isspace(ch));
      else {
        attrset(COLOR_PAIR(2));
        mvprintw(LINES-2,2,"Please write only numbers");
      }
    } /* x foor loop */
    if(y%3==2){
      x_axis=5;
      y_axis++;
    }
  } /* y foor loop */
  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,x_axis,y_axis;
  x_axis=5;
  y_axis=5;
  draw_background();
  attrset(COLOR_PAIR(2));
  mvprintw(3,2,"Here goes the solution:");
  for(y=0;y<9;y++) {
    for(x=0;x<9;x++) {
      mvprintw(y_axis,x_axis,"%i", sudoku[y][x]);
      x_axis+=2;
      if(x%3==2)
        x_axis+=2;
      if(x==8){
        x_axis=5;
        y_axis++;
      }
    } /* x foor loop */
    if(y%3==2){
        x_axis=5;
        y_axis++;
    }
  } /* y foor loop */
  nocbreak();
  mvprintw(LINES-2,2,"Press Enter to continue");
  getch();
  cbreak();
  return(1);
}

/* Print a message about how to use this program */
void helpmsg(void) {
  puts("Just start this tool without any parameters, and you will be guided through the rest.");
  puts("\nPress Enter to continue");
}

int draw_background(){
  int x,y;
  attrset(COLOR_PAIR(1));
  for(x=0;x<COLS;x++)
  {
    for(y=0;y<LINES;y++)
    {
      move(y,x);
      addch(' ');
    }
  }
  attrset(COLOR_PAIR(1));
  mvprintw(1,(COLS-strlen(HEADLINE))/2,HEADLINE);
  return(0);
}

void end_all(int sig){
  endwin();
  exit(sig);
}

int main(int argc, char *argv[]) {
  int sudoku[9][9]={0};
  signal(SIGINT,end_all);
  initscr();
  nonl();
  cbreak();
  noecho();
  keypad(stdscr,FALSE);
  nodelay(stdscr,FALSE);
  if(argc!=1) {
    helpmsg();
    getchar();
    exit(1);
  }
  if(has_colors())
  {
    start_color();
    /* colors are:
        COLOR_BLACK
        COLOR_RED
        COLOR_GREEN
        COLOR_YELLOW
        COLOR_BLUE
        COLOR_MAGENTA
        COLOR_CYAN
        COLOR_WHITE
    */
    init_pair(1, COLOR_RED,     COLOR_WHITE); /* background and headline */
    init_pair(2, COLOR_BLACK,   COLOR_WHITE); /* text */
  }
  else
  {
    printf("Color error\n");
    endwin();
    exit(1);
  }
  draw_background();
  readinput(sudoku);
  attrset(COLOR_PAIR(2));
  mvprintw(3,2,"Calculating");
  if(solve(sudoku,0,0)) {
    attrset(COLOR_PAIR(2));
    mvprintw(LINES-2,2,"%s can not be solved", argv[1]);
    endwin();
    exit(1);
  }
  return(0);
}