Return to Snippet

Revision: 32874
at October 3, 2010 18:38 by cpergiel


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

Initial URL

                                

Initial Description

                                

Initial Title
Program to solve Challenger number puzzle

Initial Tags

                                

Initial Language
C