/* $Header$

computes basic "rule" application to a sudoku position
*/

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

/* Uses global variables.  Bad style... I know, but the
   goal here it to do the job in as little code as possible,
   not to be re-usable or re-entrant. */

typedef struct { int col,row,val; } sudokuCell;
typedef struct { int val[9], nVal; } sudokuState;
sudokuState pos[9][9];  /* current known position */
sudokuCell reduceList[81]; /* list of cells to be reduced across board */
int nReduced, nReduce;
int nGiven;
int nByElimination;
int nByDeduction;

void initPosition()
{
  int i,j,k;
  nReduced = nReduce = 0;
  for (i=0; i < 9; i++)
    {
      for (j=0; j < 9; j++)
        {
	  for (k=0; k < 9; k++)
	    {
	      pos[i][j].val[k]=k+1;
	    }
	  pos[i][j].nVal=9;
	}
    }
  nGiven = nByElimination = nByDeduction = 0;
}

void parsePosLine(char *buf, int row, sudokuState *p)
{
  int i;
  char *bp;

  bp = buf;
  for (i=0; i<9; i++)
    {
      while (isspace(*bp)) bp++;
      if ((*bp >= '1') && (*bp <= '9'))
	{
	  p[i].val[0] = (int)(*bp - '0');
	  p[i].nVal = 1;
	  reduceList[nReduce].row = row;
	  reduceList[nReduce].col = i;
	  reduceList[nReduce++].val = p[i].val[0];
	  nGiven++;
	}
      bp++;
    }
}

void loadPosition(char *fNam)
{
  FILE *f = stdin;
  int i;

  initPosition();

  if (strcmp(fNam,"-") != 0)
    {
      f = fopen(fNam,"r");
      if (f == NULL)
	{
	  fprintf(stderr,"Could not read %s.\n",fNam);
	  exit(2);
	}
    }

  for (i=0;i<9;)
    {
      char buf[128];

      if (fgets(buf,sizeof(buf),f) == NULL)
	{
	  fprintf(stderr,"Premature end of input\n");
	  exit(2);
	}
      if (strlen(buf) <= 8)
	continue;
      parsePosLine(buf,i,pos[i]);
      i++;
    }

  if ( f!=stdin)
    fclose(f);
}

#include <unistd.h>

void printPosition(FILE *f)
{
  int i;

  if (f == stderr)
    {
      usleep(250000);
      fputs("\033[H\n",stderr); /* cursor home */
#if 0
      puts("\033[2J"); /* clear screen */
      fprintf(f,"%c",(char)12); /* clear screen, i think */
#endif
    }

  for (i=0; i < 9; i++)
    {
      int j;
      for (j=0; j<9; j++)
	{
	  if (pos[i][j].nVal > 1) fprintf(f,".");
	  else fprintf(f,"%d",pos[i][j].val[0]);
	  if (j%3 == 2) fprintf(f," ");
	}

      if (f == stderr)
	{ /* print choices left */
	  fprintf(f," \t ");
	  for (j=0; j<9; j++)
	    {
	      int k;
	      k = pos[i][j].nVal;
	      if (k <= 1)
		fprintf(f,"+");
	      else
		fprintf(f,"%d",k);
	      if (j%3 == 2) fprintf(f," ");
	    }
	}
      if (i%3 == 2) fprintf(f,"\n\n");
      else fprintf(f,"\n");
    }
#if 0  /* not needed since I'm not positioing cursor w/ esc codes */
  if (f == stderr)
    { /* clear junk */
      printBlankLine(5);
      fprintf(f,"\033[6A"); /* move up 5 lines */
    }
#endif
  fflush(f);
}

/* Add newly found KNOWN value to list for reduction */
void reduceListPush(row,col,val)
{
  /* new known cell.  schedule reduction */

  fprintf(stderr,"\033[14;1H");  /* move to desired position, VT100 */
  fprintf(stderr,"%d,%d must be %d\r",row+1,col+1,val);fflush(stderr);

  reduceList[nReduce].row=row;
  reduceList[nReduce].col=col;
  reduceList[nReduce++].val=val;
  pos[row][col].val[0] = val;
  pos[row][col].nVal = 1;
}

void printStats()
{
  fprintf(stderr,"\033[16;1H");  /* move to desired position, VT100 */
  fprintf(stderr,"%d Given, %d by Elimination, %d by Deduction.     ",
	  nGiven, nByElimination, nByDeduction);fflush(stderr);
}

void removeVal(int row, int col, int val)
{
  int i;
  sudokuState *p;

  p = &pos[row][col];
  if (p->nVal <= 1)
    return;  /* already known */
  for (i=0; i< p->nVal; i++)
    {
      if (p->val[i] == val)
	{
	  for(p->nVal--; i < p->nVal; i++)
	    p->val[i] = p->val[i+1];
	}
    }
  if (p->nVal > 1)
    return;

  /* new known cell.  schedule reduction */
  nByElimination++;
  reduceListPush(row,col,p->val[0]);
  printStats();
}

/* apply the 3 rules, make sure this value does not appear
   again in this cell, or this row, or this col */
void reduce(int col, int row, int val)
{
  int i,loCol,hiCol,loRow,hiRow;

  for (i=0; i<9; i++)
    {
      removeVal(row,i,val);
      removeVal(i,col,val);
    }

  loCol = (col/3)*3;
  hiCol = loCol + 2;
  loRow = (row/3)*3;
  hiRow = loRow+2;
  for (i=loRow; i <= hiRow; i++)
    {
      int j;
      for (j=loCol; j <= hiCol; j++)
	{
	  removeVal(i,j,val);
	}
    }

}

/* For known cells, make sure that value does not
   appear in that cells row, column, or group */
void enforceRules()
{
  while ((nReduce < 81) && (nReduced < nReduce))
    {
      sudokuCell *cell;
      cell = reduceList + nReduced;
      reduce(cell->col, cell->row, cell->val);
      nReduced++;

      fprintf(stderr,"\033[15;1H");  /* move to desired position, VT100 */
      /*fprintf(stderr,"\033<v><h>") VT52 mode */
      fprintf(stderr,"%d/%d reduced.     \r",nReduced,nReduce);fflush(stderr);
      printPosition(stderr);
    }
}

int indexAllowing(int val, sudokuState *s[])
{
  int i;
  for (i=0; i < 9; i++)
    {
      int j;
      for (j=0; j < s[i]->nVal; j++)
	{
	  if (s[i]->val[j] == val)
	    return(i);
	}
    }
  return(-1);  /* should NEVER happen! */     
}

/* return index (and value) for cell which is the ONLY choice
   for the returned value.
   return negative if there is no such choice */
int findUniqueOption(sudokuState *s[], int *outVal)
{
  int nChoices[9],i;
  for (i=0; i < 9; i++) nChoices[i] = 0;

  for (i=0; i < 9; i++)
    {
      if (s[i]->nVal == 1)
	{
	  nChoices[s[i]->val[0]] = -99;
	}
      else
	{
	  int j;
	  for (j=0; j < s[i]->nVal; j++)
	    nChoices[s[i]->val[j]]++;
	}
    }

  for (i=0; i < 9; i++)
    {
      if (nChoices[i] == 1)
	{
	  *outVal = i;
	  return(indexAllowing(i,s));
	}
    }
  return(-1);
}

/* if there are any unique options in this row,col, or neigh,
   set that value and re-evaluate rules */
void enforceUniqueOptions(int row[9], int col[9], sudokuState *loc[9])
{
  int j,val;
  while ((j = findUniqueOption(loc,&val)) >= 0)
    {
      nByDeduction++;
      reduceListPush(row[j],col[j],val);
      printStats();
      enforceRules();
    }
}

/* For any row, col, or group, check for situations
   where only 1 position is able to take on a given value.
   When this is the case, set that position. */
void findUniqueOptions()
{
  int row[9],col[9],i;
  sudokuState *loc[9];

  /* check rows */
  for (i=0; i < 9; i++)
    {
      int j;
      for (j=0; j < 9; j++)
	{
	  row[j] = i;
	  col[j] = j;
	  loc[j] = &(pos[i][j]);
	}
      enforceUniqueOptions(row,col,loc);
    }

  /* check column */
  for (i=0; i < 9; i++)
    {
      int j;
      for (j=0; j < 9; j++)
	{
	  row[j] = j;
	  col[j] = i;
	  loc[j] = &(pos[j][i]);
	}
      enforceUniqueOptions(row,col,loc);
    }

  /* check neighborhood */
  for (i=0; i < 9; i++)
    {
      int j;
      for (j=0; j < 9; j++)
	{
	  row[j] = (i/3)*3 + j/3;
	  col[j] = (i%3)*3 + j%3;
	  loc[j] = &(pos[row[j]][col[j]]);
	}
      enforceUniqueOptions(row,col,loc);
    }
}

int main(int argc, char *argv[])
{
  if (argc != 2)
    {
      fprintf(stderr,"Usage : %s <SudokuPosition.txt|->\n\n",argv[0]);
      return(1);
    }

  fputs("\033[2J",stderr); /* clear screen */
  loadPosition(argv[1]);
  printPosition(stderr);

  enforceRules();
  while(nReduce < 81)
    findUniqueOptions();

  fprintf(stderr,"========================= Done.\n\n\n\n\n\n");
  printPosition(stdout);
  return(0);
}

/****
$Log$
*/