tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/*
2 * singles.c: implementation of Hitori ('let me alone') from Nikoli.
3 *
4 * Make single-get able to fetch a specific puzzle ID from menneske.no?
5 *
6 * www.menneske.no solving methods:
7 *
8 * Done:
9 * SC: if you circle a cell, any cells in same row/col with same no --> black
10 * -- solver_op_circle
11 * SB: if you make a cell black, any cells around it --> white
12 * -- solver_op_blacken
13 * ST: 3 identical cells in row, centre is white and outer two black.
14 * SP: 2 identical cells with single-cell gap, middle cell is white.
15 * -- solver_singlesep (both ST and SP)
16 * PI: if you have a pair of same number in row/col, any other
17 * cells of same number must be black.
18 * -- solve_doubles
19 * CC: if you have a black on edge one cell away from corner, cell
20 * on edge diag. adjacent must be white.
21 * CE: if you have 2 black cells of triangle on edge, third cell must
22 * be white.
23 * QM: if you have 3 black cells of diagonal square in middle, fourth
24 * cell must be white.
25 * -- solve_allblackbutone (CC, CE, and QM).
26 * QC: a corner with 4 identical numbers (or 2 and 2) must have the
27 * corner cell (and cell diagonal to that) black.
28 * TC: a corner with 3 identical numbers (with the L either way)
29 * must have the apex of L black, and other two white.
30 * DC: a corner with 2 identical numbers in domino can set a white
31 * cell along wall.
32 * -- solve_corners (QC, TC, DC)
33 * IP: pair with one-offset-pair force whites by offset pair
34 * -- solve_offsetpair
35 * MC: any cells diag. adjacent to black cells that would split board
36 * into separate white regions must be white.
37 * -- solve_removesplits
38 *
39 * Still to do:
40 *
41 * TEP: 3 pairs of dominos parallel to side, can mark 4 white cells
42 * alongside.
43 * DEP: 2 pairs of dominos parallel to side, can mark 2 white cells.
44 * FI: if you have two sets of double-cells packed together, singles
45 * in that row/col must be white (qv. PI)
46 * QuM: four identical cells (or 2 and 2) in middle of grid only have
47 * two possible solutions each.
48 * FDE: doubles one row/column away from edge can force a white cell.
49 * FDM: doubles in centre (next to bits of diag. square) can force a white cell.
50 * MP: two pairs with same number between force number to black.
51 * CnC: if circling a cell leads to impossible board, cell is black.
52 * MC: if we have two possiblilities, can we force a white circle?
53 *
54 */
55
56#include <stdio.h>
57#include <stdlib.h>
58#include <string.h>
59#include <assert.h>
60#include <ctype.h>
61#ifdef NO_TGMATH_H
62# include <math.h>
63#else
64# include <tgmath.h>
65#endif
66
67#include "puzzles.h"
68#include "latin.h"
69
70#ifdef STANDALONE_SOLVER
71static bool verbose = false;
72#endif
73
74#define PREFERRED_TILE_SIZE 32
75#define TILE_SIZE (ds->tilesize)
76#define BORDER (TILE_SIZE / 2)
77
78#define CRAD ((TILE_SIZE / 2) - 1)
79#define TEXTSZ ((14*CRAD/10) - 1) /* 2 * sqrt(2) of CRAD */
80
81#define COORD(x) ( (x) * TILE_SIZE + BORDER )
82#define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
83
84#define INGRID(s,x,y) ((x) >= 0 && (x) < (s)->w && (y) >= 0 && (y) < (s)->h)
85
86#define FLASH_TIME 0.7F
87
88enum {
89 COL_BACKGROUND, COL_UNUSED1, COL_LOWLIGHT,
90 COL_BLACK, COL_WHITE, COL_BLACKNUM, COL_GRID,
91 COL_CURSOR, COL_ERROR,
92 NCOLOURS
93};
94
95enum {
96 PREF_SHOW_BLACK_NUMS,
97 N_PREF_ITEMS
98};
99
100struct game_params {
101 int w, h, diff;
102};
103
104#define F_BLACK 0x1
105#define F_CIRCLE 0x2
106#define F_ERROR 0x4
107#define F_SCRATCH 0x8
108
109struct game_state {
110 int w, h, n, o; /* n = w*h; o = max(w, h) */
111 bool completed, used_solve, impossible;
112 int *nums; /* size w*h */
113 unsigned int *flags; /* size w*h */
114};
115
116/* top, right, bottom, left */
117static const int dxs[4] = { 0, 1, 0, -1 };
118static const int dys[4] = { -1, 0, 1, 0 };
119
120/* --- Game parameters and preset functions --- */
121
122#define DIFFLIST(A) \
123 A(EASY,Easy,e) \
124 A(TRICKY,Tricky,k)
125
126#define ENUM(upper,title,lower) DIFF_ ## upper,
127#define TITLE(upper,title,lower) #title,
128#define ENCODE(upper,title,lower) #lower
129#define CONFIG(upper,title,lower) ":" #title
130
131enum { DIFFLIST(ENUM) DIFF_MAX, DIFF_ANY };
132static char const *const singles_diffnames[] = { DIFFLIST(TITLE) };
133static char const singles_diffchars[] = DIFFLIST(ENCODE);
134#define DIFFCOUNT lenof(singles_diffchars)
135#define DIFFCONFIG DIFFLIST(CONFIG)
136
137static game_params *default_params(void)
138{
139 game_params *ret = snew(game_params);
140 ret->w = ret->h = 5;
141 ret->diff = DIFF_EASY;
142
143 return ret;
144}
145
146static const struct game_params singles_presets[] = {
147 { 5, 5, DIFF_EASY },
148 { 5, 5, DIFF_TRICKY },
149 { 6, 6, DIFF_EASY },
150 { 6, 6, DIFF_TRICKY },
151 { 8, 8, DIFF_EASY },
152 { 8, 8, DIFF_TRICKY },
153 { 10, 10, DIFF_EASY },
154 { 10, 10, DIFF_TRICKY },
155 { 12, 12, DIFF_EASY },
156 { 12, 12, DIFF_TRICKY }
157};
158
159static bool game_fetch_preset(int i, char **name, game_params **params)
160{
161 game_params *ret;
162 char buf[80];
163
164 if (i < 0 || i >= lenof(singles_presets))
165 return false;
166
167 ret = default_params();
168 *ret = singles_presets[i];
169 *params = ret;
170
171 sprintf(buf, "%dx%d %s", ret->w, ret->h, singles_diffnames[ret->diff]);
172 *name = dupstr(buf);
173
174 return true;
175}
176
177static void free_params(game_params *params)
178{
179 sfree(params);
180}
181
182static game_params *dup_params(const game_params *params)
183{
184 game_params *ret = snew(game_params);
185 *ret = *params; /* structure copy */
186 return ret;
187}
188
189static void decode_params(game_params *ret, char const *string)
190{
191 char const *p = string;
192 int i;
193
194 ret->w = ret->h = atoi(p);
195 while (*p && isdigit((unsigned char)*p)) p++;
196 if (*p == 'x') {
197 p++;
198 ret->h = atoi(p);
199 while (*p && isdigit((unsigned char)*p)) p++;
200 }
201 if (*p == 'd') {
202 ret->diff = DIFF_MAX; /* which is invalid */
203 p++;
204 for (i = 0; i < DIFFCOUNT; i++) {
205 if (*p == singles_diffchars[i])
206 ret->diff = i;
207 }
208 p++;
209 }
210}
211
212static char *encode_params(const game_params *params, bool full)
213{
214 char data[256];
215
216 if (full)
217 sprintf(data, "%dx%dd%c", params->w, params->h, singles_diffchars[params->diff]);
218 else
219 sprintf(data, "%dx%d", params->w, params->h);
220
221 return dupstr(data);
222}
223
224static config_item *game_configure(const game_params *params)
225{
226 config_item *ret;
227 char buf[80];
228
229 ret = snewn(4, config_item);
230
231 ret[0].name = "Width";
232 ret[0].type = C_STRING;
233 sprintf(buf, "%d", params->w);
234 ret[0].u.string.sval = dupstr(buf);
235
236 ret[1].name = "Height";
237 ret[1].type = C_STRING;
238 sprintf(buf, "%d", params->h);
239 ret[1].u.string.sval = dupstr(buf);
240
241 ret[2].name = "Difficulty";
242 ret[2].type = C_CHOICES;
243 ret[2].u.choices.choicenames = DIFFCONFIG;
244 ret[2].u.choices.selected = params->diff;
245
246 ret[3].name = NULL;
247 ret[3].type = C_END;
248
249 return ret;
250}
251
252static game_params *custom_params(const config_item *cfg)
253{
254 game_params *ret = snew(game_params);
255
256 ret->w = atoi(cfg[0].u.string.sval);
257 ret->h = atoi(cfg[1].u.string.sval);
258 ret->diff = cfg[2].u.choices.selected;
259
260 return ret;
261}
262
263static const char *validate_params(const game_params *params, bool full)
264{
265 if (params->w < 2 || params->h < 2)
266 return "Width and height must be at least two";
267 if (params->w > 10+26+26 || params->h > 10+26+26)
268 return "Puzzle is too large";
269 if (full) {
270 if (params->diff < 0 || params->diff >= DIFF_MAX)
271 return "Unknown difficulty rating";
272 }
273
274 return NULL;
275}
276
277/* --- Game description string generation and unpicking --- */
278
279static game_state *blank_game(int w, int h)
280{
281 game_state *state = snew(game_state);
282
283 memset(state, 0, sizeof(game_state));
284 state->w = w;
285 state->h = h;
286 state->n = w*h;
287 state->o = max(w,h);
288
289 state->completed = false;
290 state->used_solve = false;
291 state->impossible = false;
292
293 state->nums = snewn(state->n, int);
294 state->flags = snewn(state->n, unsigned int);
295
296 memset(state->nums, 0, state->n*sizeof(int));
297 memset(state->flags, 0, state->n*sizeof(unsigned int));
298
299 return state;
300}
301
302static game_state *dup_game(const game_state *state)
303{
304 game_state *ret = blank_game(state->w, state->h);
305
306 ret->completed = state->completed;
307 ret->used_solve = state->used_solve;
308 ret->impossible = state->impossible;
309
310 memcpy(ret->nums, state->nums, state->n*sizeof(int));
311 memcpy(ret->flags, state->flags, state->n*sizeof(unsigned int));
312
313 return ret;
314}
315
316static void free_game(game_state *state)
317{
318 sfree(state->nums);
319 sfree(state->flags);
320 sfree(state);
321}
322
323static char n2c(int num) {
324 if (num < 10)
325 return '0' + num;
326 else if (num < 10+26)
327 return 'a' + num - 10;
328 else
329 return 'A' + num - 10 - 26;
330 return '?';
331}
332
333static int c2n(char c) {
334 if (isdigit((unsigned char)c))
335 return (int)(c - '0');
336 else if (c >= 'a' && c <= 'z')
337 return (int)(c - 'a' + 10);
338 else if (c >= 'A' && c <= 'Z')
339 return (int)(c - 'A' + 10 + 26);
340 return -1;
341}
342
343static void unpick_desc(const game_params *params, const char *desc,
344 game_state **sout, const char **mout)
345{
346 game_state *state = blank_game(params->w, params->h);
347 const char *msg = NULL;
348 int num = 0, i = 0;
349
350 if (strlen(desc) != state->n) {
351 msg = "Game description is wrong length";
352 goto done;
353 }
354 for (i = 0; i < state->n; i++) {
355 num = c2n(desc[i]);
356 if (num <= 0 || num > state->o) {
357 msg = "Game description contains unexpected characters";
358 goto done;
359 }
360 state->nums[i] = num;
361 }
362done:
363 if (msg) { /* sth went wrong. */
364 if (mout) *mout = msg;
365 free_game(state);
366 } else {
367 if (mout) *mout = NULL;
368 if (sout) *sout = state;
369 else free_game(state);
370 }
371}
372
373static char *generate_desc(game_state *state, bool issolve)
374{
375 char *ret = snewn(state->n+1+(issolve?1:0), char);
376 int i, p=0;
377
378 if (issolve)
379 ret[p++] = 'S';
380 for (i = 0; i < state->n; i++)
381 ret[p++] = n2c(state->nums[i]);
382 ret[p] = '\0';
383 return ret;
384}
385
386/* --- Useful game functions (completion, etc.) --- */
387
388static bool game_can_format_as_text_now(const game_params *params)
389{
390 return true;
391}
392
393static char *game_text_format(const game_state *state)
394{
395 int len, x, y, i;
396 char *ret, *p;
397
398 len = (state->w)*2; /* one row ... */
399 len = len * (state->h*2); /* ... h rows, including gaps ... */
400 len += 1; /* ... final NL */
401 p = ret = snewn(len, char);
402
403 for (y = 0; y < state->h; y++) {
404 for (x = 0; x < state->w; x++) {
405 i = y*state->w + x;
406 if (x > 0) *p++ = ' ';
407 *p++ = (state->flags[i] & F_BLACK) ? '*' : n2c(state->nums[i]);
408 }
409 *p++ = '\n';
410 for (x = 0; x < state->w; x++) {
411 i = y*state->w + x;
412 if (x > 0) *p++ = ' ';
413 *p++ = (state->flags[i] & F_CIRCLE) ? '~' : ' ';
414 }
415 *p++ = '\n';
416 }
417 *p++ = '\0';
418 assert(p - ret == len);
419
420 return ret;
421}
422
423static void debug_state(const char *desc, game_state *state) {
424 char *dbg = game_text_format(state);
425 debug(("%s:\n%s", desc, dbg));
426 sfree(dbg);
427}
428
429static void connect_if_same(game_state *state, DSF *dsf, int i1, int i2)
430{
431 int c1, c2;
432
433 if ((state->flags[i1] & F_BLACK) != (state->flags[i2] & F_BLACK))
434 return;
435
436 c1 = dsf_canonify(dsf, i1);
437 c2 = dsf_canonify(dsf, i2);
438 dsf_merge(dsf, c1, c2);
439}
440
441static void connect_dsf(game_state *state, DSF *dsf)
442{
443 int x, y, i;
444
445 /* Construct a dsf array for connected blocks; connections
446 * tracked to right and down. */
447 dsf_reinit(dsf);
448 for (x = 0; x < state->w; x++) {
449 for (y = 0; y < state->h; y++) {
450 i = y*state->w + x;
451
452 if (x < state->w-1)
453 connect_if_same(state, dsf, i, i+1); /* right */
454 if (y < state->h-1)
455 connect_if_same(state, dsf, i, i+state->w); /* down */
456 }
457 }
458}
459
460#define CC_MARK_ERRORS 1
461#define CC_MUST_FILL 2
462
463static int check_rowcol(game_state *state, int starti, int di, int sz, unsigned flags)
464{
465 int nerr = 0, n, m, i, j;
466
467 /* if any circled numbers have identical non-circled numbers on
468 * same row/column, error (non-circled)
469 * if any circled numbers in same column are same number, highlight them.
470 * if any rows/columns have >1 of same number, not complete. */
471
472 for (n = 0, i = starti; n < sz; n++, i += di) {
473 if (state->flags[i] & F_BLACK) continue;
474 for (m = n+1, j = i+di; m < sz; m++, j += di) {
475 if (state->flags[j] & F_BLACK) continue;
476 if (state->nums[i] != state->nums[j]) continue;
477
478 nerr++; /* ok, we have two numbers the same in a row. */
479 if (!(flags & CC_MARK_ERRORS)) continue;
480
481 /* If we have two circles in the same row around
482 * two identical numbers, they are _both_ wrong. */
483 if ((state->flags[i] & F_CIRCLE) &&
484 (state->flags[j] & F_CIRCLE)) {
485 state->flags[i] |= F_ERROR;
486 state->flags[j] |= F_ERROR;
487 }
488 /* Otherwise, if we have a circle, any other identical
489 * numbers in that row are obviously wrong. We don't
490 * highlight this, however, since it makes the process
491 * of solving the puzzle too easy (you circle a number
492 * and it promptly tells you which numbers to blacken! */
493#if 0
494 else if (state->flags[i] & F_CIRCLE)
495 state->flags[j] |= F_ERROR;
496 else if (state->flags[j] & F_CIRCLE)
497 state->flags[i] |= F_ERROR;
498#endif
499 }
500 }
501 return nerr;
502}
503
504static bool check_complete(game_state *state, unsigned flags)
505{
506 DSF *dsf = dsf_new(state->n);
507 int x, y, i, error = 0, nwhite, w = state->w, h = state->h;
508
509 if (flags & CC_MARK_ERRORS) {
510 for (i = 0; i < state->n; i++)
511 state->flags[i] &= ~F_ERROR;
512 }
513 connect_dsf(state, dsf);
514
515 /* If we're the solver we need the grid all to be definitively
516 * black or definitively white (i.e. circled) otherwise the solver
517 * has found an ambiguous grid. */
518 if (flags & CC_MUST_FILL) {
519 for (i = 0; i < state->n; i++) {
520 if (!(state->flags[i] & F_BLACK) && !(state->flags[i] & F_CIRCLE))
521 error += 1;
522 }
523 }
524
525 /* Mark any black squares in groups of >1 as errors.
526 * Count number of white squares. */
527 nwhite = 0;
528 for (i = 0; i < state->n; i++) {
529 if (state->flags[i] & F_BLACK) {
530 if (dsf_size(dsf, i) > 1) {
531 error += 1;
532 if (flags & CC_MARK_ERRORS)
533 state->flags[i] |= F_ERROR;
534 }
535 } else
536 nwhite += 1;
537 }
538
539 /* Check attributes of white squares, row- and column-wise. */
540 for (x = 0; x < w; x++) /* check cols from (x,0) */
541 error += check_rowcol(state, x, w, h, flags);
542 for (y = 0; y < h; y++) /* check rows from (0,y) */
543 error += check_rowcol(state, y*w, 1, w, flags);
544
545 /* If there's more than one white region, pick the largest one to
546 * be the canonical one (arbitrarily tie-breaking towards lower
547 * array indices), and mark all the others as erroneous. */
548 {
549 int largest = 0, canonical = -1;
550 for (i = 0; i < state->n; i++)
551 if (!(state->flags[i] & F_BLACK)) {
552 int size = dsf_size(dsf, i);
553 if (largest < size) {
554 largest = size;
555 canonical = dsf_canonify(dsf, i);
556 }
557 }
558
559 if (largest < nwhite) {
560 for (i = 0; i < state->n; i++)
561 if (!(state->flags[i] & F_BLACK) &&
562 dsf_canonify(dsf, i) != canonical) {
563 error += 1;
564 if (flags & CC_MARK_ERRORS)
565 state->flags[i] |= F_ERROR;
566 }
567 }
568 }
569
570 dsf_free(dsf);
571 return !(error > 0);
572}
573
574static char *game_state_diff(const game_state *src, const game_state *dst,
575 bool issolve)
576{
577 char *ret = NULL, buf[80], c;
578 int retlen = 0, x, y, i, k;
579 unsigned int fmask = F_BLACK | F_CIRCLE;
580
581 assert(src->n == dst->n);
582
583 if (issolve) {
584 ret = sresize(ret, 3, char);
585 ret[0] = 'S'; ret[1] = ';'; ret[2] = '\0';
586 retlen += 2;
587 }
588
589 for (x = 0; x < dst->w; x++) {
590 for (y = 0; y < dst->h; y++) {
591 i = y*dst->w + x;
592 if ((src->flags[i] & fmask) != (dst->flags[i] & fmask)) {
593 assert((dst->flags[i] & fmask) != fmask);
594 if (dst->flags[i] & F_BLACK)
595 c = 'B';
596 else if (dst->flags[i] & F_CIRCLE)
597 c = 'C';
598 else
599 c = 'E';
600 k = sprintf(buf, "%c%d,%d;", (int)c, x, y);
601 ret = sresize(ret, retlen + k + 1, char);
602 strcpy(ret + retlen, buf);
603 retlen += k;
604 }
605 }
606 }
607 return ret;
608}
609
610/* --- Solver --- */
611
612enum { BLACK, CIRCLE };
613
614struct solver_op {
615 int x, y, op; /* op one of BLACK or CIRCLE. */
616 const char *desc; /* must be non-malloced. */
617};
618
619struct solver_state {
620 struct solver_op *ops;
621 int n_ops, n_alloc;
622 int *scratch;
623};
624
625static struct solver_state *solver_state_new(game_state *state)
626{
627 struct solver_state *ss = snew(struct solver_state);
628
629 ss->ops = NULL;
630 ss->n_ops = ss->n_alloc = 0;
631 ss->scratch = snewn(state->n, int);
632
633 return ss;
634}
635
636static void solver_state_free(struct solver_state *ss)
637{
638 sfree(ss->scratch);
639 if (ss->ops) sfree(ss->ops);
640 sfree(ss);
641}
642
643static void solver_op_add(struct solver_state *ss, int x, int y, int op, const char *desc)
644{
645 struct solver_op *sop;
646
647 if (ss->n_alloc < ss->n_ops + 1) {
648 ss->n_alloc = (ss->n_alloc + 1) * 2;
649 ss->ops = sresize(ss->ops, ss->n_alloc, struct solver_op);
650 }
651 sop = &(ss->ops[ss->n_ops++]);
652 sop->x = x; sop->y = y; sop->op = op; sop->desc = desc;
653 debug(("added solver op %s ('%s') at (%d,%d)\n",
654 op == BLACK ? "BLACK" : "CIRCLE", desc, x, y));
655}
656
657static void solver_op_circle(game_state *state, struct solver_state *ss,
658 int x, int y)
659{
660 int i = y*state->w + x;
661
662 if (!INGRID(state, x, y)) return;
663 if (state->flags[i] & F_BLACK) {
664 debug(("... solver wants to add auto-circle on black (%d,%d)\n", x, y));
665 state->impossible = true;
666 return;
667 }
668 /* Only add circle op if it's not already circled. */
669 if (!(state->flags[i] & F_CIRCLE)) {
670 solver_op_add(ss, x, y, CIRCLE, "SB - adjacent to black square");
671 }
672}
673
674static void solver_op_blacken(game_state *state, struct solver_state *ss,
675 int x, int y, int num)
676{
677 int i = y*state->w + x;
678
679 if (!INGRID(state, x, y)) return;
680 if (state->nums[i] != num) return;
681 if (state->flags[i] & F_CIRCLE) {
682 debug(("... solver wants to add auto-black on circled(%d,%d)\n", x, y));
683 state->impossible = true;
684 return;
685 }
686 /* Only add black op if it's not already black. */
687 if (!(state->flags[i] & F_BLACK)) {
688 solver_op_add(ss, x, y, BLACK, "SC - number on same row/col as circled");
689 }
690}
691
692static int solver_ops_do(game_state *state, struct solver_state *ss)
693{
694 int next_op = 0, i, x, y, n_ops = 0;
695 struct solver_op op;
696
697 /* Care here: solver_op_* may call solver_op_add which may extend the
698 * ss->n_ops. */
699
700 while (next_op < ss->n_ops) {
701 op = ss->ops[next_op++]; /* copy this away, it may get reallocated. */
702 i = op.y*state->w + op.x;
703
704 if (op.op == BLACK) {
705 if (state->flags[i] & F_CIRCLE) {
706 debug(("Solver wants to blacken circled square (%d,%d)!\n", op.x, op.y));
707 state->impossible = true;
708 return n_ops;
709 }
710 if (!(state->flags[i] & F_BLACK)) {
711 debug(("... solver adding black at (%d,%d): %s\n", op.x, op.y, op.desc));
712#ifdef STANDALONE_SOLVER
713 if (verbose)
714 printf("Adding black at (%d,%d): %s\n", op.x, op.y, op.desc);
715#endif
716 state->flags[i] |= F_BLACK;
717 /*debug_state("State after adding black", state);*/
718 n_ops++;
719 solver_op_circle(state, ss, op.x-1, op.y);
720 solver_op_circle(state, ss, op.x+1, op.y);
721 solver_op_circle(state, ss, op.x, op.y-1);
722 solver_op_circle(state, ss, op.x, op.y+1);
723 }
724 } else {
725 if (state->flags[i] & F_BLACK) {
726 debug(("Solver wants to circle blackened square (%d,%d)!\n", op.x, op.y));
727 state->impossible = true;
728 return n_ops;
729 }
730 if (!(state->flags[i] & F_CIRCLE)) {
731 debug(("... solver adding circle at (%d,%d): %s\n", op.x, op.y, op.desc));
732#ifdef STANDALONE_SOLVER
733 if (verbose)
734 printf("Adding circle at (%d,%d): %s\n", op.x, op.y, op.desc);
735#endif
736 state->flags[i] |= F_CIRCLE;
737 /*debug_state("State after adding circle", state);*/
738 n_ops++;
739 for (x = 0; x < state->w; x++) {
740 if (x != op.x)
741 solver_op_blacken(state, ss, x, op.y, state->nums[i]);
742 }
743 for (y = 0; y < state->h; y++) {
744 if (y != op.y)
745 solver_op_blacken(state, ss, op.x, y, state->nums[i]);
746 }
747 }
748 }
749 }
750 ss->n_ops = 0;
751 return n_ops;
752}
753
754/* If the grid has two identical numbers with one cell between them, the inner
755 * cell _must_ be white (and thus circled); (at least) one of the two must be
756 * black (since they're in the same column or row) and thus the middle cell is
757 * next to a black cell. */
758static int solve_singlesep(game_state *state, struct solver_state *ss)
759{
760 int x, y, i, ir, irr, id, idd, n_ops = ss->n_ops;
761
762 for (x = 0; x < state->w; x++) {
763 for (y = 0; y < state->h; y++) {
764 i = y*state->w + x;
765
766 /* Cell two to our right? */
767 ir = i + 1; irr = ir + 1;
768 if (x < (state->w-2) &&
769 state->nums[i] == state->nums[irr] &&
770 !(state->flags[ir] & F_CIRCLE)) {
771 solver_op_add(ss, x+1, y, CIRCLE, "SP/ST - between identical nums");
772 }
773 /* Cell two below us? */
774 id = i + state->w; idd = id + state->w;
775 if (y < (state->h-2) &&
776 state->nums[i] == state->nums[idd] &&
777 !(state->flags[id] & F_CIRCLE)) {
778 solver_op_add(ss, x, y+1, CIRCLE, "SP/ST - between identical nums");
779 }
780 }
781 }
782 return ss->n_ops - n_ops;
783}
784
785/* If we have two identical numbers next to each other (in a row or column),
786 * any other identical numbers in that column must be black. */
787static int solve_doubles(game_state *state, struct solver_state *ss)
788{
789 int x, y, i, ii, n_ops = ss->n_ops, xy;
790
791 for (y = 0, i = 0; y < state->h; y++) {
792 for (x = 0; x < state->w; x++, i++) {
793 assert(i == y*state->w+x);
794 if (state->flags[i] & F_BLACK) continue;
795
796 ii = i+1; /* check cell to our right. */
797 if (x < (state->w-1) &&
798 !(state->flags[ii] & F_BLACK) &&
799 state->nums[i] == state->nums[ii]) {
800 for (xy = 0; xy < state->w; xy++) {
801 if (xy == x || xy == (x+1)) continue;
802 if (state->nums[y*state->w + xy] == state->nums[i] &&
803 !(state->flags[y*state->w + xy] & F_BLACK))
804 solver_op_add(ss, xy, y, BLACK, "PI - same row as pair");
805 }
806 }
807
808 ii = i+state->w; /* check cell below us */
809 if (y < (state->h-1) &&
810 !(state->flags[ii] & F_BLACK) &&
811 state->nums[i] == state->nums[ii]) {
812 for (xy = 0; xy < state->h; xy++) {
813 if (xy == y || xy == (y+1)) continue;
814 if (state->nums[xy*state->w + x] == state->nums[i] &&
815 !(state->flags[xy*state->w + x] & F_BLACK))
816 solver_op_add(ss, x, xy, BLACK, "PI - same col as pair");
817 }
818 }
819 }
820 }
821 return ss->n_ops - n_ops;
822}
823
824/* If a white square has all-but-one possible adjacent squares black, the
825 * one square left over must be white. */
826static int solve_allblackbutone(game_state *state, struct solver_state *ss)
827{
828 int x, y, i, n_ops = ss->n_ops, xd, yd, id, ifree;
829 int dis[4], d;
830
831 dis[0] = -state->w;
832 dis[1] = 1;
833 dis[2] = state->w;
834 dis[3] = -1;
835
836 for (y = 0, i = 0; y < state->h; y++) {
837 for (x = 0; x < state->w; x++, i++) {
838 assert(i == y*state->w+x);
839 if (state->flags[i] & F_BLACK) continue;
840
841 ifree = -1;
842 for (d = 0; d < 4; d++) {
843 xd = x + dxs[d]; yd = y + dys[d]; id = i + dis[d];
844 if (!INGRID(state, xd, yd)) continue;
845
846 if (state->flags[id] & F_CIRCLE)
847 goto skip; /* this cell already has a way out */
848 if (!(state->flags[id] & F_BLACK)) {
849 if (ifree != -1)
850 goto skip; /* this cell has >1 white cell around it. */
851 ifree = id;
852 }
853 }
854 if (ifree != -1)
855 solver_op_add(ss, ifree%state->w, ifree/state->w, CIRCLE,
856 "CC/CE/QM: white cell with single non-black around it");
857 else {
858 debug(("White cell with no escape at (%d,%d)\n", x, y));
859 state->impossible = true;
860 return 0;
861 }
862skip: ;
863 }
864 }
865 return ss->n_ops - n_ops;
866}
867
868/* If we have 4 numbers the same in a 2x2 corner, the far corner and the
869 * diagonally-adjacent square must both be black.
870 * If we have 3 numbers the same in a 2x2 corner, the apex of the L
871 * thus formed must be black.
872 * If we have 2 numbers the same in a 2x2 corner, the non-same cell
873 * one away from the corner must be white. */
874static void solve_corner(game_state *state, struct solver_state *ss,
875 int x, int y, int dx, int dy)
876{
877 int is[4], ns[4], xx, yy, w = state->w;
878
879 for (yy = 0; yy < 2; yy++) {
880 for (xx = 0; xx < 2; xx++) {
881 is[yy*2+xx] = (y + dy*yy) * w + (x + dx*xx);
882 ns[yy*2+xx] = state->nums[is[yy*2+xx]];
883 }
884 } /* order is now (corner, side 1, side 2, inner) */
885
886 if (ns[0] == ns[1] && ns[0] == ns[2] && ns[0] == ns[3]) {
887 solver_op_add(ss, is[0]%w, is[0]/w, BLACK, "QC: corner with 4 matching");
888 solver_op_add(ss, is[3]%w, is[3]/w, BLACK, "QC: corner with 4 matching");
889 } else if (ns[0] == ns[1] && ns[0] == ns[2]) {
890 /* corner and 2 sides: apex is corner. */
891 solver_op_add(ss, is[0]%w, is[0]/w, BLACK, "TC: corner apex from 3 matching");
892 } else if (ns[1] == ns[2] && ns[1] == ns[3]) {
893 /* side, side, fourth: apex is fourth. */
894 solver_op_add(ss, is[3]%w, is[3]/w, BLACK, "TC: inside apex from 3 matching");
895 } else if (ns[0] == ns[1] || ns[1] == ns[3]) {
896 /* either way here we match the non-identical side. */
897 solver_op_add(ss, is[2]%w, is[2]/w, CIRCLE, "DC: corner with 2 matching");
898 } else if (ns[0] == ns[2] || ns[2] == ns[3]) {
899 /* ditto */
900 solver_op_add(ss, is[1]%w, is[1]/w, CIRCLE, "DC: corner with 2 matching");
901 }
902}
903
904static int solve_corners(game_state *state, struct solver_state *ss)
905{
906 int n_ops = ss->n_ops;
907
908 solve_corner(state, ss, 0, 0, 1, 1);
909 solve_corner(state, ss, state->w-1, 0, -1, 1);
910 solve_corner(state, ss, state->w-1, state->h-1, -1, -1);
911 solve_corner(state, ss, 0, state->h-1, 1, -1);
912
913 return ss->n_ops - n_ops;
914}
915
916/* If you have the following situation:
917 * ...
918 * ...x A x x y A x...
919 * ...x B x x B y x...
920 * ...
921 * then both squares marked 'y' must be white. One of the left-most A or B must
922 * be white (since two side-by-side black cells are disallowed), which means
923 * that the corresponding right-most A or B must be black (since you can't
924 * have two of the same number on one line); thus, the adjacent squares
925 * to that right-most A or B must be white, which include the two marked 'y'
926 * in either case.
927 * Obviously this works in any row or column. It also works if A == B.
928 * It doesn't work for the degenerate case:
929 * ...x A A x x
930 * ...x B y x x
931 * where the square marked 'y' isn't necessarily white (consider the left-most A
932 * is black).
933 *
934 * */
935static void solve_offsetpair_pair(game_state *state, struct solver_state *ss,
936 int x1, int y1, int x2, int y2)
937{
938 int ox, oy, w = state->w, ax, ay, an, d, dx[2], dy[2], dn, xd, yd;
939
940 if (x1 == x2) { /* same column */
941 ox = 1; oy = 0;
942 } else {
943 assert(y1 == y2);
944 ox = 0; oy = 1;
945 }
946
947 /* We try adjacent to (x1,y1) and the two diag. adjacent to (x2, y2).
948 * We expect to be called twice, once each way around. */
949 ax = x1+ox; ay = y1+oy;
950 assert(INGRID(state, ax, ay));
951 an = state->nums[ay*w + ax];
952
953 dx[0] = x2 + ox + oy; dx[1] = x2 + ox - oy;
954 dy[0] = y2 + oy + ox; dy[1] = y2 + oy - ox;
955
956 for (d = 0; d < 2; d++) {
957 if (INGRID(state, dx[d], dy[d]) && (dx[d] != ax || dy[d] != ay)) {
958 /* The 'dx != ax || dy != ay' removes the degenerate case,
959 * mentioned above. */
960 dn = state->nums[dy[d]*w + dx[d]];
961 if (an == dn) {
962 /* We have a match; so (WLOG) the 'A' marked above are at
963 * (x1,y1) and (x2,y2), and the 'B' are at (ax,ay) and (dx,dy). */
964 debug(("Found offset-pair: %d at (%d,%d) and (%d,%d)\n",
965 state->nums[y1*w + x1], x1, y1, x2, y2));
966 debug((" and: %d at (%d,%d) and (%d,%d)\n",
967 an, ax, ay, dx[d], dy[d]));
968
969 xd = dx[d] - x2; yd = dy[d] - y2;
970 solver_op_add(ss, x2 + xd, y2, CIRCLE, "IP: next to offset-pair");
971 solver_op_add(ss, x2, y2 + yd, CIRCLE, "IP: next to offset-pair");
972 }
973 }
974 }
975}
976
977static int solve_offsetpair(game_state *state, struct solver_state *ss)
978{
979 int n_ops = ss->n_ops, x, xx, y, yy, n1, n2;
980
981 for (x = 0; x < state->w-1; x++) {
982 for (y = 0; y < state->h; y++) {
983 n1 = state->nums[y*state->w + x];
984 for (yy = y+1; yy < state->h; yy++) {
985 n2 = state->nums[yy*state->w + x];
986 if (n1 == n2) {
987 solve_offsetpair_pair(state, ss, x, y, x, yy);
988 solve_offsetpair_pair(state, ss, x, yy, x, y);
989 }
990 }
991 }
992 }
993 for (y = 0; y < state->h-1; y++) {
994 for (x = 0; x < state->w; x++) {
995 n1 = state->nums[y*state->w + x];
996 for (xx = x+1; xx < state->w; xx++) {
997 n2 = state->nums[y*state->w + xx];
998 if (n1 == n2) {
999 solve_offsetpair_pair(state, ss, x, y, xx, y);
1000 solve_offsetpair_pair(state, ss, xx, y, x, y);
1001 }
1002 }
1003 }
1004 }
1005 return ss->n_ops - n_ops;
1006}
1007
1008static bool solve_hassinglewhiteregion(
1009 game_state *state, struct solver_state *ss)
1010{
1011 int i, j, nwhite = 0, lwhite = -1, szwhite, start, end, next, a, d, x, y;
1012
1013 for (i = 0; i < state->n; i++) {
1014 if (!(state->flags[i] & F_BLACK)) {
1015 nwhite++;
1016 lwhite = i;
1017 }
1018 state->flags[i] &= ~F_SCRATCH;
1019 }
1020 if (lwhite == -1) {
1021 debug(("solve_hassinglewhite: no white squares found!\n"));
1022 state->impossible = true;
1023 return false;
1024 }
1025 /* We don't use connect_dsf here; it's too slow, and there's a quicker
1026 * algorithm if all we want is the size of one region. */
1027 /* Having written this, this algorithm is only about 5% faster than
1028 * using a dsf. */
1029 memset(ss->scratch, -1, state->n * sizeof(int));
1030 ss->scratch[0] = lwhite;
1031 state->flags[lwhite] |= F_SCRATCH;
1032 start = 0; end = next = 1;
1033 while (start < end) {
1034 for (a = start; a < end; a++) {
1035 i = ss->scratch[a]; assert(i != -1);
1036 for (d = 0; d < 4; d++) {
1037 x = (i % state->w) + dxs[d];
1038 y = (i / state->w) + dys[d];
1039 j = y*state->w + x;
1040 if (!INGRID(state, x, y)) continue;
1041 if (state->flags[j] & (F_BLACK | F_SCRATCH)) continue;
1042 ss->scratch[next++] = j;
1043 state->flags[j] |= F_SCRATCH;
1044 }
1045 }
1046 start = end; end = next;
1047 }
1048 szwhite = next;
1049 return (szwhite == nwhite);
1050}
1051
1052static void solve_removesplits_check(game_state *state, struct solver_state *ss,
1053 int x, int y)
1054{
1055 int i = y*state->w + x;
1056 bool issingle;
1057
1058 if (!INGRID(state, x, y)) return;
1059 if ((state->flags[i] & F_CIRCLE) || (state->flags[i] & F_BLACK))
1060 return;
1061
1062 /* If putting a black square at (x,y) would make the white region
1063 * non-contiguous, it must be circled. */
1064 state->flags[i] |= F_BLACK;
1065 issingle = solve_hassinglewhiteregion(state, ss);
1066 state->flags[i] &= ~F_BLACK;
1067
1068 if (!issingle)
1069 solver_op_add(ss, x, y, CIRCLE, "MC: black square here would split white region");
1070}
1071
1072/* For all black squares, search in squares diagonally adjacent to see if
1073 * we can rule out putting a black square there (because it would make the
1074 * white region non-contiguous). */
1075/* This function is likely to be somewhat slow. */
1076static int solve_removesplits(game_state *state, struct solver_state *ss)
1077{
1078 int i, x, y, n_ops = ss->n_ops;
1079
1080 if (!solve_hassinglewhiteregion(state, ss)) {
1081 debug(("solve_removesplits: white region is not contiguous at start!\n"));
1082 state->impossible = true;
1083 return 0;
1084 }
1085
1086 for (i = 0; i < state->n; i++) {
1087 if (!(state->flags[i] & F_BLACK)) continue;
1088
1089 x = i%state->w; y = i/state->w;
1090 solve_removesplits_check(state, ss, x-1, y-1);
1091 solve_removesplits_check(state, ss, x+1, y-1);
1092 solve_removesplits_check(state, ss, x+1, y+1);
1093 solve_removesplits_check(state, ss, x-1, y+1);
1094 }
1095 return ss->n_ops - n_ops;
1096}
1097
1098/*
1099 * This function performs a solver step that isn't implicit in the rules
1100 * of the game and is thus treated somewhat differently.
1101 *
1102 * It marks cells whose number does not exist elsewhere in its row/column
1103 * with circles. As it happens the game generator here does mean that this
1104 * is always correct, but it's a solving method that people should not have
1105 * to rely upon (except in the hidden 'sneaky' difficulty setting) and so
1106 * all grids at 'tricky' and above are checked to make sure that the grid
1107 * is no easier if this solving step is performed beforehand.
1108 *
1109 * Calling with ss=NULL just returns the number of sneaky deductions that
1110 * would have been made.
1111 */
1112static int solve_sneaky(game_state *state, struct solver_state *ss)
1113{
1114 int i, ii, x, xx, y, yy, nunique = 0;
1115
1116 /* Clear SCRATCH flags. */
1117 for (i = 0; i < state->n; i++) state->flags[i] &= ~F_SCRATCH;
1118
1119 for (x = 0; x < state->w; x++) {
1120 for (y = 0; y < state->h; y++) {
1121 i = y*state->w + x;
1122
1123 /* Check for duplicate numbers on our row, mark (both) if so */
1124 for (xx = x; xx < state->w; xx++) {
1125 ii = y*state->w + xx;
1126 if (i == ii) continue;
1127
1128 if (state->nums[i] == state->nums[ii]) {
1129 state->flags[i] |= F_SCRATCH;
1130 state->flags[ii] |= F_SCRATCH;
1131 }
1132 }
1133
1134 /* Check for duplicate numbers on our col, mark (both) if so */
1135 for (yy = y; yy < state->h; yy++) {
1136 ii = yy*state->w + x;
1137 if (i == ii) continue;
1138
1139 if (state->nums[i] == state->nums[ii]) {
1140 state->flags[i] |= F_SCRATCH;
1141 state->flags[ii] |= F_SCRATCH;
1142 }
1143 }
1144 }
1145 }
1146
1147 /* Any cell with no marking has no duplicates on its row or column:
1148 * set its CIRCLE. */
1149 for (i = 0; i < state->n; i++) {
1150 if (!(state->flags[i] & F_SCRATCH)) {
1151 if (ss) solver_op_add(ss, i%state->w, i/state->w, CIRCLE,
1152 "SNEAKY: only one of its number in row and col");
1153 nunique += 1;
1154 } else
1155 state->flags[i] &= ~F_SCRATCH;
1156 }
1157 return nunique;
1158}
1159
1160static int solve_specific(game_state *state, int diff, bool sneaky)
1161{
1162 struct solver_state *ss = solver_state_new(state);
1163
1164 if (sneaky) solve_sneaky(state, ss);
1165
1166 /* Some solver operations we only have to perform once --
1167 * they're only based on the numbers available, and not black
1168 * squares or circles which may be added later. */
1169
1170 solve_singlesep(state, ss); /* never sets impossible */
1171 solve_doubles(state, ss); /* ditto */
1172 solve_corners(state, ss); /* ditto */
1173
1174 if (diff >= DIFF_TRICKY)
1175 solve_offsetpair(state, ss); /* ditto */
1176
1177 while (1) {
1178 if (ss->n_ops > 0) solver_ops_do(state, ss);
1179 if (state->impossible) break;
1180
1181 if (solve_allblackbutone(state, ss) > 0) continue;
1182 if (state->impossible) break;
1183
1184 if (diff >= DIFF_TRICKY) {
1185 if (solve_removesplits(state, ss) > 0) continue;
1186 if (state->impossible) break;
1187 }
1188
1189 break;
1190 }
1191
1192 solver_state_free(ss);
1193 return state->impossible ? -1 : check_complete(state, CC_MUST_FILL);
1194}
1195
1196static char *solve_game(const game_state *state, const game_state *currstate,
1197 const char *aux, const char **error)
1198{
1199 game_state *solved = dup_game(currstate);
1200 char *move = NULL;
1201
1202 if (solve_specific(solved, DIFF_ANY, false) > 0) goto solved;
1203 free_game(solved);
1204
1205 solved = dup_game(state);
1206 if (solve_specific(solved, DIFF_ANY, false) > 0) goto solved;
1207 free_game(solved);
1208
1209 *error = "Unable to solve puzzle.";
1210 return NULL;
1211
1212solved:
1213 move = game_state_diff(currstate, solved, true);
1214 free_game(solved);
1215 return move;
1216}
1217
1218/* --- Game generation --- */
1219
1220/* A correctly completed Hitori board is essentially a latin square
1221 * (no duplicated numbers in any row or column) with black squares
1222 * added such that no black square touches another, and the white
1223 * squares make a contiguous region.
1224 *
1225 * So we can generate it by:
1226 * constructing a latin square
1227 * adding black squares at random (minding the constraints)
1228 * altering the numbers under the new black squares such that
1229 the solver gets a headstart working out where they are.
1230 */
1231
1232static bool new_game_is_good(const game_params *params,
1233 game_state *state, game_state *tosolve)
1234{
1235 int sret, sret_easy = 0;
1236
1237 memcpy(tosolve->nums, state->nums, state->n * sizeof(int));
1238 memset(tosolve->flags, 0, state->n * sizeof(unsigned int));
1239 tosolve->completed = false;
1240 tosolve->impossible = false;
1241
1242 /*
1243 * We try and solve it twice, once at our requested difficulty level
1244 * (ensuring it's soluble at all) and once at the level below (if
1245 * it exists), which we hope to fail: if you can also solve it at
1246 * the level below then it's too easy and we have to try again.
1247 *
1248 * With this puzzle in particular there's an extra finesse, which is
1249 * that we check that the generated puzzle isn't too easy _with
1250 * an extra solver step first_, which is the 'sneaky' mode of deductions
1251 * (asserting that any number which fulfils the latin-square rules
1252 * on its row/column must be white). This is an artefact of the
1253 * generation process and not implicit in the rules, so we don't want
1254 * people to be able to use it to make the puzzle easier.
1255 */
1256
1257 assert(params->diff < DIFF_MAX);
1258 sret = solve_specific(tosolve, params->diff, false);
1259 if (params->diff > DIFF_EASY) {
1260 memset(tosolve->flags, 0, state->n * sizeof(unsigned int));
1261 tosolve->completed = false;
1262 tosolve->impossible = false;
1263
1264 /* this is the only time the 'sneaky' flag is set. */
1265 sret_easy = solve_specific(tosolve, params->diff-1, true);
1266 }
1267
1268 if (sret <= 0 || sret_easy > 0) {
1269 debug(("Generated puzzle %s at chosen difficulty %s\n",
1270 sret <= 0 ? "insoluble" : "too easy",
1271 singles_diffnames[params->diff]));
1272 return false;
1273 }
1274 return true;
1275}
1276
1277#define MAXTRIES 20
1278
1279static int best_black_col(game_state *state, random_state *rs, int *scratch,
1280 int i, int *rownums, int *colnums)
1281{
1282 int w = state->w, x = i%w, y = i/w, j, o = state->o;
1283
1284 /* Randomise the list of numbers to try. */
1285 for (i = 0; i < o; i++) scratch[i] = i;
1286 shuffle(scratch, o, sizeof(int), rs);
1287
1288 /* Try each number in turn, first giving preference to removing
1289 * latin-square characteristics (i.e. those numbers which only
1290 * occur once in a row/column). The '&&' here, although intuitively
1291 * wrong, results in a smaller number of 'sneaky' deductions on
1292 * solvable boards. */
1293 for (i = 0; i < o; i++) {
1294 j = scratch[i] + 1;
1295 if (rownums[y*o + j-1] == 1 && colnums[x*o + j-1] == 1)
1296 goto found;
1297 }
1298
1299 /* Then try each number in turn returning the first one that's
1300 * not actually unique in its row/column (see comment below) */
1301 for (i = 0; i < o; i++) {
1302 j = scratch[i] + 1;
1303 if (rownums[y*o + j-1] != 0 || colnums[x*o + j-1] != 0)
1304 goto found;
1305 }
1306 assert(!"unable to place number under black cell.");
1307 return 0;
1308
1309found:
1310 /* Update column and row counts assuming this number will be placed. */
1311 rownums[y*o + j-1] += 1;
1312 colnums[x*o + j-1] += 1;
1313 return j;
1314}
1315
1316static char *new_game_desc(const game_params *params_orig, random_state *rs,
1317 char **aux, bool interactive)
1318{
1319 game_params *params = dup_params(params_orig);
1320 game_state *state = blank_game(params->w, params->h);
1321 game_state *tosolve = blank_game(params->w, params->h);
1322 int i, j, *scratch, *rownums, *colnums, x, y, ntries;
1323 int w = state->w, h = state->h, o = state->o;
1324 char *ret;
1325 digit *latin;
1326 struct solver_state *ss = solver_state_new(state);
1327
1328 /* Downgrade difficulty to Easy for puzzles so tiny that they aren't
1329 * possible to generate at Tricky. These are 2x2, 2x3 and 3x3, i.e.
1330 * any puzzle that doesn't have one dimension at least 4. */
1331 if ((w < 4 || h < 4) && params->diff > DIFF_EASY)
1332 params->diff = DIFF_EASY;
1333
1334 scratch = snewn(state->n, int);
1335 rownums = snewn(h*o, int);
1336 colnums = snewn(w*o, int);
1337
1338generate:
1339 ss->n_ops = 0;
1340 debug(("Starting game generation, size %dx%d\n", w, h));
1341
1342 memset(state->flags, 0, state->n*sizeof(unsigned int));
1343
1344 /* First, generate the latin rectangle.
1345 * The order of this, o, is max(w,h). */
1346 latin = latin_generate_rect(w, h, rs);
1347 for (i = 0; i < state->n; i++)
1348 state->nums[i] = (int)latin[i];
1349 sfree(latin);
1350 debug_state("State after latin square", state);
1351
1352 /* Add black squares at random, using bits of solver as we go (to lay
1353 * white squares), until we can lay no more blacks. */
1354 for (i = 0; i < state->n; i++)
1355 scratch[i] = i;
1356 shuffle(scratch, state->n, sizeof(int), rs);
1357 for (j = 0; j < state->n; j++) {
1358 i = scratch[j];
1359 if ((state->flags[i] & F_CIRCLE) || (state->flags[i] & F_BLACK)) {
1360 debug(("generator skipping (%d,%d): %s\n", i%w, i/w,
1361 (state->flags[i] & F_CIRCLE) ? "CIRCLE" : "BLACK"));
1362 continue; /* solver knows this must be one or the other already. */
1363 }
1364
1365 /* Add a random black cell... */
1366 solver_op_add(ss, i%w, i/w, BLACK, "Generator: adding random black cell");
1367 solver_ops_do(state, ss);
1368
1369 /* ... and do as well as we know how to lay down whites that are now forced. */
1370 solve_allblackbutone(state, ss);
1371 solver_ops_do(state, ss);
1372
1373 solve_removesplits(state, ss);
1374 solver_ops_do(state, ss);
1375
1376 if (state->impossible) {
1377 debug(("generator made impossible, restarting...\n"));
1378 goto generate;
1379 }
1380 }
1381 debug_state("State after adding blacks", state);
1382
1383 /* Now we know which squares are white and which are black, we lay numbers
1384 * under black squares at random, except that the number must appear in
1385 * white cells at least once more in the same column or row as that [black]
1386 * square. That's necessary to avoid multiple solutions, where blackening
1387 * squares in the finished puzzle becomes optional. We use two arrays:
1388 *
1389 * rownums[ROW * o + NUM-1] is the no. of white cells containing NUM in y=ROW
1390 * colnums[COL * o + NUM-1] is the no. of white cells containing NUM in x=COL
1391 */
1392
1393 memset(rownums, 0, h*o * sizeof(int));
1394 memset(colnums, 0, w*o * sizeof(int));
1395 for (i = 0; i < state->n; i++) {
1396 if (state->flags[i] & F_BLACK) continue;
1397 j = state->nums[i];
1398 x = i%w; y = i/w;
1399 rownums[y * o + j-1] += 1;
1400 colnums[x * o + j-1] += 1;
1401 }
1402
1403 ntries = 0;
1404randomise:
1405 for (i = 0; i < state->n; i++) {
1406 if (!(state->flags[i] & F_BLACK)) continue;
1407 state->nums[i] = best_black_col(state, rs, scratch, i, rownums, colnums);
1408 }
1409 debug_state("State after adding numbers", state);
1410
1411 /* DIFF_ANY just returns whatever we first generated, for testing purposes. */
1412 if (params->diff != DIFF_ANY &&
1413 !new_game_is_good(params, state, tosolve)) {
1414 ntries++;
1415 if (ntries > MAXTRIES) {
1416 debug(("Ran out of randomisation attempts, re-generating.\n"));
1417 goto generate;
1418 }
1419 debug(("Re-randomising numbers under black squares.\n"));
1420 goto randomise;
1421 }
1422
1423 ret = generate_desc(state, false);
1424
1425 free_game(tosolve);
1426 free_game(state);
1427 free_params(params);
1428 solver_state_free(ss);
1429 sfree(scratch);
1430 sfree(rownums);
1431 sfree(colnums);
1432
1433 return ret;
1434}
1435
1436static const char *validate_desc(const game_params *params, const char *desc)
1437{
1438 const char *ret = NULL;
1439
1440 unpick_desc(params, desc, NULL, &ret);
1441 return ret;
1442}
1443
1444static game_state *new_game(midend *me, const game_params *params,
1445 const char *desc)
1446{
1447 game_state *state = NULL;
1448
1449 unpick_desc(params, desc, &state, NULL);
1450 if (!state) assert(!"new_game failed to unpick");
1451 return state;
1452}
1453
1454/* --- Game UI and move routines --- */
1455
1456struct game_ui {
1457 int cx, cy;
1458 bool cshow, show_black_nums;
1459};
1460
1461static game_ui *new_ui(const game_state *state)
1462{
1463 game_ui *ui = snew(game_ui);
1464
1465 ui->cx = ui->cy = 0;
1466 ui->cshow = getenv_bool("PUZZLES_SHOW_CURSOR", false);
1467 ui->show_black_nums = false;
1468
1469 return ui;
1470}
1471
1472static config_item *get_prefs(game_ui *ui)
1473{
1474 config_item *ret;
1475
1476 ret = snewn(N_PREF_ITEMS+1, config_item);
1477
1478 ret[PREF_SHOW_BLACK_NUMS].name = "Show numbers on black squares";
1479 ret[PREF_SHOW_BLACK_NUMS].kw = "show-black-nums";
1480 ret[PREF_SHOW_BLACK_NUMS].type = C_BOOLEAN;
1481 ret[PREF_SHOW_BLACK_NUMS].u.boolean.bval = ui->show_black_nums;
1482
1483 ret[N_PREF_ITEMS].name = NULL;
1484 ret[N_PREF_ITEMS].type = C_END;
1485
1486 return ret;
1487}
1488
1489static void set_prefs(game_ui *ui, const config_item *cfg)
1490{
1491 ui->show_black_nums = cfg[PREF_SHOW_BLACK_NUMS].u.boolean.bval;
1492}
1493
1494static void free_ui(game_ui *ui)
1495{
1496 sfree(ui);
1497}
1498
1499static void game_changed_state(game_ui *ui, const game_state *oldstate,
1500 const game_state *newstate)
1501{
1502 if (!oldstate->completed && newstate->completed)
1503 ui->cshow = false;
1504}
1505
1506static const char *current_key_label(const game_ui *ui,
1507 const game_state *state, int button)
1508{
1509 if (IS_CURSOR_SELECT(button) && ui->cshow) {
1510 unsigned int f = state->flags[ui->cy * state->w + ui->cx];
1511 if (f & F_BLACK) return "Restore";
1512 if (f & F_CIRCLE) return "Remove";
1513 return button == CURSOR_SELECT ? "Black" : "Circle";
1514 }
1515 return "";
1516}
1517
1518#define DS_BLACK 0x1
1519#define DS_CIRCLE 0x2
1520#define DS_CURSOR 0x4
1521#define DS_BLACK_NUM 0x8
1522#define DS_ERROR 0x10
1523#define DS_FLASH 0x20
1524#define DS_IMPOSSIBLE 0x40
1525
1526struct game_drawstate {
1527 int tilesize;
1528 bool started, solved;
1529 int w, h, n;
1530
1531 unsigned int *flags;
1532};
1533
1534static char *interpret_move(const game_state *state, game_ui *ui,
1535 const game_drawstate *ds,
1536 int mx, int my, int button)
1537{
1538 char buf[80], c;
1539 int i, x = FROMCOORD(mx), y = FROMCOORD(my);
1540 enum { NONE, TOGGLE_BLACK, TOGGLE_CIRCLE, UI } action = NONE;
1541
1542 if (IS_CURSOR_MOVE(button))
1543 return move_cursor(button, &ui->cx, &ui->cy, state->w, state->h, true,
1544 &ui->cshow);
1545 else if (IS_CURSOR_SELECT(button)) {
1546 x = ui->cx; y = ui->cy;
1547 if (!ui->cshow) {
1548 action = UI;
1549 ui->cshow = true;
1550 }
1551 if (button == CURSOR_SELECT) {
1552 action = TOGGLE_BLACK;
1553 } else if (button == CURSOR_SELECT2) {
1554 action = TOGGLE_CIRCLE;
1555 }
1556 } else if (IS_MOUSE_DOWN(button)) {
1557 if (ui->cshow) {
1558 ui->cshow = false;
1559 action = UI;
1560 }
1561 if (!INGRID(state, x, y)) {
1562 ui->show_black_nums = !ui->show_black_nums;
1563 action = UI;
1564 } else if (button == LEFT_BUTTON) {
1565 action = TOGGLE_BLACK;
1566 } else if (button == RIGHT_BUTTON) {
1567 action = TOGGLE_CIRCLE;
1568 }
1569 }
1570 if (action == UI) return MOVE_UI_UPDATE;
1571
1572 if (action == TOGGLE_BLACK || action == TOGGLE_CIRCLE) {
1573 i = y * state->w + x;
1574 if (state->flags[i] & (F_BLACK | F_CIRCLE))
1575 c = 'E';
1576 else
1577 c = (action == TOGGLE_BLACK) ? 'B' : 'C';
1578 sprintf(buf, "%c%d,%d", (int)c, x, y);
1579 return dupstr(buf);
1580 }
1581
1582 return NULL;
1583}
1584
1585static game_state *execute_move(const game_state *state, const char *move)
1586{
1587 game_state *ret = dup_game(state);
1588 int x, y, i, n;
1589
1590 debug(("move: %s\n", move));
1591
1592 while (*move) {
1593 char c = *move;
1594 if (c == 'B' || c == 'C' || c == 'E') {
1595 move++;
1596 if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1597 !INGRID(state, x, y))
1598 goto badmove;
1599
1600 i = y*ret->w + x;
1601 ret->flags[i] &= ~(F_CIRCLE | F_BLACK); /* empty first, always. */
1602 if (c == 'B')
1603 ret->flags[i] |= F_BLACK;
1604 else if (c == 'C')
1605 ret->flags[i] |= F_CIRCLE;
1606 move += n;
1607 } else if (c == 'S') {
1608 move++;
1609 ret->used_solve = true;
1610 } else
1611 goto badmove;
1612
1613 if (*move == ';')
1614 move++;
1615 else if (*move)
1616 goto badmove;
1617 }
1618 if (check_complete(ret, CC_MARK_ERRORS)) ret->completed = true;
1619 return ret;
1620
1621badmove:
1622 free_game(ret);
1623 return NULL;
1624}
1625
1626/* ----------------------------------------------------------------------
1627 * Drawing routines.
1628 */
1629
1630static void game_compute_size(const game_params *params, int tilesize,
1631 const game_ui *ui, int *x, int *y)
1632{
1633 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1634 struct { int tilesize; } ads, *ds = &ads;
1635 ads.tilesize = tilesize;
1636
1637 *x = TILE_SIZE * params->w + 2 * BORDER;
1638 *y = TILE_SIZE * params->h + 2 * BORDER;
1639}
1640
1641static void game_set_size(drawing *dr, game_drawstate *ds,
1642 const game_params *params, int tilesize)
1643{
1644 ds->tilesize = tilesize;
1645}
1646
1647static float *game_colours(frontend *fe, int *ncolours)
1648{
1649 float *ret = snewn(3 * NCOLOURS, float);
1650 int i;
1651
1652 game_mkhighlight(fe, ret, COL_BACKGROUND, -1, COL_LOWLIGHT);
1653 for (i = 0; i < 3; i++) {
1654 ret[COL_BLACK * 3 + i] = 0.0F;
1655 ret[COL_BLACKNUM * 3 + i] = 0.4F;
1656 ret[COL_WHITE * 3 + i] = 1.0F;
1657 ret[COL_GRID * 3 + i] = ret[COL_LOWLIGHT * 3 + i];
1658 ret[COL_UNUSED1 * 3 + i] = 0.0F; /* To placate an assertion. */
1659 }
1660 ret[COL_CURSOR * 3 + 0] = 0.2F;
1661 ret[COL_CURSOR * 3 + 1] = 0.8F;
1662 ret[COL_CURSOR * 3 + 2] = 0.0F;
1663
1664 ret[COL_ERROR * 3 + 0] = 1.0F;
1665 ret[COL_ERROR * 3 + 1] = 0.0F;
1666 ret[COL_ERROR * 3 + 2] = 0.0F;
1667
1668 *ncolours = NCOLOURS;
1669 return ret;
1670}
1671
1672static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1673{
1674 struct game_drawstate *ds = snew(struct game_drawstate);
1675
1676 ds->tilesize = 0;
1677 ds->started = false;
1678 ds->solved = false;
1679 ds->w = state->w;
1680 ds->h = state->h;
1681 ds->n = state->n;
1682
1683 ds->flags = snewn(state->n, unsigned int);
1684
1685 memset(ds->flags, 0, state->n*sizeof(unsigned int));
1686
1687 return ds;
1688}
1689
1690static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1691{
1692 sfree(ds->flags);
1693 sfree(ds);
1694}
1695
1696static void tile_redraw(drawing *dr, game_drawstate *ds, int x, int y,
1697 int num, unsigned int f)
1698{
1699 int tcol, bg, cx, cy, tsz;
1700 bool dnum;
1701 char buf[32];
1702
1703 if (f & DS_BLACK) {
1704 bg = (f & DS_ERROR) ? COL_ERROR : COL_BLACK;
1705 tcol = COL_BLACKNUM;
1706 dnum = (f & DS_BLACK_NUM);
1707 } else {
1708 bg = (f & DS_FLASH) ? COL_LOWLIGHT : COL_BACKGROUND;
1709 tcol = (f & DS_ERROR) ? COL_ERROR : COL_BLACK;
1710 dnum = true;
1711 }
1712
1713 cx = x + TILE_SIZE/2; cy = y + TILE_SIZE/2;
1714
1715 draw_rect(dr, x, y, TILE_SIZE, TILE_SIZE, bg);
1716 draw_rect_outline(dr, x, y, TILE_SIZE, TILE_SIZE,
1717 (f & DS_IMPOSSIBLE) ? COL_ERROR : COL_GRID);
1718
1719 if (f & DS_CIRCLE) {
1720 draw_circle(dr, cx, cy, CRAD, tcol, tcol);
1721 draw_circle(dr, cx, cy, CRAD-1, bg, tcol);
1722 }
1723
1724 if (dnum) {
1725 sprintf(buf, "%d", num);
1726 if (strlen(buf) == 1)
1727 tsz = TEXTSZ;
1728 else
1729 tsz = (CRAD*2 - 1) / strlen(buf);
1730 draw_text(dr, cx, cy, FONT_VARIABLE, tsz,
1731 ALIGN_VCENTRE | ALIGN_HCENTRE, tcol, buf);
1732 }
1733
1734 if (f & DS_CURSOR)
1735 draw_rect_corners(dr, cx, cy, TEXTSZ/2, COL_CURSOR);
1736
1737 draw_update(dr, x, y, TILE_SIZE, TILE_SIZE);
1738}
1739
1740static void game_redraw(drawing *dr, game_drawstate *ds,
1741 const game_state *oldstate, const game_state *state,
1742 int dir, const game_ui *ui,
1743 float animtime, float flashtime)
1744{
1745 int x, y, i, flash;
1746 unsigned int f;
1747
1748 flash = (int)(flashtime * 5 / FLASH_TIME) % 2;
1749
1750 if (!ds->started) {
1751 int wsz = TILE_SIZE * state->w + 2 * BORDER;
1752 int hsz = TILE_SIZE * state->h + 2 * BORDER;
1753 draw_rect_outline(dr, COORD(0)-1, COORD(0)-1,
1754 TILE_SIZE * state->w + 2, TILE_SIZE * state->h + 2,
1755 COL_GRID);
1756 draw_update(dr, 0, 0, wsz, hsz);
1757 }
1758 for (x = 0; x < state->w; x++) {
1759 for (y = 0; y < state->h; y++) {
1760 i = y*state->w + x;
1761 f = 0;
1762
1763 if (flash) f |= DS_FLASH;
1764 if (state->impossible) f |= DS_IMPOSSIBLE;
1765
1766 if (ui->cshow && x == ui->cx && y == ui->cy)
1767 f |= DS_CURSOR;
1768 if (state->flags[i] & F_BLACK) {
1769 f |= DS_BLACK;
1770 if (ui->show_black_nums) f |= DS_BLACK_NUM;
1771 }
1772 if (state->flags[i] & F_CIRCLE)
1773 f |= DS_CIRCLE;
1774 if (state->flags[i] & F_ERROR)
1775 f |= DS_ERROR;
1776
1777 if (!ds->started || ds->flags[i] != f) {
1778 tile_redraw(dr, ds, COORD(x), COORD(y),
1779 state->nums[i], f);
1780 ds->flags[i] = f;
1781 }
1782 }
1783 }
1784 ds->started = true;
1785}
1786
1787static float game_anim_length(const game_state *oldstate,
1788 const game_state *newstate, int dir, game_ui *ui)
1789{
1790 return 0.0F;
1791}
1792
1793static float game_flash_length(const game_state *oldstate,
1794 const game_state *newstate, int dir, game_ui *ui)
1795{
1796 if (!oldstate->completed &&
1797 newstate->completed && !newstate->used_solve)
1798 return FLASH_TIME;
1799 return 0.0F;
1800}
1801
1802static void game_get_cursor_location(const game_ui *ui,
1803 const game_drawstate *ds,
1804 const game_state *state,
1805 const game_params *params,
1806 int *x, int *y, int *w, int *h)
1807{
1808 if(ui->cshow) {
1809 *x = COORD(ui->cx);
1810 *y = COORD(ui->cy);
1811 *w = *h = TILE_SIZE;
1812 }
1813}
1814
1815static int game_status(const game_state *state)
1816{
1817 return state->completed ? +1 : 0;
1818}
1819
1820static void game_print_size(const game_params *params, const game_ui *ui,
1821 float *x, float *y)
1822{
1823 int pw, ph;
1824
1825 /* 8mm squares by default. */
1826 game_compute_size(params, 800, ui, &pw, &ph);
1827 *x = pw / 100.0F;
1828 *y = ph / 100.0F;
1829}
1830
1831static void game_print(drawing *dr, const game_state *state, const game_ui *ui,
1832 int tilesize)
1833{
1834 int ink = print_mono_colour(dr, 0);
1835 int paper = print_mono_colour(dr, 1);
1836 int x, y, ox, oy, i;
1837 char buf[32];
1838
1839 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1840 game_drawstate ads, *ds = &ads;
1841 game_set_size(dr, ds, NULL, tilesize);
1842
1843 print_line_width(dr, 2 * TILE_SIZE / 40);
1844
1845 for (x = 0; x < state->w; x++) {
1846 for (y = 0; y < state->h; y++) {
1847 ox = COORD(x); oy = COORD(y);
1848 i = y*state->w+x;
1849
1850 if (state->flags[i] & F_BLACK) {
1851 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink);
1852 } else {
1853 draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink);
1854
1855 if (state->flags[i] & DS_CIRCLE)
1856 draw_circle(dr, ox+TILE_SIZE/2, oy+TILE_SIZE/2, CRAD,
1857 paper, ink);
1858
1859 sprintf(buf, "%d", state->nums[i]);
1860 draw_text(dr, ox+TILE_SIZE/2, oy+TILE_SIZE/2, FONT_VARIABLE,
1861 TEXTSZ/strlen(buf), ALIGN_VCENTRE | ALIGN_HCENTRE,
1862 ink, buf);
1863 }
1864 }
1865 }
1866}
1867
1868#ifdef COMBINED
1869#define thegame singles
1870#endif
1871
1872const struct game thegame = {
1873 "Singles", "games.singles", "singles",
1874 default_params,
1875 game_fetch_preset, NULL,
1876 decode_params,
1877 encode_params,
1878 free_params,
1879 dup_params,
1880 true, game_configure, custom_params,
1881 validate_params,
1882 new_game_desc,
1883 validate_desc,
1884 new_game,
1885 dup_game,
1886 free_game,
1887 true, solve_game,
1888 true, game_can_format_as_text_now, game_text_format,
1889 get_prefs, set_prefs,
1890 new_ui,
1891 free_ui,
1892 NULL, /* encode_ui */
1893 NULL, /* decode_ui */
1894 NULL, /* game_request_keys */
1895 game_changed_state,
1896 current_key_label,
1897 interpret_move,
1898 execute_move,
1899 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1900 game_colours,
1901 game_new_drawstate,
1902 game_free_drawstate,
1903 game_redraw,
1904 game_anim_length,
1905 game_flash_length,
1906 game_get_cursor_location,
1907 game_status,
1908 true, false, game_print_size, game_print,
1909 false, /* wants_statusbar */
1910 false, NULL, /* timing_state */
1911 REQUIRE_RBUTTON, /* flags */
1912};
1913
1914#ifdef STANDALONE_SOLVER
1915
1916#include <time.h>
1917#include <stdarg.h>
1918
1919static void start_soak(game_params *p, random_state *rs)
1920{
1921 time_t tt_start, tt_now, tt_last;
1922 char *desc, *aux;
1923 game_state *s;
1924 int i, n = 0, ndiff[DIFF_MAX], diff, sret, nblack = 0, nsneaky = 0;
1925
1926 tt_start = tt_now = time(NULL);
1927
1928 printf("Soak-testing a %dx%d grid.\n", p->w, p->h);
1929 p->diff = DIFF_ANY;
1930
1931 memset(ndiff, 0, DIFF_MAX * sizeof(int));
1932
1933 while (1) {
1934 n++;
1935 desc = new_game_desc(p, rs, &aux, false);
1936 s = new_game(NULL, p, desc);
1937 nsneaky += solve_sneaky(s, NULL);
1938
1939 for (diff = 0; diff < DIFF_MAX; diff++) {
1940 memset(s->flags, 0, s->n * sizeof(unsigned int));
1941 s->completed = false;
1942 s->impossible = false;
1943 sret = solve_specific(s, diff, false);
1944 if (sret > 0) {
1945 ndiff[diff]++;
1946 break;
1947 } else if (sret < 0)
1948 fprintf(stderr, "Impossible! %s\n", desc);
1949 }
1950 for (i = 0; i < s->n; i++) {
1951 if (s->flags[i] & F_BLACK) nblack++;
1952 }
1953 free_game(s);
1954 sfree(desc);
1955
1956 tt_last = time(NULL);
1957 if (tt_last > tt_now) {
1958 tt_now = tt_last;
1959 printf("%d total, %3.1f/s, bl/sn %3.1f%%/%3.1f%%: ",
1960 n, (double)n / ((double)tt_now - tt_start),
1961 ((double)nblack * 100.0) / (double)(n * p->w * p->h),
1962 ((double)nsneaky * 100.0) / (double)(n * p->w * p->h));
1963 for (diff = 0; diff < DIFF_MAX; diff++) {
1964 if (diff > 0) printf(", ");
1965 printf("%d (%3.1f%%) %s",
1966 ndiff[diff], (double)ndiff[diff] * 100.0 / (double)n,
1967 singles_diffnames[diff]);
1968 }
1969 printf("\n");
1970 }
1971 }
1972}
1973
1974int main(int argc, char **argv)
1975{
1976 char *id = NULL, *desc, *desc_gen = NULL, *tgame, *aux;
1977 const char *err;
1978 game_state *s = NULL;
1979 game_params *p = NULL;
1980 int soln, ret = 1;
1981 bool soak = false;
1982 time_t seed = time(NULL);
1983 random_state *rs = NULL;
1984
1985 setvbuf(stdout, NULL, _IONBF, 0);
1986
1987 while (--argc > 0) {
1988 char *p = *++argv;
1989 if (!strcmp(p, "-v")) {
1990 verbose = true;
1991 } else if (!strcmp(p, "--soak")) {
1992 soak = true;
1993 } else if (!strcmp(p, "--seed")) {
1994 if (argc == 0) {
1995 fprintf(stderr, "%s: --seed needs an argument", argv[0]);
1996 goto done;
1997 }
1998 seed = (time_t)atoi(*++argv);
1999 argc--;
2000 } else if (*p == '-') {
2001 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2002 return 1;
2003 } else {
2004 id = p;
2005 }
2006 }
2007
2008 rs = random_new((void*)&seed, sizeof(time_t));
2009
2010 if (!id) {
2011 fprintf(stderr, "usage: %s [-v] [--soak] <params> | <game_id>\n", argv[0]);
2012 goto done;
2013 }
2014 desc = strchr(id, ':');
2015 if (desc) *desc++ = '\0';
2016
2017 p = default_params();
2018 decode_params(p, id);
2019 err = validate_params(p, true);
2020 if (err) {
2021 fprintf(stderr, "%s: %s", argv[0], err);
2022 goto done;
2023 }
2024
2025 if (soak) {
2026 if (desc) {
2027 fprintf(stderr, "%s: --soak only needs params, not game desc.\n", argv[0]);
2028 goto done;
2029 }
2030 start_soak(p, rs);
2031 } else {
2032 if (!desc) desc = desc_gen = new_game_desc(p, rs, &aux, false);
2033
2034 err = validate_desc(p, desc);
2035 if (err) {
2036 fprintf(stderr, "%s: %s\n", argv[0], err);
2037 free_params(p);
2038 goto done;
2039 }
2040 s = new_game(NULL, p, desc);
2041
2042 if (verbose) {
2043 tgame = game_text_format(s);
2044 fputs(tgame, stdout);
2045 sfree(tgame);
2046 }
2047
2048 soln = solve_specific(s, DIFF_ANY, false);
2049 tgame = game_text_format(s);
2050 fputs(tgame, stdout);
2051 sfree(tgame);
2052 printf("Game was %s.\n\n",
2053 soln < 0 ? "impossible" : soln > 0 ? "solved" : "not solved");
2054 }
2055 ret = 0;
2056
2057done:
2058 if (desc_gen) sfree(desc_gen);
2059 if (p) free_params(p);
2060 if (s) free_game(s);
2061 if (rs) random_free(rs);
2062
2063 return ret;
2064}
2065
2066#endif
2067
2068
2069/* vim: set shiftwidth=4 tabstop=8: */