Posted By

cpergiel on 10/03/10

Statistics

Viewed 511 times
Favorited by 0 user(s)

Program to solve Challenger number puzzle

/ Published in: C  Copy this code and paste it in your HTML
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))
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;
45. int differ; // 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 =
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;
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.
157. {
158. int x;
159. int y;
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.
187. differ[x + COLUMN1 ] -= adjust;
188. differ[y + ROW1 ] -= adjust;
189. // ik = list[x][y];
190. if (ik>0)
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.v = 9; a.known = 1;
296. a.v = 6; a.known = 1;
297. a.v = 8; a.known = 1;
298. a.v = 7; a.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. }
322. count++;
323. }
324. writeln("No solution");
325.
326. exit:
327. show_result();
328. printf("count = %d" EOL, count);
329. getenter();
330. } Subscribe to comments