diff options
Diffstat (limited to 'apps/plugins/puzzles/fifteen.c')
-rw-r--r-- | apps/plugins/puzzles/fifteen.c | 1215 |
1 files changed, 1215 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/fifteen.c b/apps/plugins/puzzles/fifteen.c new file mode 100644 index 0000000000..0d5e7f5b0c --- /dev/null +++ b/apps/plugins/puzzles/fifteen.c | |||
@@ -0,0 +1,1215 @@ | |||
1 | /* | ||
2 | * fifteen.c: standard 15-puzzle. | ||
3 | */ | ||
4 | |||
5 | #include <stdio.h> | ||
6 | #include <stdlib.h> | ||
7 | #include <string.h> | ||
8 | #include "rbassert.h" | ||
9 | #include <ctype.h> | ||
10 | #include <math.h> | ||
11 | |||
12 | #include "puzzles.h" | ||
13 | |||
14 | #define PREFERRED_TILE_SIZE 48 | ||
15 | #define TILE_SIZE (ds->tilesize) | ||
16 | #define BORDER (TILE_SIZE / 2) | ||
17 | #define HIGHLIGHT_WIDTH (TILE_SIZE / 20) | ||
18 | #define COORD(x) ( (x) * TILE_SIZE + BORDER ) | ||
19 | #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 ) | ||
20 | |||
21 | #define ANIM_TIME 0.13F | ||
22 | #define FLASH_FRAME 0.13F | ||
23 | |||
24 | #define X(state, i) ( (i) % (state)->w ) | ||
25 | #define Y(state, i) ( (i) / (state)->w ) | ||
26 | #define C(state, x, y) ( (y) * (state)->w + (x) ) | ||
27 | |||
28 | #define PARITY_P(params, gap) (((X((params), (gap)) - ((params)->w - 1)) ^ \ | ||
29 | (Y((params), (gap)) - ((params)->h - 1)) ^ \ | ||
30 | (((params)->w * (params)->h) + 1)) & 1) | ||
31 | #define PARITY_S(state) PARITY_P((state), ((state)->gap_pos)) | ||
32 | |||
33 | enum { | ||
34 | COL_BACKGROUND, | ||
35 | COL_TEXT, | ||
36 | COL_HIGHLIGHT, | ||
37 | COL_LOWLIGHT, | ||
38 | NCOLOURS | ||
39 | }; | ||
40 | |||
41 | struct game_params { | ||
42 | int w, h; | ||
43 | }; | ||
44 | |||
45 | struct game_state { | ||
46 | int w, h, n; | ||
47 | int *tiles; | ||
48 | int gap_pos; | ||
49 | int completed; | ||
50 | int used_solve; /* used to suppress completion flash */ | ||
51 | int movecount; | ||
52 | }; | ||
53 | |||
54 | static game_params *default_params(void) | ||
55 | { | ||
56 | game_params *ret = snew(game_params); | ||
57 | |||
58 | ret->w = ret->h = 4; | ||
59 | |||
60 | return ret; | ||
61 | } | ||
62 | |||
63 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
64 | { | ||
65 | if (i == 0) { | ||
66 | *params = default_params(); | ||
67 | *name = dupstr("4x4"); | ||
68 | return TRUE; | ||
69 | } | ||
70 | return FALSE; | ||
71 | } | ||
72 | |||
73 | static void free_params(game_params *params) | ||
74 | { | ||
75 | sfree(params); | ||
76 | } | ||
77 | |||
78 | static game_params *dup_params(const game_params *params) | ||
79 | { | ||
80 | game_params *ret = snew(game_params); | ||
81 | *ret = *params; /* structure copy */ | ||
82 | return ret; | ||
83 | } | ||
84 | |||
85 | static void decode_params(game_params *ret, char const *string) | ||
86 | { | ||
87 | ret->w = ret->h = atoi(string); | ||
88 | while (*string && isdigit((unsigned char)*string)) string++; | ||
89 | if (*string == 'x') { | ||
90 | string++; | ||
91 | ret->h = atoi(string); | ||
92 | } | ||
93 | } | ||
94 | |||
95 | static char *encode_params(const game_params *params, int full) | ||
96 | { | ||
97 | char data[256]; | ||
98 | |||
99 | sprintf(data, "%dx%d", params->w, params->h); | ||
100 | |||
101 | return dupstr(data); | ||
102 | } | ||
103 | |||
104 | static config_item *game_configure(const game_params *params) | ||
105 | { | ||
106 | config_item *ret; | ||
107 | char buf[80]; | ||
108 | |||
109 | ret = snewn(3, config_item); | ||
110 | |||
111 | ret[0].name = "Width"; | ||
112 | ret[0].type = C_STRING; | ||
113 | sprintf(buf, "%d", params->w); | ||
114 | ret[0].sval = dupstr(buf); | ||
115 | ret[0].ival = 0; | ||
116 | |||
117 | ret[1].name = "Height"; | ||
118 | ret[1].type = C_STRING; | ||
119 | sprintf(buf, "%d", params->h); | ||
120 | ret[1].sval = dupstr(buf); | ||
121 | ret[1].ival = 0; | ||
122 | |||
123 | ret[2].name = NULL; | ||
124 | ret[2].type = C_END; | ||
125 | ret[2].sval = NULL; | ||
126 | ret[2].ival = 0; | ||
127 | |||
128 | return ret; | ||
129 | } | ||
130 | |||
131 | static game_params *custom_params(const config_item *cfg) | ||
132 | { | ||
133 | game_params *ret = snew(game_params); | ||
134 | |||
135 | ret->w = atoi(cfg[0].sval); | ||
136 | ret->h = atoi(cfg[1].sval); | ||
137 | |||
138 | return ret; | ||
139 | } | ||
140 | |||
141 | static char *validate_params(const game_params *params, int full) | ||
142 | { | ||
143 | if (params->w < 2 || params->h < 2) | ||
144 | return "Width and height must both be at least two"; | ||
145 | |||
146 | return NULL; | ||
147 | } | ||
148 | |||
149 | static int perm_parity(int *perm, int n) | ||
150 | { | ||
151 | int i, j, ret; | ||
152 | |||
153 | ret = 0; | ||
154 | |||
155 | for (i = 0; i < n-1; i++) | ||
156 | for (j = i+1; j < n; j++) | ||
157 | if (perm[i] > perm[j]) | ||
158 | ret = !ret; | ||
159 | |||
160 | return ret; | ||
161 | } | ||
162 | |||
163 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
164 | char **aux, int interactive) | ||
165 | { | ||
166 | int gap, n, i, x; | ||
167 | int x1, x2, p1, p2, parity; | ||
168 | int *tiles, *used; | ||
169 | char *ret; | ||
170 | int retlen; | ||
171 | |||
172 | n = params->w * params->h; | ||
173 | |||
174 | tiles = snewn(n, int); | ||
175 | used = snewn(n, int); | ||
176 | |||
177 | for (i = 0; i < n; i++) { | ||
178 | tiles[i] = -1; | ||
179 | used[i] = FALSE; | ||
180 | } | ||
181 | |||
182 | gap = random_upto(rs, n); | ||
183 | tiles[gap] = 0; | ||
184 | used[0] = TRUE; | ||
185 | |||
186 | /* | ||
187 | * Place everything else except the last two tiles. | ||
188 | */ | ||
189 | for (x = 0, i = n-1; i > 2; i--) { | ||
190 | int k = random_upto(rs, i); | ||
191 | int j; | ||
192 | |||
193 | for (j = 0; j < n; j++) | ||
194 | if (!used[j] && (k-- == 0)) | ||
195 | break; | ||
196 | |||
197 | assert(j < n && !used[j]); | ||
198 | used[j] = TRUE; | ||
199 | |||
200 | while (tiles[x] >= 0) | ||
201 | x++; | ||
202 | assert(x < n); | ||
203 | tiles[x] = j; | ||
204 | } | ||
205 | |||
206 | /* | ||
207 | * Find the last two locations, and the last two pieces. | ||
208 | */ | ||
209 | while (tiles[x] >= 0) | ||
210 | x++; | ||
211 | assert(x < n); | ||
212 | x1 = x; | ||
213 | x++; | ||
214 | while (tiles[x] >= 0) | ||
215 | x++; | ||
216 | assert(x < n); | ||
217 | x2 = x; | ||
218 | |||
219 | for (i = 0; i < n; i++) | ||
220 | if (!used[i]) | ||
221 | break; | ||
222 | p1 = i; | ||
223 | for (i = p1+1; i < n; i++) | ||
224 | if (!used[i]) | ||
225 | break; | ||
226 | p2 = i; | ||
227 | |||
228 | /* | ||
229 | * Determine the required parity of the overall permutation. | ||
230 | * This is the XOR of: | ||
231 | * | ||
232 | * - The chessboard parity ((x^y)&1) of the gap square. The | ||
233 | * bottom right counts as even. | ||
234 | * | ||
235 | * - The parity of n. (The target permutation is 1,...,n-1,0 | ||
236 | * rather than 0,...,n-1; this is a cyclic permutation of | ||
237 | * the starting point and hence is odd iff n is even.) | ||
238 | */ | ||
239 | parity = PARITY_P(params, gap); | ||
240 | |||
241 | /* | ||
242 | * Try the last two tiles one way round. If that fails, swap | ||
243 | * them. | ||
244 | */ | ||
245 | tiles[x1] = p1; | ||
246 | tiles[x2] = p2; | ||
247 | if (perm_parity(tiles, n) != parity) { | ||
248 | tiles[x1] = p2; | ||
249 | tiles[x2] = p1; | ||
250 | assert(perm_parity(tiles, n) == parity); | ||
251 | } | ||
252 | |||
253 | /* | ||
254 | * Now construct the game description, by describing the tile | ||
255 | * array as a simple sequence of comma-separated integers. | ||
256 | */ | ||
257 | ret = NULL; | ||
258 | retlen = 0; | ||
259 | for (i = 0; i < n; i++) { | ||
260 | char buf[80]; | ||
261 | int k; | ||
262 | |||
263 | k = sprintf(buf, "%d,", tiles[i]); | ||
264 | |||
265 | ret = sresize(ret, retlen + k + 1, char); | ||
266 | strcpy(ret + retlen, buf); | ||
267 | retlen += k; | ||
268 | } | ||
269 | ret[retlen-1] = '\0'; /* delete last comma */ | ||
270 | |||
271 | sfree(tiles); | ||
272 | sfree(used); | ||
273 | |||
274 | return ret; | ||
275 | } | ||
276 | |||
277 | static char *validate_desc(const game_params *params, const char *desc) | ||
278 | { | ||
279 | const char *p; | ||
280 | char *err; | ||
281 | int i, area; | ||
282 | int *used; | ||
283 | |||
284 | area = params->w * params->h; | ||
285 | p = desc; | ||
286 | err = NULL; | ||
287 | |||
288 | used = snewn(area, int); | ||
289 | for (i = 0; i < area; i++) | ||
290 | used[i] = FALSE; | ||
291 | |||
292 | for (i = 0; i < area; i++) { | ||
293 | const char *q = p; | ||
294 | int n; | ||
295 | |||
296 | if (*p < '0' || *p > '9') { | ||
297 | err = "Not enough numbers in string"; | ||
298 | goto leave; | ||
299 | } | ||
300 | while (*p >= '0' && *p <= '9') | ||
301 | p++; | ||
302 | if (i < area-1 && *p != ',') { | ||
303 | err = "Expected comma after number"; | ||
304 | goto leave; | ||
305 | } | ||
306 | else if (i == area-1 && *p) { | ||
307 | err = "Excess junk at end of string"; | ||
308 | goto leave; | ||
309 | } | ||
310 | n = atoi(q); | ||
311 | if (n < 0 || n >= area) { | ||
312 | err = "Number out of range"; | ||
313 | goto leave; | ||
314 | } | ||
315 | if (used[n]) { | ||
316 | err = "Number used twice"; | ||
317 | goto leave; | ||
318 | } | ||
319 | used[n] = TRUE; | ||
320 | |||
321 | if (*p) p++; /* eat comma */ | ||
322 | } | ||
323 | |||
324 | leave: | ||
325 | sfree(used); | ||
326 | return err; | ||
327 | } | ||
328 | |||
329 | static game_state *new_game(midend *me, const game_params *params, | ||
330 | const char *desc) | ||
331 | { | ||
332 | game_state *state = snew(game_state); | ||
333 | int i; | ||
334 | const char *p; | ||
335 | |||
336 | state->w = params->w; | ||
337 | state->h = params->h; | ||
338 | state->n = params->w * params->h; | ||
339 | state->tiles = snewn(state->n, int); | ||
340 | |||
341 | state->gap_pos = 0; | ||
342 | p = desc; | ||
343 | i = 0; | ||
344 | for (i = 0; i < state->n; i++) { | ||
345 | assert(*p); | ||
346 | state->tiles[i] = atoi(p); | ||
347 | if (state->tiles[i] == 0) | ||
348 | state->gap_pos = i; | ||
349 | while (*p && *p != ',') | ||
350 | p++; | ||
351 | if (*p) p++; /* eat comma */ | ||
352 | } | ||
353 | assert(!*p); | ||
354 | assert(state->tiles[state->gap_pos] == 0); | ||
355 | |||
356 | state->completed = state->movecount = 0; | ||
357 | state->used_solve = FALSE; | ||
358 | |||
359 | return state; | ||
360 | } | ||
361 | |||
362 | static game_state *dup_game(const game_state *state) | ||
363 | { | ||
364 | game_state *ret = snew(game_state); | ||
365 | |||
366 | ret->w = state->w; | ||
367 | ret->h = state->h; | ||
368 | ret->n = state->n; | ||
369 | ret->tiles = snewn(state->w * state->h, int); | ||
370 | memcpy(ret->tiles, state->tiles, state->w * state->h * sizeof(int)); | ||
371 | ret->gap_pos = state->gap_pos; | ||
372 | ret->completed = state->completed; | ||
373 | ret->movecount = state->movecount; | ||
374 | ret->used_solve = state->used_solve; | ||
375 | |||
376 | return ret; | ||
377 | } | ||
378 | |||
379 | static void free_game(game_state *state) | ||
380 | { | ||
381 | sfree(state->tiles); | ||
382 | sfree(state); | ||
383 | } | ||
384 | |||
385 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
386 | const char *aux, char **error) | ||
387 | { | ||
388 | return dupstr("S"); | ||
389 | } | ||
390 | |||
391 | static int game_can_format_as_text_now(const game_params *params) | ||
392 | { | ||
393 | return TRUE; | ||
394 | } | ||
395 | |||
396 | static char *game_text_format(const game_state *state) | ||
397 | { | ||
398 | char *ret, *p, buf[80]; | ||
399 | int x, y, col, maxlen; | ||
400 | |||
401 | /* | ||
402 | * First work out how many characters we need to display each | ||
403 | * number. | ||
404 | */ | ||
405 | col = sprintf(buf, "%d", state->n-1); | ||
406 | |||
407 | /* | ||
408 | * Now we know the exact total size of the grid we're going to | ||
409 | * produce: it's got h rows, each containing w lots of col, w-1 | ||
410 | * spaces and a trailing newline. | ||
411 | */ | ||
412 | maxlen = state->h * state->w * (col+1); | ||
413 | |||
414 | ret = snewn(maxlen+1, char); | ||
415 | p = ret; | ||
416 | |||
417 | for (y = 0; y < state->h; y++) { | ||
418 | for (x = 0; x < state->w; x++) { | ||
419 | int v = state->tiles[state->w*y+x]; | ||
420 | if (v == 0) | ||
421 | sprintf(buf, "%*s", col, ""); | ||
422 | else | ||
423 | sprintf(buf, "%*d", col, v); | ||
424 | memcpy(p, buf, col); | ||
425 | p += col; | ||
426 | if (x+1 == state->w) | ||
427 | *p++ = '\n'; | ||
428 | else | ||
429 | *p++ = ' '; | ||
430 | } | ||
431 | } | ||
432 | |||
433 | assert(p - ret == maxlen); | ||
434 | *p = '\0'; | ||
435 | return ret; | ||
436 | } | ||
437 | |||
438 | static game_ui *new_ui(const game_state *state) | ||
439 | { | ||
440 | return NULL; | ||
441 | } | ||
442 | |||
443 | static void free_ui(game_ui *ui) | ||
444 | { | ||
445 | } | ||
446 | |||
447 | static char *encode_ui(const game_ui *ui) | ||
448 | { | ||
449 | return NULL; | ||
450 | } | ||
451 | |||
452 | static void decode_ui(game_ui *ui, const char *encoding) | ||
453 | { | ||
454 | } | ||
455 | |||
456 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
457 | const game_state *newstate) | ||
458 | { | ||
459 | } | ||
460 | |||
461 | struct game_drawstate { | ||
462 | int started; | ||
463 | int w, h, bgcolour; | ||
464 | int *tiles; | ||
465 | int tilesize; | ||
466 | }; | ||
467 | |||
468 | static int flip_cursor(int button) | ||
469 | { | ||
470 | switch (button) { | ||
471 | case CURSOR_UP: return CURSOR_DOWN; | ||
472 | case CURSOR_DOWN: return CURSOR_UP; | ||
473 | case CURSOR_LEFT: return CURSOR_RIGHT; | ||
474 | case CURSOR_RIGHT: return CURSOR_LEFT; | ||
475 | } | ||
476 | return 0; | ||
477 | } | ||
478 | |||
479 | static void next_move_3x2(int ax, int ay, int bx, int by, | ||
480 | int gx, int gy, int *dx, int *dy) | ||
481 | { | ||
482 | /* When w = 3 and h = 2 and the tile going in the top left corner | ||
483 | * is at (ax, ay) and the tile going in the bottom left corner is | ||
484 | * at (bx, by) and the blank tile is at (gx, gy), how do you move? */ | ||
485 | |||
486 | /* Hard-coded shortest solutions. Sorry. */ | ||
487 | static const unsigned char move[120] = { | ||
488 | 1,2,0,1,2,2, | ||
489 | 2,0,0,2,0,0, | ||
490 | 0,0,2,0,2,0, | ||
491 | 0,0,0,2,0,2, | ||
492 | 2,0,0,0,2,0, | ||
493 | |||
494 | 0,3,0,1,1,1, | ||
495 | 3,0,3,2,1,2, | ||
496 | 2,1,1,0,1,0, | ||
497 | 2,1,2,1,0,1, | ||
498 | 1,2,0,2,1,2, | ||
499 | |||
500 | 0,1,3,1,3,0, | ||
501 | 1,3,1,3,0,3, | ||
502 | 0,0,3,3,0,0, | ||
503 | 0,0,0,1,2,1, | ||
504 | 3,0,0,1,1,1, | ||
505 | |||
506 | 3,1,1,1,3,0, | ||
507 | 1,1,1,1,1,1, | ||
508 | 1,3,1,1,3,0, | ||
509 | 1,1,3,3,1,3, | ||
510 | 1,3,0,0,0,0 | ||
511 | }; | ||
512 | static const struct { int dx, dy; } d[4] = {{+1,0},{-1,0},{0,+1},{0,-1}}; | ||
513 | |||
514 | int ea = 3*ay + ax, eb = 3*by + bx, eg = 3*gy + gx, v; | ||
515 | if (eb > ea) --eb; | ||
516 | if (eg > ea) --eg; | ||
517 | if (eg > eb) --eg; | ||
518 | v = move[ea + eb*6 + eg*5*6]; | ||
519 | *dx = d[v].dx; | ||
520 | *dy = d[v].dy; | ||
521 | } | ||
522 | |||
523 | static void next_move(int nx, int ny, int ox, int oy, int gx, int gy, | ||
524 | int tx, int ty, int w, int *dx, int *dy) | ||
525 | { | ||
526 | const int to_tile_x = (gx < nx ? +1 : -1); | ||
527 | const int to_goal_x = (gx < tx ? +1 : -1); | ||
528 | const int gap_x_on_goal_side = ((nx-tx) * (nx-gx) > 0); | ||
529 | |||
530 | assert (nx != tx || ny != ty); /* not already in place */ | ||
531 | assert (nx != gx || ny != gy); /* not placing the gap */ | ||
532 | assert (ty <= ny); /* because we're greedy (and flipping) */ | ||
533 | assert (ty <= gy); /* because we're greedy (and flipping) */ | ||
534 | |||
535 | /* TODO: define a termination function. Idea: 0 if solved, or | ||
536 | * the number of moves to solve the next piece plus the number of | ||
537 | * further unsolved pieces times an upper bound on the number of | ||
538 | * moves required to solve any piece. If such a function can be | ||
539 | * found, we have (termination && (termination => correctness)). | ||
540 | * The catch is our temporary disturbance of 2x3 corners. */ | ||
541 | |||
542 | /* handles end-of-row, when 3 and 4 are in the top right 2x3 box */ | ||
543 | if (tx == w - 2 && | ||
544 | ny <= ty + 2 && (nx == tx || nx == tx + 1) && | ||
545 | oy <= ty + 2 && (ox == tx || ox == tx + 1) && | ||
546 | gy <= ty + 2 && (gx == tx || gx == tx + 1)) | ||
547 | { | ||
548 | next_move_3x2(oy - ty, tx + 1 - ox, | ||
549 | ny - ty, tx + 1 - nx, | ||
550 | gy - ty, tx + 1 - gx, dy, dx); | ||
551 | *dx *= -1; | ||
552 | return; | ||
553 | } | ||
554 | |||
555 | if (tx == w - 1) { | ||
556 | if (ny <= ty + 2 && (nx == tx || nx == tx - 1) && | ||
557 | gy <= ty + 2 && (gx == tx || gx == tx - 1)) { | ||
558 | next_move_3x2(ny - ty, tx - nx, 0, 1, gy - ty, tx - gx, dy, dx); | ||
559 | *dx *= -1; | ||
560 | } else if (gy == ty) | ||
561 | *dy = +1; | ||
562 | else if (nx != tx || ny != ty + 1) { | ||
563 | next_move((w - 1) - nx, ny, -1, -1, (w - 1) - gx, gy, | ||
564 | 0, ty + 1, -1, dx, dy); | ||
565 | *dx *= -1; | ||
566 | } else if (gx == nx) | ||
567 | *dy = -1; | ||
568 | else | ||
569 | *dx = +1; | ||
570 | return; | ||
571 | } | ||
572 | |||
573 | /* note that *dy = -1 is unsafe when gy = ty + 1 and gx < tx */ | ||
574 | if (gy < ny) | ||
575 | if (nx == gx || (gy == ty && gx == tx)) | ||
576 | *dy = +1; | ||
577 | else if (!gap_x_on_goal_side) | ||
578 | *dx = to_tile_x; | ||
579 | else if (ny - ty > abs(nx - tx)) | ||
580 | *dx = to_tile_x; | ||
581 | else *dy = +1; | ||
582 | |||
583 | else if (gy == ny) | ||
584 | if (nx == tx) /* then we know ny > ty */ | ||
585 | if (gx > nx || ny > ty + 1) | ||
586 | *dy = -1; /* ... so this is safe */ | ||
587 | else | ||
588 | *dy = +1; | ||
589 | else if (gap_x_on_goal_side) | ||
590 | *dx = to_tile_x; | ||
591 | else if (gy == ty || (gy == ty + 1 && gx < tx)) | ||
592 | *dy = +1; | ||
593 | else | ||
594 | *dy = -1; | ||
595 | |||
596 | else if (nx == tx) /* gy > ny */ | ||
597 | if (gx > nx) | ||
598 | *dy = -1; | ||
599 | else | ||
600 | *dx = +1; | ||
601 | else if (gx == nx) | ||
602 | *dx = to_goal_x; | ||
603 | else if (gap_x_on_goal_side) | ||
604 | if (gy == ty + 1 && gx < tx) | ||
605 | *dx = to_tile_x; | ||
606 | else | ||
607 | *dy = -1; | ||
608 | |||
609 | else if (ny - ty > abs(nx - tx)) | ||
610 | *dy = -1; | ||
611 | else | ||
612 | *dx = to_tile_x; | ||
613 | } | ||
614 | |||
615 | static int compute_hint(const game_state *state, int *out_x, int *out_y) | ||
616 | { | ||
617 | /* The overall solving process is this: | ||
618 | * 1. Find the next piece to be put in its place | ||
619 | * 2. Move it diagonally towards its place | ||
620 | * 3. Move it horizontally or vertically towards its place | ||
621 | * (Modulo the last two tiles at the end of each row/column) | ||
622 | */ | ||
623 | |||
624 | int gx = X(state, state->gap_pos); | ||
625 | int gy = Y(state, state->gap_pos); | ||
626 | |||
627 | int tx, ty, nx, ny, ox, oy, /* {target,next,next2}_{x,y} */ i; | ||
628 | int dx = 0, dy = 0; | ||
629 | |||
630 | /* 1. Find the next piece | ||
631 | * if (there are no more unfinished columns than rows) { | ||
632 | * fill the top-most row, left to right | ||
633 | * } else { fill the left-most column, top to bottom } | ||
634 | */ | ||
635 | const int w = state->w, h = state->h, n = w*h; | ||
636 | int next_piece = 0, next_piece_2 = 0, solr = 0, solc = 0; | ||
637 | int unsolved_rows = h, unsolved_cols = w; | ||
638 | |||
639 | assert(out_x); | ||
640 | assert(out_y); | ||
641 | |||
642 | while (solr < h && solc < w) { | ||
643 | int start, step, stop; | ||
644 | if (unsolved_cols <= unsolved_rows) | ||
645 | start = solr*w + solc, step = 1, stop = unsolved_cols; | ||
646 | else | ||
647 | start = solr*w + solc, step = w, stop = unsolved_rows; | ||
648 | for (i = 0; i < stop; ++i) { | ||
649 | const int j = start + i*step; | ||
650 | if (state->tiles[j] != j + 1) { | ||
651 | next_piece = j + 1; | ||
652 | next_piece_2 = next_piece + step; | ||
653 | break; | ||
654 | } | ||
655 | } | ||
656 | if (i < stop) break; | ||
657 | |||
658 | (unsolved_cols <= unsolved_rows) | ||
659 | ? (++solr, --unsolved_rows) | ||
660 | : (++solc, --unsolved_cols); | ||
661 | } | ||
662 | |||
663 | if (next_piece == n) | ||
664 | return FALSE; | ||
665 | |||
666 | /* 2, 3. Move the next piece towards its place */ | ||
667 | |||
668 | /* gx, gy already set */ | ||
669 | tx = X(state, next_piece - 1); /* where we're going */ | ||
670 | ty = Y(state, next_piece - 1); | ||
671 | for (i = 0; i < n && state->tiles[i] != next_piece; ++i); | ||
672 | nx = X(state, i); /* where we're at */ | ||
673 | ny = Y(state, i); | ||
674 | for (i = 0; i < n && state->tiles[i] != next_piece_2; ++i); | ||
675 | ox = X(state, i); | ||
676 | oy = Y(state, i); | ||
677 | |||
678 | if (unsolved_cols <= unsolved_rows) | ||
679 | next_move(nx, ny, ox, oy, gx, gy, tx, ty, w, &dx, &dy); | ||
680 | else | ||
681 | next_move(ny, nx, oy, ox, gy, gx, ty, tx, h, &dy, &dx); | ||
682 | |||
683 | assert (dx || dy); | ||
684 | |||
685 | *out_x = gx + dx; | ||
686 | *out_y = gy + dy; | ||
687 | return TRUE; | ||
688 | } | ||
689 | |||
690 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
691 | const game_drawstate *ds, | ||
692 | int x, int y, int button) | ||
693 | { | ||
694 | int cx = X(state, state->gap_pos), nx = cx; | ||
695 | int cy = Y(state, state->gap_pos), ny = cy; | ||
696 | char buf[80]; | ||
697 | |||
698 | button &= ~MOD_MASK; | ||
699 | |||
700 | if (button == LEFT_BUTTON) { | ||
701 | nx = FROMCOORD(x); | ||
702 | ny = FROMCOORD(y); | ||
703 | if (nx < 0 || nx >= state->w || ny < 0 || ny >= state->h) | ||
704 | return NULL; /* out of bounds */ | ||
705 | } else if (IS_CURSOR_MOVE(button)) { | ||
706 | static int invert_cursor = -1; | ||
707 | if (invert_cursor == -1) { | ||
708 | char *env = getenv("FIFTEEN_INVERT_CURSOR"); | ||
709 | invert_cursor = (env && (env[0] == 'y' || env[0] == 'Y')); | ||
710 | } | ||
711 | button = flip_cursor(button); /* the default */ | ||
712 | if (invert_cursor) | ||
713 | button = flip_cursor(button); /* undoes the first flip */ | ||
714 | move_cursor(button, &nx, &ny, state->w, state->h, FALSE); | ||
715 | } else if ((button == 'h' || button == 'H') && !state->completed) { | ||
716 | if (!compute_hint(state, &nx, &ny)) | ||
717 | return NULL; /* shouldn't happen, since ^^we^^checked^^ */ | ||
718 | } else | ||
719 | return NULL; /* no move */ | ||
720 | |||
721 | /* | ||
722 | * Any click location should be equal to the gap location | ||
723 | * in _precisely_ one coordinate. | ||
724 | */ | ||
725 | if ((cx == nx) ^ (cy == ny)) { | ||
726 | sprintf(buf, "M%d,%d", nx, ny); | ||
727 | return dupstr(buf); | ||
728 | } | ||
729 | |||
730 | return NULL; | ||
731 | } | ||
732 | |||
733 | static game_state *execute_move(const game_state *from, const char *move) | ||
734 | { | ||
735 | int gx, gy, dx, dy, ux, uy, up, p; | ||
736 | game_state *ret; | ||
737 | |||
738 | if (!strcmp(move, "S")) { | ||
739 | int i; | ||
740 | |||
741 | ret = dup_game(from); | ||
742 | |||
743 | /* | ||
744 | * Simply replace the grid with a solved one. For this game, | ||
745 | * this isn't a useful operation for actually telling the user | ||
746 | * what they should have done, but it is useful for | ||
747 | * conveniently being able to get hold of a clean state from | ||
748 | * which to practise manoeuvres. | ||
749 | */ | ||
750 | for (i = 0; i < ret->n; i++) | ||
751 | ret->tiles[i] = (i+1) % ret->n; | ||
752 | ret->gap_pos = ret->n-1; | ||
753 | ret->used_solve = TRUE; | ||
754 | ret->completed = ret->movecount = 1; | ||
755 | |||
756 | return ret; | ||
757 | } | ||
758 | |||
759 | gx = X(from, from->gap_pos); | ||
760 | gy = Y(from, from->gap_pos); | ||
761 | |||
762 | if (move[0] != 'M' || | ||
763 | sscanf(move+1, "%d,%d", &dx, &dy) != 2 || | ||
764 | (dx == gx && dy == gy) || (dx != gx && dy != gy) || | ||
765 | dx < 0 || dx >= from->w || dy < 0 || dy >= from->h) | ||
766 | return NULL; | ||
767 | |||
768 | /* | ||
769 | * Find the unit displacement from the original gap | ||
770 | * position towards this one. | ||
771 | */ | ||
772 | ux = (dx < gx ? -1 : dx > gx ? +1 : 0); | ||
773 | uy = (dy < gy ? -1 : dy > gy ? +1 : 0); | ||
774 | up = C(from, ux, uy); | ||
775 | |||
776 | ret = dup_game(from); | ||
777 | |||
778 | ret->gap_pos = C(from, dx, dy); | ||
779 | assert(ret->gap_pos >= 0 && ret->gap_pos < ret->n); | ||
780 | |||
781 | ret->tiles[ret->gap_pos] = 0; | ||
782 | |||
783 | for (p = from->gap_pos; p != ret->gap_pos; p += up) { | ||
784 | assert(p >= 0 && p < from->n); | ||
785 | ret->tiles[p] = from->tiles[p + up]; | ||
786 | ret->movecount++; | ||
787 | } | ||
788 | |||
789 | /* | ||
790 | * See if the game has been completed. | ||
791 | */ | ||
792 | if (!ret->completed) { | ||
793 | ret->completed = ret->movecount; | ||
794 | for (p = 0; p < ret->n; p++) | ||
795 | if (ret->tiles[p] != (p < ret->n-1 ? p+1 : 0)) | ||
796 | ret->completed = 0; | ||
797 | } | ||
798 | |||
799 | return ret; | ||
800 | } | ||
801 | |||
802 | /* ---------------------------------------------------------------------- | ||
803 | * Drawing routines. | ||
804 | */ | ||
805 | |||
806 | static void game_compute_size(const game_params *params, int tilesize, | ||
807 | int *x, int *y) | ||
808 | { | ||
809 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
810 | struct { int tilesize; } ads, *ds = &ads; | ||
811 | ads.tilesize = tilesize; | ||
812 | |||
813 | *x = TILE_SIZE * params->w + 2 * BORDER; | ||
814 | *y = TILE_SIZE * params->h + 2 * BORDER; | ||
815 | } | ||
816 | |||
817 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
818 | const game_params *params, int tilesize) | ||
819 | { | ||
820 | ds->tilesize = tilesize; | ||
821 | } | ||
822 | |||
823 | static float *game_colours(frontend *fe, int *ncolours) | ||
824 | { | ||
825 | float *ret = snewn(3 * NCOLOURS, float); | ||
826 | int i; | ||
827 | |||
828 | game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT); | ||
829 | |||
830 | for (i = 0; i < 3; i++) | ||
831 | ret[COL_TEXT * 3 + i] = 0.0; | ||
832 | |||
833 | *ncolours = NCOLOURS; | ||
834 | return ret; | ||
835 | } | ||
836 | |||
837 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
838 | { | ||
839 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
840 | int i; | ||
841 | |||
842 | ds->started = FALSE; | ||
843 | ds->w = state->w; | ||
844 | ds->h = state->h; | ||
845 | ds->bgcolour = COL_BACKGROUND; | ||
846 | ds->tiles = snewn(ds->w*ds->h, int); | ||
847 | ds->tilesize = 0; /* haven't decided yet */ | ||
848 | for (i = 0; i < ds->w*ds->h; i++) | ||
849 | ds->tiles[i] = -1; | ||
850 | |||
851 | return ds; | ||
852 | } | ||
853 | |||
854 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
855 | { | ||
856 | sfree(ds->tiles); | ||
857 | sfree(ds); | ||
858 | } | ||
859 | |||
860 | static void draw_tile(drawing *dr, game_drawstate *ds, const game_state *state, | ||
861 | int x, int y, int tile, int flash_colour) | ||
862 | { | ||
863 | if (tile == 0) { | ||
864 | draw_rect(dr, x, y, TILE_SIZE, TILE_SIZE, | ||
865 | flash_colour); | ||
866 | } else { | ||
867 | int coords[6]; | ||
868 | char str[40]; | ||
869 | |||
870 | coords[0] = x + TILE_SIZE - 1; | ||
871 | coords[1] = y + TILE_SIZE - 1; | ||
872 | coords[2] = x + TILE_SIZE - 1; | ||
873 | coords[3] = y; | ||
874 | coords[4] = x; | ||
875 | coords[5] = y + TILE_SIZE - 1; | ||
876 | draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT); | ||
877 | |||
878 | coords[0] = x; | ||
879 | coords[1] = y; | ||
880 | draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT); | ||
881 | |||
882 | draw_rect(dr, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH, | ||
883 | TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH, | ||
884 | flash_colour); | ||
885 | |||
886 | sprintf(str, "%d", tile); | ||
887 | draw_text(dr, x + TILE_SIZE/2, y + TILE_SIZE/2, | ||
888 | FONT_VARIABLE, TILE_SIZE/3, ALIGN_VCENTRE | ALIGN_HCENTRE, | ||
889 | COL_TEXT, str); | ||
890 | } | ||
891 | draw_update(dr, x, y, TILE_SIZE, TILE_SIZE); | ||
892 | } | ||
893 | |||
894 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
895 | const game_state *oldstate, const game_state *state, | ||
896 | int dir, const game_ui *ui, | ||
897 | float animtime, float flashtime) | ||
898 | { | ||
899 | int i, pass, bgcolour; | ||
900 | |||
901 | if (flashtime > 0) { | ||
902 | int frame = (int)(flashtime / FLASH_FRAME); | ||
903 | bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT); | ||
904 | } else | ||
905 | bgcolour = COL_BACKGROUND; | ||
906 | |||
907 | if (!ds->started) { | ||
908 | int coords[10]; | ||
909 | |||
910 | draw_rect(dr, 0, 0, | ||
911 | TILE_SIZE * state->w + 2 * BORDER, | ||
912 | TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND); | ||
913 | draw_update(dr, 0, 0, | ||
914 | TILE_SIZE * state->w + 2 * BORDER, | ||
915 | TILE_SIZE * state->h + 2 * BORDER); | ||
916 | |||
917 | /* | ||
918 | * Recessed area containing the whole puzzle. | ||
919 | */ | ||
920 | coords[0] = COORD(state->w) + HIGHLIGHT_WIDTH - 1; | ||
921 | coords[1] = COORD(state->h) + HIGHLIGHT_WIDTH - 1; | ||
922 | coords[2] = COORD(state->w) + HIGHLIGHT_WIDTH - 1; | ||
923 | coords[3] = COORD(0) - HIGHLIGHT_WIDTH; | ||
924 | coords[4] = coords[2] - TILE_SIZE; | ||
925 | coords[5] = coords[3] + TILE_SIZE; | ||
926 | coords[8] = COORD(0) - HIGHLIGHT_WIDTH; | ||
927 | coords[9] = COORD(state->h) + HIGHLIGHT_WIDTH - 1; | ||
928 | coords[6] = coords[8] + TILE_SIZE; | ||
929 | coords[7] = coords[9] - TILE_SIZE; | ||
930 | draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT); | ||
931 | |||
932 | coords[1] = COORD(0) - HIGHLIGHT_WIDTH; | ||
933 | coords[0] = COORD(0) - HIGHLIGHT_WIDTH; | ||
934 | draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT); | ||
935 | |||
936 | ds->started = TRUE; | ||
937 | } | ||
938 | |||
939 | /* | ||
940 | * Now draw each tile. We do this in two passes to make | ||
941 | * animation easy. | ||
942 | */ | ||
943 | for (pass = 0; pass < 2; pass++) { | ||
944 | for (i = 0; i < state->n; i++) { | ||
945 | int t, t0; | ||
946 | /* | ||
947 | * Figure out what should be displayed at this | ||
948 | * location. It's either a simple tile, or it's a | ||
949 | * transition between two tiles (in which case we say | ||
950 | * -1 because it must always be drawn). | ||
951 | */ | ||
952 | |||
953 | if (oldstate && oldstate->tiles[i] != state->tiles[i]) | ||
954 | t = -1; | ||
955 | else | ||
956 | t = state->tiles[i]; | ||
957 | |||
958 | t0 = t; | ||
959 | |||
960 | if (ds->bgcolour != bgcolour || /* always redraw when flashing */ | ||
961 | ds->tiles[i] != t || ds->tiles[i] == -1 || t == -1) { | ||
962 | int x, y; | ||
963 | |||
964 | /* | ||
965 | * Figure out what to _actually_ draw, and where to | ||
966 | * draw it. | ||
967 | */ | ||
968 | if (t == -1) { | ||
969 | int x0, y0, x1, y1; | ||
970 | int j; | ||
971 | |||
972 | /* | ||
973 | * On the first pass, just blank the tile. | ||
974 | */ | ||
975 | if (pass == 0) { | ||
976 | x = COORD(X(state, i)); | ||
977 | y = COORD(Y(state, i)); | ||
978 | t = 0; | ||
979 | } else { | ||
980 | float c; | ||
981 | |||
982 | t = state->tiles[i]; | ||
983 | |||
984 | /* | ||
985 | * Don't bother moving the gap; just don't | ||
986 | * draw it. | ||
987 | */ | ||
988 | if (t == 0) | ||
989 | continue; | ||
990 | |||
991 | /* | ||
992 | * Find the coordinates of this tile in the old and | ||
993 | * new states. | ||
994 | */ | ||
995 | x1 = COORD(X(state, i)); | ||
996 | y1 = COORD(Y(state, i)); | ||
997 | for (j = 0; j < oldstate->n; j++) | ||
998 | if (oldstate->tiles[j] == state->tiles[i]) | ||
999 | break; | ||
1000 | assert(j < oldstate->n); | ||
1001 | x0 = COORD(X(state, j)); | ||
1002 | y0 = COORD(Y(state, j)); | ||
1003 | |||
1004 | c = (animtime / ANIM_TIME); | ||
1005 | if (c < 0.0F) c = 0.0F; | ||
1006 | if (c > 1.0F) c = 1.0F; | ||
1007 | |||
1008 | x = x0 + (int)(c * (x1 - x0)); | ||
1009 | y = y0 + (int)(c * (y1 - y0)); | ||
1010 | } | ||
1011 | |||
1012 | } else { | ||
1013 | if (pass == 0) | ||
1014 | continue; | ||
1015 | x = COORD(X(state, i)); | ||
1016 | y = COORD(Y(state, i)); | ||
1017 | } | ||
1018 | |||
1019 | draw_tile(dr, ds, state, x, y, t, bgcolour); | ||
1020 | } | ||
1021 | ds->tiles[i] = t0; | ||
1022 | } | ||
1023 | } | ||
1024 | ds->bgcolour = bgcolour; | ||
1025 | |||
1026 | /* | ||
1027 | * Update the status bar. | ||
1028 | */ | ||
1029 | { | ||
1030 | char statusbuf[256]; | ||
1031 | |||
1032 | /* | ||
1033 | * Don't show the new status until we're also showing the | ||
1034 | * new _state_ - after the game animation is complete. | ||
1035 | */ | ||
1036 | if (oldstate) | ||
1037 | state = oldstate; | ||
1038 | |||
1039 | if (state->used_solve) | ||
1040 | sprintf(statusbuf, "Moves since auto-solve: %d", | ||
1041 | state->movecount - state->completed); | ||
1042 | else | ||
1043 | sprintf(statusbuf, "%sMoves: %d", | ||
1044 | (state->completed ? "COMPLETED! " : ""), | ||
1045 | (state->completed ? state->completed : state->movecount)); | ||
1046 | |||
1047 | status_bar(dr, statusbuf); | ||
1048 | } | ||
1049 | } | ||
1050 | |||
1051 | static float game_anim_length(const game_state *oldstate, | ||
1052 | const game_state *newstate, int dir, game_ui *ui) | ||
1053 | { | ||
1054 | return ANIM_TIME; | ||
1055 | } | ||
1056 | |||
1057 | static float game_flash_length(const game_state *oldstate, | ||
1058 | const game_state *newstate, int dir, game_ui *ui) | ||
1059 | { | ||
1060 | if (!oldstate->completed && newstate->completed && | ||
1061 | !oldstate->used_solve && !newstate->used_solve) | ||
1062 | return 2 * FLASH_FRAME; | ||
1063 | else | ||
1064 | return 0.0F; | ||
1065 | } | ||
1066 | |||
1067 | static int game_status(const game_state *state) | ||
1068 | { | ||
1069 | return state->completed ? +1 : 0; | ||
1070 | } | ||
1071 | |||
1072 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
1073 | { | ||
1074 | return TRUE; | ||
1075 | } | ||
1076 | |||
1077 | static void game_print_size(const game_params *params, float *x, float *y) | ||
1078 | { | ||
1079 | } | ||
1080 | |||
1081 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
1082 | { | ||
1083 | } | ||
1084 | |||
1085 | #ifdef COMBINED | ||
1086 | #define thegame fifteen | ||
1087 | #endif | ||
1088 | |||
1089 | const struct game thegame = { | ||
1090 | "Fifteen", "games.fifteen", "fifteen", | ||
1091 | default_params, | ||
1092 | game_fetch_preset, | ||
1093 | decode_params, | ||
1094 | encode_params, | ||
1095 | free_params, | ||
1096 | dup_params, | ||
1097 | TRUE, game_configure, custom_params, | ||
1098 | validate_params, | ||
1099 | new_game_desc, | ||
1100 | validate_desc, | ||
1101 | new_game, | ||
1102 | dup_game, | ||
1103 | free_game, | ||
1104 | TRUE, solve_game, | ||
1105 | TRUE, game_can_format_as_text_now, game_text_format, | ||
1106 | new_ui, | ||
1107 | free_ui, | ||
1108 | encode_ui, | ||
1109 | decode_ui, | ||
1110 | game_changed_state, | ||
1111 | interpret_move, | ||
1112 | execute_move, | ||
1113 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, | ||
1114 | game_colours, | ||
1115 | game_new_drawstate, | ||
1116 | game_free_drawstate, | ||
1117 | game_redraw, | ||
1118 | game_anim_length, | ||
1119 | game_flash_length, | ||
1120 | game_status, | ||
1121 | FALSE, FALSE, game_print_size, game_print, | ||
1122 | TRUE, /* wants_statusbar */ | ||
1123 | FALSE, game_timing_state, | ||
1124 | 0, /* flags */ | ||
1125 | }; | ||
1126 | |||
1127 | #ifdef STANDALONE_SOLVER | ||
1128 | |||
1129 | int main(int argc, char **argv) | ||
1130 | { | ||
1131 | game_params *params; | ||
1132 | game_state *state; | ||
1133 | char *id = NULL, *desc, *err; | ||
1134 | int grade = FALSE; | ||
1135 | char *progname = argv[0]; | ||
1136 | |||
1137 | char buf[80]; | ||
1138 | int limit, x, y, solvable; | ||
1139 | |||
1140 | while (--argc > 0) { | ||
1141 | char *p = *++argv; | ||
1142 | if (!strcmp(p, "-v")) { | ||
1143 | /* solver_show_working = TRUE; */ | ||
1144 | } else if (!strcmp(p, "-g")) { | ||
1145 | grade = TRUE; | ||
1146 | } else if (*p == '-') { | ||
1147 | fprintf(stderr, "%s: unrecognised option `%s'\n", progname, p); | ||
1148 | return 1; | ||
1149 | } else { | ||
1150 | id = p; | ||
1151 | } | ||
1152 | } | ||
1153 | |||
1154 | if (!id) { | ||
1155 | fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]); | ||
1156 | return 1; | ||
1157 | } | ||
1158 | |||
1159 | desc = strchr(id, ':'); | ||
1160 | if (!desc) { | ||
1161 | fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); | ||
1162 | return 1; | ||
1163 | } | ||
1164 | *desc++ = '\0'; | ||
1165 | |||
1166 | params = default_params(); | ||
1167 | decode_params(params, id); | ||
1168 | err = validate_desc(params, desc); | ||
1169 | if (err) { | ||
1170 | free_params(params); | ||
1171 | fprintf(stderr, "%s: %s\n", argv[0], err); | ||
1172 | return 1; | ||
1173 | } | ||
1174 | |||
1175 | state = new_game(NULL, params, desc); | ||
1176 | free_params(params); | ||
1177 | |||
1178 | solvable = (PARITY_S(state) == perm_parity(state->tiles, state->n)); | ||
1179 | if (grade || !solvable) { | ||
1180 | free_game(state); | ||
1181 | fputs(solvable ? "Game is solvable" : "Game is unsolvable", | ||
1182 | grade ? stdout : stderr); | ||
1183 | return !grade; | ||
1184 | } | ||
1185 | |||
1186 | for (limit = 5 * state->n * state->n * state->n; limit; --limit) { | ||
1187 | game_state *next_state; | ||
1188 | if (!compute_hint(state, &x, &y)) { | ||
1189 | fprintf(stderr, "couldn't compute next move while solving %s:%s", | ||
1190 | id, desc); | ||
1191 | return 1; | ||
1192 | } | ||
1193 | printf("Move the space to (%d, %d), moving %d into the space\n", | ||
1194 | x + 1, y + 1, state->tiles[C(state, x, y)]); | ||
1195 | sprintf(buf, "M%d,%d", x, y); | ||
1196 | next_state = execute_move(state, buf); | ||
1197 | |||
1198 | free_game(state); | ||
1199 | if (!next_state) { | ||
1200 | fprintf(stderr, "invalid move when solving %s:%s\n", id, desc); | ||
1201 | return 1; | ||
1202 | } | ||
1203 | state = next_state; | ||
1204 | if (next_state->completed) { | ||
1205 | free_game(state); | ||
1206 | return 0; | ||
1207 | } | ||
1208 | } | ||
1209 | |||
1210 | free_game(state); | ||
1211 | fprintf(stderr, "ran out of moves for %s:%s\n", id, desc); | ||
1212 | return 1; | ||
1213 | } | ||
1214 | |||
1215 | #endif | ||