## Posted By

cpergiel on 10/03/10

# Program to solve Challenger number puzzle

/ Published in: C

`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();}`