Revision: 32874
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
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