#define null ((void *) 0)

// Originally this was written hard-coded for 3x3 puzzles with defines
// for ROOT and SIZE. To generalize the program it was easiest to make
// a global constant "root", and change all the defines to refer to
// it.
// #define ROOT			3
#define ROOT root
#define SIZE 			(ROOT*ROOT)

// CHECK_LIMIT too originally was hard-coded, but it is interesting to
// make it configurable. It controls how hard the program looks for
// solutions before giving up and guessing. A high value of ROOT means
// it will positively find all solutions, but it can take a long time
// - for instance, to fill up a 5x5 blank array by guessing gives the
// following data (note real time includes the time to hit "return" 25
// times to enter a blank array):
//			
//  CHECK_DATA\	time
//			4	0.39u 0.13s 0:05.48 9.4%
//			5	0.98u 0.11s 0:05.37 20.2%
//			6	3.23u 0.14s 0:07.75 43.4%
//			7	8.15u 0.12s 0:12.73 64.9%
//			8	18.96u 0.15s 0:23.68 80.7%
//			9	

#define CHECK_LIMIT		check_limit
// #define CHECK_LIMIT		9
#define LIMIT_MINIMUM	2

// for passing back command line arguments
#define AA_TEST				0xf		// if nonzero use one of the compiled-in test puzzles
// Control printing output
#define A_PRINTFOUNDCELL	0x10	// print whenever a cell's value is found
#define A_PRINTCLEARING		0x20	// print whenever a value is eliminated from a cell
#define A_PRINTFOUNDCYCLE	0x40	// print whenever a cycle is found and it wants to clear
#define A_PRINTCHECKREF		0x80	// print whenever it starts checking a reference
#define A_PRINTENTRIES		0x100	// print whenever it enters a function
#define AA_PRINTBITS (A_PRINTFOUNDCELL | A_PRINTCLEARING | A_PRINTFOUNDCYCLE | A_PRINTCHECKREF | A_PRINTENTRIES)

#define A_ALPHA			0x1000		// use letters rather than numbers
#define A_HEX			0x2000		// use hexadecimal
#define A_GRIDONFOUND	0x4000
#define A_GRIDONGUESS	0x8000
#define A_ERROR			0x10000

// bits used in cell mask. 
#define M_ALL   	((1 << SIZE) - 1)	// stand for possible values in the cell

// Exit codes
#define E_SUCCESS 		0
#define E_UNSOLVABLE 	1
#define E_BADCALL 		2
#define E_ALLOCFAIL 	3
#define E_BADINIT	 	4

// offsets of the links for the different directions
#define D_VERT   0
#define D_HORIZ  1
#define D_SQUARE 2

// Following are the 3 structures used in this application. 

// overall puzzle state, contains all the cells and other state data
struct state {
  struct cell *cells;	// list of cells, from 0 to SIZE*SIZE - 1
  struct ref *refs;		// list of references, from 0 to 3*SIZE*SIZE - 1
  int list;				// head of list of cells to try to narrow down possibilities
  int solved;			// number of cells solved and fully processed
  // for statistical purposes, not needed to work
  int *circuits;
  int listDepth;
  int listMaxDepth;
  int guesses;
  int tries;
};

// a cell structure, one of the 81 squares to be filled in
struct cell {
  unsigned int mask;	// mask of the possible values for this cell: 0x1 = 1, 0x2 = 2, 0x4 = 3...
  int count;			// number of bits set (possible values for this cell)
  int refs;				// offset into state->refs, add D_* to get value for each direction
};

// references a cell, is used to maintain a list of potential
// progress. Each cell can be on the list up to 3 times, one for each
// direction. The list is kept sorted with the smallest values
// first. The smallest values are both faster to process and more
// likely to help eliminate possibilities elsewhere in their
// row/column/square.
struct ref {
  int cell;				// cell to which this ref refers to
  int dir;				// direction (D_VERT, D_HORIZ, D_SQUARE)
  int level;			// starts out as the number of bits set in the
						// cell, but each time the cell is tested
						// unsuccessfully it is incremented by 1, up
						// to the limit CHECK_LIMIT
  int next;				// forward link for list of potentials, -2 if not on list
  int prev;				// backward link for list of potentials, -2 if not on list
};

