#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdarg.h>
#include "sudoku.h"

char *dirs[] = {"down", "across", "square"};

/**********************************************************
 * When I first saw this puzzle I thought a program to solve it would
 * be pretty nice. I like the data structures used here.
 *
 * PUZZLE INTRODUCTION
 *
 * The sudoku puzzle is a 9x9 array of cells filled with the integers
 * 1-9, subject to the condition that each row, column, and major 3x3
 * subarray contains each number exactly once. A puzzle will give a
 * starting condition of several squares already filled in, and it is
 * up to the solver (or the program) to fill in the rest. See
 * www.sudoku.com.
 *
 * After solving a couple manually I realized the important thing to
 * keep track of is which digits are still possible in each
 * cell. Cells are linked together in 3 chains. This way going through
 * a row, column, or square is identical programatically. References
 * are used to represent a cell and a direction, and are linked into a
 * sorted list of cells that potentially can provide information to
 * approach the solution.
 *
 * The program loops through first logically using all the information
 * given to reduce the number of possibilities. If that is not
 * sufficient to solve the puzzle it will start guessing and looking
 * for the results of the guess. This is done recursively, and it
 * should find a solution for any puzzle that is possible.
 *
 * This has been generalized to work for arrays of 4x4, 9x9, 16x16,
 * and 25x25. The limitation is a bit mask that keeps track of the
 * remaining possibilities, so N^2 must be less than 32: n = 2, 3, 4,
 * 5.
 *
 * compile: * gcc -o sudoku sudoku.c
 *
 * compile for debug: 
 *		gcc -g -o sudoku sudoku.c sudoku_debug.c
 *
 * call: 
 * 		sudoku [-2 | -3 | -4 | -5] [-t[0|1|2|3|4]] [-g] [-d[0-9]]
 * where:
 *  -N: does an NxN puzzle (n = 2, 3, 4, 5)
 *	-t[X] uses sample puzzle X (uses 0 if no X). 
 *	-g: prints out a table of possibilities before guessing
 *	-d0...9: controls amount of output, 0 = minimal, 9 = debug

 * -lN: N is a parameter used to decide how much effort to put in on
 * deducing a solution before starting to guess. The accompanying file
 * 5x5.txt shows how it works for "puzzles" that require a lot of
 * guessing. In most cases a small value will work fine.
 *
 * copyright russell young June 2005
 * sudoku@young-0.com
 **********************************************************/
int solve(struct state *state);

#define REPORT(X_level, ...) {if (customize & (X_level)) printf(__VA_ARGS__);}
static unsigned int customize = 0;
int root = 3;
int check_limit = 6;
static int total_guesses = 0;

// test puzzles come from http://www.puzzle.jp

// test data invoked by -t switch. 

// This is a special case I found on the web. It has a couple of
// twists, one of which is using hex notation, which I had to hack
// in. To run this, use the following switches: -t -4 -h
char *testdata4[][16] = {
  {"...928.....3AB41",
   "4..1F.C5.......9",
   "..FAE69..4.D7205",
   "..6371..20......",
   "...63C2......1..",
   ".7.D.........0FA",
   "1.A.....E.2B35D.",
   "948..7A...3F....",
   "..2819F45.C..3B.",
   ".A...37E62.9....",
   "......86B...9...",
   ".9BC02.A18FE....",
   "85...4D.9..0.C..",
   "A........6..F...",
   "..7...B...A.0.6.",
   ".....0.F47......"
  }
};

char *testdata[][9] = {
  {".6.a.4...",		// test 0, removed a number so it needs to guess to solve
   "..83.56..",
   "2.......1",
   "8..4.7..6",
   "..6...3..",
   "7..9.1..4",
   "5.......2",
   "..72.69..",
   ".4.5.8.7."
  },
  {"2..67....",		// test 1
   "..6...2.1",
   "4.....8..",
   "5....93..",
   ".3.....5.",
   "..28....7",
   "..1.....4",
   "7.8...6..",
   "....53..8"
  },
  {".7..1..9.",		// test 2
   "9..8....7",
   "..3.....6",
   ".4...15..",
   ".3.....1.",
   "..27...6.",
   "5.....6..",
   "6....5..2",
   ".8..2..7."
  },
  {"6.....54.",		// test 3
   ".3..27...",
   ".....9...",
   ".......53",
   "..4...8..",
   "26.......",
   "...8.....",
   "...46..7.",
   ".59.....2"
  },
  {".........",		// test 4
   "..783....",
   "..5..264.",
   "..26...7.",
   ".4.....8.",
   ".6...32..",
   ".284..5..",
   "....961..",
   "........."}
};

/////////////////////////////////////////////
//
// PRINTING AND DEBUGGING FUNCTIONS
//
/////////////////////////////////////////////

//
// print out the completed solution
//

// translate from bits to display value
//
// this works for any bit value to from bit 0 to bit 25 (a to z)
// DEF is a default value to return if the mask is wrong.
// This assumes only one bit is set, if more than one the result is undefined
char getValue(unsigned int mask, char def) {
  unsigned int m;
  int i, base = 0;
  char ret = 0;
  if (!mask || (mask & 0xfc000000)) {	// if 0 or > bit 25 signal some problem 
	return (def) ? def : '.';
  }
  for (i = 16; i; i /= 2) {
	if (m = mask >> i) {
	  ret += i;
	  mask = m;
	}
  }
  if (customize & A_ALPHA) {
	return ret + 'a';
  }
  if (customize & A_HEX) {
	return (ret > 9) ? ret + 'a' - 10 : ret + '0';
  }
  return ret + '1';
}

// count the number of bits set in a given mask
int bitsSet(unsigned int mask) {
  static const char bits[] = {0, 1, 1, 2, 1, 2, 2, 3, 
							  1, 2, 2, 3, 2, 3, 3, 4};
  int i = 0;
  while (mask) {
	i += bits[mask & 0xf];
	mask >>= 4;
  }
  return i;
}

void printCircuitCounts(struct state *state) {
  int i;
  char out1[200], out2[200];
  char *p1 = out1, *p2 = out2;
  int total = 0;
  for (i = 0; i < CHECK_LIMIT; i++) {
	p1 += sprintf(p1, "%10d", i + 1);
	p2 += sprintf(p2, "%10d", state->circuits[i]);
	total += state->circuits[i];
  }
  printf("Looked at %d candidates, found %d circuits\n", state->tries, total);
  printf("Circuits: %s\n", out1);
  printf("          %s\n", out2);
}

// build a string of length LEN consisting of the character FILLER
// (isn't there a library function for this?)
void rowOf(char *str, int len, char filler) {
  while (len--) {
	*str++ = filler;
  }
  *str = 0;
}

// Print out the solution 
void printSolution(struct state *state) {
  int i, y;
  char *p = null, out[100];
  char separator[100];

  rowOf(separator, 2*SIZE + 2, '-');
  separator[2*SIZE + 1] = '\n';
  REPORT(A_PRINTENTRIES, "Entering printSolution\n");
  for (p = out, y = 0; y < SIZE*SIZE; y += SIZE, p = out) {
	for (i = y; i < y + SIZE; i++) {
	  *p++ = (i % ROOT) ? ' ' : '|';
	  *p++ = getValue(state->cells[i].mask, 0);
	}
	*p = 0;
	printf("%s%s|\n", (y%(ROOT*SIZE)) ? "" : separator, out);
  }
  printf(separator);
}

//
// partial solution/debugging printout
//
// This prints out inside each cell the values that are still possible.
// To make it fit the values are printed in an NxN array. This makes the 
// printing tricky. The structure is:
// 		loop over the lines in the puzzle
//			For each line, loop over the sublines (that is, for 9x9, "123", "456", "789")
//				for each subline loop over the cells in the line
//					loop over the values in the subline ([1, 2, 3], [4, 5, 6], or [7, 8, 9])

void printPossibilities(struct state *state) {
  int y, i, j, k;
  unsigned int m, m0, mask;
  char *p = null, out[200];
  char sepSmall[200], sepBig[200];
  struct cell *cell = null;

  REPORT(A_PRINTENTRIES, "Entering printPossibilities\n");
  i = SIZE*(ROOT + 3) + ROOT + 2;
  rowOf(sepBig, i + 1, '=');
  rowOf(sepSmall, i + 1, '-');
  sepBig[i] = '\n';
  sepSmall[i] = '\n';

  for (y = 0; y < SIZE*SIZE; y += SIZE) {			// row of cells
	printf((y % (SIZE*ROOT)) ? sepSmall : sepBig);
	for (m0 = 1, j = 0; j < SIZE; j += ROOT, m0 <<= ROOT) {	// one line
	  p = out;
	  for (i = y; i < y + SIZE; i++) {
		*p++ = '|';
		if (!(i % ROOT)) {
		  *p++ = '|';
		}
		*p++ = ' ';
		cell = state->cells + i;
		for (m = m0, k = 0; k < ROOT; k++, m <<= 1) {
		  *p++ = getValue(cell->mask & m, ' ');
		}
		*p++ = ' ';
	  }
	  *p++ = 0;
	  printf("%s||\n", out);
	}
  }
  printf(sepBig);
}

/////////////////////////
//
// support/initialization functions:
//
/////////////////////////

// MEMORY FUNCTIONS

// frees memory allocated by the MAKESTATE call. It behaves well for
// null or partially allocated structures.
void freeState(struct state *state) {
  REPORT(A_PRINTENTRIES, "Entering freeState\n");
  if (state) {
	if (state->cells) {
	  free(state->cells);
	}
	if (state->refs) {
	  free(state->refs);
	}
	if (state->circuits) {
	  free(state->circuits);
	}
	free(state);
  }
}

// This sets up a state structure in memory. The return value is an
// initialized structure, which can be built in separate ways
// depending on the arguments.
// 
// If the first argument is null MAKESTATE allocates the memory for a
// new state structure. Otherwise it reinitializes the one it is
// passed.
//
// If the second argument is null MAKESTATE initializes the state
// structure for a new puzzle. Otherwise it deep-copies the original
// structure to the new one.
//
struct state *makeState(struct state *new, struct state *orig) {
  int c;
  void *hold[3];
  struct cell *cell = null;
  struct ref *ref = null;
  int *circuits;
  void *cells, *refs;
  REPORT(A_PRINTENTRIES, "Entering makeState with %s previous state to %s\n", (new) ? "existing" : "no", (orig) ? "copy" : "initialize");
  if (!new) {		// if no address is passed then allocate the structures
	if (!(new = malloc(sizeof(struct state)))
		|| !(new->cells = calloc(sizeof(struct cell), SIZE*SIZE))
		|| !(new->circuits = calloc(sizeof(int), CHECK_LIMIT))
		|| !(new->refs = calloc(sizeof(struct ref), 3*SIZE*SIZE))) {
	  freeState(new);
	return null;
	}
  }
  if (orig) {		// if a source state is passed it copy it to the result
	hold[0] = new->refs;
	hold[1] = new->cells;
	hold[2] = new->circuits;
	memcpy(new, orig, sizeof(struct state));
	new->refs = (struct ref *)hold[0];
	new->cells = (struct cell *)hold[1];
	new->circuits = (int *)hold[2];
	memcpy(new->circuits, orig->circuits, CHECK_LIMIT*sizeof(int));
	memcpy(new->cells, orig->cells, SIZE*SIZE*sizeof(struct cell));
	memcpy(new->refs, orig->refs, 3*SIZE*SIZE*sizeof(struct ref));
  }
  // otherwise initialize the state for a new puzzle This means
  // initializing the state struct, cell array, and ref array
  else {
	new->list = -1;
	memset(new->circuits, 0, CHECK_LIMIT*sizeof(int));
	new->tries = new->guesses = new->listMaxDepth = new->listDepth = new->solved = 0;
	for (cell = new->cells, ref = new->refs, c = 0; c < SIZE*SIZE; cell++, c++) {
	  cell->mask = M_ALL;
	  cell->count = SIZE;
	  cell->refs = 3*c;

	  ref->cell = c;
	  ref->dir = D_VERT;
	  ref->prev = ref->next = -2;
	  ref++->level = SIZE;

	  ref->cell = c;
	  ref->dir = D_HORIZ;
	  ref->prev = ref->next = -2;
	  ref++->level = SIZE;

	  ref->cell = c;
	  ref->dir = D_SQUARE;
	  ref->prev = ref->next = -2;
	  ref++->level = SIZE;
	}
  }
  return new;
}

// removes a reference from the list of possibilities. If it is not on
// the list then do nothing.
void dequeueRef(struct state *state, int r) {
  struct ref *ref = state->refs + r;
  if (ref->next != -2) {	// if not on the list then don't bother
	state->listDepth--;
	if (ref->prev == -1) {	// prev == -1 means ref is at top of list
	  state->list = ref->next;
	}
	else {					// else in the middle somewhere
	  state->refs[ref->prev].next = ref->next;
	}
	if (ref->next != -1) {	// next == -1 means ref is at the end of the list
	  state->refs[ref->next].prev = ref->prev;
	}
	ref->prev = ref->next = -2;	// -2 means it is off the list
  }
}

// dequeues the 3 references to a given cell
void dequeue(struct state *state, int c) {
  int r = state->cells[c].refs;
  dequeueRef(state, r++);
  dequeueRef(state, r++);
  dequeueRef(state, r++);
}

// puts a given reference on the list of possibilities. The list is
// sorted from low to high, so the reference needs to look along until
// it finds an entry with higher level. The ref is removed from the
// list first if it is already on it, and if the level is over
// CHECK_LIMIT it is not put on.
void enqueueRef(struct state *state, int r) {
  struct ref *ref = state->refs + r;
  int i;
  int prev = ref->prev, level = ref->level;
  dequeueRef(state, r);
  if (level > CHECK_LIMIT) {
	return;
  }
  for (i = (prev >= 0) ? state->refs[prev].next : state->list; 
	   (i >= 0) && (state->refs[i].level < level); 
	   i = state->refs[i].next) {
	prev = i;
  }
  ref->prev = prev;
  ref->next = i;
  if (prev >= 0) {
	state->refs[prev].next = r;
  }
  else {
	state->list = r;
  }
  if (i >= 0) {
	state->refs[i].prev = r;
  }
  state->listDepth += 1;
  if (state->listDepth > state->listMaxDepth) {
	state->listMaxDepth = state->listDepth;
  }
}

// enqueues the 3 references associated with a cell.
void enqueue(struct state *state, int c) {
  struct ref *r0, *r1, *r2;
  struct cell *cell = state->cells + c;
  int r = cell->refs;
  int count = cell->count;
  int prev, ptr;
  dequeue(state, c);	// checks if necessary

  if (cell->count > CHECK_LIMIT) {
	return;
  }
  r0 = state->refs + r;
  r1 = r0 + 1;
  r2 = r0 + 2;
  r1->prev = r;
  r2->prev = r0->next = r + 1;
  r1->next = r + 2;
  r0->level = r1->level = r2->level = cell->count;

  for (prev = -1, ptr = state->list; (ptr >= 0) && (state->refs[ptr].level < count); ptr = state->refs[ptr].next) {
	prev = ptr;
  }
  r2->next = ptr;
  r0->prev = prev;
  if (prev == -1) {
	state->list = r;
  }
  else {
	state->refs[prev].next = r;
  }
  if (ptr != -1) {
	state->refs[ptr].prev = r + 2;
  }
  state->listDepth += 3;
  if (state->listDepth > state->listMaxDepth) {
	state->listMaxDepth = state->listDepth;
  }
}

// Gets the next cell in any direction: across, down, within a square.
int next(int c, int dir) {
  int ret;
  switch (dir) {
  case D_HORIZ:	return ((c + 1) % SIZE) ? c + 1 : c - SIZE + 1;
  case D_VERT:  return (c < SIZE*(SIZE - 1)) ? c + SIZE : c % SIZE;
  case D_SQUARE: 
	if ((c + 1)%ROOT) {
	  return c + 1;
	}
	return (c % (ROOT*SIZE) >= ROOT*SIZE - SIZE) ? c - (ROOT - 1)*SIZE - ROOT  + 1 : c + SIZE - ROOT + 1;
  default: 
	printf("BAD DIRECTION CODE %d\n", dir);
  }
}

////////////////////////////////////////////
//
// Higher level solving functions
//
////////////////////////////////////////////

// Given a mask, clears those bits from cells in a row/column/square
int clearMask(struct state *state, unsigned int mask) {
  int r = state->list;
  unsigned int oldmask;
  struct cell *cell = null;
  int i, c;
  int ccount = 0, mcount = 0;			// use this to check for contradictions
  int dir = state->refs[r].dir;
  c = state->refs[r].cell;
  REPORT(A_PRINTENTRIES | A_PRINTCLEARING, "  Clearing mask 0x%x from cell %d %s\n", mask, c, dirs[dir]);
  for (i = 0; i < SIZE; i++, c = next(c, dir)) {
	cell = state->cells + c;
	// 3 possibilities: the cell's bits all fall within the mask, all
	// fall outside the mask, or some are inside and some outside. If
	// all inside it is part of the cycle that formed this mask; if
	// all outside this mask has no affect on it; if inside and
	// outside the mask bits are cleared and the cell's refs are put
	// onto the list of possibilities.
	if (cell->mask & mask) {	// bits are set in the determined mask
	  if (cell->mask & ~mask) {	// and other bits are set too
		ccount++;
		oldmask = cell->mask;
		cell->mask &= ~mask;
		cell->count = bitsSet(cell->mask);
		if (cell->count == 1) {
		  state->solved += 1;
		  REPORT(A_PRINTFOUNDCELL, "    Found value for cell %d is %c, old mask 0x%x\n", c, getValue(cell->mask, 0), oldmask);
		  if (customize & A_GRIDONFOUND) {
			printPossibilities(state);
		  }
		}
		else {
		  REPORT(A_PRINTCLEARING, "    Cleared bit(s) for cell %d, mask was 0x%x, is 0x%x\n", c, oldmask, cell->mask);
		}
		enqueue(state, c);		// requeue all refs
	  }
	  else {	// no outside bits set, it is one of the selected cells
				// remove only this reference
		dequeueRef(state, cell->refs + dir);
		mcount++;
	  }
	}
  }

  i = bitsSet(mask);
  if (ccount) {
	state->circuits[i - 1]++;
  }
  REPORT(A_PRINTFOUNDCYCLE, "Found a cycle of %d, mask 0x%x, %s from cell %d\n", i, mask, dirs[dir], c);
  // if this is not equal then there are too many cells for the bits
  // set, which implies a contradiction in the initial state
  return (mcount == i);
}

// This is the main solving function. It finds a set of X cells whose
// mask takes up X bits. In this case those X bits can be cleared for
// all the other cells in the row/column/square. For instance, if X is
// 1 then a single cell fulfills it, and the row and the column and
// the square can all have that digit cleared. For 2, if cell 2 is 3
// or 4 and cell 3 is 3 or 4 also, then no other cells in that row can
// have 3 or 4 (but columns can and squares can).
//
// This does not mean that there must be a cell with X bits set. For
// instance, if cell 11 is 1 or 2, cell 12 is 2 or 3, cell 13 is 3 or
// 4, and cell 15 is 4 or 1, the cells in the row from 9 to 17 not in
// the above list (9, 10, 14, 16, 17) cannot be 1, 2, 3, or 4.
unsigned int findCircuit(struct state *state, int c, int dir, int bits, unsigned int mask, int soFar, int remaining) {
  struct cell *cell = null;
  unsigned int m1;
  REPORT(A_PRINTENTRIES | A_PRINTCHECKREF, "Entering findCircuit with cell %d, dir %s, mask 0x%x, %d bits, %d so far and %d remaining\n", c, dirs[dir], mask, bits, soFar, remaining);
  while ((bits > soFar) && (remaining > bits - soFar)) {
	cell = &state->cells[c];
	m1 = mask | cell->mask;
	remaining--;
	if ((bitsSet(m1) <= bits) && (m1 = findCircuit(state, next(c, dir), dir, bits, m1, soFar + 1, remaining))) {
	  return m1;
	}
	c = next(c, dir);
  }
  return (bits == soFar) ? mask : 0;
}

// only call with nonempty list
// return 0 on error
int deduce(struct state *state) {
  struct ref *ref = &state->refs[state->list];
  unsigned int mask = state->cells[ref->cell].mask;
  int ret = 1;
  REPORT(A_PRINTENTRIES, "Entering deduce\n");
  if (mask = findCircuit(state, state->refs[state->list].cell, ref->dir, ref->level, mask, 0, SIZE)) {
	ret = clearMask(state, mask);
  }
  else {
	// bump up the level. The level starts out as CELL->COUNT, but is
	// inc'ed every time it fails to be in a cycle. When it gets over
	// CHECK_LIMIT the ENQUEUE drops it from the queue.
	(ref->level)++;
	enqueueRef(state, state->list);
  }
  return ret;
}

// Tries guessing results if there are no more deductions to be
// made. It copies the state and works in the copy, so if a guess does
// not work out it can change the guess and try again.
//
// If a guess is correct (provides a complete solution) the old state
// structure is freed and the copy used for the guess is returned
// instead. Otherwise it returns NULL to signal failure.
//
// This calls SOLVE, and so can be called recursively.
int guess(struct state *state) {
  struct state *guess = null;
  struct cell *cell = null;
  int c, min, i;
  unsigned int m, mask;

  REPORT(A_PRINTENTRIES, "Entering GUESS\n");
  if (customize & A_GRIDONGUESS) {
	printPossibilities(state);
  }
  // This may not be optimal. To find the best cell to guess in I look
  // for one with the minimal number of possibilities. This limits the
  // number of guesses that must be tried before realizing a puzzle is
  // impossible, but in an impossible puzzle may deepen the required
  // nesting of guesses, which could be worse. It might be better to
  // look for an incomplete row, column, or square with the minimum
  // number of unsolved cells
  for (min = 100, cell = state->cells, i = 0; (i < SIZE*SIZE) && (min > 2); i++, cell++) {
	if ((1 < cell->count) && (cell->count < min)) {
	  min = cell->count;
	  c = i;
	}
  }
  mask = state->cells[c].mask;
  for (m = 1 << SIZE - 1; m; m >>= 1) {
	if (mask & m) {
	  guess = makeState(guess, state);
	  total_guesses++;
	  guess->guesses++;
	  guess->solved++;
	  guess->cells[c].mask = m;
	  guess->cells[c].count = 1;
	  enqueue(guess, c);
	  if (solve(guess)) {
		makeState(state, guess);	// copies successful state to preceding state
		freeState(guess);
		return 1;
	  }
	}
  }
  freeState(guess);
  return 0;
}

 // Solve the current puzzle as far as possible, when no more can be
 // deduced guess.
int solve(struct state *state) {
  REPORT(A_PRINTENTRIES, "Entering solve\n");
  while (state->list >= 0) {	// deduce all that is possible...
	state->tries += 1;
	if (!deduce(state)) {
	  return 0;
	}
  }
  if (state->solved < SIZE*SIZE) {	//... and then guess
	//	printf("There are no more logical steps, try guessing\n");
	return guess(state);
  }
  return 1;
}

/******************************************************************
 * 
 * Initialization and startuo functions
 *
*******************************************************************/
// initially set a single cell to a given value
int initCell(struct state *state, int x, int y, char value) {
  int c = SIZE*y + x;
  int num;
  struct cell *cell = &state->cells[c];
  if (cell->mask != M_ALL) {
	return 0;
  }
  if (('A' <= value) && (value <= 'Z')) {
	value = value - 'A' + 'a';
  }
  if (customize & A_HEX) {
	if (('0' <= value) && (value <= '9')) {
	  num = value - '0';
	}
	else if (('a' <= value) && (value <= 'f')) {
	  num = value + 10 - 'a';
	}
	else return 1;
  }
  else if (('1' <= value) && (value <= '9')) {
	num = value - '1';
  }
  else if (('a' <= value) && (value <= 'z')) {
	num = value - 'a';
	customize |= A_ALPHA;
  }
  else if (('A' <= value) && (value <= 'Z')) {
	num = value - 'A';
	customize |= A_ALPHA;
  }
  else {
	return 1;
  }
  cell->mask = 1 << num;
  cell->count = 1;
  state->solved++;
  enqueue(state, c);
  REPORT(A_PRINTENTRIES, "Initializing [%d, %d] (cell #%d) to %c\n", x + 1, y + 1, c, value);
  return 1;
}

// initializes the entire puzzle
int initPuzzle(struct state *state, int test) {
  int x, y, num = 0, i, c;
  char input[100], *pc = null;
  struct cell *cell = null;

  REPORT(A_PRINTENTRIES, "Entering initPuzzle\n");
  for (y = 0; y < SIZE; y++) {
	if (!test) {
	  printf("Enter line %d: ", y + 1);
	  pc = input;
	  fgets(input, SIZE + 6, stdin);
	}
	else {
	  pc = (ROOT == 4) ? testdata4[0][y] : testdata[test - 1][y];
	}
	for (x = 0; *pc && (x < SIZE); x++, pc++) {
	  if (!initCell(state, x, y, *pc)) {
		return 0;
	  }
	}
  }
}

// reads the command line arguments
int processArgs(int argc, char **argv) {
  int i, j, l;
  int ret = 0;
  char ch;
  for (i = 1; i < argc; i++) {
	ch = argv[i][0];
	if (ch == '-') {
	  switch (argv[i][1]) {
	  case '2': root = 2; break;
	  case '3': root = 3; break;
	  case '4': root = 4; break;
	  case '5': root = 5; break;
	  case 't': 
		ch = argv[i][2];
		if (!ch) {
		  customize |= 0x1;
		}
		else if (('0' <= ch) && (ch < '0' + sizeof(testdata)/(9*sizeof(char *)))) {
		  customize |= (1 + ch - '0');
		}
		else {
		  printf("bad test indicator\n");
		  return 0;
		}
		break;
	  case 'l': 
		for (j = 2, l = 0; ('0' <= argv[i][j]) && (argv[i][j] <= '9'); j++) {
		  l = l*10 + argv[i][j] - '0';
		}
		CHECK_LIMIT = (l < LIMIT_MINIMUM) ? LIMIT_MINIMUM : l;
		break;
	  case 'g': customize |= A_GRIDONGUESS; break;
	  case 'h': customize |= A_HEX; break;
	  case 'f': customize |= A_GRIDONFOUND; break;
	  case 'd': 
		if (argv[i][3]) {
		  customize |= (AA_PRINTBITS & ((10*(argv[i][2] - '0') + argv[i][3] - '0') << 4));
		}
		else if (argv[i][2]) {
		  customize |= (AA_PRINTBITS & ((argv[i][2] - '0') << 4));
		}
		else {
		  customize |= A_PRINTFOUNDCELL;
		}
		break;
	  default: return 0;
	  }
	}
	else if (('0' <= ch) && (ch <= '9')) {
	  customize |= (ch - '0');
	  REPORT(A_PRINTENTRIES, "Setting report level to %d\n", ch - '0');
	}
	else {
	  return 0;
	}
  }
  if ((SIZE > 16) || (SIZE > 9) && !(customize & A_HEX)) {
	customize |= A_ALPHA;
  }
  if (CHECK_LIMIT > SIZE) {
	CHECK_LIMIT = SIZE;
  }
  return 1;
}

// main entry point
int main(int argc, char **argv) {
  int i, foundOne;
  struct state *state = null;
  int ret;

  if (!processArgs(argc, argv)) {
	ret = E_BADCALL;
  }
  else if (!(state = makeState(null, null))) {
	printf("Memory allocation error on startup\n");
	ret = E_ALLOCFAIL;
  }	  
  else if (!initPuzzle(state, customize & AA_TEST)) {
	  printf("Bad input to puzzle\n");
	  ret = E_BADINIT;
	}
  else if (solve(state)) {
	printf("Solved! list maximum was %d\n there were %d total guesses, %d guesses in the solution\n", state->listMaxDepth, total_guesses, state->guesses);
	printCircuitCounts(state);
	printSolution(state);
	ret = E_SUCCESS;
  }
  else {
	printf("Unsolvable\n");
	printPossibilities(state);
	ret = E_UNSOLVABLE;
  }
  freeState(state);
  return ret;
}

