72c00e19 |
1 | /* |
2 | * magnets.c: implementation of janko.at 'magnets puzzle' game. |
3 | * |
4 | * http://64.233.179.104/translate_c?hl=en&u=http://www.janko.at/Raetsel/Magnete/Beispiel.htm |
5 | * |
6 | * Puzzle definition is just the size, and then the list of + (across then |
7 | * down) and - (across then down) present, then domino edges. |
8 | * |
9 | * An example: |
10 | * |
11 | * + 2 0 1 |
12 | * +-----+ |
13 | * 1|+ -| |1 |
14 | * |-+-+ | |
15 | * 0|-|#| |1 |
16 | * | +-+-| |
17 | * 2|+|- +|1 |
18 | * +-----+ |
19 | * 1 2 0 - |
20 | * |
21 | * 3x3:201,102,120,111,LRTT*BBLR |
22 | * |
23 | * 'Zotmeister' examples: |
24 | * 5x5:.2..1,3..1.,.2..2,2..2.,LRLRTTLRTBBT*BTTBLRBBLRLR |
25 | * 9x9:3.51...33,.2..23.13,..33.33.2,12...5.3.,**TLRTLR*,*TBLRBTLR,TBLRLRBTT,BLRTLRTBB,LRTB*TBLR,LRBLRBLRT,TTTLRLRTB,BBBTLRTB*,*LRBLRB** |
26 | * |
27 | * Janko 6x6 with solution: |
28 | * 6x6:322223,323132,232223,232223,LRTLRTTTBLRBBBTTLRLRBBLRTTLRTTBBLRBB |
29 | * |
30 | * janko 8x8: |
31 | * 8x8:34131323,23131334,43122323,21332243,LRTLRLRT,LRBTTTTB,LRTBBBBT,TTBTLRTB,BBTBTTBT,TTBTBBTB,BBTBLRBT,LRBLRLRB |
32 | */ |
33 | |
34 | #include <stdio.h> |
35 | #include <stdlib.h> |
36 | #include <string.h> |
37 | #include <assert.h> |
38 | #include <ctype.h> |
39 | #include <math.h> |
40 | |
41 | #include "puzzles.h" |
42 | |
43 | #ifdef STANDALONE_SOLVER |
44 | int verbose = 0; |
45 | #endif |
46 | |
47 | enum { |
48 | COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT, |
49 | COL_TEXT, COL_ERROR, COL_CURSOR, |
50 | COL_NEUTRAL, COL_NEGATIVE, COL_POSITIVE, COL_NOT, |
51 | NCOLOURS |
52 | }; |
53 | |
54 | /* Cell states. */ |
55 | enum { EMPTY = 0, NEUTRAL = EMPTY, POSITIVE = 1, NEGATIVE = 2 }; |
56 | |
57 | #if defined DEBUGGING || defined STANDALONE_SOLVER |
58 | static const char *cellnames[3] = { "neutral", "positive", "negative" }; |
59 | #define NAME(w) ( ((w) < 0 || (w) > 2) ? "(out of range)" : cellnames[(w)] ) |
60 | #endif |
61 | |
62 | #define GRID2CHAR(g) ( ((g) >= 0 && (g) <= 2) ? ".+-"[(g)] : '?' ) |
63 | #define CHAR2GRID(c) ( (c) == '+' ? POSITIVE : (c) == '-' ? NEGATIVE : NEUTRAL ) |
64 | |
65 | #define INGRID(s,x,y) ((x) >= 0 && (x) < (s)->w && (y) >= 0 && (y) < (s)->h) |
66 | |
67 | #define OPPOSITE(x) ( ((x)*2) % 3 ) /* 0 --> 0, |
68 | 1 --> 2, |
69 | 2 --> 4 --> 1 */ |
70 | |
71 | #define FLASH_TIME 0.7F |
72 | |
73 | /* Macro ickery copied from slant.c */ |
74 | #define DIFFLIST(A) \ |
75 | A(EASY,Easy,e) \ |
76 | A(TRICKY,Tricky,t) |
77 | #define ENUM(upper,title,lower) DIFF_ ## upper, |
78 | #define TITLE(upper,title,lower) #title, |
79 | #define ENCODE(upper,title,lower) #lower |
80 | #define CONFIG(upper,title,lower) ":" #title |
81 | enum { DIFFLIST(ENUM) DIFFCOUNT }; |
82 | static char const *const magnets_diffnames[] = { DIFFLIST(TITLE) "(count)" }; |
83 | static char const magnets_diffchars[] = DIFFLIST(ENCODE); |
84 | #define DIFFCONFIG DIFFLIST(CONFIG) |
85 | |
86 | |
87 | /* --------------------------------------------------------------- */ |
88 | /* Game parameter functions. */ |
89 | |
90 | struct game_params { |
91 | int w, h, diff, stripclues; |
92 | }; |
93 | |
94 | #define DEFAULT_PRESET 2 |
95 | |
96 | static const struct game_params magnets_presets[] = { |
97 | {6, 5, DIFF_EASY, 0}, |
98 | {6, 5, DIFF_TRICKY, 0}, |
99 | {6, 5, DIFF_TRICKY, 1}, |
100 | {8, 7, DIFF_EASY, 0}, |
101 | {8, 7, DIFF_TRICKY, 0}, |
102 | {8, 7, DIFF_TRICKY, 1}, |
103 | {10, 9, DIFF_TRICKY, 0}, |
104 | {10, 9, DIFF_TRICKY, 1} |
105 | }; |
106 | |
107 | static game_params *default_params(void) |
108 | { |
109 | game_params *ret = snew(game_params); |
110 | |
111 | *ret = magnets_presets[DEFAULT_PRESET]; |
112 | |
113 | return ret; |
114 | } |
115 | |
116 | static int game_fetch_preset(int i, char **name, game_params **params) |
117 | { |
118 | game_params *ret; |
119 | char buf[64]; |
120 | |
121 | if (i < 0 || i >= lenof(magnets_presets)) return FALSE; |
122 | |
123 | ret = default_params(); |
124 | *ret = magnets_presets[i]; /* struct copy */ |
125 | *params = ret; |
126 | |
127 | sprintf(buf, "%dx%d %s%s", |
128 | magnets_presets[i].w, magnets_presets[i].h, |
129 | magnets_diffnames[magnets_presets[i].diff], |
130 | magnets_presets[i].stripclues ? ", strip clues" : ""); |
131 | *name = dupstr(buf); |
132 | |
133 | return TRUE; |
134 | } |
135 | |
136 | static void free_params(game_params *params) |
137 | { |
138 | sfree(params); |
139 | } |
140 | |
141 | static game_params *dup_params(game_params *params) |
142 | { |
143 | game_params *ret = snew(game_params); |
144 | *ret = *params; /* structure copy */ |
145 | return ret; |
146 | } |
147 | |
148 | static void decode_params(game_params *ret, char const *string) |
149 | { |
150 | ret->w = ret->h = atoi(string); |
151 | while (*string && isdigit((unsigned char) *string)) ++string; |
152 | if (*string == 'x') { |
153 | string++; |
154 | ret->h = atoi(string); |
155 | while (*string && isdigit((unsigned char)*string)) string++; |
156 | } |
157 | |
158 | ret->diff = DIFF_EASY; |
159 | if (*string == 'd') { |
160 | int i; |
161 | string++; |
162 | for (i = 0; i < DIFFCOUNT; i++) |
163 | if (*string == magnets_diffchars[i]) |
164 | ret->diff = i; |
165 | if (*string) string++; |
166 | } |
167 | |
168 | ret->stripclues = 0; |
169 | if (*string == 'S') { |
170 | string++; |
171 | ret->stripclues = 1; |
172 | } |
173 | } |
174 | |
175 | static char *encode_params(game_params *params, int full) |
176 | { |
177 | char buf[256]; |
178 | sprintf(buf, "%dx%d", params->w, params->h); |
179 | if (full) |
180 | sprintf(buf + strlen(buf), "d%c%s", |
181 | magnets_diffchars[params->diff], |
182 | params->stripclues ? "S" : ""); |
183 | return dupstr(buf); |
184 | } |
185 | |
186 | static config_item *game_configure(game_params *params) |
187 | { |
188 | config_item *ret; |
189 | char buf[64]; |
190 | |
191 | ret = snewn(5, config_item); |
192 | |
193 | ret[0].name = "Width"; |
194 | ret[0].type = C_STRING; |
195 | sprintf(buf, "%d", params->w); |
196 | ret[0].sval = dupstr(buf); |
197 | ret[0].ival = 0; |
198 | |
199 | ret[1].name = "Height"; |
200 | ret[1].type = C_STRING; |
201 | sprintf(buf, "%d", params->h); |
202 | ret[1].sval = dupstr(buf); |
203 | ret[1].ival = 0; |
204 | |
205 | ret[2].name = "Difficulty"; |
206 | ret[2].type = C_CHOICES; |
207 | ret[2].sval = DIFFCONFIG; |
208 | ret[2].ival = params->diff; |
209 | |
210 | ret[3].name = "Strip clues"; |
211 | ret[3].type = C_BOOLEAN; |
212 | ret[3].sval = NULL; |
213 | ret[3].ival = params->stripclues; |
214 | |
215 | ret[4].name = NULL; |
216 | ret[4].type = C_END; |
217 | ret[4].sval = NULL; |
218 | ret[4].ival = 0; |
219 | |
220 | return ret; |
221 | } |
222 | |
223 | static game_params *custom_params(config_item *cfg) |
224 | { |
225 | game_params *ret = snew(game_params); |
226 | |
227 | ret->w = atoi(cfg[0].sval); |
228 | ret->h = atoi(cfg[1].sval); |
229 | ret->diff = cfg[2].ival; |
230 | ret->stripclues = cfg[3].ival; |
231 | |
232 | return ret; |
233 | } |
234 | |
235 | static char *validate_params(game_params *params, int full) |
236 | { |
237 | if (params->w < 2) return "Width must be at least one"; |
238 | if (params->h < 2) return "Height must be at least one"; |
239 | if (params->diff < 0 || params->diff >= DIFFCOUNT) |
240 | return "Unknown difficulty level"; |
241 | |
242 | return NULL; |
243 | } |
244 | |
245 | /* --------------------------------------------------------------- */ |
246 | /* Game state allocation, deallocation. */ |
247 | |
248 | struct game_common { |
249 | int *dominoes; /* size w*h, dominoes[i] points to other end of domino. */ |
250 | int *rowcount; /* size 3*h, array of [plus, minus, neutral] counts */ |
251 | int *colcount; /* size 3*w, ditto */ |
252 | int refcount; |
253 | }; |
254 | |
255 | #define GS_ERROR 1 |
256 | #define GS_SET 2 |
257 | #define GS_NOTPOSITIVE 4 |
258 | #define GS_NOTNEGATIVE 8 |
259 | #define GS_NOTNEUTRAL 16 |
260 | #define GS_MARK 32 |
261 | |
262 | #define GS_NOTMASK (GS_NOTPOSITIVE|GS_NOTNEGATIVE|GS_NOTNEUTRAL) |
263 | |
264 | #define NOTFLAG(w) ( (w) == NEUTRAL ? GS_NOTNEUTRAL : \ |
265 | (w) == POSITIVE ? GS_NOTPOSITIVE : \ |
266 | (w) == NEGATIVE ? GS_NOTNEGATIVE : \ |
267 | 0 ) |
268 | |
269 | #define POSSIBLE(f,w) (!(state->flags[(f)] & NOTFLAG(w))) |
270 | |
271 | struct game_state { |
272 | int w, h, wh; |
273 | int *grid; /* size w*h, for cell state (pos/neg) */ |
274 | unsigned int *flags; /* size w*h */ |
275 | int solved, completed, numbered; |
276 | |
277 | struct game_common *common; /* domino layout never changes. */ |
278 | }; |
279 | |
280 | static void clear_state(game_state *ret) |
281 | { |
282 | int i; |
283 | |
284 | ret->solved = ret->completed = ret->numbered = 0; |
285 | |
286 | memset(ret->common->rowcount, 0, ret->h*3*sizeof(int)); |
287 | memset(ret->common->colcount, 0, ret->w*3*sizeof(int)); |
288 | |
289 | for (i = 0; i < ret->wh; i++) { |
290 | ret->grid[i] = EMPTY; |
291 | ret->flags[i] = 0; |
292 | ret->common->dominoes[i] = i; |
293 | } |
294 | } |
295 | |
296 | static game_state *new_state(int w, int h) |
297 | { |
298 | game_state *ret = snew(game_state); |
299 | |
300 | memset(ret, 0, sizeof(game_state)); |
301 | ret->w = w; |
302 | ret->h = h; |
303 | ret->wh = w*h; |
304 | |
305 | ret->grid = snewn(ret->wh, int); |
306 | ret->flags = snewn(ret->wh, unsigned int); |
307 | |
308 | ret->common = snew(struct game_common); |
309 | ret->common->refcount = 1; |
310 | |
311 | ret->common->dominoes = snewn(ret->wh, int); |
312 | ret->common->rowcount = snewn(ret->h*3, int); |
313 | ret->common->colcount = snewn(ret->w*3, int); |
314 | |
315 | clear_state(ret); |
316 | |
317 | return ret; |
318 | } |
319 | |
320 | static game_state *dup_game(game_state *src) |
321 | { |
322 | game_state *dest = snew(game_state); |
323 | |
324 | dest->w = src->w; |
325 | dest->h = src->h; |
326 | dest->wh = src->wh; |
327 | |
328 | dest->solved = src->solved; |
329 | dest->completed = src->completed; |
330 | dest->numbered = src->numbered; |
331 | |
332 | dest->common = src->common; |
333 | dest->common->refcount++; |
334 | |
335 | dest->grid = snewn(dest->wh, int); |
336 | memcpy(dest->grid, src->grid, dest->wh*sizeof(int)); |
337 | |
338 | dest->flags = snewn(dest->wh, unsigned int); |
339 | memcpy(dest->flags, src->flags, dest->wh*sizeof(unsigned int)); |
340 | |
341 | return dest; |
342 | } |
343 | |
344 | static void free_game(game_state *state) |
345 | { |
346 | state->common->refcount--; |
347 | if (state->common->refcount == 0) { |
348 | sfree(state->common->dominoes); |
349 | sfree(state->common->rowcount); |
350 | sfree(state->common->colcount); |
351 | sfree(state->common); |
352 | } |
353 | sfree(state->flags); |
354 | sfree(state->grid); |
355 | sfree(state); |
356 | } |
357 | |
358 | /* --------------------------------------------------------------- */ |
359 | /* Game generation and reading. */ |
360 | |
361 | /* For a game of size w*h the game description is: |
362 | * w-sized string of column + numbers (L-R), or '.' for none |
363 | * semicolon |
364 | * h-sized string of row + numbers (T-B), or '.' |
365 | * semicolon |
366 | * w-sized string of column - numbers (L-R), or '.' |
367 | * semicolon |
368 | * h-sized string of row - numbers (T-B), or '.' |
369 | * semicolon |
370 | * w*h-sized string of 'L', 'R', 'U', 'D' for domino associations, |
371 | * or '*' for a black singleton square. |
372 | * |
373 | * for a total length of 2w + 2h + wh + 4. |
374 | */ |
375 | |
376 | static char n2c(int num) { /* XXX cloned from singles.c */ |
377 | if (num == -1) |
378 | return '.'; |
379 | if (num < 10) |
380 | return '0' + num; |
381 | else if (num < 10+26) |
382 | return 'a' + num - 10; |
383 | else |
384 | return 'A' + num - 10 - 26; |
385 | return '?'; |
386 | } |
387 | |
388 | static int c2n(char c) { /* XXX cloned from singles.c */ |
4d6d1277 |
389 | if (isdigit((unsigned char)c)) |
72c00e19 |
390 | return (int)(c - '0'); |
391 | else if (c >= 'a' && c <= 'z') |
392 | return (int)(c - 'a' + 10); |
393 | else if (c >= 'A' && c <= 'Z') |
394 | return (int)(c - 'A' + 10 + 26); |
395 | return -1; |
396 | } |
397 | |
398 | static char *readrow(char *desc, int n, int *array, int off, const char **prob) |
399 | { |
400 | int i, num; |
401 | char c; |
402 | |
403 | for (i = 0; i < n; i++) { |
404 | c = *desc++; |
405 | if (c == 0) goto badchar; |
406 | if (c == '.') |
407 | num = -1; |
408 | else { |
409 | num = c2n(c); |
410 | if (num < 0) goto badchar; |
411 | } |
412 | array[i*3+off] = num; |
413 | } |
414 | c = *desc++; |
415 | if (c != ',') goto badchar; |
416 | return desc; |
417 | |
418 | badchar: |
419 | *prob = (c == 0) ? |
420 | "Game description too short" : |
421 | "Game description contained unexpected characters"; |
422 | return NULL; |
423 | } |
424 | |
425 | static game_state *new_game_int(game_params *params, char *desc, const char **prob) |
426 | { |
427 | game_state *state = new_state(params->w, params->h); |
428 | int x, y, idx, *count; |
429 | char c; |
430 | |
431 | *prob = NULL; |
432 | |
433 | /* top row, left-to-right */ |
434 | desc = readrow(desc, state->w, state->common->colcount, POSITIVE, prob); |
435 | if (*prob) goto done; |
436 | |
437 | /* left column, top-to-bottom */ |
438 | desc = readrow(desc, state->h, state->common->rowcount, POSITIVE, prob); |
439 | if (*prob) goto done; |
440 | |
441 | /* bottom row, left-to-right */ |
442 | desc = readrow(desc, state->w, state->common->colcount, NEGATIVE, prob); |
443 | if (*prob) goto done; |
444 | |
445 | /* right column, top-to-bottom */ |
446 | desc = readrow(desc, state->h, state->common->rowcount, NEGATIVE, prob); |
447 | if (*prob) goto done; |
448 | |
449 | /* Add neutral counts (== size - pos - neg) to columns and rows. |
450 | * Any singleton cells will just be treated as permanently neutral. */ |
451 | count = state->common->colcount; |
452 | for (x = 0; x < state->w; x++) { |
453 | if (count[x*3+POSITIVE] < 0 || count[x*3+NEGATIVE] < 0) |
454 | count[x*3+NEUTRAL] = -1; |
455 | else { |
456 | count[x*3+NEUTRAL] = |
457 | state->h - count[x*3+POSITIVE] - count[x*3+NEGATIVE]; |
458 | if (count[x*3+NEUTRAL] < 0) { |
459 | *prob = "Column counts inconsistent"; |
460 | goto done; |
461 | } |
462 | } |
463 | } |
464 | count = state->common->rowcount; |
465 | for (y = 0; y < state->h; y++) { |
466 | if (count[y*3+POSITIVE] < 0 || count[y*3+NEGATIVE] < 0) |
467 | count[y*3+NEUTRAL] = -1; |
468 | else { |
469 | count[y*3+NEUTRAL] = |
470 | state->w - count[y*3+POSITIVE] - count[y*3+NEGATIVE]; |
471 | if (count[y*3+NEUTRAL] < 0) { |
472 | *prob = "Row counts inconsistent"; |
473 | goto done; |
474 | } |
475 | } |
476 | } |
477 | |
478 | |
479 | for (y = 0; y < state->h; y++) { |
480 | for (x = 0; x < state->w; x++) { |
481 | idx = y*state->w + x; |
482 | nextchar: |
483 | c = *desc++; |
484 | |
485 | if (c == 'L') /* this square is LHS of a domino */ |
486 | state->common->dominoes[idx] = idx+1; |
487 | else if (c == 'R') /* ... RHS of a domino */ |
488 | state->common->dominoes[idx] = idx-1; |
489 | else if (c == 'T') /* ... top of a domino */ |
490 | state->common->dominoes[idx] = idx+state->w; |
491 | else if (c == 'B') /* ... bottom of a domino */ |
492 | state->common->dominoes[idx] = idx-state->w; |
493 | else if (c == '*') /* singleton */ |
494 | state->common->dominoes[idx] = idx; |
495 | else if (c == ',') /* spacer, ignore */ |
496 | goto nextchar; |
497 | else goto badchar; |
498 | } |
499 | } |
500 | |
501 | /* Check dominoes as input are sensibly consistent |
502 | * (i.e. each end points to the other) */ |
503 | for (idx = 0; idx < state->wh; idx++) { |
504 | if (state->common->dominoes[idx] < 0 || |
505 | state->common->dominoes[idx] > state->wh || |
506 | state->common->dominoes[state->common->dominoes[idx]] != idx) { |
507 | *prob = "Domino descriptions inconsistent"; |
508 | goto done; |
509 | } |
510 | if (state->common->dominoes[idx] == idx) { |
511 | state->grid[idx] = NEUTRAL; |
512 | state->flags[idx] |= GS_SET; |
513 | } |
514 | } |
515 | /* Success. */ |
516 | state->numbered = 1; |
517 | goto done; |
518 | |
519 | badchar: |
520 | *prob = (c == 0) ? |
521 | "Game description too short" : |
522 | "Game description contained unexpected characters"; |
523 | |
524 | done: |
525 | if (*prob) { |
526 | free_game(state); |
527 | return NULL; |
528 | } |
529 | return state; |
530 | } |
531 | |
532 | static char *validate_desc(game_params *params, char *desc) |
533 | { |
534 | const char *prob; |
535 | game_state *st = new_game_int(params, desc, &prob); |
536 | if (!st) return (char*)prob; |
537 | free_game(st); |
538 | return NULL; |
539 | } |
540 | |
541 | static game_state *new_game(midend *me, game_params *params, char *desc) |
542 | { |
543 | const char *prob; |
544 | game_state *st = new_game_int(params, desc, &prob); |
545 | assert(st); |
546 | return st; |
547 | } |
548 | |
549 | static char *generate_desc(game_state *new) |
550 | { |
551 | int x, y, idx, other, w = new->w, h = new->h; |
552 | char *desc = snewn(new->wh + 2*(w + h) + 5, char), *p = desc; |
553 | |
554 | for (x = 0; x < w; x++) *p++ = n2c(new->common->colcount[x*3+POSITIVE]); |
555 | *p++ = ','; |
556 | for (y = 0; y < h; y++) *p++ = n2c(new->common->rowcount[y*3+POSITIVE]); |
557 | *p++ = ','; |
558 | |
559 | for (x = 0; x < w; x++) *p++ = n2c(new->common->colcount[x*3+NEGATIVE]); |
560 | *p++ = ','; |
561 | for (y = 0; y < h; y++) *p++ = n2c(new->common->rowcount[y*3+NEGATIVE]); |
562 | *p++ = ','; |
563 | |
564 | for (y = 0; y < h; y++) { |
565 | for (x = 0; x < w; x++) { |
566 | idx = y*w + x; |
567 | other = new->common->dominoes[idx]; |
568 | |
569 | if (other == idx) *p++ = '*'; |
570 | else if (other == idx+1) *p++ = 'L'; |
571 | else if (other == idx-1) *p++ = 'R'; |
572 | else if (other == idx+w) *p++ = 'T'; |
573 | else if (other == idx-w) *p++ = 'B'; |
574 | else assert(!"mad domino orientation"); |
575 | } |
576 | } |
577 | *p = '\0'; |
578 | |
579 | return desc; |
580 | } |
581 | |
582 | static void game_text_hborder(game_state *state, char **p_r) |
583 | { |
584 | char *p = *p_r; |
585 | int x; |
586 | |
587 | *p++ = ' '; |
588 | *p++ = '+'; |
589 | for (x = 0; x < state->w*2-1; x++) *p++ = '-'; |
590 | *p++ = '+'; |
591 | *p++ = '\n'; |
592 | |
593 | *p_r = p; |
594 | } |
595 | |
596 | static int game_can_format_as_text_now(game_params *params) |
597 | { |
598 | return TRUE; |
599 | } |
600 | |
601 | static char *game_text_format(game_state *state) |
602 | { |
603 | int len, x, y, i; |
604 | char *ret, *p; |
605 | |
606 | len = ((state->w*2)+4) * ((state->h*2)+4) + 2; |
607 | p = ret = snewn(len, char); |
608 | |
609 | /* top row: '+' then column totals for plus. */ |
610 | *p++ = '+'; |
611 | for (x = 0; x < state->w; x++) { |
612 | *p++ = ' '; |
613 | *p++ = n2c(state->common->colcount[x*3+POSITIVE]); |
614 | } |
615 | *p++ = '\n'; |
616 | |
617 | /* top border. */ |
618 | game_text_hborder(state, &p); |
619 | |
620 | for (y = 0; y < state->h; y++) { |
621 | *p++ = n2c(state->common->rowcount[y*3+POSITIVE]); |
622 | *p++ = '|'; |
623 | for (x = 0; x < state->w; x++) { |
624 | i = y*state->w+x; |
625 | *p++ = state->common->dominoes[i] == i ? '#' : |
626 | state->grid[i] == POSITIVE ? '+' : |
627 | state->grid[i] == NEGATIVE ? '-' : |
628 | state->flags[i] & GS_SET ? '*' : ' '; |
629 | if (x < (state->w-1)) |
630 | *p++ = state->common->dominoes[i] == i+1 ? ' ' : '|'; |
631 | } |
632 | *p++ = '|'; |
633 | *p++ = n2c(state->common->rowcount[y*3+NEGATIVE]); |
634 | *p++ = '\n'; |
635 | |
636 | if (y < (state->h-1)) { |
637 | *p++ = ' '; |
638 | *p++ = '|'; |
639 | for (x = 0; x < state->w; x++) { |
640 | i = y*state->w+x; |
641 | *p++ = state->common->dominoes[i] == i+state->w ? ' ' : '-'; |
642 | if (x < (state->w-1)) |
643 | *p++ = '+'; |
644 | } |
645 | *p++ = '|'; |
646 | *p++ = '\n'; |
647 | } |
648 | } |
649 | |
650 | /* bottom border. */ |
651 | game_text_hborder(state, &p); |
652 | |
653 | /* bottom row: column totals for minus then '-'. */ |
654 | *p++ = ' '; |
655 | for (x = 0; x < state->w; x++) { |
656 | *p++ = ' '; |
657 | *p++ = n2c(state->common->colcount[x*3+NEGATIVE]); |
658 | } |
659 | *p++ = ' '; |
660 | *p++ = '-'; |
661 | *p++ = '\n'; |
662 | *p++ = '\0'; |
663 | |
664 | return ret; |
665 | } |
666 | |
667 | static void game_debug(game_state *state, const char *desc) |
668 | { |
669 | char *fmt = game_text_format(state); |
670 | debug(("%s:\n%s\n", desc, fmt)); |
671 | sfree(fmt); |
672 | } |
673 | |
674 | enum { ROW, COLUMN }; |
675 | |
676 | typedef struct rowcol { |
677 | int i, di, n, roworcol, num; |
678 | int *targets; |
679 | const char *name; |
680 | } rowcol; |
681 | |
682 | static rowcol mkrowcol(game_state *state, int num, int roworcol) |
683 | { |
684 | rowcol rc; |
685 | |
686 | rc.roworcol = roworcol; |
687 | rc.num = num; |
688 | |
689 | if (roworcol == ROW) { |
690 | rc.i = num * state->w; |
691 | rc.di = 1; |
692 | rc.n = state->w; |
693 | rc.targets = &(state->common->rowcount[num*3]); |
694 | rc.name = "row"; |
695 | } else if (roworcol == COLUMN) { |
696 | rc.i = num; |
697 | rc.di = state->w; |
698 | rc.n = state->h; |
699 | rc.targets = &(state->common->colcount[num*3]); |
700 | rc.name = "column"; |
701 | } else { |
702 | assert(!"unknown roworcol"); |
703 | } |
704 | return rc; |
705 | } |
706 | |
707 | static int count_rowcol(game_state *state, int num, int roworcol, int which) |
708 | { |
709 | int i, count = 0; |
710 | rowcol rc = mkrowcol(state, num, roworcol); |
711 | |
712 | for (i = 0; i < rc.n; i++, rc.i += rc.di) { |
713 | if (which < 0) { |
714 | if (state->grid[rc.i] == EMPTY && |
715 | !(state->flags[rc.i] & GS_SET)) |
716 | count++; |
717 | } else if (state->grid[rc.i] == which) |
718 | count++; |
719 | } |
720 | return count; |
721 | } |
722 | |
723 | static void check_rowcol(game_state *state, int num, int roworcol, int which, |
724 | int *wrong, int *incomplete) |
725 | { |
726 | int count, target = mkrowcol(state, num, roworcol).targets[which]; |
727 | |
728 | if (target == -1) return; /* no number to check against. */ |
729 | |
730 | count = count_rowcol(state, num, roworcol, which); |
731 | if (count < target) *incomplete = 1; |
732 | if (count > target) *wrong = 1; |
733 | } |
734 | |
735 | static int check_completion(game_state *state) |
736 | { |
737 | int i, j, x, y, idx, w = state->w, h = state->h; |
738 | int which = POSITIVE, wrong = 0, incomplete = 0; |
739 | |
740 | /* Check row and column counts for magnets. */ |
741 | for (which = POSITIVE, j = 0; j < 2; which = OPPOSITE(which), j++) { |
742 | for (i = 0; i < w; i++) |
743 | check_rowcol(state, i, COLUMN, which, &wrong, &incomplete); |
744 | |
745 | for (i = 0; i < h; i++) |
746 | check_rowcol(state, i, ROW, which, &wrong, &incomplete); |
747 | } |
748 | /* Check each domino has been filled, and that we don't have |
749 | * touching identical terminals. */ |
750 | for (i = 0; i < state->wh; i++) state->flags[i] &= ~GS_ERROR; |
751 | for (x = 0; x < w; x++) { |
752 | for (y = 0; y < h; y++) { |
753 | idx = y*w + x; |
754 | if (state->common->dominoes[idx] == idx) |
755 | continue; /* no domino here */ |
756 | |
757 | if (!(state->flags[idx] & GS_SET)) |
758 | incomplete = 1; |
759 | |
760 | which = state->grid[idx]; |
761 | if (which != NEUTRAL) { |
762 | #define CHECK(xx,yy) do { \ |
763 | if (INGRID(state,xx,yy) && \ |
764 | (state->grid[(yy)*w+(xx)] == which)) { \ |
765 | wrong = 1; \ |
766 | state->flags[(yy)*w+(xx)] |= GS_ERROR; \ |
767 | state->flags[y*w+x] |= GS_ERROR; \ |
768 | } \ |
769 | } while(0) |
770 | CHECK(x,y-1); |
771 | CHECK(x,y+1); |
772 | CHECK(x-1,y); |
773 | CHECK(x+1,y); |
774 | #undef CHECK |
775 | } |
776 | } |
777 | } |
778 | return wrong ? -1 : incomplete ? 0 : 1; |
779 | } |
780 | |
781 | static const int dx[4] = {-1, 1, 0, 0}; |
782 | static const int dy[4] = {0, 0, -1, 1}; |
783 | |
784 | static void solve_clearflags(game_state *state) |
785 | { |
786 | int i; |
787 | |
788 | for (i = 0; i < state->wh; i++) { |
789 | state->flags[i] &= ~GS_NOTMASK; |
790 | if (state->common->dominoes[i] != i) |
791 | state->flags[i] &= ~GS_SET; |
792 | } |
793 | } |
794 | |
795 | /* Knowing a given cell cannot be a certain colour also tells us |
796 | * something about the other cell in that domino. */ |
797 | static int solve_unflag(game_state *state, int i, int which, |
798 | const char *why, rowcol *rc) |
799 | { |
800 | int ii, ret = 0; |
801 | #if defined DEBUGGING || defined STANDALONE_SOLVER |
802 | int w = state->w; |
803 | #endif |
804 | |
805 | assert(i >= 0 && i < state->wh); |
806 | ii = state->common->dominoes[i]; |
807 | if (ii == i) return 0; |
808 | |
809 | if (rc) |
810 | debug(("solve_unflag: (%d,%d) for %s %d", i%w, i/w, rc->name, rc->num)); |
811 | |
812 | if ((state->flags[i] & GS_SET) && (state->grid[i] == which)) { |
813 | debug(("solve_unflag: (%d,%d) already %s, cannot unflag (for %s).", |
814 | i%w, i/w, NAME(which), why)); |
815 | return -1; |
816 | } |
817 | if ((state->flags[ii] & GS_SET) && (state->grid[ii] == OPPOSITE(which))) { |
818 | debug(("solve_unflag: (%d,%d) opposite already %s, cannot unflag (for %s).", |
819 | ii%w, ii/w, NAME(OPPOSITE(which)), why)); |
820 | return -1; |
821 | } |
822 | if (POSSIBLE(i, which)) { |
823 | state->flags[i] |= NOTFLAG(which); |
824 | ret++; |
825 | debug(("solve_unflag: (%d,%d) CANNOT be %s (%s)", |
826 | i%w, i/w, NAME(which), why)); |
827 | } |
828 | if (POSSIBLE(ii, OPPOSITE(which))) { |
829 | state->flags[ii] |= NOTFLAG(OPPOSITE(which)); |
830 | ret++; |
831 | debug(("solve_unflag: (%d,%d) CANNOT be %s (%s, other half)", |
832 | ii%w, ii/w, NAME(OPPOSITE(which)), why)); |
833 | } |
834 | #ifdef STANDALONE_SOLVER |
835 | if (verbose && ret) { |
836 | printf("(%d,%d)", i%w, i/w); |
837 | if (rc) printf(" in %s %d", rc->name, rc->num); |
838 | printf(" cannot be %s (%s); opposite (%d,%d) not %s.\n", |
839 | NAME(which), why, ii%w, ii/w, NAME(OPPOSITE(which))); |
840 | } |
841 | #endif |
842 | return ret; |
843 | } |
844 | |
845 | static int solve_unflag_surrounds(game_state *state, int i, int which) |
846 | { |
847 | int x = i%state->w, y = i/state->w, xx, yy, j, ii; |
848 | |
849 | assert(INGRID(state, x, y)); |
850 | |
851 | for (j = 0; j < 4; j++) { |
852 | xx = x+dx[j]; yy = y+dy[j]; |
853 | if (!INGRID(state, xx, yy)) continue; |
854 | |
855 | ii = yy*state->w+xx; |
856 | if (solve_unflag(state, ii, which, "adjacent to set cell", NULL) < 0) |
857 | return -1; |
858 | } |
859 | return 0; |
860 | } |
861 | |
862 | /* Sets a cell to a particular colour, and also perform other |
863 | * housekeeping around that. */ |
864 | static int solve_set(game_state *state, int i, int which, |
865 | const char *why, rowcol *rc) |
866 | { |
867 | int ii; |
868 | #if defined DEBUGGING || defined STANDALONE_SOLVER |
869 | int w = state->w; |
870 | #endif |
871 | |
872 | ii = state->common->dominoes[i]; |
873 | |
874 | if (state->flags[i] & GS_SET) { |
875 | if (state->grid[i] == which) { |
876 | return 0; /* was already set and held, do nothing. */ |
877 | } else { |
878 | debug(("solve_set: (%d,%d) is held and %s, cannot set to %s", |
879 | i%w, i/w, NAME(state->grid[i]), NAME(which))); |
880 | return -1; |
881 | } |
882 | } |
883 | if ((state->flags[ii] & GS_SET) && state->grid[ii] != OPPOSITE(which)) { |
884 | debug(("solve_set: (%d,%d) opposite is held and %s, cannot set to %s", |
885 | ii%w, ii/w, NAME(state->grid[ii]), NAME(OPPOSITE(which)))); |
886 | return -1; |
887 | } |
888 | if (!POSSIBLE(i, which)) { |
889 | debug(("solve_set: (%d,%d) NOT %s, cannot set.", i%w, i/w, NAME(which))); |
890 | return -1; |
891 | } |
892 | if (!POSSIBLE(ii, OPPOSITE(which))) { |
893 | debug(("solve_set: (%d,%d) NOT %s, cannot set (%d,%d).", |
894 | ii%w, ii/w, NAME(OPPOSITE(which)), i%w, i/w)); |
895 | return -1; |
896 | } |
897 | |
898 | #ifdef STANDALONE_SOLVER |
899 | if (verbose) { |
900 | printf("(%d,%d)", i%w, i/w); |
901 | if (rc) printf(" in %s %d", rc->name, rc->num); |
902 | printf(" set to %s (%s), opposite (%d,%d) set to %s.\n", |
903 | NAME(which), why, ii%w, ii/w, NAME(OPPOSITE(which))); |
904 | } |
905 | #endif |
906 | if (rc) |
907 | debug(("solve_set: (%d,%d) for %s %d", i%w, i/w, rc->name, rc->num)); |
908 | debug(("solve_set: (%d,%d) setting to %s (%s), surrounds first:", |
909 | i%w, i/w, NAME(which), why)); |
910 | |
911 | if (which != NEUTRAL) { |
912 | if (solve_unflag_surrounds(state, i, which) < 0) |
913 | return -1; |
914 | if (solve_unflag_surrounds(state, ii, OPPOSITE(which)) < 0) |
915 | return -1; |
916 | } |
917 | |
918 | state->grid[i] = which; |
919 | state->grid[ii] = OPPOSITE(which); |
920 | |
921 | state->flags[i] |= GS_SET; |
922 | state->flags[ii] |= GS_SET; |
923 | |
924 | debug(("solve_set: (%d,%d) set to %s (%s)", i%w, i/w, NAME(which), why)); |
925 | |
926 | return 1; |
927 | } |
928 | |
929 | /* counts should be int[4]. */ |
930 | static void solve_counts(game_state *state, rowcol rc, int *counts, int *unset) |
931 | { |
932 | int i, j, which; |
933 | |
934 | assert(counts); |
935 | for (i = 0; i < 4; i++) { |
936 | counts[i] = 0; |
937 | if (unset) unset[i] = 0; |
938 | } |
939 | |
940 | for (i = rc.i, j = 0; j < rc.n; i += rc.di, j++) { |
941 | if (state->flags[i] & GS_SET) { |
942 | assert(state->grid[i] < 3); |
943 | counts[state->grid[i]]++; |
944 | } else if (unset) { |
945 | for (which = 0; which <= 2; which++) { |
946 | if (POSSIBLE(i, which)) |
947 | unset[which]++; |
948 | } |
949 | } |
950 | } |
951 | } |
952 | |
953 | static int solve_checkfull(game_state *state, rowcol rc, int *counts) |
954 | { |
955 | int starti = rc.i, j, which, didsth = 0, target; |
956 | int unset[4]; |
957 | |
958 | assert(state->numbered); /* only useful (should only be called) if numbered. */ |
959 | |
960 | solve_counts(state, rc, counts, unset); |
961 | |
962 | for (which = 0; which <= 2; which++) { |
963 | target = rc.targets[which]; |
964 | if (target == -1) continue; |
965 | |
966 | /*debug(("%s %d for %s: target %d, count %d, unset %d", |
967 | rc.name, rc.num, NAME(which), |
968 | target, counts[which], unset[which]));*/ |
969 | |
970 | if (target < counts[which]) { |
971 | debug(("%s %d has too many (%d) %s squares (target %d), impossible!", |
972 | rc.name, rc.num, counts[which], NAME(which), target)); |
973 | return -1; |
974 | } |
975 | if (target == counts[which]) { |
976 | /* We have the correct no. of the colour in this row/column |
977 | * already; unflag all the rest. */ |
978 | for (rc.i = starti, j = 0; j < rc.n; rc.i += rc.di, j++) { |
979 | if (state->flags[rc.i] & GS_SET) continue; |
980 | if (!POSSIBLE(rc.i, which)) continue; |
981 | |
982 | if (solve_unflag(state, rc.i, which, "row/col full", &rc) < 0) |
983 | return -1; |
984 | didsth = 1; |
985 | } |
986 | } else if ((target - counts[which]) == unset[which]) { |
987 | /* We need all the remaining unset squares for this colour; |
988 | * set them all. */ |
989 | for (rc.i = starti, j = 0; j < rc.n; rc.i += rc.di, j++) { |
990 | if (state->flags[rc.i] & GS_SET) continue; |
991 | if (!POSSIBLE(rc.i, which)) continue; |
992 | |
993 | if (solve_set(state, rc.i, which, "row/col needs all unset", &rc) < 0) |
994 | return -1; |
995 | didsth = 1; |
996 | } |
997 | } |
998 | } |
999 | return didsth; |
1000 | } |
1001 | |
1002 | static int solve_startflags(game_state *state) |
1003 | { |
1004 | int x, y, i; |
1005 | |
1006 | for (x = 0; x < state->w; x++) { |
1007 | for (y = 0; y < state->h; y++) { |
1008 | i = y*state->w+x; |
1009 | if (state->common->dominoes[i] == i) continue; |
1010 | if (state->grid[i] != NEUTRAL || |
1011 | state->flags[i] & GS_SET) { |
1012 | if (solve_set(state, i, state->grid[i], "initial set-and-hold", NULL) < 0) |
1013 | return -1; |
1014 | } |
1015 | } |
1016 | } |
1017 | return 0; |
1018 | } |
1019 | |
1020 | typedef int (*rowcolfn)(game_state *state, rowcol rc, int *counts); |
1021 | |
1022 | static int solve_rowcols(game_state *state, rowcolfn fn) |
1023 | { |
1024 | int x, y, didsth = 0, ret; |
1025 | rowcol rc; |
1026 | int counts[4]; |
1027 | |
1028 | for (x = 0; x < state->w; x++) { |
1029 | rc = mkrowcol(state, x, COLUMN); |
1030 | solve_counts(state, rc, counts, NULL); |
1031 | |
1032 | ret = fn(state, rc, counts); |
1033 | if (ret < 0) return ret; |
1034 | didsth += ret; |
1035 | } |
1036 | for (y = 0; y < state->h; y++) { |
1037 | rc = mkrowcol(state, y, ROW); |
1038 | solve_counts(state, rc, counts, NULL); |
1039 | |
1040 | ret = fn(state, rc, counts); |
1041 | if (ret < 0) return ret; |
1042 | didsth += ret; |
1043 | } |
1044 | return didsth; |
1045 | } |
1046 | |
1047 | static int solve_force(game_state *state) |
1048 | { |
1049 | int x, y, i, which, didsth = 0; |
1050 | unsigned long f; |
1051 | |
1052 | for (i = 0; i < state->wh; i++) { |
1053 | if (state->flags[i] & GS_SET) continue; |
1054 | if (state->common->dominoes[i] == i) continue; |
1055 | |
1056 | f = state->flags[i] & GS_NOTMASK; |
1057 | which = -1; |
1058 | if (f == (GS_NOTPOSITIVE|GS_NOTNEGATIVE)) |
1059 | which = NEUTRAL; |
1060 | if (f == (GS_NOTPOSITIVE|GS_NOTNEUTRAL)) |
1061 | which = NEGATIVE; |
1062 | if (f == (GS_NOTNEGATIVE|GS_NOTNEUTRAL)) |
1063 | which = POSITIVE; |
1064 | if (which != -1) { |
1065 | x = i%state->w; y = i/state->w; |
1066 | if (solve_set(state, i, which, "forced by flags", NULL) < 0) |
1067 | return -1; |
1068 | didsth = 1; |
1069 | } |
1070 | } |
1071 | return didsth; |
1072 | } |
1073 | |
1074 | static int solve_neither(game_state *state) |
1075 | { |
1076 | int x, y, i, j, didsth = 0; |
1077 | |
1078 | for (i = 0; i < state->wh; i++) { |
1079 | if (state->flags[i] & GS_SET) continue; |
1080 | j = state->common->dominoes[i]; |
1081 | if (i == j) continue; |
1082 | |
1083 | if (((state->flags[i] & GS_NOTPOSITIVE) && |
1084 | (state->flags[j] & GS_NOTPOSITIVE)) || |
1085 | ((state->flags[i] & GS_NOTNEGATIVE) && |
1086 | (state->flags[j] & GS_NOTNEGATIVE))) { |
1087 | x = i%state->w; y = i/state->w; |
1088 | if (solve_set(state, i, NEUTRAL, "neither tile magnet", NULL) < 0) |
1089 | return -1; |
1090 | didsth = 1; |
1091 | } |
1092 | } |
1093 | return didsth; |
1094 | } |
1095 | |
1096 | static int solve_advancedfull(game_state *state, rowcol rc, int *counts) |
1097 | { |
1098 | int i, j, nfound = 0, clearpos = 0, clearneg = 0, ret = 0; |
1099 | |
1100 | /* For this row/col, look for a domino entirely within the row where |
1101 | * both ends can only be + or - (but isn't held). |
1102 | * The +/- counts can thus be decremented by 1 each, and the 'unset' |
1103 | * count by 2. |
1104 | * |
1105 | * Once that's done for all such dominoes (and they're marked), try |
1106 | * and made usual deductions about rest of the row based on new totals. */ |
1107 | |
1108 | if (rc.targets[POSITIVE] == -1 && rc.targets[NEGATIVE] == -1) |
1109 | return 0; /* don't have a target for either colour, nothing to do. */ |
1110 | if ((rc.targets[POSITIVE] >= 0 && counts[POSITIVE] == rc.targets[POSITIVE]) && |
1111 | (rc.targets[NEGATIVE] >= 0 && counts[NEGATIVE] == rc.targets[NEGATIVE])) |
1112 | return 0; /* both colours are full up already, nothing to do. */ |
1113 | |
1114 | for (i = rc.i, j = 0; j < rc.n; i += rc.di, j++) |
1115 | state->flags[i] &= ~GS_MARK; |
1116 | |
1117 | for (i = rc.i, j = 0; j < rc.n; i += rc.di, j++) { |
1118 | if (state->flags[i] & GS_SET) continue; |
1119 | |
1120 | /* We're looking for a domino in our row/col, thus if |
1121 | * dominoes[i] -> i+di we've found one. */ |
1122 | if (state->common->dominoes[i] != i+rc.di) continue; |
1123 | |
1124 | /* We need both squares of this domino to be either + or - |
1125 | * (i.e. both NOTNEUTRAL only). */ |
1126 | if (((state->flags[i] & GS_NOTMASK) != GS_NOTNEUTRAL) || |
1127 | ((state->flags[i+rc.di] & GS_NOTMASK) != GS_NOTNEUTRAL)) |
1128 | continue; |
1129 | |
1130 | debug(("Domino in %s %d at (%d,%d) must be polarised.", |
1131 | rc.name, rc.num, i%state->w, i/state->w)); |
1132 | state->flags[i] |= GS_MARK; |
1133 | state->flags[i+rc.di] |= GS_MARK; |
1134 | nfound++; |
1135 | } |
1136 | if (nfound == 0) return 0; |
1137 | |
1138 | /* nfound is #dominoes we matched, which will all be marked. */ |
1139 | counts[POSITIVE] += nfound; |
1140 | counts[NEGATIVE] += nfound; |
1141 | |
1142 | if (rc.targets[POSITIVE] >= 0 && counts[POSITIVE] == rc.targets[POSITIVE]) { |
1143 | debug(("%s %d has now filled POSITIVE:", rc.name, rc.num)); |
1144 | clearpos = 1; |
1145 | } |
1146 | if (rc.targets[NEGATIVE] >= 0 && counts[NEGATIVE] == rc.targets[NEGATIVE]) { |
1147 | debug(("%s %d has now filled NEGATIVE:", rc.name, rc.num)); |
1148 | clearneg = 1; |
1149 | } |
1150 | |
1151 | if (!clearpos && !clearneg) return 0; |
1152 | |
1153 | for (i = rc.i, j = 0; j < rc.n; i += rc.di, j++) { |
1154 | if (state->flags[i] & GS_SET) continue; |
1155 | if (state->flags[i] & GS_MARK) continue; |
1156 | |
1157 | if (clearpos && !(state->flags[i] & GS_NOTPOSITIVE)) { |
1158 | if (solve_unflag(state, i, POSITIVE, "row/col full (+ve) [tricky]", &rc) < 0) |
1159 | return -1; |
1160 | ret++; |
1161 | } |
1162 | if (clearneg && !(state->flags[i] & GS_NOTNEGATIVE)) { |
1163 | if (solve_unflag(state, i, NEGATIVE, "row/col full (-ve) [tricky]", &rc) < 0) |
1164 | return -1; |
1165 | ret++; |
1166 | } |
1167 | } |
1168 | |
1169 | return ret; |
1170 | } |
1171 | |
1172 | /* If we only have one neutral still to place on a row/column then no |
1173 | dominoes entirely in that row/column can be neutral. */ |
1174 | static int solve_nonneutral(game_state *state, rowcol rc, int *counts) |
1175 | { |
1176 | int i, j, ret = 0; |
1177 | |
1178 | if (rc.targets[NEUTRAL] != counts[NEUTRAL]+1) |
1179 | return 0; |
1180 | |
1181 | for (i = rc.i, j = 0; j < rc.n; i += rc.di, j++) { |
1182 | if (state->flags[i] & GS_SET) continue; |
1183 | if (state->common->dominoes[i] != i+rc.di) continue; |
1184 | |
1185 | if (!(state->flags[i] & GS_NOTNEUTRAL)) { |
1186 | if (solve_unflag(state, i, NEUTRAL, "single neutral in row/col [tricky]", &rc) < 0) |
1187 | return -1; |
1188 | ret++; |
1189 | } |
1190 | } |
1191 | return ret; |
1192 | } |
1193 | |
1194 | /* If we need to fill all unfilled cells with +-, and we need 1 more of |
1195 | * one than the other, and we have a single odd-numbered region of unfilled |
1196 | * cells, that odd-numbered region must start and end with the extra number. */ |
1197 | static int solve_oddlength(game_state *state, rowcol rc, int *counts) |
1198 | { |
1199 | int i, j, ret = 0, extra, tpos, tneg; |
1200 | int start = -1, length = 0, inempty = 0, startodd = -1; |
1201 | |
1202 | /* need zero neutral cells still to find... */ |
1203 | if (rc.targets[NEUTRAL] != counts[NEUTRAL]) |
1204 | return 0; |
1205 | |
1206 | /* ...and #positive and #negative to differ by one. */ |
1207 | tpos = rc.targets[POSITIVE] - counts[POSITIVE]; |
1208 | tneg = rc.targets[NEGATIVE] - counts[NEGATIVE]; |
1209 | if (tpos == tneg+1) |
1210 | extra = POSITIVE; |
1211 | else if (tneg == tpos+1) |
1212 | extra = NEGATIVE; |
1213 | else return 0; |
1214 | |
1215 | for (i = rc.i, j = 0; j < rc.n; i += rc.di, j++) { |
1216 | if (state->flags[i] & GS_SET) { |
1217 | if (inempty) { |
1218 | if (length % 2) { |
1219 | /* we've just finished an odd-length section. */ |
1220 | if (startodd != -1) goto twoodd; |
1221 | startodd = start; |
1222 | } |
1223 | inempty = 0; |
1224 | } |
1225 | } else { |
1226 | if (inempty) |
1227 | length++; |
1228 | else { |
1229 | start = i; |
1230 | length = 1; |
1231 | inempty = 1; |
1232 | } |
1233 | } |
1234 | } |
1235 | if (inempty && (length % 2)) { |
1236 | if (startodd != -1) goto twoodd; |
1237 | startodd = start; |
1238 | } |
1239 | if (startodd != -1) |
1240 | ret = solve_set(state, startodd, extra, "odd-length section start", &rc); |
1241 | |
1242 | return ret; |
1243 | |
1244 | twoodd: |
1245 | debug(("%s %d has >1 odd-length sections, starting at %d,%d and %d,%d.", |
1246 | rc.name, rc.num, |
1247 | startodd%state->w, startodd/state->w, |
1248 | start%state->w, start/state->w)); |
1249 | return 0; |
1250 | } |
1251 | |
1252 | /* Count the number of remaining empty dominoes in any row/col. |
1253 | * If that number is equal to the #remaining positive, |
1254 | * or to the #remaining negative, no empty cells can be neutral. */ |
1255 | static int solve_countdominoes_neutral(game_state *state, rowcol rc, int *counts) |
1256 | { |
1257 | int i, j, ndom = 0, nonn = 0, ret = 0; |
1258 | |
1259 | if ((rc.targets[POSITIVE] == -1) && (rc.targets[NEGATIVE] == -1)) |
1260 | return 0; /* need at least one target to compare. */ |
1261 | |
1262 | for (i = rc.i, j = 0; j < rc.n; i += rc.di, j++) { |
1263 | if (state->flags[i] & GS_SET) continue; |
1264 | assert(state->grid[i] == EMPTY); |
1265 | |
1266 | /* Skip solo cells, or second cell in domino. */ |
1267 | if ((state->common->dominoes[i] == i) || |
1268 | (state->common->dominoes[i] == i-rc.di)) |
1269 | continue; |
1270 | |
1271 | ndom++; |
1272 | } |
1273 | |
1274 | if ((rc.targets[POSITIVE] != -1) && |
1275 | (rc.targets[POSITIVE]-counts[POSITIVE] == ndom)) |
1276 | nonn = 1; |
1277 | if ((rc.targets[NEGATIVE] != -1) && |
1278 | (rc.targets[NEGATIVE]-counts[NEGATIVE] == ndom)) |
1279 | nonn = 1; |
1280 | |
1281 | if (!nonn) return 0; |
1282 | |
1283 | for (i = rc.i, j = 0; j < rc.n; i += rc.di, j++) { |
1284 | if (state->flags[i] & GS_SET) continue; |
1285 | |
1286 | if (!(state->flags[i] & GS_NOTNEUTRAL)) { |
1287 | if (solve_unflag(state, i, NEUTRAL, "all dominoes +/- [tricky]", &rc) < 0) |
1288 | return -1; |
1289 | ret++; |
1290 | } |
1291 | } |
1292 | return ret; |
1293 | } |
1294 | |
1295 | static int solve_domino_count(game_state *state, rowcol rc, int i, int which) |
1296 | { |
1297 | int nposs = 0; |
1298 | |
1299 | /* Skip solo cells or 2nd in domino. */ |
1300 | if ((state->common->dominoes[i] == i) || |
1301 | (state->common->dominoes[i] == i-rc.di)) |
1302 | return 0; |
1303 | |
1304 | if (state->flags[i] & GS_SET) |
1305 | return 0; |
1306 | |
1307 | if (POSSIBLE(i, which)) |
1308 | nposs++; |
1309 | |
1310 | if (state->common->dominoes[i] == i+rc.di) { |
1311 | /* second cell of domino is on our row: test that too. */ |
1312 | if (POSSIBLE(i+rc.di, which)) |
1313 | nposs++; |
1314 | } |
1315 | return nposs; |
1316 | } |
1317 | |
1318 | /* Count number of dominoes we could put each of + and - into. If it is equal |
1319 | * to the #left, any domino we can only put + or - in one cell of must have it. */ |
1320 | static int solve_countdominoes_nonneutral(game_state *state, rowcol rc, int *counts) |
1321 | { |
1322 | int which, w, i, j, ndom = 0, didsth = 0, toset; |
1323 | |
1324 | for (which = POSITIVE, w = 0; w < 2; which = OPPOSITE(which), w++) { |
1325 | if (rc.targets[which] == -1) continue; |
1326 | |
1327 | for (i = rc.i, j = 0; j < rc.n; i += rc.di, j++) { |
1328 | if (solve_domino_count(state, rc, i, which) > 0) |
1329 | ndom++; |
1330 | } |
1331 | |
1332 | if ((rc.targets[which] - counts[which]) != ndom) |
1333 | continue; |
1334 | |
1335 | for (i = rc.i, j = 0; j < rc.n; i += rc.di, j++) { |
1336 | if (solve_domino_count(state, rc, i, which) == 1) { |
1337 | if (POSSIBLE(i, which)) |
1338 | toset = i; |
1339 | else { |
1340 | /* paranoia, should have been checked by solve_domino_count. */ |
1341 | assert(state->common->dominoes[i] == i+rc.di); |
1342 | assert(POSSIBLE(i+rc.di, which)); |
1343 | toset = i+rc.di; |
1344 | } |
1345 | if (solve_set(state, toset, which, "all empty dominoes need +/- [tricky]", &rc) < 0) |
1346 | return -1; |
1347 | didsth++; |
1348 | } |
1349 | } |
1350 | } |
1351 | return didsth; |
1352 | } |
1353 | |
1354 | /* danger, evil macro. can't use the do { ... } while(0) trick because |
1355 | * the continue breaks. */ |
1356 | #define SOLVE_FOR_ROWCOLS(fn) \ |
1357 | ret = solve_rowcols(state, fn); \ |
1358 | if (ret < 0) { debug(("%s said impossible, cannot solve", #fn)); return -1; } \ |
1359 | if (ret > 0) continue |
1360 | |
1361 | static int solve_state(game_state *state, int diff) |
1362 | { |
1363 | int ret; |
1364 | |
1365 | debug(("solve_state, difficulty %s", magnets_diffnames[diff])); |
1366 | |
1367 | solve_clearflags(state); |
1368 | if (solve_startflags(state) < 0) return -1; |
1369 | |
1370 | while (1) { |
1371 | ret = solve_force(state); |
1372 | if (ret > 0) continue; |
1373 | if (ret < 0) return -1; |
1374 | |
1375 | ret = solve_neither(state); |
1376 | if (ret > 0) continue; |
1377 | if (ret < 0) return -1; |
1378 | |
1379 | SOLVE_FOR_ROWCOLS(solve_checkfull); |
1380 | SOLVE_FOR_ROWCOLS(solve_oddlength); |
1381 | |
1382 | if (diff < DIFF_TRICKY) break; |
1383 | |
1384 | SOLVE_FOR_ROWCOLS(solve_advancedfull); |
1385 | SOLVE_FOR_ROWCOLS(solve_nonneutral); |
1386 | SOLVE_FOR_ROWCOLS(solve_countdominoes_neutral); |
1387 | SOLVE_FOR_ROWCOLS(solve_countdominoes_nonneutral); |
1388 | |
1389 | /* more ... */ |
1390 | |
1391 | break; |
1392 | } |
1393 | return check_completion(state); |
1394 | } |
1395 | |
1396 | |
1397 | static char *game_state_diff(game_state *src, game_state *dst, int issolve) |
1398 | { |
1399 | char *ret = NULL, buf[80], c; |
1400 | int retlen = 0, x, y, i, k; |
1401 | |
1402 | assert(src->w == dst->w && src->h == dst->h); |
1403 | |
1404 | if (issolve) { |
1405 | ret = sresize(ret, 3, char); |
1406 | ret[0] = 'S'; ret[1] = ';'; ret[2] = '\0'; |
1407 | retlen += 2; |
1408 | } |
1409 | for (x = 0; x < dst->w; x++) { |
1410 | for (y = 0; y < dst->h; y++) { |
1411 | i = y*dst->w+x; |
1412 | |
1413 | if (src->common->dominoes[i] == i) continue; |
1414 | |
1415 | #define APPEND do { \ |
1416 | ret = sresize(ret, retlen + k + 1, char); \ |
1417 | strcpy(ret + retlen, buf); \ |
1418 | retlen += k; \ |
1419 | } while(0) |
1420 | |
1421 | if ((src->grid[i] != dst->grid[i]) || |
1422 | ((src->flags[i] & GS_SET) != (dst->flags[i] & GS_SET))) { |
1423 | if (dst->grid[i] == EMPTY && !(dst->flags[i] & GS_SET)) |
1424 | c = ' '; |
1425 | else |
1426 | c = GRID2CHAR(dst->grid[i]); |
1427 | k = sprintf(buf, "%c%d,%d;", (int)c, x, y); |
1428 | APPEND; |
1429 | } |
1430 | } |
1431 | } |
1432 | debug(("game_state_diff returns %s", ret)); |
1433 | return ret; |
1434 | } |
1435 | |
1436 | static void solve_from_aux(game_state *state, char *aux) |
1437 | { |
1438 | int i; |
1439 | assert(strlen(aux) == state->wh); |
1440 | for (i = 0; i < state->wh; i++) { |
1441 | state->grid[i] = CHAR2GRID(aux[i]); |
1442 | state->flags[i] |= GS_SET; |
1443 | } |
1444 | } |
1445 | |
1446 | static char *solve_game(game_state *state, game_state *currstate, |
1447 | char *aux, char **error) |
1448 | { |
1449 | game_state *solved = dup_game(currstate); |
1450 | char *move = NULL; |
1451 | int ret; |
1452 | |
1453 | if (aux && strlen(aux) == state->wh) { |
1454 | solve_from_aux(solved, aux); |
1455 | goto solved; |
1456 | } |
1457 | |
1458 | if (solve_state(solved, DIFFCOUNT) > 0) goto solved; |
1459 | free_game(solved); |
1460 | |
1461 | solved = dup_game(state); |
1462 | ret = solve_state(solved, DIFFCOUNT); |
1463 | if (ret > 0) goto solved; |
1464 | free_game(solved); |
1465 | |
1466 | *error = (ret < 0) ? "Puzzle is impossible." : "Unable to solve puzzle."; |
1467 | return NULL; |
1468 | |
1469 | solved: |
1470 | move = game_state_diff(currstate, solved, 1); |
1471 | free_game(solved); |
1472 | return move; |
1473 | } |
1474 | |
1475 | static int solve_unnumbered(game_state *state) |
1476 | { |
1477 | int i, ret; |
1478 | while (1) { |
1479 | ret = solve_force(state); |
1480 | if (ret > 0) continue; |
1481 | if (ret < 0) return -1; |
1482 | |
1483 | ret = solve_neither(state); |
1484 | if (ret > 0) continue; |
1485 | if (ret < 0) return -1; |
1486 | |
1487 | break; |
1488 | } |
1489 | for (i = 0; i < state->wh; i++) { |
1490 | if (!(state->flags[i] & GS_SET)) return 0; |
1491 | } |
1492 | return 1; |
1493 | } |
1494 | |
1495 | static int lay_dominoes(game_state *state, random_state *rs, int *scratch) |
1496 | { |
1497 | int n, i, ret = 0, x, y, nlaid = 0, n_initial_neutral; |
1498 | |
1499 | for (i = 0; i < state->wh; i++) { |
1500 | scratch[i] = i; |
1501 | state->grid[i] = EMPTY; |
1502 | state->flags[i] = (state->common->dominoes[i] == i) ? GS_SET : 0; |
1503 | } |
1504 | shuffle(scratch, state->wh, sizeof(int), rs); |
1505 | |
1506 | n_initial_neutral = (state->wh > 100) ? 5 : (state->wh / 10); |
1507 | |
1508 | for (n = 0; n < state->wh; n++) { |
1509 | /* Find a space ... */ |
1510 | |
1511 | i = scratch[n]; |
1512 | if (state->flags[i] & GS_SET) continue; /* already laid here. */ |
1513 | |
1514 | /* ...and lay a domino if we can. */ |
1515 | |
1516 | x = i%state->w; y = i/state->w; |
1517 | debug(("Laying domino at i:%d, (%d,%d)\n", i, x, y)); |
1518 | |
1519 | /* The choice of which type of domino to lay here leads to subtle differences |
1520 | * in the sorts of boards that get produced. Too much bias towards magnets |
1521 | * leads to games that are too easy. |
1522 | * |
1523 | * Currently, it lays a small set of dominoes at random as neutral, and |
1524 | * then lays the rest preferring to be magnets -- however, if the |
1525 | * current layout is such that a magnet won't go there, then it lays |
1526 | * another neutral. |
1527 | * |
1528 | * The number of initially neutral dominoes is limited as grids get bigger: |
1529 | * too many neutral dominoes invariably ends up with insoluble puzzle at |
1530 | * this size, and the positioning process means it'll always end up laying |
1531 | * more than the initial 5 anyway. |
1532 | */ |
1533 | |
1534 | /* We should always be able to lay a neutral anywhere. */ |
1535 | assert(!(state->flags[i] & GS_NOTNEUTRAL)); |
1536 | |
1537 | if (n < n_initial_neutral) { |
1538 | debug((" ...laying neutral\n")); |
1539 | ret = solve_set(state, i, NEUTRAL, "layout initial neutral", NULL); |
1540 | } else { |
1541 | debug((" ... preferring magnet\n")); |
1542 | if (!(state->flags[i] & GS_NOTPOSITIVE)) |
1543 | ret = solve_set(state, i, POSITIVE, "layout", NULL); |
1544 | else if (!(state->flags[i] & GS_NOTNEGATIVE)) |
1545 | ret = solve_set(state, i, NEGATIVE, "layout", NULL); |
1546 | else |
1547 | ret = solve_set(state, i, NEUTRAL, "layout", NULL); |
1548 | } |
1549 | if (!ret) { |
1550 | debug(("Unable to lay anything at (%d,%d), giving up.", x, y)); |
1551 | ret = -1; |
1552 | break; |
1553 | } |
1554 | |
1555 | nlaid++; |
1556 | ret = solve_unnumbered(state); |
1557 | if (ret == -1) |
1558 | debug(("solve_unnumbered decided impossible.\n")); |
1559 | if (ret != 0) |
1560 | break; |
1561 | } |
1562 | |
1563 | debug(("Laid %d dominoes, total %d dominoes.\n", nlaid, state->wh/2)); |
1564 | game_debug(state, "Final layout"); |
1565 | return ret; |
1566 | } |
1567 | |
1568 | static void gen_game(game_state *new, random_state *rs) |
1569 | { |
1570 | int ret, x, y, val; |
1571 | int *scratch = snewn(new->wh, int); |
1572 | |
1573 | #ifdef STANDALONE_SOLVER |
1574 | if (verbose) printf("Generating new game...\n"); |
1575 | #endif |
1576 | |
1577 | clear_state(new); |
1578 | sfree(new->common->dominoes); /* bit grotty. */ |
1579 | new->common->dominoes = domino_layout(new->w, new->h, rs); |
1580 | |
1581 | do { |
1582 | ret = lay_dominoes(new, rs, scratch); |
1583 | } while(ret == -1); |
1584 | |
1585 | /* for each cell, update colcount/rowcount as appropriate. */ |
1586 | memset(new->common->colcount, 0, new->w*3*sizeof(int)); |
1587 | memset(new->common->rowcount, 0, new->h*3*sizeof(int)); |
1588 | for (x = 0; x < new->w; x++) { |
1589 | for (y = 0; y < new->h; y++) { |
1590 | val = new->grid[y*new->w+x]; |
1591 | new->common->colcount[x*3+val]++; |
1592 | new->common->rowcount[y*3+val]++; |
1593 | } |
1594 | } |
1595 | new->numbered = 1; |
1596 | |
1597 | sfree(scratch); |
1598 | } |
1599 | |
1600 | static void generate_aux(game_state *new, char *aux) |
1601 | { |
1602 | int i; |
1603 | for (i = 0; i < new->wh; i++) |
1604 | aux[i] = GRID2CHAR(new->grid[i]); |
1605 | aux[new->wh] = '\0'; |
1606 | } |
1607 | |
1608 | static int check_difficulty(game_params *params, game_state *new, |
1609 | random_state *rs) |
1610 | { |
1611 | int *scratch, *grid_correct, slen, i; |
1612 | |
1613 | memset(new->grid, EMPTY, new->wh*sizeof(int)); |
1614 | |
1615 | if (params->diff > DIFF_EASY) { |
1616 | /* If this is too easy, return. */ |
1617 | if (solve_state(new, params->diff-1) > 0) { |
1618 | debug(("Puzzle is too easy.")); |
1619 | return -1; |
1620 | } |
1621 | } |
1622 | if (solve_state(new, params->diff) <= 0) { |
1623 | debug(("Puzzle is not soluble at requested difficulty.")); |
1624 | return -1; |
1625 | } |
1626 | if (!params->stripclues) return 0; |
1627 | |
1628 | /* Copy the correct grid away. */ |
1629 | grid_correct = snewn(new->wh, int); |
1630 | memcpy(grid_correct, new->grid, new->wh*sizeof(int)); |
1631 | |
1632 | /* Create shuffled array of side-clue locations. */ |
1633 | slen = new->w*2 + new->h*2; |
1634 | scratch = snewn(slen, int); |
1635 | for (i = 0; i < slen; i++) scratch[i] = i; |
1636 | shuffle(scratch, slen, sizeof(int), rs); |
1637 | |
1638 | /* For each clue, check whether removing it makes the puzzle unsoluble; |
1639 | * put it back if so. */ |
1640 | for (i = 0; i < slen; i++) { |
1641 | int num = scratch[i], which, roworcol, target, targetn, ret; |
1642 | rowcol rc; |
1643 | |
1644 | /* work out which clue we meant. */ |
1645 | if (num < new->w+new->h) { which = POSITIVE; } |
1646 | else { which = NEGATIVE; num -= new->w+new->h; } |
1647 | |
1648 | if (num < new->w) { roworcol = COLUMN; } |
1649 | else { roworcol = ROW; num -= new->w; } |
1650 | |
1651 | /* num is now the row/column index in question. */ |
1652 | rc = mkrowcol(new, num, roworcol); |
1653 | |
1654 | /* Remove clue, storing original... */ |
1655 | target = rc.targets[which]; |
1656 | targetn = rc.targets[NEUTRAL]; |
1657 | rc.targets[which] = -1; |
1658 | rc.targets[NEUTRAL] = -1; |
1659 | |
1660 | /* ...and see if we can still solve it. */ |
1661 | game_debug(new, "removed clue, new board:"); |
1662 | memset(new->grid, EMPTY, new->wh * sizeof(int)); |
1663 | ret = solve_state(new, params->diff); |
1664 | assert(ret != -1); |
1665 | |
1666 | if (ret == 0 || |
1667 | memcmp(new->grid, grid_correct, new->wh*sizeof(int)) != 0) { |
1668 | /* We made it ambiguous: put clue back. */ |
1669 | debug(("...now impossible/different, put clue back.")); |
1670 | rc.targets[which] = target; |
1671 | rc.targets[NEUTRAL] = targetn; |
1672 | } |
1673 | } |
1674 | sfree(scratch); |
1675 | sfree(grid_correct); |
1676 | |
1677 | return 0; |
1678 | } |
1679 | |
1680 | static char *new_game_desc(game_params *params, random_state *rs, |
1681 | char **aux_r, int interactive) |
1682 | { |
1683 | game_state *new = new_state(params->w, params->h); |
1684 | char *desc, *aux = snewn(new->wh+1, char); |
1685 | |
1686 | do { |
1687 | gen_game(new, rs); |
1688 | generate_aux(new, aux); |
1689 | } while (check_difficulty(params, new, rs) < 0); |
1690 | |
1691 | /* now we're complete, generate the description string |
1692 | * and an aux_info for the completed game. */ |
1693 | desc = generate_desc(new); |
1694 | |
1695 | free_game(new); |
1696 | |
1697 | *aux_r = aux; |
1698 | return desc; |
1699 | } |
1700 | |
1701 | struct game_ui { |
1702 | int cur_x, cur_y, cur_visible; |
1703 | }; |
1704 | |
1705 | static game_ui *new_ui(game_state *state) |
1706 | { |
1707 | game_ui *ui = snew(game_ui); |
1708 | ui->cur_x = ui->cur_y = 0; |
1709 | ui->cur_visible = 0; |
1710 | return ui; |
1711 | } |
1712 | |
1713 | static void free_ui(game_ui *ui) |
1714 | { |
1715 | sfree(ui); |
1716 | } |
1717 | |
1718 | static char *encode_ui(game_ui *ui) |
1719 | { |
1720 | return NULL; |
1721 | } |
1722 | |
1723 | static void decode_ui(game_ui *ui, char *encoding) |
1724 | { |
1725 | } |
1726 | |
1727 | static void game_changed_state(game_ui *ui, game_state *oldstate, |
1728 | game_state *newstate) |
1729 | { |
1730 | if (!oldstate->completed && newstate->completed) |
1731 | ui->cur_visible = 0; |
1732 | } |
1733 | |
1734 | struct game_drawstate { |
1735 | int tilesize, started, solved; |
1736 | int w, h; |
1737 | unsigned long *what; /* size w*h */ |
1738 | unsigned long *colwhat, *rowwhat; /* size 3*w, 3*h */ |
1739 | }; |
1740 | |
1741 | #define DS_WHICH_MASK 0xf |
1742 | |
1743 | #define DS_ERROR 0x10 |
1744 | #define DS_CURSOR 0x20 |
1745 | #define DS_SET 0x40 |
1746 | #define DS_FULL 0x80 |
1747 | #define DS_NOTPOS 0x100 |
1748 | #define DS_NOTNEG 0x200 |
1749 | #define DS_NOTNEU 0x400 |
1750 | #define DS_FLASH 0x800 |
1751 | |
1752 | #define PREFERRED_TILE_SIZE 32 |
1753 | #define TILE_SIZE (ds->tilesize) |
1754 | #define BORDER (TILE_SIZE / 8) |
1755 | |
1756 | #define COORD(x) ( (x+1) * TILE_SIZE + BORDER ) |
1757 | #define FROMCOORD(x) ( (x - BORDER) / TILE_SIZE - 1 ) |
1758 | |
1759 | static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, |
1760 | int x, int y, int button) |
1761 | { |
1762 | int gx = FROMCOORD(x), gy = FROMCOORD(y), idx, curr; |
1763 | char *nullret = NULL, buf[80], movech; |
1764 | enum { CYCLE_MAGNET, CYCLE_NEUTRAL } action; |
1765 | |
1766 | if (IS_CURSOR_MOVE(button)) { |
1767 | move_cursor(button, &ui->cur_x, &ui->cur_y, state->w, state->h, 0); |
1768 | ui->cur_visible = 1; |
1769 | return ""; |
1770 | } else if (IS_CURSOR_SELECT(button)) { |
1771 | if (!ui->cur_visible) { |
1772 | ui->cur_visible = 1; |
1773 | return ""; |
1774 | } |
1775 | action = (button == CURSOR_SELECT) ? CYCLE_MAGNET : CYCLE_NEUTRAL; |
1776 | gx = ui->cur_x; |
1777 | gy = ui->cur_y; |
1778 | } else if (INGRID(state, gx, gy) && |
1779 | (button == LEFT_BUTTON || button == RIGHT_BUTTON)) { |
1780 | if (ui->cur_visible) { |
1781 | ui->cur_visible = 0; |
1782 | nullret = ""; |
1783 | } |
1784 | action = (button == LEFT_BUTTON) ? CYCLE_MAGNET : CYCLE_NEUTRAL; |
1785 | } else |
1786 | return NULL; |
1787 | |
1788 | idx = gy * state->w + gx; |
1789 | if (state->common->dominoes[idx] == idx) return nullret; |
1790 | curr = state->grid[idx]; |
1791 | |
1792 | if (action == CYCLE_MAGNET) { |
1793 | /* ... empty --> positive --> negative --> empty ... */ |
1794 | |
1795 | if (state->grid[idx] == NEUTRAL && state->flags[idx] & GS_SET) |
1796 | return nullret; /* can't cycle a magnet from a neutral. */ |
1797 | movech = (curr == EMPTY) ? '+' : (curr == POSITIVE) ? '-' : ' '; |
1798 | } else if (action == CYCLE_NEUTRAL) { |
1799 | /* ... empty -> neutral -> !neutral --> empty ... */ |
1800 | |
1801 | if (state->grid[idx] != NEUTRAL) |
1802 | return nullret; /* can't cycle through neutral from a magnet. */ |
1803 | |
1804 | /* All of these are grid == EMPTY == NEUTRAL; it twiddles |
1805 | * combinations of flags. */ |
1806 | if (state->flags[idx] & GS_SET) /* neutral */ |
1807 | movech = '?'; |
1808 | else if (state->flags[idx] & GS_NOTNEUTRAL) /* !neutral */ |
1809 | movech = ' '; |
1810 | else |
1811 | movech = '.'; |
f8bc7e70 |
1812 | } else { |
72c00e19 |
1813 | assert(!"unknown action"); |
f8bc7e70 |
1814 | movech = 0; /* placate optimiser */ |
1815 | } |
72c00e19 |
1816 | |
1817 | sprintf(buf, "%c%d,%d", movech, gx, gy); |
1818 | |
1819 | return dupstr(buf); |
1820 | } |
1821 | |
1822 | static game_state *execute_move(game_state *state, char *move) |
1823 | { |
1824 | game_state *ret = dup_game(state); |
1825 | int x, y, n, idx, idx2; |
1826 | char c; |
1827 | |
1828 | if (!*move) goto badmove; |
1829 | while (*move) { |
1830 | c = *move++; |
1831 | if (c == 'S') { |
1832 | ret->solved = TRUE; |
1833 | n = 0; |
1834 | } else if (c == '+' || c == '-' || |
1835 | c == '.' || c == ' ' || c == '?') { |
1836 | if ((sscanf(move, "%d,%d%n", &x, &y, &n) != 2) || |
1837 | !INGRID(state, x, y)) goto badmove; |
1838 | |
1839 | idx = y*state->w + x; |
1840 | idx2 = state->common->dominoes[idx]; |
1841 | if (idx == idx2) goto badmove; |
1842 | |
1843 | ret->flags[idx] &= ~GS_NOTMASK; |
1844 | ret->flags[idx2] &= ~GS_NOTMASK; |
1845 | |
1846 | if (c == ' ' || c == '?') { |
1847 | ret->grid[idx] = EMPTY; |
1848 | ret->grid[idx2] = EMPTY; |
1849 | ret->flags[idx] &= ~GS_SET; |
1850 | ret->flags[idx2] &= ~GS_SET; |
1851 | if (c == '?') { |
1852 | ret->flags[idx] |= GS_NOTNEUTRAL; |
1853 | ret->flags[idx2] |= GS_NOTNEUTRAL; |
1854 | } |
1855 | } else { |
1856 | ret->grid[idx] = CHAR2GRID(c); |
1857 | ret->grid[idx2] = OPPOSITE(CHAR2GRID(c)); |
1858 | ret->flags[idx] |= GS_SET; |
1859 | ret->flags[idx2] |= GS_SET; |
1860 | } |
1861 | } else |
1862 | goto badmove; |
1863 | |
1864 | move += n; |
1865 | if (*move == ';') move++; |
1866 | else if (*move) goto badmove; |
1867 | } |
1868 | if (check_completion(ret) == 1) |
1869 | ret->completed = 1; |
1870 | |
1871 | return ret; |
1872 | |
1873 | badmove: |
1874 | free_game(ret); |
1875 | return NULL; |
1876 | } |
1877 | |
1878 | /* ---------------------------------------------------------------------- |
1879 | * Drawing routines. |
1880 | */ |
1881 | |
1882 | static void game_compute_size(game_params *params, int tilesize, |
1883 | int *x, int *y) |
1884 | { |
1885 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ |
1886 | struct { int tilesize; } ads, *ds = &ads; |
1887 | ads.tilesize = tilesize; |
1888 | |
1889 | *x = TILE_SIZE * (params->w+2) + 2 * BORDER; |
1890 | *y = TILE_SIZE * (params->h+2) + 2 * BORDER; |
1891 | } |
1892 | |
1893 | static void game_set_size(drawing *dr, game_drawstate *ds, |
1894 | game_params *params, int tilesize) |
1895 | { |
1896 | ds->tilesize = tilesize; |
1897 | } |
1898 | |
1899 | static float *game_colours(frontend *fe, int *ncolours) |
1900 | { |
1901 | float *ret = snewn(3 * NCOLOURS, float); |
1902 | int i; |
1903 | |
1904 | game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT); |
1905 | |
1906 | for (i = 0; i < 3; i++) { |
1907 | ret[COL_TEXT * 3 + i] = 0.0F; |
1908 | ret[COL_NEGATIVE * 3 + i] = 0.0F; |
1909 | ret[COL_CURSOR * 3 + i] = 0.9F; |
1910 | } |
1911 | |
1912 | ret[COL_POSITIVE * 3 + 0] = 0.8F; |
1913 | ret[COL_POSITIVE * 3 + 1] = 0.0F; |
1914 | ret[COL_POSITIVE * 3 + 2] = 0.0F; |
1915 | |
1916 | ret[COL_NEUTRAL * 3 + 0] = 0.10F; |
1917 | ret[COL_NEUTRAL * 3 + 1] = 0.60F; |
1918 | ret[COL_NEUTRAL * 3 + 2] = 0.10F; |
1919 | |
1920 | ret[COL_ERROR * 3 + 0] = 1.0F; |
1921 | ret[COL_ERROR * 3 + 1] = 0.0F; |
1922 | ret[COL_ERROR * 3 + 2] = 0.0F; |
1923 | |
1924 | ret[COL_NOT * 3 + 0] = 0.2F; |
1925 | ret[COL_NOT * 3 + 1] = 0.2F; |
1926 | ret[COL_NOT * 3 + 2] = 1.0F; |
1927 | |
1928 | *ncolours = NCOLOURS; |
1929 | return ret; |
1930 | } |
1931 | |
1932 | static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) |
1933 | { |
1934 | struct game_drawstate *ds = snew(struct game_drawstate); |
1935 | |
1936 | ds->tilesize = ds->started = ds->solved = 0; |
1937 | ds->w = state->w; |
1938 | ds->h = state->h; |
1939 | |
1940 | ds->what = snewn(state->wh, unsigned long); |
1941 | memset(ds->what, 0, state->wh*sizeof(unsigned long)); |
1942 | |
1943 | ds->colwhat = snewn(state->w*3, unsigned long); |
1944 | memset(ds->colwhat, 0, state->w*3*sizeof(unsigned long)); |
1945 | ds->rowwhat = snewn(state->h*3, unsigned long); |
1946 | memset(ds->rowwhat, 0, state->h*3*sizeof(unsigned long)); |
1947 | |
1948 | return ds; |
1949 | } |
1950 | |
1951 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) |
1952 | { |
1953 | sfree(ds->colwhat); |
1954 | sfree(ds->rowwhat); |
1955 | sfree(ds->what); |
1956 | sfree(ds); |
1957 | } |
1958 | |
1959 | static void draw_num_col(drawing *dr, game_drawstate *ds, int rowcol, int which, |
1960 | int idx, int colbg, int col, int num) |
1961 | { |
1962 | char buf[32]; |
1963 | int cx, cy, tsz; |
1964 | |
1965 | if (num < 0) return; |
1966 | |
1967 | sprintf(buf, "%d", num); |
1968 | tsz = (strlen(buf) == 1) ? (7*TILE_SIZE/10) : (9*TILE_SIZE/10)/strlen(buf); |
1969 | |
1970 | if (rowcol == ROW) { |
1971 | cx = BORDER; |
1972 | if (which == NEGATIVE) cx += TILE_SIZE * (ds->w+1); |
1973 | cy = BORDER + TILE_SIZE * (idx+1); |
1974 | } else { |
1975 | cx = BORDER + TILE_SIZE * (idx+1); |
1976 | cy = BORDER; |
1977 | if (which == NEGATIVE) cy += TILE_SIZE * (ds->h+1); |
1978 | } |
1979 | |
1980 | draw_rect(dr, cx, cy, TILE_SIZE, TILE_SIZE, colbg); |
1981 | draw_text(dr, cx + TILE_SIZE/2, cy + TILE_SIZE/2, FONT_VARIABLE, tsz, |
1982 | ALIGN_VCENTRE | ALIGN_HCENTRE, col, buf); |
1983 | |
1984 | draw_update(dr, cx, cy, TILE_SIZE, TILE_SIZE); |
1985 | } |
1986 | |
1987 | static void draw_num(drawing *dr, game_drawstate *ds, int rowcol, int which, |
1988 | int idx, unsigned long c, int num) |
1989 | { |
1990 | draw_num_col(dr, ds, rowcol, which, idx, COL_BACKGROUND, |
1991 | (c & DS_ERROR) ? COL_ERROR : COL_TEXT, num); |
1992 | } |
1993 | |
1994 | static void draw_sym(drawing *dr, game_drawstate *ds, int x, int y, int which, int col) |
1995 | { |
1996 | int cx = COORD(x), cy = COORD(y); |
1997 | int ccx = cx + TILE_SIZE/2, ccy = cy + TILE_SIZE/2; |
1998 | int roff = TILE_SIZE/4, rsz = 2*roff+1; |
1999 | int soff = TILE_SIZE/16, ssz = 2*soff+1; |
2000 | |
2001 | if (which == POSITIVE || which == NEGATIVE) { |
2002 | draw_rect(dr, ccx - roff, ccy - soff, rsz, ssz, col); |
2003 | if (which == POSITIVE) |
2004 | draw_rect(dr, ccx - soff, ccy - roff, ssz, rsz, col); |
2005 | } else if (col == COL_NOT) { |
2006 | /* not-a-neutral is a blue question mark. */ |
2007 | char qu[2] = { '?', 0 }; |
2008 | draw_text(dr, ccx, ccy, FONT_VARIABLE, 7*TILE_SIZE/10, |
2009 | ALIGN_VCENTRE | ALIGN_HCENTRE, col, qu); |
2010 | } else { |
2011 | draw_line(dr, ccx - roff, ccy - roff, ccx + roff, ccy + roff, col); |
2012 | draw_line(dr, ccx + roff, ccy - roff, ccx - roff, ccy + roff, col); |
2013 | } |
2014 | } |
2015 | |
2016 | enum { |
2017 | TYPE_L, |
2018 | TYPE_R, |
2019 | TYPE_T, |
2020 | TYPE_B, |
2021 | TYPE_BLANK |
2022 | }; |
2023 | |
2024 | /* NOT responsible for redrawing background or updating. */ |
2025 | static void draw_tile_col(drawing *dr, game_drawstate *ds, int *dominoes, |
2026 | int x, int y, int which, int bg, int fg, int perc) |
2027 | { |
2028 | int cx = COORD(x), cy = COORD(y), i, other, type = TYPE_BLANK; |
2029 | int gutter, radius, coffset; |
2030 | |
2031 | /* gutter is TSZ/16 for 100%, 8*TSZ/16 (TSZ/2) for 0% */ |
2032 | gutter = (TILE_SIZE / 16) + ((100 - perc) * (7*TILE_SIZE / 16))/100; |
2033 | radius = (perc * (TILE_SIZE / 8)) / 100; |
2034 | coffset = gutter + radius; |
2035 | |
2036 | i = y*ds->w + x; |
2037 | other = dominoes[i]; |
2038 | |
2039 | if (other == i) return; |
2040 | else if (other == i+1) type = TYPE_L; |
2041 | else if (other == i-1) type = TYPE_R; |
2042 | else if (other == i+ds->w) type = TYPE_T; |
2043 | else if (other == i-ds->w) type = TYPE_B; |
2044 | else assert(!"mad domino orientation"); |
2045 | |
2046 | /* domino drawing shamelessly stolen from dominosa.c. */ |
2047 | if (type == TYPE_L || type == TYPE_T) |
2048 | draw_circle(dr, cx+coffset, cy+coffset, |
2049 | radius, bg, bg); |
2050 | if (type == TYPE_R || type == TYPE_T) |
2051 | draw_circle(dr, cx+TILE_SIZE-1-coffset, cy+coffset, |
2052 | radius, bg, bg); |
2053 | if (type == TYPE_L || type == TYPE_B) |
2054 | draw_circle(dr, cx+coffset, cy+TILE_SIZE-1-coffset, |
2055 | radius, bg, bg); |
2056 | if (type == TYPE_R || type == TYPE_B) |
2057 | draw_circle(dr, cx+TILE_SIZE-1-coffset, |
2058 | cy+TILE_SIZE-1-coffset, |
2059 | radius, bg, bg); |
2060 | |
2061 | for (i = 0; i < 2; i++) { |
2062 | int x1, y1, x2, y2; |
2063 | |
2064 | x1 = cx + (i ? gutter : coffset); |
2065 | y1 = cy + (i ? coffset : gutter); |
2066 | x2 = cx + TILE_SIZE-1 - (i ? gutter : coffset); |
2067 | y2 = cy + TILE_SIZE-1 - (i ? coffset : gutter); |
2068 | if (type == TYPE_L) |
2069 | x2 = cx + TILE_SIZE; |
2070 | else if (type == TYPE_R) |
2071 | x1 = cx; |
2072 | else if (type == TYPE_T) |
2073 | y2 = cy + TILE_SIZE ; |
2074 | else if (type == TYPE_B) |
2075 | y1 = cy; |
2076 | |
2077 | draw_rect(dr, x1, y1, x2-x1+1, y2-y1+1, bg); |
2078 | } |
2079 | |
2080 | if (fg != -1) draw_sym(dr, ds, x, y, which, fg); |
2081 | } |
2082 | |
2083 | static void draw_tile(drawing *dr, game_drawstate *ds, int *dominoes, |
2084 | int x, int y, unsigned long flags) |
2085 | { |
2086 | int cx = COORD(x), cy = COORD(y), bg, fg, perc = 100; |
2087 | int which = flags & DS_WHICH_MASK; |
2088 | |
2089 | flags &= ~DS_WHICH_MASK; |
2090 | |
2091 | draw_rect(dr, cx, cy, TILE_SIZE, TILE_SIZE, COL_BACKGROUND); |
2092 | |
2093 | if (flags & DS_CURSOR) |
2094 | bg = COL_CURSOR; /* off-white white for cursor */ |
2095 | else if (which == POSITIVE) |
2096 | bg = COL_POSITIVE; |
2097 | else if (which == NEGATIVE) |
2098 | bg = COL_NEGATIVE; |
2099 | else if (flags & DS_SET) |
2100 | bg = COL_NEUTRAL; /* green inner for neutral cells */ |
2101 | else |
2102 | bg = COL_LOWLIGHT; /* light grey for empty cells. */ |
2103 | |
2104 | if (which == EMPTY && !(flags & DS_SET)) { |
2105 | int notwhich = -1; |
2106 | fg = -1; /* don't draw cross unless actually set as neutral. */ |
2107 | |
2108 | if (flags & DS_NOTPOS) notwhich = POSITIVE; |
2109 | if (flags & DS_NOTNEG) notwhich = NEGATIVE; |
2110 | if (flags & DS_NOTNEU) notwhich = NEUTRAL; |
2111 | if (notwhich != -1) { |
2112 | which = notwhich; |
2113 | fg = COL_NOT; |
2114 | } |
2115 | } else |
2116 | fg = (flags & DS_ERROR) ? COL_ERROR : |
2117 | (flags & DS_CURSOR) ? COL_TEXT : COL_BACKGROUND; |
2118 | |
2119 | draw_rect(dr, cx, cy, TILE_SIZE, TILE_SIZE, COL_BACKGROUND); |
2120 | |
2121 | if (flags & DS_FLASH) { |
2122 | int bordercol = COL_HIGHLIGHT; |
2123 | draw_tile_col(dr, ds, dominoes, x, y, which, bordercol, -1, perc); |
2124 | perc = 3*perc/4; |
2125 | } |
2126 | draw_tile_col(dr, ds, dominoes, x, y, which, bg, fg, perc); |
2127 | |
2128 | draw_update(dr, cx, cy, TILE_SIZE, TILE_SIZE); |
2129 | } |
2130 | |
2131 | |
2132 | static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, |
2133 | game_state *state, int dir, game_ui *ui, |
2134 | float animtime, float flashtime) |
2135 | { |
2136 | int x, y, w = state->w, h = state->h, which, i, j, flash; |
2137 | unsigned long c = 0; |
2138 | |
2139 | flash = (int)(flashtime * 5 / FLASH_TIME) % 2; |
2140 | |
2141 | if (!ds->started) { |
2142 | /* draw background, corner +-. */ |
2143 | draw_rect(dr, 0, 0, |
2144 | TILE_SIZE * (w+2) + 2 * BORDER, |
2145 | TILE_SIZE * (h+2) + 2 * BORDER, |
2146 | COL_BACKGROUND); |
2147 | |
2148 | draw_sym(dr, ds, -1, -1, POSITIVE, COL_TEXT); |
2149 | draw_sym(dr, ds, state->w, state->h, NEGATIVE, COL_TEXT); |
2150 | |
2151 | draw_update(dr, 0, 0, |
2152 | TILE_SIZE * (ds->w+2) + 2 * BORDER, |
2153 | TILE_SIZE * (ds->h+2) + 2 * BORDER); |
2154 | } |
2155 | |
2156 | /* Draw grid */ |
2157 | for (y = 0; y < h; y++) { |
2158 | for (x = 0; x < w; x++) { |
2159 | int idx = y*w+x; |
2160 | |
2161 | c = state->grid[idx]; |
2162 | |
2163 | if (state->flags[idx] & GS_ERROR) |
2164 | c |= DS_ERROR; |
2165 | if (state->flags[idx] & GS_SET) |
2166 | c |= DS_SET; |
2167 | |
2168 | if (x == ui->cur_x && y == ui->cur_y && ui->cur_visible) |
2169 | c |= DS_CURSOR; |
2170 | |
2171 | if (flash) |
2172 | c |= DS_FLASH; |
2173 | |
2174 | if (state->flags[idx] & GS_NOTPOSITIVE) |
2175 | c |= DS_NOTPOS; |
2176 | if (state->flags[idx] & GS_NOTNEGATIVE) |
2177 | c |= DS_NOTNEG; |
2178 | if (state->flags[idx] & GS_NOTNEUTRAL) |
2179 | c |= DS_NOTNEU; |
2180 | |
2181 | if (ds->what[idx] != c || !ds->started) { |
2182 | draw_tile(dr, ds, state->common->dominoes, x, y, c); |
2183 | ds->what[idx] = c; |
2184 | } |
2185 | } |
2186 | } |
2187 | /* Draw counts around side */ |
2188 | for (which = POSITIVE, j = 0; j < 2; which = OPPOSITE(which), j++) { |
2189 | int target, count; |
2190 | for (i = 0; i < w; i++) { |
2191 | target = state->common->colcount[i*3+which]; |
2192 | count = count_rowcol(state, i, COLUMN, which); |
2193 | c = 0; |
2194 | if ((count > target) || |
2195 | (count < target && !count_rowcol(state, i, COLUMN, -1))) |
2196 | c |= DS_ERROR; |
2197 | if (count == target) c |= DS_FULL; |
2198 | if (c != ds->colwhat[i*3+which] || !ds->started) { |
2199 | draw_num(dr, ds, COLUMN, which, i, c, |
2200 | state->common->colcount[i*3+which]); |
2201 | ds->colwhat[i*3+which] = c; |
2202 | } |
2203 | } |
2204 | for (i = 0; i < h; i++) { |
2205 | target = state->common->rowcount[i*3+which]; |
2206 | count = count_rowcol(state, i, ROW, which); |
2207 | c = 0; |
2208 | if ((count > target) || |
2209 | (count < target && !count_rowcol(state, i, ROW, -1))) |
2210 | c |= DS_ERROR; |
2211 | if (count == target) c |= DS_FULL; |
2212 | if (c != ds->rowwhat[i*3+which] || !ds->started) { |
2213 | draw_num(dr, ds, ROW, which, i, c, |
2214 | state->common->rowcount[i*3+which]); |
2215 | ds->rowwhat[i*3+which] = c; |
2216 | } |
2217 | } |
2218 | } |
2219 | |
2220 | ds->started = 1; |
2221 | } |
2222 | |
2223 | static float game_anim_length(game_state *oldstate, game_state *newstate, |
2224 | int dir, game_ui *ui) |
2225 | { |
2226 | return 0.0F; |
2227 | } |
2228 | |
2229 | static float game_flash_length(game_state *oldstate, game_state *newstate, |
2230 | int dir, game_ui *ui) |
2231 | { |
2232 | if (!oldstate->completed && newstate->completed && |
2233 | !oldstate->solved && !newstate->solved) |
2234 | return FLASH_TIME; |
2235 | return 0.0F; |
2236 | } |
2237 | |
4496362f |
2238 | static int game_is_solved(game_state *state) |
2239 | { |
2240 | return state->completed; |
2241 | } |
2242 | |
72c00e19 |
2243 | static int game_timing_state(game_state *state, game_ui *ui) |
2244 | { |
2245 | return TRUE; |
2246 | } |
2247 | |
2248 | static void game_print_size(game_params *params, float *x, float *y) |
2249 | { |
2250 | int pw, ph; |
2251 | |
2252 | /* |
2253 | * I'll use 6mm squares by default. |
2254 | */ |
2255 | game_compute_size(params, 600, &pw, &ph); |
2256 | *x = pw / 100.0F; |
2257 | *y = ph / 100.0F; |
2258 | } |
2259 | |
2260 | static void game_print(drawing *dr, game_state *state, int tilesize) |
2261 | { |
2262 | int w = state->w, h = state->h; |
2263 | int ink = print_mono_colour(dr, 0); |
2264 | int paper = print_mono_colour(dr, 1); |
2265 | int x, y, target, count, which, i, j; |
2266 | |
2267 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ |
2268 | game_drawstate ads, *ds = &ads; |
2269 | game_set_size(dr, ds, NULL, tilesize); |
2270 | ds->w = w; ds->h = h; |
2271 | |
2272 | /* Border. */ |
2273 | print_line_width(dr, TILE_SIZE/12); |
2274 | |
2275 | /* Numbers and +/- for corners. */ |
2276 | draw_sym(dr, ds, -1, -1, POSITIVE, ink); |
2277 | draw_sym(dr, ds, state->w, state->h, NEGATIVE, ink); |
2278 | for (which = POSITIVE, j = 0; j < 2; which = OPPOSITE(which), j++) { |
2279 | for (i = 0; i < w; i++) { |
2280 | target = state->common->colcount[i*3+which]; |
2281 | count = count_rowcol(state, i, COLUMN, which); |
2282 | draw_num_col(dr, ds, COLUMN, which, i, paper, ink, |
2283 | state->common->colcount[i*3+which]); |
2284 | } |
2285 | for (i = 0; i < h; i++) { |
2286 | target = state->common->rowcount[i*3+which]; |
2287 | count = count_rowcol(state, i, ROW, which); |
2288 | draw_num_col(dr, ds, ROW, which, i, paper, ink, |
2289 | state->common->rowcount[i*3+which]); |
2290 | } |
2291 | } |
2292 | |
2293 | /* Dominoes. */ |
2294 | for (x = 0; x < w; x++) { |
2295 | for (y = 0; y < h; y++) { |
2296 | i = y*state->w + x; |
2297 | if (state->common->dominoes[i] == i+1 || |
2298 | state->common->dominoes[i] == i+w) { |
2299 | int dx = state->common->dominoes[i] == i+1 ? 2 : 1; |
2300 | int dy = 3 - dx; |
2301 | int xx, yy; |
2302 | int cx = COORD(x), cy = COORD(y); |
2303 | |
2304 | print_line_width(dr, 0); |
2305 | |
2306 | /* Ink the domino */ |
2307 | for (yy = 0; yy < 2; yy++) |
2308 | for (xx = 0; xx < 2; xx++) |
2309 | draw_circle(dr, |
2310 | cx+xx*dx*TILE_SIZE+(1-2*xx)*3*TILE_SIZE/16, |
2311 | cy+yy*dy*TILE_SIZE+(1-2*yy)*3*TILE_SIZE/16, |
2312 | TILE_SIZE/8, ink, ink); |
2313 | draw_rect(dr, cx + TILE_SIZE/16, cy + 3*TILE_SIZE/16, |
2314 | dx*TILE_SIZE - 2*(TILE_SIZE/16), |
2315 | dy*TILE_SIZE - 6*(TILE_SIZE/16), ink); |
2316 | draw_rect(dr, cx + 3*TILE_SIZE/16, cy + TILE_SIZE/16, |
2317 | dx*TILE_SIZE - 6*(TILE_SIZE/16), |
2318 | dy*TILE_SIZE - 2*(TILE_SIZE/16), ink); |
2319 | |
2320 | /* Un-ink the domino interior */ |
2321 | for (yy = 0; yy < 2; yy++) |
2322 | for (xx = 0; xx < 2; xx++) |
2323 | draw_circle(dr, |
2324 | cx+xx*dx*TILE_SIZE+(1-2*xx)*3*TILE_SIZE/16, |
2325 | cy+yy*dy*TILE_SIZE+(1-2*yy)*3*TILE_SIZE/16, |
2326 | 3*TILE_SIZE/32, paper, paper); |
2327 | draw_rect(dr, cx + 3*TILE_SIZE/32, cy + 3*TILE_SIZE/16, |
2328 | dx*TILE_SIZE - 2*(3*TILE_SIZE/32), |
2329 | dy*TILE_SIZE - 6*(TILE_SIZE/16), paper); |
2330 | draw_rect(dr, cx + 3*TILE_SIZE/16, cy + 3*TILE_SIZE/32, |
2331 | dx*TILE_SIZE - 6*(TILE_SIZE/16), |
2332 | dy*TILE_SIZE - 2*(3*TILE_SIZE/32), paper); |
2333 | } |
2334 | } |
2335 | } |
2336 | |
2337 | /* Grid symbols (solution). */ |
2338 | for (x = 0; x < w; x++) { |
2339 | for (y = 0; y < h; y++) { |
2340 | i = y*state->w + x; |
2341 | if ((state->grid[i] != NEUTRAL) || (state->flags[i] & GS_SET)) |
2342 | draw_sym(dr, ds, x, y, state->grid[i], ink); |
2343 | } |
2344 | } |
2345 | } |
2346 | |
2347 | #ifdef COMBINED |
2348 | #define thegame magnets |
2349 | #endif |
2350 | |
2351 | const struct game thegame = { |
2352 | "Magnets", "games.magnets", "magnets", |
2353 | default_params, |
2354 | game_fetch_preset, |
2355 | decode_params, |
2356 | encode_params, |
2357 | free_params, |
2358 | dup_params, |
2359 | TRUE, game_configure, custom_params, |
2360 | validate_params, |
2361 | new_game_desc, |
2362 | validate_desc, |
2363 | new_game, |
2364 | dup_game, |
2365 | free_game, |
2366 | TRUE, solve_game, |
2367 | TRUE, game_can_format_as_text_now, game_text_format, |
2368 | new_ui, |
2369 | free_ui, |
2370 | encode_ui, |
2371 | decode_ui, |
2372 | game_changed_state, |
2373 | interpret_move, |
2374 | execute_move, |
2375 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, |
2376 | game_colours, |
2377 | game_new_drawstate, |
2378 | game_free_drawstate, |
2379 | game_redraw, |
2380 | game_anim_length, |
2381 | game_flash_length, |
4496362f |
2382 | game_is_solved, |
72c00e19 |
2383 | TRUE, FALSE, game_print_size, game_print, |
2384 | FALSE, /* wants_statusbar */ |
2385 | FALSE, game_timing_state, |
2386 | REQUIRE_RBUTTON, /* flags */ |
2387 | }; |
2388 | |
2389 | #ifdef STANDALONE_SOLVER |
2390 | |
2391 | #include <time.h> |
2392 | #include <stdarg.h> |
2393 | |
2394 | const char *quis = NULL; |
2395 | int csv = 0; |
2396 | |
2397 | void usage(FILE *out) { |
2398 | fprintf(out, "usage: %s [-v] [--print] <params>|<game id>\n", quis); |
2399 | } |
2400 | |
2401 | void doprint(game_state *state) |
2402 | { |
2403 | char *fmt = game_text_format(state); |
2404 | printf("%s", fmt); |
2405 | sfree(fmt); |
2406 | } |
2407 | |
2408 | static void pnum(int n, int ntot, const char *desc) |
2409 | { |
2410 | printf("%2.1f%% (%d) %s", (double)n*100.0 / (double)ntot, n, desc); |
2411 | } |
2412 | |
2413 | static void start_soak(game_params *p, random_state *rs) |
2414 | { |
2415 | time_t tt_start, tt_now, tt_last; |
2416 | char *aux; |
2417 | game_state *s, *s2; |
2418 | int n = 0, nsolved = 0, nimpossible = 0, ntricky = 0, ret, i; |
2419 | long nn, nn_total = 0, nn_solved = 0, nn_tricky = 0; |
2420 | |
2421 | tt_start = tt_now = time(NULL); |
2422 | |
2423 | if (csv) |
2424 | printf("time, w, h, #generated, #solved, #tricky, #impossible, " |
2425 | "#neutral, #neutral/solved, #neutral/tricky\n"); |
2426 | else |
2427 | printf("Soak-testing a %dx%d grid.\n", p->w, p->h); |
2428 | |
2429 | s = new_state(p->w, p->h); |
2430 | aux = snewn(s->wh+1, char); |
2431 | |
2432 | while (1) { |
2433 | gen_game(s, rs); |
2434 | |
2435 | nn = 0; |
2436 | for (i = 0; i < s->wh; i++) { |
2437 | if (s->grid[i] == NEUTRAL) nn++; |
2438 | } |
2439 | |
2440 | generate_aux(s, aux); |
2441 | memset(s->grid, EMPTY, s->wh * sizeof(int)); |
2442 | s2 = dup_game(s); |
2443 | |
2444 | ret = solve_state(s, DIFFCOUNT); |
2445 | |
2446 | n++; |
2447 | nn_total += nn; |
2448 | if (ret > 0) { |
2449 | nsolved++; |
2450 | nn_solved += nn; |
2451 | if (solve_state(s2, DIFF_EASY) <= 0) { |
2452 | ntricky++; |
2453 | nn_tricky += nn; |
2454 | } |
2455 | } else if (ret < 0) { |
2456 | char *desc = generate_desc(s); |
2457 | solve_from_aux(s, aux); |
2458 | printf("Game considered impossible:\n %dx%d:%s\n", |
2459 | p->w, p->h, desc); |
2460 | sfree(desc); |
2461 | doprint(s); |
2462 | nimpossible++; |
2463 | } |
2464 | |
2465 | free_game(s2); |
2466 | |
2467 | tt_last = time(NULL); |
2468 | if (tt_last > tt_now) { |
2469 | tt_now = tt_last; |
2470 | if (csv) { |
2471 | printf("%d,%d,%d, %d,%d,%d,%d, %ld,%ld,%ld\n", |
2472 | (int)(tt_now - tt_start), p->w, p->h, |
2473 | n, nsolved, ntricky, nimpossible, |
2474 | nn_total, nn_solved, nn_tricky); |
2475 | } else { |
2476 | printf("%d total, %3.1f/s, ", |
2477 | n, (double)n / ((double)tt_now - tt_start)); |
2478 | pnum(nsolved, n, "solved"); printf(", "); |
2479 | pnum(ntricky, n, "tricky"); |
2480 | if (nimpossible > 0) |
2481 | pnum(nimpossible, n, "impossible"); |
2482 | printf("\n"); |
2483 | |
2484 | printf(" overall %3.1f%% neutral (%3.1f%% for solved, %3.1f%% for tricky)\n", |
2485 | (double)(nn_total * 100) / (double)(p->w * p->h * n), |
2486 | (double)(nn_solved * 100) / (double)(p->w * p->h * nsolved), |
2487 | (double)(nn_tricky * 100) / (double)(p->w * p->h * ntricky)); |
2488 | } |
2489 | } |
2490 | } |
2491 | free_game(s); |
2492 | sfree(aux); |
2493 | } |
2494 | |
2495 | int main(int argc, const char *argv[]) |
2496 | { |
2497 | int print = 0, soak = 0, solved = 0, ret; |
2498 | char *id = NULL, *desc, *desc_gen = NULL, *err, *aux = NULL; |
2499 | game_state *s = NULL; |
2500 | game_params *p = NULL; |
2501 | random_state *rs = NULL; |
2502 | time_t seed = time(NULL); |
2503 | |
2504 | setvbuf(stdout, NULL, _IONBF, 0); |
2505 | |
2506 | quis = argv[0]; |
2507 | while (--argc > 0) { |
2508 | char *p = (char*)(*++argv); |
2509 | if (!strcmp(p, "-v") || !strcmp(p, "--verbose")) { |
2510 | verbose = 1; |
2511 | } else if (!strcmp(p, "--csv")) { |
2512 | csv = 1; |
2513 | } else if (!strcmp(p, "-e") || !strcmp(p, "--seed")) { |
2514 | seed = atoi(*++argv); |
2515 | argc--; |
2516 | } else if (!strcmp(p, "-p") || !strcmp(p, "--print")) { |
2517 | print = 1; |
2518 | } else if (!strcmp(p, "-s") || !strcmp(p, "--soak")) { |
2519 | soak = 1; |
2520 | } else if (*p == '-') { |
2521 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); |
2522 | usage(stderr); |
2523 | exit(1); |
2524 | } else { |
2525 | id = p; |
2526 | } |
2527 | } |
2528 | |
2529 | rs = random_new((void*)&seed, sizeof(time_t)); |
2530 | |
2531 | if (!id) { |
2532 | fprintf(stderr, "usage: %s [-v] [--soak] <params> | <game_id>\n", argv[0]); |
2533 | goto done; |
2534 | } |
2535 | desc = strchr(id, ':'); |
2536 | if (desc) *desc++ = '\0'; |
2537 | |
2538 | p = default_params(); |
2539 | decode_params(p, id); |
2540 | err = validate_params(p, 1); |
2541 | if (err) { |
2542 | fprintf(stderr, "%s: %s", argv[0], err); |
2543 | goto done; |
2544 | } |
2545 | |
2546 | if (soak) { |
2547 | if (desc) { |
2548 | fprintf(stderr, "%s: --soak needs parameters, not description.\n", quis); |
2549 | goto done; |
2550 | } |
2551 | start_soak(p, rs); |
2552 | goto done; |
2553 | } |
2554 | |
2555 | if (!desc) |
2556 | desc = desc_gen = new_game_desc(p, rs, &aux, 0); |
2557 | |
2558 | err = validate_desc(p, desc); |
2559 | if (err) { |
2560 | fprintf(stderr, "%s: %s\nDescription: %s\n", quis, err, desc); |
72c00e19 |
2561 | goto done; |
2562 | } |
2563 | s = new_game(NULL, p, desc); |
2564 | printf("%s:%s (seed %ld)\n", id, desc, seed); |
2565 | if (aux) { |
2566 | /* We just generated this ourself. */ |
2567 | if (verbose || print) { |
2568 | doprint(s); |
2569 | solve_from_aux(s, aux); |
2570 | solved = 1; |
2571 | } |
2572 | } else { |
2573 | doprint(s); |
2574 | verbose = 1; |
2575 | ret = solve_state(s, DIFFCOUNT); |
2576 | if (ret < 0) printf("Puzzle is impossible.\n"); |
2577 | else if (ret == 0) printf("Puzzle is ambiguous.\n"); |
2578 | else printf("Puzzle was solved.\n"); |
2579 | verbose = 0; |
2580 | solved = 1; |
2581 | } |
2582 | if (solved) doprint(s); |
2583 | |
2584 | done: |
2585 | if (desc_gen) sfree(desc_gen); |
2586 | if (p) free_params(p); |
2587 | if (s) free_game(s); |
2588 | if (rs) random_free(rs); |
2589 | if (aux) sfree(aux); |
2590 | |
2591 | return 0; |
2592 | } |
2593 | |
2594 | #endif |
2595 | |
2596 | /* vim: set shiftwidth=4 tabstop=8: */ |