char*	title = "Program to solve Challenger game.";
 
/* Challenger puzzle consists of four rows of four numbers each.
Each number may have a value from one to nine.
Each puzzle includes:
- four numbers randomly placed in the four by four matrix, one in each column
  and one in each row,
- the total of the numbers in each row,
- the total of the numbers in each column,
- the total of the numbers on the two diagonals.
*/
 
#include	<stdio.h>
#include	<string.h>
 
#ifdef _DEBUG
	#define	DEBUG	1
#else
	#define	DEBUG	0
#endif
 
#define	EOL			"
"
#define	START		1
#define	STOP		9
#define	dimensionof(p)	(sizeof(p)/sizeof(p[0]))
#define	putEOL()		printf(EOL)
#define	writeln(p)		printf("%s" EOL, p)
#define	zerofill(p)		memset(p, 0, sizeof(p))
 
typedef	unsigned char	boolean;
 
/*	There are ten totals given: the totals of:
	- the four rows,
	- the four columns and
	- the two diagonals.
	We keep them in the array 'totals'. We also have an array ('differ') of 
	the same size that we use to keep track of the difference between the 
	totals of the values currently stored in the matrix and the provided total.
	The 'up diagonal' goes from the lower left to the upper right.
	The 'down diagonal' goes from the upper left to the lower right.
*/
 
int		totals[10];
int		differ[10];		// difference between current totals and target totals
 
enum{	COLUMN1=0,	COLUMN2,	COLUMN3,	COLUMN4,
		ROW1,		ROW2,		ROW3,		ROW4,
		UP_DIAGONAL,			DOWN_DIAGONAL};
 
/*		0 1st column total
		1 2nd   "      "
		2 3rd   "      "
		3 4th   "      "
		4 1st row total
		5 2nd  "    "
		6 3rd  "    "
		7 4th  "    "
		8 up diagonal total
		9 down diagonal total
*/
/*	Each element in the 4 x 4 matrix is used in computing at least two totals,
	three if it is on one of the diagonals. This array holds a list of indices
	for each element in the matrix. The indices are used to access elements in
	the arrays 'totals' and 'differ'. Minus one (-1) indicates that entry isn't
	used.
*/
 
//			 x  y
//		column	row
//			 |  |
int		list[4][4] = 
{
	DOWN_DIAGONAL,	-1,				-1,				UP_DIAGONAL,
	-1,				DOWN_DIAGONAL,	UP_DIAGONAL,	-1,
	-1,				UP_DIAGONAL,	DOWN_DIAGONAL,	-1,
	UP_DIAGONAL,	-1,				-1,				DOWN_DIAGONAL,
};
 
struct
{
	int		v;
	boolean	known;
}	a[4][4];
 
 
 
void show_list(void)
{
	int		x;
	int		y;
 
	if (DEBUG)
	{
		putEOL();
		writeln("List");
		writeln("   x   y   entries");
 
		for (x=0; x<4; x++)
		{
			for (y=0; y<4; y++)
			{
				printf("   %d", x);
				printf("   %d", y);
				printf("   %d", list[x][y]);
				putEOL();
			}
		}
		putEOL();
	}
}
 
 
 
void show_result(void)
{
	int		x;
	int		y;
 
// Upward diagonals
 
	printf("                    ");
	printf(" %3d"	EOL, totals[UP_DIAGONAL]);
	printf("                ");
	printf(" %3d"	EOL, differ[UP_DIAGONAL]);
 
// Row by row
 
	for (y=0; y<4; y++)
	{
		for (x=0; x<4; x++)
			printf("   %d", a[x][y].v);
 
		printf(" %3d"	 , differ[y + ROW1]);
		printf(" %3d" EOL, totals[y + ROW1]);
	}
 
// Column differences and down diagonal
 
	for (x=0; x<4; x++)
		printf(" %3d", differ[x + COLUMN1]);
 
	printf(" %3d"	EOL, differ[DOWN_DIAGONAL]);
 
// Totals
 
	for (x=0; x<4; x++)
		printf(" %3d", totals[x + COLUMN1]);
 
	printf("    ");
	printf(" %3d"	EOL, totals[DOWN_DIAGONAL]);
}
 
 
 
void adjust(void)
{
	int		x;
	int		y;
	int		adjust;
	int		ik;
	int		total;
 
	for (x=0; x<4; x++)
	{
		for (y=0; y<4; y++)
		{
			if (a[x][y].known)
				continue;
 
			total	= differ[x + COLUMN1]
					+ differ[y + ROW1	];
			ik = list[x][y];
			if (ik>0)
				total += differ[ik];
 
			if (total == 0)
				continue;
 
			if ((total > 0) && (a[x][y].v < STOP))	adjust =  1;
			else
			if ((total < 0) && (a[x][y].v > START))	adjust = -1;
			else
				continue;
 
			a[x][y].v			  += adjust;
			differ[x + COLUMN1	] -= adjust;
			differ[y + ROW1		] -= adjust;
//			ik = list[x][y];
			if (ik>0)
				differ[ik] -= adjust;
		}
	}
	if (DEBUG)
		show_result();
}
 
 
 
void compute_differences(void)
{
	int		x;
	int		y;
	int		total;
 
// Column totals
 
	for (x=0; x<4; x++)
	{
		total = 0;
		for (y=0; y<4; y++)
			total += a[x][y].v;
 
		differ[x+COLUMN1] = totals[x+COLUMN1] - total;
	}
 
// Row totals
 
	for (y=0; y<4; y++)
	{
		total = 0;
		for (x=0; x<4; x++)
			total += a[x][y].v;
 
		differ[y+ROW1] = totals[y+ROW1] - total;
	}
 
	total = 0;
	for (x=0; x<4; x++)
		total += a[x][x].v;
 
	differ[DOWN_DIAGONAL] = totals[DOWN_DIAGONAL] - total;
 
	total = 0;
	for (x=0; x<4; x++)
		total += a[x][3-x].v;
 
	differ[UP_DIAGONAL] = totals[UP_DIAGONAL] - total;
}
 
 
 
boolean valid(void)
{
	int		x;
 
	for (x=0; x<dimensionof(differ); x++)
		if (differ[x] != 0)
			return 0;
 
	return 1;
}
 
 
 
void getenter(void)
{
	printf("Press ENTER to continue/exit.");
	while (getchar()!=0xa)
		;
}
 
 
 
void main(void)
{
	int		x;
	int		y;
	int		count	=		   0;
 
	writeln(title);
	show_list();
 
// Initialize
 
	zerofill(a		);
	zerofill(totals	);
	zerofill(differ	);
 
	for (x=0; x<4; x++)
	{
		for (y=0; y<4; y++)
			a[x][y].v = 5;		// (1st + last) / 2
	}
 
// Set known values
//					32 up diagonal total
//		9			31 \
//			6		28  \ row
//	8				28  / totals
//				7	33 /
//	30	33	31	26	28 down diagonal total
//   column totals
 
	a[1][0].v = 9;	a[1][0].known = 1;
	a[2][1].v = 6;	a[2][1].known = 1;
	a[0][2].v = 8;	a[0][2].known = 1;
	a[3][3].v = 7;	a[3][3].known = 1;
	totals[COLUMN1]			= 30;	// column totals
	totals[COLUMN2]			= 33;
	totals[COLUMN3]			= 31;
	totals[COLUMN4]			= 26;
	totals[ROW1]			= 31;	// row totals
	totals[ROW2]			= 28;
	totals[ROW3]			= 28;
	totals[ROW4]			= 33;
	totals[UP_DIAGONAL]		= 32;
	totals[DOWN_DIAGONAL]	= 28;
 
	compute_differences();
 
	writeln(EOL "Puzzle");
	show_result();
	while (1)
	{
		if (valid())
		{
			writeln(EOL "Solution");
			goto exit;
		}
		adjust();
		count++;
	}
	writeln("No solution");
 
exit:
	show_result();
	printf("count = %d" EOL, count);
	getenter();
}