/*
 *    sudoku00.c   -  sudoku puzzle experiments
 * 
 *  Sudoku puzzles consist of a 9x9 array of numbers 1-9, with the puzzle
 *  area also viewed as a 3x3 array of 3x3 arrays of numbers 1-9,
 *  such that:
 *   
 *    1) Each digit 1-9 appears exactly once in each row
 *    2) Each digit 1-9 appears exactly once in each column
 *    3) Each digit 1-9 appears exactly once in each 3x3 box.
 * 
 *  Here we adopt the notation that the rows are numbered 0 to 8 from top
 *  to bottom, columns are numbered 0 to 8 from left to right, and 3x3
 *  boxes are number 0-2 across the top, 3-5 across the middle, and
 *  6-8 across the bottom of the puzzle.
 *    
 *
 *----------------------------------------------------------------------
 *  01/04/2006  Initial Version
 *  01/11/2006  This version uses single bit flags to indicate whether
 *              or not a particular is excluded as a candidate for each
 *              unknown puzzle position.
 *  01/14/2006  This version packages the algorithm 1, 2, and 3 solution
 *              attempts as a function.
 *  01/16/2006  Ready for preliminary publication. This version quickly
 *              (and surprisingly!) converges to the solution of all of
 *              the few samples I have on hand at this time, but the
 *              trial and error algorithm is VERY simple so the program
 *              WILL fail on some puzzles that lack a unique solution,
 *              and probably on others as well.
 *  01/17/2006  Fixed calls to the set_digit_in_xxx() functions; before
 *              this change, the "only place to put a ..." messages did
 *              not appear in the output.
 *----------------------------------------------------------------------
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define DIGIT_1_MASK 0x100

/*
 * Two dimensional array elements are stored by row,
 * and accessed like this: ARRAY[row][col].
 */

/*
 * The space characters in toe following are ignored. 
 */
char sample_puzzle[9][29] =
{   
   " -  -  4  -  -  -  9  -  - ",
   " -  7  6  1  -  -  -  -  - ", 
   " -  -  -  -  7  -  1  2  - ", 
   " 9  -  8  4  -  -  -  -  - ", 
   " 3  6  -  -  1  -  -  -  - ",  
   " 5  -  -  -  -  7  -  3  8 ", 
   " -  -  -  3  -  -  -  7  9 ", 
   " 6  8  -  -  -  1  -  -  2 ", 
   " -  -  -  -  5  -  6  -  1 "
};

/*
 * The following union 'u' is the main puzzle storage. Each position is
 * either a digit (1,9) or a '-' indicating empty.
 */
union {
   char p[9][9];
   char plinear[81];
} u,u2;

/*
 * The following array simplifies dealing with the 3x3 boxes. Here we
 * denote upper left hand box 'box 0', the one to the right of it 'box 1',
 * the one under it 'box 3' and so forth.
 */ 

/*
 * The linear indexes into the puzzle for each of the nine positions
 * in each of the nine 3x3 boxes.
 */
unsigned char lix[9][9] = {
   {  0 ,1  ,2   ,9 ,10 ,11 ,18 ,19 ,20 }  
  ,{  3 ,4  ,5  ,12 ,13 ,14 ,21 ,22 ,23 }                         
  ,{  6 ,7  ,8  ,15 ,16 ,17 ,24 ,25 ,26 }                          
  ,{ 27 ,28 ,29 ,36 ,37 ,38 ,45 ,46 ,47 }                      
  ,{ 30 ,31 ,32 ,39 ,40 ,41 ,48 ,49 ,50 }                      
  ,{ 33 ,34 ,35 ,42 ,43 ,44 ,51 ,52 ,53 }                      
  ,{ 54 ,55 ,56 ,63 ,64 ,65 ,72 ,73 ,74 }                      
  ,{ 57 ,58 ,59 ,66 ,67 ,68 ,75 ,76 ,77 }                      
  ,{ 60 ,61 ,62 ,69 ,70 ,71 ,78 ,79 ,80 }
};

void print_puzzle(void)
{
   int c,i,j;
   
   for (i=0;i<9;i++) {
      for (j=0;j<9;j++) {
         c = u.p[i][j];
         if ((c < '0') || (c > '9')) c = '-';
         printf (" %c ",c);
      }
      printf ("\n");
   }
} /* end of print_puzzle() */

typedef struct unk_struct {
   unsigned char col;
   unsigned char row;
   unsigned char box;
   unsigned char candidate_cnt;
   unsigned char candidates[10];
   unsigned short excluded;
   struct unk_struct *prev;
   struct unk_struct *next;
} unk_type;
int unk_count ,unk_count2;
unk_type unk_array[9][9] ,unk_array2[9][9];
unk_type *unk ,*unk2;
unk_type *unk_head ,*unk_head2;
unk_type *unk_tail ,*unk_tail2;

void unlink_unk(void)
{
   if (unk_count == 1) {
      unk_head = NULL;
      unk_tail = NULL;
   }
   else if (unk == unk_head) {
      unk_head = unk->next;
      unk_head->prev = NULL;
   }
   else if (unk == unk_tail) {
      unk_tail = unk->prev;
      unk_tail->next = NULL;
   }
   else {
      (unk->prev)->next = unk->next;
      (unk->next)->prev = unk->prev;
   }
   unk_count--;
} /* end of unlink_unk()  */

void update_excluded(char digit ,unk_type *unk)
{
      int d,i,n,row,col,box;
   
      d = digit - '1';
      row = unk->row;
      col = unk->col;
      box = unk->box;
      n = DIGIT_1_MASK >> d;
/*    printf("row %d, col %d, box %d, mask 0x%03x\n", row, col, box, n); */
      for (i=0;i<9;i++) {
         unk_array[row][i].excluded |= n;
         unk_array[i][col].excluded |= n;
         (&unk_array[0][0]+lix[box][i])->excluded |= n;
      }
} /* end of update_excluded */

void set_digit_in_row(int d, int row, int quiet)
{
   int i,digit;
   digit = d + '1';
   /* Assume that the position to be set WILL be found */
   for (unk=unk_head;;unk=unk->next) {
      if (unk->row != row) continue;
      for (i=0;i<unk->candidate_cnt;i++) {
         if (unk->candidates[i] == digit) {
            if (!quiet)
               printf ("[%d,%d] = %c (only place to put a '%c' in row %d)\n",
                       row, unk->col, digit, digit ,row);
            u.p[row][unk->col] = digit;
            update_excluded(digit ,unk);
            unlink_unk();
            return;
         }
      }
   }
} /* end of set_digit_in_row() */

void set_digit_in_col(int d, int col, int quiet)
{
   int i,digit;
   digit = d + '1';
   /* Assume that the position to be set WILL be found */
   for (unk=unk_head;;unk=unk->next) {
      if (unk->col != col) continue;
      for (i=0;i<unk->candidate_cnt;i++) {
         if (unk->candidates[i] == digit) {
            if (!quiet)
               printf ("[%d,%d] = %c (only place to put a '%c' in col %d)\n",
                       unk->row, col, digit, digit ,col);
            u.p[unk->row][col] = digit;
            update_excluded(digit ,unk);
            unlink_unk();
            return;
         }
      }
   }
} /* end of set_digit_in_col() */

void set_digit_in_box(int d, int box, int quiet)
{
   int i,digit;
   digit = d + '1';
   /* Assume that the position to be set WILL be found */
   for (unk=unk_head;;unk=unk->next) {
      if (unk->box != box) continue;
      for (i=0;i<unk->candidate_cnt;i++) {
         if (unk->candidates[i] == digit) {
            if (!quiet)
               printf ("[%d,%d] = %c (only place to put a '%c' in box %d)\n",
                       unk->row, unk->col, digit, digit ,box);
            u.p[unk->row][unk->col] = digit;
            update_excluded(digit ,unk);
            unlink_unk();
            return;
         }
      }
   }
} /* end of set_digit_in_box() */

int total_candidates;

/* In the following, the first index is for digit (1,2, ... 9) */
unsigned char row_candidate_cnt[9][9];
unsigned char col_candidate_cnt[9][9];
unsigned char box_candidate_cnt[9][9];

/*
 * In the following, the indices are box, digit, (box_row or box_col).
 * Box_rows are numbered 0-2 within the box, box_columns likewise.
 */
unsigned char box_digit_row_cnt[9][9][3];
unsigned char box_digit_col_cnt[9][9][3];

int algorithm123 (int quiet)
/* returns 0  if all positions are filled
*          1  normal completion with not all positions filled
*          2  if an impossible case was encountered.
*/
{
   int i,j,k,m,n;
   int c,col,r,row,box;
   int box_row,box_col;
   int d,digit;
   
   /*
    * Build a candidate list for each of the unknown positions,
    * and count up the candidates by (digit and row), (digit and col),
    * and (digit and 3x3 box).
    */
   iterate:
   if (unk_count == 0) return 0;   
   total_candidates = 0;
   memset ((void *)row_candidate_cnt, 0, 81);
   memset ((void *)col_candidate_cnt, 0, 81);
   memset ((void *)box_candidate_cnt, 0, 81);
   unk = unk_head;
   for (k=0;k<unk_count;k++) {
      unk->candidate_cnt = 0;
      memset(unk->candidates,0,10);
      col = unk->col;
      row = unk->row;
      box = unk->box;     
      /* check the digits in order */
      for (d=0;d<9;d++) {
         digit = '1' + d;
         if (unk->excluded & (DIGIT_1_MASK >> d)) continue;
         unk->candidates[unk->candidate_cnt++] = digit;
         total_candidates++;

         /* Update the canditate by row, column, and 3x3 box tallies. */
         row_candidate_cnt[d][row]++;
         col_candidate_cnt[d][col]++;
         box_candidate_cnt[d][box]++;
         
      }
      /* all done checking this position */
#if 0      
      if (!quiet) {
         printf ("[%d,%d] has %d candidates: "
                 ,unk->row,unk->col,unk->candidate_cnt);
         for (n=0;n<unk->candidate_cnt;n++) printf("%c",unk->candidates[n]);
         printf("\n");
      }
      
#endif
      /* If we have only one candidate, use it! */
      if (unk->candidate_cnt == 1) {
         /* fill in the solution to this position */
         u.p[row][col] = unk->candidates[0];
         update_excluded(unk->candidates[0],unk);
         /* remove this unknown from the unknown list */
         unlink_unk();
         if (!quiet) {
            printf ("[%d,%d] = %c (only digit possible for [%d,%d])\n",
                    row ,col ,unk->candidates[0] ,row ,col);
         }
         
         goto iterate;
      }
      if (unk->candidate_cnt == 0) return 2;
      unk = unk->next;
   }
#if 0   
   printf("Found %d total candidates\n" ,total_candidates);
#endif
   
   /*
    * Here we have determined all the candidates for all the unknown
    * positions, but no position has exactly one candidate.
    */
#if 0
   printf("-- candidates --\n");
   printf("       123456789\n");
   
   n = 0;
   for (i=0;i<9;i++) {
      printf("row %d: ",i);
      for (j=0;j<9;j++) {
         m = row_candidate_cnt[j][i];
         printf("%d",m);
         n += m;
      }
      printf("\n");
   }
   
   n = 0;
   for (i=0;i<9;i++) {
      printf("col %d: ",i);
      for (j=0;j<9;j++) {
         m = col_candidate_cnt[j][i];
         printf("%d",m);
         n += m;
      }
      printf("\n");
   }
   
   n = 0;
   for (i=0;i<9;i++) {
      printf("box %d: ",i);
      for (j=0;j<9;j++) {
         m = box_candidate_cnt[j][i];
         printf("%d",m);
         n += m;
      }
      printf("\n");
   }
#endif

   /*
    *  At this point we have already filled all the positions that we could
    *  using the simple rule that each row, column, and 3x3 box can have only
    *  one digit from (1,2,3,4,5,6,7,8,9).
    * 
    *  Now we use the rule that if any given row, column, or 3x3 box has
    *  only one candidate for a particular digit, then that candidate must
    *  be correct digit for the associated position.
    */
   for (i=0;i<9;i++) {  /* digits */
      for (j=0;j<9;j++) {
         if (row_candidate_cnt[i][j] == 1) {
            set_digit_in_row(i,j,quiet);
            goto iterate;
         }
         if (col_candidate_cnt[i][j] == 1) {
            set_digit_in_col(i,j,quiet);
            goto iterate;
         }
         if (box_candidate_cnt[i][j] == 1) {
            set_digit_in_box(i,j,quiet);
            goto iterate;
         }
      }
   }
  
   /*
    * Here we try algorithm three, which is this: if within any box,
    * the candidates for any particular digit are all within one row
    * or column, then mark all the positions in the same row or column
    * but outside the box in question as excluded for that digit;
    * then repeat algorithms one and two.
    */
   memset ((void *) box_digit_row_cnt, 0, sizeof(box_digit_row_cnt));
   memset ((void *) box_digit_col_cnt, 0, sizeof(box_digit_col_cnt));
   unk = unk_head;
   for (i=0;i<unk_count;i++) {
      box = unk->box;
      box_row = unk->row % 3; 
      box_col = unk->col % 3;
      for (j=0;j<unk->candidate_cnt;j++) {
         d = unk->candidates[j] - '1';
         box_digit_row_cnt[box][d][box_row]++;
         box_digit_col_cnt[box][d][box_col]++;
      }
      unk = unk->next;
   }
   
   /*  Just print out the totals we just accumulated. */
   for (i=0;i<9;i++) {
      for (j=0;j<3;j++) {
#if 0         
         printf("[box %d][row %d]: ",i,j);
         for (d=0;d<9;d++) {
            printf("%d",box_digit_row_cnt[i][d][j]);
         }
         printf("  [box %d][col %d]: ",i,j);
         for (d=0;d<9;d++) {
            printf("%d",box_digit_col_cnt[i][d][j]);
         }
         printf("\n");
#endif         
      }
   }
   
   /*
    *  Now we look for occurances of the algorithm three situation
    */
   for (d=0;d<9;d++) {  /* all the digits */
      for (i=0;i<9;i++) {  /* all the boxes */
         m = n = 0;
         for (k=0;k<3;k++) {  /* all the rows/columns */
            if (box_digit_row_cnt[i][d][k] > 0) {
               m++;
               r = k;
            }
            if (box_digit_col_cnt[i][d][k] > 0) {
               n++;
               c = k;
            }
         }
         if (m == 0) continue; /* this digit not possible in this box */
         if (m == 1) {         /* all the candidates are in a single row */
            row = r + 3 * (i / 3);   /* puzzle row */
            /*
             * But if there are no more candidates in the corresponding
             * puzzle row, algorithm three is not applicable.
             */
            if (row_candidate_cnt[d][row] == n) continue;
            /*
             * Set any applicable excluded bits
             */
            m = DIGIT_1_MASK >> d;  
            unk = unk_head;
            for (j=0;j<unk_count;j++) {
               if ((unk->box != i) &&
                   (unk->row == row) &&
                   (!(unk->excluded & m))) {
                  printf("excluding %c from [%d,%d] (needed for box %d)\n"
                         ,'1'+ d ,row ,unk->col ,i);
                  unk->excluded |= m;
               }
               unk = unk->next;
            }
            goto iterate;
         }
         else if (n == 1) { /* all canditates are in a single column */
            c += 3 * (i % 3);   /* convert box_col to puzzle col */
            /*
             * But if there are no more candidates in the corresponding
             * puzzle row, algorithm three is not applicable.
             */
            if (col_candidate_cnt[d][c] == m) continue;
            /*
             * Set any applicable excluded bits
             */
            m = DIGIT_1_MASK >> d;  
            unk = unk_head;
            for (j=0;j<unk_count;j++) {
               if ((unk->box != i) &&
                   (unk->col == c) &&
                   (!(unk->excluded & m))) {
                  printf("excluding %c from [%d,%d] (needed for box %d)\n"
                         ,'1'+ d ,unk->row ,c ,i);
                  unk->excluded |= m;
               }
               unk = unk->next;
            }
            goto iterate;
         }
      }
   }
   return 1;
} /* end of algorithm123() */

FILE *infile;

int main (int argc, char *argv[])
{
   int i,j,k,n;
   int c,col,row,box;
   int d,digit;
   char inbuff[81];
   char *cp;
   
   /* read a possible input file */
   if (argc < 2) {
      printf("Using sample puzzle ...\n");
      for (row=0;row<9;row++) { 
         cp = sample_puzzle[row];
         col = 0;
         while (col < 9) {
            c = *cp++;
            if (c == ' ') continue;
            u.p[row][col++] = c;
         }
      }
      goto data_ready;
   }
   
   printf("Loading puzzle from '%s' ...\n",argv[1]); 
   infile = fopen(argv[1] ,"r");
   if (infile == NULL) goto bad_data;
   row = 0;
   while (row < 9) { 
      if (fgets(inbuff, 80, infile) == NULL) goto bad_data;
      /*
       *  We use '-' characters to represent empty puzzle positions,
       *  and we ignore space characters. Lines beginning with ';'
       *  are entirely ignored.
       */
      if (inbuff[0] == ';') continue;
       cp = inbuff;
       col = 0;
       while (col < 9) {
          c = *cp++;
          if (c == ' ') continue;
          if (index(".-1234567879",c) == NULL) goto bad_data;
          if (index("123456789",c) == NULL) c = '-';
           u.p[row][col++] = c;
      }
      row++;
   }
   
   data_ready:   
   print_puzzle();
   
   /* build a list of unknown puzzle positions */
   unk_count = 0;
   unk_head = NULL;
   unk_tail = NULL;
   memset((void *)unk_array,0,sizeof(unk_array));
   for (i=0;i<9;i++) {     /* row */
      for (j=0;j<9;j++) {  /* col */
         c = u.p[i][j];
         if ((c < '0') || (c > '9')) {
            unk=&unk_array[i][j];
            if (unk_count == 0) {
               unk_head = unk;
               unk_tail = unk;
            }
            else {
               unk_tail->next = unk;
               unk->prev = unk_tail;
            }
            unk->col  = j;
            unk->row  = i;
            unk->box  = j/3 + 3*(i/3); 
            unk->next = NULL;
            unk_tail  = unk;
            unk_count++;
/*          printf ("unknown: [%d,%d]\n",i,j); */
         }
      }
   }
   
   if (unk_count == 0) {
      printf ("All puzzle positions are filled!\n");
      exit (0);
   }
   printf ("There are %d unknown positions to start.\n", unk_count);

   /*
    * Build the initial excluded candidate mask for the unknown positions
    */
   unk = unk_head;
   for (k=0;k<unk_count;k++) {
      row = unk->row;
      col = unk->col;
      box = unk->box;
      n = DIGIT_1_MASK;
      for (d=0;d<9;d++) {
         digit = '1' + d;
         for (i=0;i<9;i++)
            if (    (u.p[row][i] == digit)
                 || (u.p[i][col] == digit)
                 || (u.plinear[lix[box][i]] == digit))
               unk->excluded |= n; 
         n >>= 1;           
      }
      unk = unk->next;
   }
   
   n = algorithm123(0);
   if (n == 0) goto solved;
   if (n == 2) goto bad_solution;
   printf ("Starting trial and error processing with this configuration:\n");
   print_puzzle();
   
   /*
    *  Here, the first three algorithms failed to solve the puzzle, so we
    *  are going to resort to trial and error. The basic idea is to 
    *  try all the candidates we have one at a time and:
    *     
    *    a) If algorighm123() completes the puzzle, we're done.
    *    b) If algorighm123() yields an impossible situation, mark
    *       that candidate as excluded and try again.
    *    c) Otherwise, just continue on with the next candidate.
    * 
    *  We use a saved copy of the puzzle state variables, eg, 'u2.p[][]',
    *  to set the starting conditions for algorighm123() each time,
    *  then we insert the candidate we are going to test into the working
    *  copy of the state variables, eg, 'u.p[][]'. When we exclude some
    *  candidate because it yields an impossible situation, we set the
    *  excluded bit in the _saved_ state variables.
    */
   memcpy((void *)u2.p, (void *)u.p, sizeof(u.p));
   memcpy((void *)unk_array2 ,(void *)unk_array ,sizeof(unk_array));
   unk_head2 = unk_head;
   unk_tail2 = unk_tail;
   unk_count2 = unk_count;
   unk2 = &unk_array2[0][0] + (unk_head - &unk_array[0][0]);
   for (i=0;i<unk_count2;i++) {
      col = unk2->col;
      row = unk2->row;
      for (j=0;j<unk2->candidate_cnt;j++) {
         memcpy((void *)u.p, (void *)u2.p, sizeof(u.p));
         memcpy((void *)unk_array ,(void *)unk_array2 ,sizeof(unk_array));
         unk_head = unk_head2;
         unk_tail = unk_tail2;
         unk_count = unk_count2;
         digit = unk2->candidates[j];
         printf("Trying [%d][%d] = %c ...\n"
                ,row ,col ,digit);
         u.p[row][col] = digit;
         unk = &unk_array[row][col];
         update_excluded(digit ,unk);
         unlink_unk();
         if (unk_count == 0) goto solved;                      
         n = algorithm123(1);
#if 0         
         printf("... trying [%d][%d] = %c produced result %d\n"
                ,row ,col ,digit ,n);
#endif
         if (n == 0) {
            /*
             * Backup and run n = algorithm123() again, this time with the
             * quiet flags set to false, so we get display the method for
             * each position that was filled.
             */
            memcpy((void *)u.p, (void *)u2.p, sizeof(u.p));
            memcpy((void *)unk_array ,(void *)unk_array2 ,sizeof(unk_array));
            unk_head = unk_head2;
            unk_tail = unk_tail2;
            unk_count = unk_count2;
            digit = unk2->candidates[j];
            u.p[row][col] = digit;
            unk = &unk_array[row][col];
            update_excluded(digit ,unk);
            unlink_unk();
            n = algorithm123(0);
            goto solved;
         }
         
         if (n == 2) {
            /*
             * We got into an impossible situation with this candidate,
             * so mark this candidate as impossible.
             */
            printf("... excluding %c from [%d,%d]: creates impossibility\n"
                    ,digit ,unk2->row ,unk2->col);
            unk2->excluded |= DIGIT_1_MASK >> (digit - '1');
         }
      }
      unk2 = unk2->next;
   }
   
   if (unk_count > 0) {
      /* We're hung. Dump the current candidate list. */
      printf ("Giving up. There are still %d unknown positions.\n", unk_count);
      n = 0;
      unk = unk_head;
      for (i=0;i<unk_count;i++) {
         n += unk->candidate_cnt;
         printf ("[%d,%d] candidates: ", unk->row, unk->col);
         for (j=0;j<unk->candidate_cnt;j++) printf ("%c", unk->candidates[j]);
         printf ("\n");
         unk = unk->next;
      }
      printf ("There are still %d candidates.\n", n);
   }
   
   solved:
   print_puzzle();
   exit(0);
   
   bad_solution:
   printf("Internal error - impossible situation.\n");
   exit(2);
          
   bad_data:
   printf("datafile error.\n");
   exit(1);
   
}  /* end of main() */