/*
 * Solve a sudoku-derivative puzzle.  All the rules of sudoku apply,
 *  but overlaid onto the grid are nine "thermometers", four-connected
 *  strings of cells which must be all in either increasing or
 *  decreasing order.
 *
 * This program addresses this by, conceptually, considering all 9!
 *  possible permutations for each row, column, and 3x3 box.  Those
 *  permutations that don't match the thermometers are tossed out.
 *  Then, repeatedly, each row, column, and box (collectively, "set")
 *  is overlaid with all the other sets that overlap it and those
 *  permutations that don't have at least one compatible permutation in
 *  the other set are tossed out.
 *
 * The 27 sets are:
 *	0..8: the rows, each row left to right, 0 topmost.
 *	9..17: the columns, each column top to bottom, 9 leftmost.
 *	18..26: the boxes, in reading order, each in reading order.
 */

#include <stdio.h>
#include <strings.h>

#define NPERMS (9*8*7*6*5*4*3*2*1)

static unsigned char perms[NPERMS][9];
static unsigned int permlists[27][NPERMS+1];

static void gen_perms(void)
{
 int px;
 unsigned char p[9];

 void gen(unsigned int avail, unsigned char *pp)
  { int i;
    if (avail == 0)
     { bcopy(&p[0],&perms[px][0],9);
       px ++;
       return;
     }
    for (i=9-1;i>=0;i--)
     { if ((avail >> i) & 1)
	{ *pp = i;
	  gen(avail&~(1<<i),pp+1);
	}
     }
  }

 px = 0;
 gen(0x1ff,&p[0]);
 if (px != NPERMS) abort();
}

static void filter_perms(unsigned int *list, int (*test)(int))
{
 int i;
 int n;

 n = *list++;
 for (i=n-1;i>=0;i--)
  { if (! (*test)(list[i]))
     { n --;
       if (i != n) list[i] = list[n];
     }
  }
 list[-1] = n;
}

static int inorder(const unsigned char *p, int n)
{
 int i;

 if (n < 2) abort();
 if (p[0] > p[1])
  { for (i=n-1;i>=2;i--)
     { if (p[i-1] < p[i]) return(0);
     }
  }
 else
  { for (i=n-1;i>=2;i--)
     { if (p[i-1] > p[i]) return(0);
     }
  }
 return(1);
}

static int test_row_0(int px)
{
 if (! inorder(&perms[px][2],3)) return(0);
 return(1);
}

static int test_row_3(int px)
{
 if (! inorder(&perms[px][2],5)) return(0);
 return(1);
}

static int test_row_5(int px)
{
 if (! inorder(&perms[px][5],3)) return(0);
 return(1);
}

static int test_row_6(int px)
{
 if (! inorder(&perms[px][2],3)) return(0);
 return(1);
}

static int test_row_7(int px)
{
 if (! inorder(&perms[px][1],3)) return(0);
 return(1);
}

static int test_row_8(int px)
{
 if (p[8] != 5) return(0);
 return(1);
}

static int test_col_1(int px)
{
 if (! inorder(&perms[px][4],4)) return(0);
 return(1);
}

static void init_lists(void)
{
 int i;

 permlists[0][0] = NPERMS;
 for (i=NPERMS-1;i>=0;i--) permlists[0][i+1] = i;
 for (i=27-1;i>0;i--) bcopy(&permlists[0],&permlists[i],sizeof(permlists[0]));
 filter_perms(&permlists[0][0],&test_row_0);
 filter_perms(&permlists[3][0],&test_row_3);
 filter_perms(&permlists[5][0],&test_row_5);
 filter_perms(&permlists[6][0],&test_row_6);
 filter_perms(&permlists[7][0],&test_row_7);
 filter_perms(&permlists[8][0],&test_row_8);
 filter_perms(&permlists[10][0],&test_col_1);
}

int main(void);
int main(void)
{
 gen_perms();
 init_lists();
 return(0);
}