Posted By

cpergiel on 10/03/10


Tagged


Versions (?)

Program to solve Challenger number puzzle


 / Published in: C
 

  1. char* title = "Program to solve Challenger game.";
  2.  
  3. /* Challenger puzzle consists of four rows of four numbers each.
  4. Each number may have a value from one to nine.
  5. Each puzzle includes:
  6. - four numbers randomly placed in the four by four matrix, one in each column
  7.   and one in each row,
  8. - the total of the numbers in each row,
  9. - the total of the numbers in each column,
  10. - the total of the numbers on the two diagonals.
  11. */
  12.  
  13. #include <stdio.h>
  14. #include <string.h>
  15.  
  16. #ifdef _DEBUG
  17. #define DEBUG 1
  18. #else
  19. #define DEBUG 0
  20. #endif
  21.  
  22. #define EOL "
  23. "
  24. #define START 1
  25. #define STOP 9
  26. #define dimensionof(p) (sizeof(p)/sizeof(p[0]))
  27. #define putEOL() printf(EOL)
  28. #define writeln(p) printf("%s" EOL, p)
  29. #define zerofill(p) memset(p, 0, sizeof(p))
  30.  
  31. typedef unsigned char boolean;
  32.  
  33. /* There are ten totals given: the totals of:
  34. - the four rows,
  35. - the four columns and
  36. - the two diagonals.
  37. We keep them in the array 'totals'. We also have an array ('differ') of
  38. the same size that we use to keep track of the difference between the
  39. totals of the values currently stored in the matrix and the provided total.
  40. The 'up diagonal' goes from the lower left to the upper right.
  41. The 'down diagonal' goes from the upper left to the lower right.
  42. */
  43.  
  44. int totals[10];
  45. int differ[10]; // difference between current totals and target totals
  46.  
  47. enum{ COLUMN1=0, COLUMN2, COLUMN3, COLUMN4,
  48. ROW1, ROW2, ROW3, ROW4,
  49. UP_DIAGONAL, DOWN_DIAGONAL};
  50.  
  51. /* 0 1st column total
  52. 1 2nd " "
  53. 2 3rd " "
  54. 3 4th " "
  55. 4 1st row total
  56. 5 2nd " "
  57. 6 3rd " "
  58. 7 4th " "
  59. 8 up diagonal total
  60. 9 down diagonal total
  61. */
  62. /* Each element in the 4 x 4 matrix is used in computing at least two totals,
  63. three if it is on one of the diagonals. This array holds a list of indices
  64. for each element in the matrix. The indices are used to access elements in
  65. the arrays 'totals' and 'differ'. Minus one (-1) indicates that entry isn't
  66. used.
  67. */
  68.  
  69. // x y
  70. // column row
  71. // | |
  72. int list[4][4] =
  73. {
  74. DOWN_DIAGONAL, -1, -1, UP_DIAGONAL,
  75. -1, DOWN_DIAGONAL, UP_DIAGONAL, -1,
  76. -1, UP_DIAGONAL, DOWN_DIAGONAL, -1,
  77. UP_DIAGONAL, -1, -1, DOWN_DIAGONAL,
  78. };
  79.  
  80. struct
  81. {
  82. int v;
  83. boolean known;
  84. } a[4][4];
  85.  
  86.  
  87.  
  88. void show_list(void)
  89. {
  90. int x;
  91. int y;
  92.  
  93. if (DEBUG)
  94. {
  95. putEOL();
  96. writeln("List");
  97. writeln(" x y entries");
  98.  
  99. for (x=0; x<4; x++)
  100. {
  101. for (y=0; y<4; y++)
  102. {
  103. printf(" %d", x);
  104. printf(" %d", y);
  105. printf(" %d", list[x][y]);
  106. putEOL();
  107. }
  108. }
  109. putEOL();
  110. }
  111. }
  112.  
  113.  
  114.  
  115. void show_result(void)
  116. {
  117. int x;
  118. int y;
  119.  
  120. // Upward diagonals
  121.  
  122. printf(" ");
  123. printf(" %3d" EOL, totals[UP_DIAGONAL]);
  124. printf(" ");
  125. printf(" %3d" EOL, differ[UP_DIAGONAL]);
  126.  
  127. // Row by row
  128.  
  129. for (y=0; y<4; y++)
  130. {
  131. for (x=0; x<4; x++)
  132. printf(" %d", a[x][y].v);
  133.  
  134. printf(" %3d" , differ[y + ROW1]);
  135. printf(" %3d" EOL, totals[y + ROW1]);
  136. }
  137.  
  138. // Column differences and down diagonal
  139.  
  140. for (x=0; x<4; x++)
  141. printf(" %3d", differ[x + COLUMN1]);
  142.  
  143. printf(" %3d" EOL, differ[DOWN_DIAGONAL]);
  144.  
  145. // Totals
  146.  
  147. for (x=0; x<4; x++)
  148. printf(" %3d", totals[x + COLUMN1]);
  149.  
  150. printf(" ");
  151. printf(" %3d" EOL, totals[DOWN_DIAGONAL]);
  152. }
  153.  
  154.  
  155.  
  156. void adjust(void)
  157. {
  158. int x;
  159. int y;
  160. int adjust;
  161. int ik;
  162. int total;
  163.  
  164. for (x=0; x<4; x++)
  165. {
  166. for (y=0; y<4; y++)
  167. {
  168. if (a[x][y].known)
  169. continue;
  170.  
  171. total = differ[x + COLUMN1]
  172. + differ[y + ROW1 ];
  173. ik = list[x][y];
  174. if (ik>0)
  175. total += differ[ik];
  176.  
  177. if (total == 0)
  178. continue;
  179.  
  180. if ((total > 0) && (a[x][y].v < STOP)) adjust = 1;
  181. else
  182. if ((total < 0) && (a[x][y].v > START)) adjust = -1;
  183. else
  184. continue;
  185.  
  186. a[x][y].v += adjust;
  187. differ[x + COLUMN1 ] -= adjust;
  188. differ[y + ROW1 ] -= adjust;
  189. // ik = list[x][y];
  190. if (ik>0)
  191. differ[ik] -= adjust;
  192. }
  193. }
  194. if (DEBUG)
  195. show_result();
  196. }
  197.  
  198.  
  199.  
  200. void compute_differences(void)
  201. {
  202. int x;
  203. int y;
  204. int total;
  205.  
  206. // Column totals
  207.  
  208. for (x=0; x<4; x++)
  209. {
  210. total = 0;
  211. for (y=0; y<4; y++)
  212. total += a[x][y].v;
  213.  
  214. differ[x+COLUMN1] = totals[x+COLUMN1] - total;
  215. }
  216.  
  217. // Row totals
  218.  
  219. for (y=0; y<4; y++)
  220. {
  221. total = 0;
  222. for (x=0; x<4; x++)
  223. total += a[x][y].v;
  224.  
  225. differ[y+ROW1] = totals[y+ROW1] - total;
  226. }
  227.  
  228. total = 0;
  229. for (x=0; x<4; x++)
  230. total += a[x][x].v;
  231.  
  232. differ[DOWN_DIAGONAL] = totals[DOWN_DIAGONAL] - total;
  233.  
  234. total = 0;
  235. for (x=0; x<4; x++)
  236. total += a[x][3-x].v;
  237.  
  238. differ[UP_DIAGONAL] = totals[UP_DIAGONAL] - total;
  239. }
  240.  
  241.  
  242.  
  243. boolean valid(void)
  244. {
  245. int x;
  246.  
  247. for (x=0; x<dimensionof(differ); x++)
  248. if (differ[x] != 0)
  249. return 0;
  250.  
  251. return 1;
  252. }
  253.  
  254.  
  255.  
  256. void getenter(void)
  257. {
  258. printf("Press ENTER to continue/exit.");
  259. while (getchar()!=0xa)
  260. ;
  261. }
  262.  
  263.  
  264.  
  265. void main(void)
  266. {
  267. int x;
  268. int y;
  269. int count = 0;
  270.  
  271. writeln(title);
  272. show_list();
  273.  
  274. // Initialize
  275.  
  276. zerofill(a );
  277. zerofill(totals );
  278. zerofill(differ );
  279.  
  280. for (x=0; x<4; x++)
  281. {
  282. for (y=0; y<4; y++)
  283. a[x][y].v = 5; // (1st + last) / 2
  284. }
  285.  
  286. // Set known values
  287. // 32 up diagonal total
  288. // 9 31 \
  289. // 6 28 \ row
  290. // 8 28 / totals
  291. // 7 33 /
  292. // 30 33 31 26 28 down diagonal total
  293. // column totals
  294.  
  295. a[1][0].v = 9; a[1][0].known = 1;
  296. a[2][1].v = 6; a[2][1].known = 1;
  297. a[0][2].v = 8; a[0][2].known = 1;
  298. a[3][3].v = 7; a[3][3].known = 1;
  299. totals[COLUMN1] = 30; // column totals
  300. totals[COLUMN2] = 33;
  301. totals[COLUMN3] = 31;
  302. totals[COLUMN4] = 26;
  303. totals[ROW1] = 31; // row totals
  304. totals[ROW2] = 28;
  305. totals[ROW3] = 28;
  306. totals[ROW4] = 33;
  307. totals[UP_DIAGONAL] = 32;
  308. totals[DOWN_DIAGONAL] = 28;
  309.  
  310. compute_differences();
  311.  
  312. writeln(EOL "Puzzle");
  313. show_result();
  314. while (1)
  315. {
  316. if (valid())
  317. {
  318. writeln(EOL "Solution");
  319. goto exit;
  320. }
  321. adjust();
  322. count++;
  323. }
  324. writeln("No solution");
  325.  
  326. exit:
  327. show_result();
  328. printf("count = %d" EOL, count);
  329. getenter();
  330. }

Report this snippet  

You need to login to post a comment.