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 * Implementation of 'Train Tracks', a puzzle from the Times on Saturday.
3 *
4 * "Lay tracks to enable the train to travel from village A to village B.
5 * The numbers indicate how many sections of rail go in each row and
6 * column. There are only straight rails and curved rails. The track
7 * cannot cross itself."
8 *
9 * Puzzles:
10 * #9 8x8:d9s5c6zgAa,1,4,1,4,4,3,S3,5,2,2,4,S5,3,3,5,1
11 * #112 8x8:w6x5mAa,1,3,1,4,6,4,S4,3,3,4,5,2,4,2,S5,1
12 * #113 8x8:gCx5xAf,1,S4,2,5,4,6,2,3,4,2,5,2,S4,4,5,1
13 * #114 8x8:p5fAzkAb,1,6,3,3,3,S6,2,3,5,4,S3,3,5,1,5,1
14 * #115 8x8:zi9d5tAb,1,3,4,5,3,S4,2,4,2,6,2,3,6,S3,3,1
15 * #942 8x8:n5iCfAzAe,2,2,S5,5,3,5,4,5,4,5,2,S5,3,4,5,3
16 */
17
18#include <stdio.h>
19#include <stdlib.h>
20#include <string.h>
21#include <assert.h>
22#include <ctype.h>
23#include <limits.h>
24#ifdef NO_TGMATH_H
25# include <math.h>
26#else
27# include <tgmath.h>
28#endif
29
30#include "puzzles.h"
31
32/* --- Game parameters --- */
33
34/*
35 * Difficulty levels. I do some macro ickery here to ensure that my
36 * enum and the various forms of my name list always match up.
37 */
38#define DIFFLIST(A) \
39 A(EASY,Easy,e) \
40 A(TRICKY,Tricky,t) \
41 A(HARD,Hard,h) \
42 /* end of list */
43
44#define ENUM(upper,title,lower) DIFF_ ## upper,
45#define TITLE(upper,title,lower) #title,
46#define ENCODE(upper,title,lower) #lower
47#define CONFIG(upper,title,lower) ":" #title
48enum { DIFFLIST(ENUM) DIFFCOUNT };
49static char const *const tracks_diffnames[] = { DIFFLIST(TITLE) };
50static char const tracks_diffchars[] = DIFFLIST(ENCODE);
51#define DIFFCONFIG DIFFLIST(CONFIG)
52
53struct game_params {
54 int w, h, diff;
55 bool single_ones;
56};
57
58static game_params *default_params(void)
59{
60 game_params *ret = snew(game_params);
61
62 ret->w = ret->h = 8;
63 ret->diff = DIFF_TRICKY;
64 ret->single_ones = true;
65
66 return ret;
67}
68
69static const struct game_params tracks_presets[] = {
70 {8, 8, DIFF_EASY, 1},
71 {8, 8, DIFF_TRICKY, 1},
72 {10, 8, DIFF_EASY, 1},
73 {10, 8, DIFF_TRICKY, 1 },
74 {10, 10, DIFF_EASY, 1},
75 {10, 10, DIFF_TRICKY, 1},
76 {10, 10, DIFF_HARD, 1},
77 {15, 10, DIFF_EASY, 1},
78 {15, 10, DIFF_TRICKY, 1},
79 {15, 15, DIFF_EASY, 1},
80 {15, 15, DIFF_TRICKY, 1},
81 {15, 15, DIFF_HARD, 1},
82};
83
84static bool game_fetch_preset(int i, char **name, game_params **params)
85{
86 game_params *ret;
87 char str[80];
88
89 if (i < 0 || i >= lenof(tracks_presets))
90 return false;
91
92 ret = snew(game_params);
93 *ret = tracks_presets[i];
94
95 sprintf(str, "%dx%d %s", ret->w, ret->h, tracks_diffnames[ret->diff]);
96
97 *name = dupstr(str);
98 *params = ret;
99 return true;
100}
101
102static void free_params(game_params *params)
103{
104 sfree(params);
105}
106
107static game_params *dup_params(const game_params *params)
108{
109 game_params *ret = snew(game_params);
110 *ret = *params; /* structure copy */
111 return ret;
112}
113
114static void decode_params(game_params *params, char const *string)
115{
116 params->w = params->h = atoi(string);
117 while (*string && isdigit((unsigned char)*string)) string++;
118 if (*string == 'x') {
119 string++;
120 params->h = atoi(string);
121 while (*string && isdigit((unsigned char)*string)) string++;
122 }
123 if (*string == 'd') {
124 int i;
125 string++;
126 params->diff = DIFF_TRICKY;
127 for (i = 0; i < DIFFCOUNT; i++)
128 if (*string == tracks_diffchars[i])
129 params->diff = i;
130 if (*string) string++;
131 }
132 params->single_ones = true;
133 if (*string == 'o') {
134 params->single_ones = false;
135 string++;
136 }
137
138}
139
140static char *encode_params(const game_params *params, bool full)
141{
142 char buf[120];
143
144 sprintf(buf, "%dx%d", params->w, params->h);
145 if (full)
146 sprintf(buf + strlen(buf), "d%c%s",
147 tracks_diffchars[params->diff],
148 params->single_ones ? "" : "o");
149 return dupstr(buf);
150}
151
152static config_item *game_configure(const game_params *params)
153{
154 config_item *ret;
155 char buf[80];
156
157 ret = snewn(5, config_item);
158
159 ret[0].name = "Width";
160 ret[0].type = C_STRING;
161 sprintf(buf, "%d", params->w);
162 ret[0].u.string.sval = dupstr(buf);
163
164 ret[1].name = "Height";
165 ret[1].type = C_STRING;
166 sprintf(buf, "%d", params->h);
167 ret[1].u.string.sval = dupstr(buf);
168
169 ret[2].name = "Difficulty";
170 ret[2].type = C_CHOICES;
171 ret[2].u.choices.choicenames = DIFFCONFIG;
172 ret[2].u.choices.selected = params->diff;
173
174 ret[3].name = "Disallow consecutive 1 clues";
175 ret[3].type = C_BOOLEAN;
176 ret[3].u.boolean.bval = params->single_ones;
177
178 ret[4].name = NULL;
179 ret[4].type = C_END;
180
181 return ret;
182}
183
184static game_params *custom_params(const config_item *cfg)
185{
186 game_params *ret = snew(game_params);
187
188 ret->w = atoi(cfg[0].u.string.sval);
189 ret->h = atoi(cfg[1].u.string.sval);
190 ret->diff = cfg[2].u.choices.selected;
191 ret->single_ones = cfg[3].u.boolean.bval;
192
193 return ret;
194}
195
196static const char *validate_params(const game_params *params, bool full)
197{
198 /*
199 * Generating anything under 4x4 runs into trouble of one kind
200 * or another.
201 */
202 if (params->w < 4 || params->h < 4)
203 return "Width and height must both be at least four";
204 if (params->w > INT_MAX / params->h)
205 return "Width times height must not be unreasonably large";
206 return NULL;
207}
208
209/* --- Game state --- */
210
211/* flag usage copied from pearl */
212
213#define R 1
214#define U 2
215#define L 4
216#define D 8
217
218#define MOVECHAR(m) ((m==R)?'R':(m==U)?'U':(m==L)?'L':(m==D)?'D':'?')
219
220#define DX(d) ( ((d)==R) - ((d)==L) )
221#define DY(d) ( ((d)==D) - ((d)==U) )
222
223#define F(d) (((d << 2) | (d >> 2)) & 0xF)
224#define C(d) (((d << 3) | (d >> 1)) & 0xF)
225#define A(d) (((d << 1) | (d >> 3)) & 0xF)
226
227#define LR (L | R)
228#define RL (R | L)
229#define UD (U | D)
230#define DU (D | U)
231#define LU (L | U)
232#define UL (U | L)
233#define LD (L | D)
234#define DL (D | L)
235#define RU (R | U)
236#define UR (U | R)
237#define RD (R | D)
238#define DR (D | R)
239#define ALLDIR 15
240#define BLANK 0
241#define UNKNOWN 15
242
243static const int nbits[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
244
245/* square grid flags */
246#define S_TRACK 1 /* a track passes through this square (--> 2 edges) */
247#define S_NOTRACK 2 /* no track passes through this square */
248#define S_ERROR 4
249#define S_CLUE 8
250#define S_MARK 16
251
252#define S_FLASH_SHIFT 8 /* Position of tile in solved track */
253#define S_FLASH_WIDTH 8 /* Width of above sub-field */
254#define S_FLASH_MASK ((1 << S_FLASH_WIDTH) - 1)
255#define S_TRACK_SHIFT 16 /* U/D/L/R flags for edge track indicators */
256#define S_NOTRACK_SHIFT 20 /* U/D/L/R flags for edge no-track indicators */
257
258/* edge grid flags */
259#define E_TRACK 1 /* a track passes through this edge */
260#define E_NOTRACK 2 /* no track passes through this edge */
261
262struct numbers {
263 int refcount;
264 int *numbers; /* sz w+h */
265 int row_s, col_s; /* stations: TODO think about multiple lines
266 (for bigger grids)? */
267};
268
269#define INGRID(state, gx, gy) ((gx) >= 0 && (gx) < (state)->p.w && \
270 (gy) >= 0 && (gy) < (state)->p.h)
271
272struct game_state {
273 game_params p;
274 unsigned int *sflags; /* size w*h */
275 struct numbers *numbers;
276 int *num_errors; /* size w+h */
277 bool completed, used_solve, impossible;
278};
279
280/* Return the four directions in which a particular edge flag is set, around a square. */
281static int S_E_DIRS(const game_state *state, int sx, int sy,
282 unsigned int eflag) {
283 return (state->sflags[sy*state->p.w+sx] >>
284 ((eflag == E_TRACK) ? S_TRACK_SHIFT : S_NOTRACK_SHIFT)) & ALLDIR;
285}
286
287/* Count the number of a particular edge flag around a grid square. */
288static int S_E_COUNT(const game_state *state, int sx, int sy,
289 unsigned int eflag) {
290 return nbits[S_E_DIRS(state, sx, sy, eflag)];
291}
292
293/* Return the two flags (E_TRACK and/or E_NOTRACK) set on a specific
294 * edge of a square. */
295static unsigned S_E_FLAGS(const game_state *state, int sx, int sy, int d) {
296 unsigned f = state->sflags[sy*state->p.w+sx];
297 int t = (f & (d << S_TRACK_SHIFT)), nt = (f & (d << S_NOTRACK_SHIFT));
298 return (t ? E_TRACK : 0) | (nt ? E_NOTRACK : 0);
299}
300
301static bool S_E_ADJ(const game_state *state, int sx, int sy, int d, int *ax,
302 int *ay, unsigned int *ad) {
303 if (d == L && sx > 0) { *ax = sx-1; *ay = sy; *ad = R; return true; }
304 if (d == R && sx < state->p.w-1) { *ax = sx+1; *ay = sy; *ad = L; return true; }
305 if (d == U && sy > 0) { *ax = sx; *ay = sy-1; *ad = D; return true; }
306 if (d == D && sy < state->p.h-1) { *ax = sx; *ay = sy+1; *ad = U; return true; }
307
308 return false;
309}
310
311/* Sets flag (E_TRACK or E_NOTRACK) on a given edge of a square. */
312static void S_E_SET(game_state *state, int sx, int sy, int d,
313 unsigned int eflag) {
314 unsigned shift = (eflag == E_TRACK) ? S_TRACK_SHIFT : S_NOTRACK_SHIFT, ad;
315 int ax, ay;
316
317 state->sflags[sy*state->p.w+sx] |= (d << shift);
318
319 if (S_E_ADJ(state, sx, sy, d, &ax, &ay, &ad)) {
320 state->sflags[ay*state->p.w+ax] |= (ad << shift);
321 }
322}
323
324/* Clears flag (E_TRACK or E_NOTRACK) on a given edge of a square. */
325static void S_E_CLEAR(game_state *state, int sx, int sy, int d,
326 unsigned int eflag) {
327 unsigned shift = (eflag == E_TRACK) ? S_TRACK_SHIFT : S_NOTRACK_SHIFT, ad;
328 int ax, ay;
329
330 state->sflags[sy*state->p.w+sx] &= ~(d << shift);
331
332 if (S_E_ADJ(state, sx, sy, d, &ax, &ay, &ad)) {
333 state->sflags[ay*state->p.w+ax] &= ~(ad << shift);
334 }
335}
336
337static void clear_game(game_state *state)
338{
339 int w = state->p.w, h = state->p.h;
340
341 memset(state->sflags, 0, w*h * sizeof(unsigned int));
342
343 memset(state->numbers->numbers, 0, (w+h) * sizeof(int));
344 state->numbers->col_s = state->numbers->row_s = -1;
345
346 memset(state->num_errors, 0, (w+h) * sizeof(int));
347
348 state->completed = state->used_solve = state->impossible = false;
349}
350
351static game_state *blank_game(const game_params *params)
352{
353 game_state *state = snew(game_state);
354 int w = params->w, h = params->h;
355
356 state->p = *params;
357
358 state->sflags = snewn(w*h, unsigned int);
359
360 state->numbers = snew(struct numbers);
361 state->numbers->refcount = 1;
362 state->numbers->numbers = snewn(w+h, int);
363
364 state->num_errors = snewn(w+h, int);
365
366 clear_game(state);
367
368 return state;
369}
370
371static void copy_game_flags(const game_state *src, game_state *dest)
372{
373 int w = src->p.w, h = src->p.h;
374
375 memcpy(dest->sflags, src->sflags, w*h*sizeof(unsigned int));
376}
377
378static game_state *dup_game(const game_state *state)
379{
380 int w = state->p.w, h = state->p.h;
381 game_state *ret = snew(game_state);
382
383 ret->p = state->p; /* structure copy */
384
385 ret->sflags = snewn(w*h, unsigned int);
386 copy_game_flags(state, ret);
387
388 ret->numbers = state->numbers;
389 state->numbers->refcount++;
390 ret->num_errors = snewn(w+h, int);
391 memcpy(ret->num_errors, state->num_errors, (w+h)*sizeof(int));
392
393 ret->completed = state->completed;
394 ret->used_solve = state->used_solve;
395 ret->impossible = state->impossible;
396
397 return ret;
398}
399
400static void free_game(game_state *state)
401{
402 if (--state->numbers->refcount <= 0) {
403 sfree(state->numbers->numbers);
404 sfree(state->numbers);
405 }
406 sfree(state->num_errors);
407 sfree(state->sflags);
408 sfree(state);
409}
410
411#define NDIRS 4
412static const unsigned int dirs_const[] = { U, D, L, R };
413
414static unsigned int find_direction(game_state *state, random_state *rs,
415 int x, int y)
416{
417 int i, nx, ny, w=state->p.w, h=state->p.h;
418 unsigned int dirs[NDIRS];
419
420 memcpy(dirs, dirs_const, sizeof(dirs));
421 shuffle(dirs, NDIRS, sizeof(*dirs), rs);
422 for (i = 0; i < NDIRS; i++) {
423 nx = x + DX(dirs[i]);
424 ny = y + DY(dirs[i]);
425 if (nx >= 0 && nx < w && ny == h) {
426 /* off the bottom of the board: we've finished the path. */
427 return dirs[i];
428 } else if (!INGRID(state, nx, ny)) {
429 /* off the board: can't move here */
430 continue;
431 } else if (S_E_COUNT(state, nx, ny, E_TRACK) > 0) {
432 /* already tracks here: can't move */
433 continue;
434 }
435 return dirs[i];
436 }
437 return 0; /* no possible directions left. */
438}
439
440static bool check_completion(game_state *state, bool mark);
441
442static void lay_path(game_state *state, random_state *rs)
443{
444 int px, py, w=state->p.w, h=state->p.h;
445 unsigned int d;
446
447start:
448 clear_game(state);
449
450 /* pick a random entry point, lay its left edge */
451 state->numbers->row_s = py = random_upto(rs, h);
452 px = 0;
453 S_E_SET(state, px, py, L, E_TRACK);
454
455 while (INGRID(state, px, py)) {
456 d = find_direction(state, rs, px, py);
457 if (d == 0)
458 goto start; /* nowhere else to go, restart */
459
460 S_E_SET(state, px, py, d, E_TRACK);
461 px += DX(d);
462 py += DY(d);
463 }
464 /* double-check we got to the right place */
465 assert(px >= 0 && px < w && py == h);
466
467 state->numbers->col_s = px;
468}
469
470static int tracks_solve(game_state *state, int diff, int *max_diff_out);
471static void debug_state(game_state *state, const char *what);
472
473/* Clue-setting algorithm:
474
475 - first lay clues randomly until it's soluble
476 - then remove clues randomly if removing them doesn't affect solubility
477
478 - We start with two clues, one at each path entrance.
479
480 More details:
481 - start with an array of all square i positions
482 - if the grid is already soluble by a level easier than we've requested,
483 go back and make a new grid
484 - if the grid is already soluble by our requested difficulty level, skip
485 the clue-laying step
486 - count the number of flags the solver managed to place, remember this.
487
488 - to lay clues:
489 - shuffle the i positions
490 - for each possible clue position:
491 - copy the solved board, strip it
492 - take the next position, add a clue there on the copy
493 - try and solve the copy
494 - if it's soluble by a level easier than we've requested, continue (on
495 to next clue position: putting a clue here makes it too easy)
496 - if it's soluble by our difficulty level, we're done:
497 - put the clue flag into the solved board
498 - go to strip-clues.
499 - if the solver didn't manage to place any more flags, continue (on to next
500 clue position: putting a clue here didn't help he solver)
501 - otherwise put the clue flag in the original board, and go on to the next
502 clue position
503 - if we get here and we've not solved it yet, we never will (did we really
504 fill _all_ the clues in?!). Go back and make a new grid.
505
506 - to strip clues:
507 - shuffle the i positions
508 - for each possible clue position:
509 - if the solved grid doesn't have a clue here, skip
510 - copy the solved board, remove this clue, strip it
511 - try and solve the copy
512 - assert that it is not soluble by a level easier than we've requested
513 - (because this should never happen)
514 - if this is (still) soluble by our difficulty level:
515 - remove this clue from the solved board, it's redundant (with the other
516 clues)
517
518 - that should be it.
519*/
520
521static game_state *copy_and_strip(const game_state *state, game_state *ret, int flipcluei)
522{
523 int i, j, w = state->p.w, h = state->p.h;
524
525 copy_game_flags(state, ret);
526
527 /* Add/remove a clue before stripping, if required */
528
529 if (flipcluei != -1)
530 ret->sflags[flipcluei] ^= S_CLUE;
531
532 /* All squares that are not clue squares have square track info erased, and some edge flags.. */
533
534 for (i = 0; i < w*h; i++) {
535 if (!(ret->sflags[i] & S_CLUE)) {
536 ret->sflags[i] &= ~(S_TRACK|S_NOTRACK|S_ERROR|S_MARK);
537 for (j = 0; j < 4; j++) {
538 unsigned f = 1<<j;
539 int xx = i%w + DX(f), yy = i/w + DY(f);
540 if (!INGRID(state, xx, yy) || !(ret->sflags[yy*w+xx] & S_CLUE)) {
541 /* only erase an edge flag if neither side of the edge is S_CLUE. */
542 S_E_CLEAR(ret, i%w, i/w, f, E_TRACK);
543 S_E_CLEAR(ret, i%w, i/w, f, E_NOTRACK);
544 }
545 }
546 }
547 }
548 return ret;
549}
550
551#ifdef STANDALONE_SOLVER
552#include <stdarg.h>
553static FILE *solver_diagnostics_fp = NULL;
554static void solver_diagnostic(const char *fmt, ...)
555{
556 va_list ap;
557 va_start(ap, fmt);
558 vfprintf(solver_diagnostics_fp, fmt, ap);
559 va_end(ap);
560 fputc('\n', solver_diagnostics_fp);
561}
562#define solverdebug(printf_params) do { \
563 if (solver_diagnostics_fp) { \
564 solver_diagnostic printf_params; \
565 } \
566 } while (0)
567#else
568#define solverdebug(printf_params) ((void)0)
569#endif
570
571static int solve_progress(const game_state *state) {
572 int i, w = state->p.w, h = state->p.h, progress = 0;
573
574 /* Work out how many flags the solver managed to set (either TRACK
575 or NOTRACK) and return this as a progress measure, to check whether
576 a partially-solved board gets any further than a previous partially-
577 solved board. */
578
579 for (i = 0; i < w*h; i++) {
580 if (state->sflags[i] & S_TRACK) progress++;
581 if (state->sflags[i] & S_NOTRACK) progress++;
582 progress += S_E_COUNT(state, i%w, i/w, E_TRACK);
583 progress += S_E_COUNT(state, i%w, i/w, E_NOTRACK);
584 }
585 return progress;
586}
587
588static bool check_phantom_moves(const game_state *state) {
589 int x, y, i;
590
591 /* Check that this state won't show 'phantom moves' at the start of the
592 * game: squares which have multiple edge flags set but no clue flag
593 * cause a piece of track to appear that isn't on a clue square. */
594
595 for (x = 0; x < state->p.w; x++) {
596 for (y = 0; y < state->p.h; y++) {
597 i = y*state->p.w+x;
598 if (state->sflags[i] & S_CLUE)
599 continue;
600 if (S_E_COUNT(state, x, y, E_TRACK) > 1)
601 return true; /* found one! */
602 }
603 }
604 return false;
605}
606
607static int add_clues(game_state *state, random_state *rs, int diff)
608{
609 int i, j, pi, w = state->p.w, h = state->p.h, progress, ret = 0, sr;
610 int *positions = snewn(w*h, int), npositions = 0;
611 int *nedges_previous_solve = snewn(w*h, int);
612 game_state *scratch = dup_game(state);
613 int diff_used;
614
615 debug_state(state, "gen: Initial board");
616
617 debug(("gen: Adding clues..."));
618
619 /* set up the shuffly-position grid for later, used for adding clues:
620 * we only bother adding clues where any edges are set. */
621 for (i = 0; i < w*h; i++) {
622 if (S_E_DIRS(state, i%w, i/w, E_TRACK) != 0) {
623 positions[npositions++] = i;
624 }
625 nedges_previous_solve[i] = 0;
626 }
627
628 /* First, check whether the puzzle is already either too easy, or just right */
629 scratch = copy_and_strip(state, scratch, -1);
630 sr = tracks_solve(scratch, diff, &diff_used);
631 if (diff_used < diff) {
632 ret = -1; /* already too easy, even without adding clues. */
633 debug(("gen: ...already too easy, need new board."));
634 goto done;
635 }
636
637 if (sr < 0)
638 assert(!"Generator should not have created impossible puzzle");
639 if (sr > 0) {
640 ret = 1; /* already soluble without any extra clues. */
641 debug(("gen: ...soluble without clues, nothing to do."));
642 goto done;
643 }
644 debug_state(scratch, "gen: Initial part-solved state: ");
645 progress = solve_progress(scratch);
646 debug(("gen: Initial solve progress is %d", progress));
647
648 /* First, lay clues until we're soluble. */
649 shuffle(positions, npositions, sizeof(int), rs);
650 for (pi = 0; pi < npositions; pi++) {
651 i = positions[pi]; /* pick a random position */
652 if (state->sflags[i] & S_CLUE)
653 continue; /* already a clue here (entrance location?) */
654 if (nedges_previous_solve[i] == 2)
655 continue; /* no point putting a clue here, we could solve both edges
656 with the previous set of clues */
657
658 /* set a clue in that position (on a copy of the board) and test solubility */
659 scratch = copy_and_strip(state, scratch, i);
660
661 if (check_phantom_moves(scratch))
662 continue; /* adding a clue here would add phantom track */
663
664 if (tracks_solve(scratch, diff, &diff_used) > 0) {
665 if (diff_used < diff) {
666 continue; /* adding a clue here makes it too easy */
667 }
668 /* we're now soluble (and we weren't before): add this clue, and then
669 start stripping clues */
670 debug(("gen: ...adding clue at (%d,%d), now soluble", i%w, i/w));
671 state->sflags[i] |= S_CLUE;
672 goto strip_clues;
673 }
674 if (solve_progress(scratch) > progress) {
675 /* We've made more progress solving: add this clue, then. */
676 progress = solve_progress(scratch);
677 debug(("gen: ... adding clue at (%d,%d), new progress %d", i%w, i/w, progress));
678 state->sflags[i] |= S_CLUE;
679
680 for (j = 0; j < w*h; j++)
681 nedges_previous_solve[j] = S_E_COUNT(scratch, j%w, j/w, E_TRACK);
682 }
683 }
684 /* If we got here we didn't ever manage to make the puzzle soluble
685 (without making it too easily soluble, that is): give up. */
686
687 debug(("gen: Unable to make soluble with clues, need new board."));
688 ret = -1;
689 goto done;
690
691strip_clues:
692 debug(("gen: Stripping clues."));
693
694 /* Now, strip redundant clues (i.e. those without which the puzzle is still
695 soluble) */
696 shuffle(positions, npositions, sizeof(int), rs);
697 for (pi = 0; pi < npositions; pi++) {
698 i = positions[pi]; /* pick a random position */
699 if (!(state->sflags[i] & S_CLUE))
700 continue; /* no clue here to strip */
701 if ((i%w == 0 && i/w == state->numbers->row_s) ||
702 (i/w == (h-1) && i%w == state->numbers->col_s))
703 continue; /* don't strip clues at entrance/exit */
704
705 scratch = copy_and_strip(state, scratch, i);
706 if (check_phantom_moves(scratch))
707 continue; /* removing a clue here would add phantom track */
708
709 if (tracks_solve(scratch, diff, NULL) > 0) {
710 debug(("gen: ... removing clue at (%d,%d), still soluble without it", i%w, i/w));
711 state->sflags[i] &= ~S_CLUE; /* still soluble without this clue. */
712 }
713 }
714 debug(("gen: Finished stripping clues."));
715 ret = 1;
716
717done:
718 sfree(positions);
719 sfree(nedges_previous_solve);
720 free_game(scratch);
721 return ret;
722}
723
724static char *new_game_desc(const game_params *params, random_state *rs,
725 char **aux, bool interactive)
726{
727 int i, j, w = params->w, h = params->h, x, y, ret;
728 game_state *state;
729 char *desc, *p;
730 game_params adjusted_params;
731
732 /*
733 * 4x4 Tricky cannot be generated, so fall back to Easy.
734 */
735 if (w == 4 && h == 4 && params->diff > DIFF_EASY) {
736 adjusted_params = *params; /* structure copy */
737 adjusted_params.diff = DIFF_EASY;
738 params = &adjusted_params;
739 }
740
741 state = blank_game(params);
742
743 /* --- lay the random path */
744
745newpath:
746 lay_path(state, rs);
747 for (x = 0; x < w; x++) {
748 for (y = 0; y < h; y++) {
749 if (S_E_COUNT(state, x, y, E_TRACK) > 0) {
750 state->sflags[y*w + x] |= S_TRACK;
751 }
752 if ((x == 0 && y == state->numbers->row_s) ||
753 (y == (h-1) && x == state->numbers->col_s)) {
754 state->sflags[y*w + x] |= S_CLUE;
755 }
756 }
757 }
758
759 /* --- Update the clue numbers based on the tracks we have generated. */
760 for (x = 0; x < w; x++) {
761 for (y = 0; y < h; y++) {
762 if (state->sflags[y*w + x] & S_TRACK) {
763 state->numbers->numbers[x]++;
764 state->numbers->numbers[y+w]++;
765 }
766 }
767 }
768 for (i = 0; i < w+h; i++) {
769 if (state->numbers->numbers[i] == 0)
770 goto newpath; /* too boring */
771 }
772
773 if (params->single_ones) {
774 bool last_was_one = true, is_one; /* disallow 1 clue at entry point */
775 for (i = 0; i < w+h; i++) {
776 is_one = (state->numbers->numbers[i] == 1);
777 if (is_one && last_was_one)
778 goto newpath; /* disallow consecutive 1 clues. */
779 last_was_one = is_one;
780 }
781 if (state->numbers->numbers[w+h-1] == 1)
782 goto newpath; /* (disallow 1 clue at exit point) */
783 }
784
785 /* --- Add clues to make a soluble puzzle */
786 ret = add_clues(state, rs, params->diff);
787 if (ret != 1) goto newpath; /* couldn't make it soluble, or too easy */
788
789 /* --- Generate the game desc based on the generated grid. */
790 desc = snewn(w*h*3 + (w+h)*5, char);
791 for (i = j = 0; i < w*h; i++) {
792 if (!(state->sflags[i] & S_CLUE) && j > 0 &&
793 desc[j-1] >= 'a' && desc[j-1] < 'z')
794 desc[j-1]++;
795 else if (!(state->sflags[i] & S_CLUE))
796 desc[j++] = 'a';
797 else {
798 unsigned int f = S_E_DIRS(state, i%w, i/w, E_TRACK);
799 desc[j++] = (f < 10) ? ('0' + f) : ('A' + (f-10));
800 }
801 }
802
803 p = desc + j;
804 for (x = 0; x < w; x++) {
805 p += sprintf(p, ",%s%d", x == state->numbers->col_s ? "S" : "",
806 state->numbers->numbers[x]);
807 }
808 for (y = 0; y < h; y++) {
809 p += sprintf(p, ",%s%d", y == state->numbers->row_s ? "S" : "",
810 state->numbers->numbers[y+w]);
811 }
812 *p++ = '\0';
813
814 ret = tracks_solve(state, DIFFCOUNT, NULL);
815 assert(ret >= 0);
816 free_game(state);
817
818 debug(("new_game_desc: %s", desc));
819 return desc;
820}
821
822static const char *validate_desc(const game_params *params, const char *desc)
823{
824 int i = 0, w = params->w, h = params->h, in = 0, out = 0;
825
826 while (*desc) {
827 unsigned int f = 0;
828 if (*desc >= '0' && *desc <= '9')
829 f = (*desc - '0');
830 else if (*desc >= 'A' && *desc <= 'F')
831 f = (*desc - 'A' + 10);
832 else if (*desc >= 'a' && *desc <= 'z')
833 i += *desc - 'a';
834 else
835 return "Game description contained unexpected characters";
836
837 if (f != 0) {
838 if (nbits[f] != 2)
839 return "Clue did not provide 2 direction flags";
840 }
841 i++;
842 desc++;
843 if (i == w*h) break;
844 }
845 for (i = 0; i < w+h; i++) {
846 if (!*desc)
847 return "Not enough numbers given after grid specification";
848 else if (*desc != ',')
849 return "Invalid character in number list";
850 desc++;
851 if (*desc == 'S') {
852 if (i < w)
853 out++;
854 else
855 in++;
856 desc++;
857 }
858 while (*desc && isdigit((unsigned char)*desc)) desc++;
859 }
860 if (in != 1 || out != 1)
861 return "Puzzle must have one entrance and one exit";
862 if (*desc)
863 return "Unexpected additional character at end of game description";
864 return NULL;
865}
866
867static game_state *new_game(midend *me, const game_params *params, const char *desc)
868{
869 game_state *state = blank_game(params);
870 int w = params->w, h = params->h, i = 0;
871
872 while (*desc) {
873 unsigned int f = 0;
874 if (*desc >= '0' && *desc <= '9')
875 f = (*desc - '0');
876 else if (*desc >= 'A' && *desc <= 'F')
877 f = (*desc - 'A' + 10);
878 else if (*desc >= 'a' && *desc <= 'z')
879 i += *desc - 'a';
880
881 if (f != 0) {
882 int x = i % w, y = i / w;
883 assert(f < 16);
884 assert(nbits[f] == 2);
885
886 state->sflags[i] |= (S_TRACK | S_CLUE);
887 if (f & U) S_E_SET(state, x, y, U, E_TRACK);
888 if (f & D) S_E_SET(state, x, y, D, E_TRACK);
889 if (f & L) S_E_SET(state, x, y, L, E_TRACK);
890 if (f & R) S_E_SET(state, x, y, R, E_TRACK);
891 }
892 i++;
893 desc++;
894 if (i == w*h) break;
895 }
896 for (i = 0; i < w+h; i++) {
897 assert(*desc == ',');
898 desc++;
899
900 if (*desc == 'S') {
901 if (i < w)
902 state->numbers->col_s = i;
903 else
904 state->numbers->row_s = i-w;
905 desc++;
906 }
907 state->numbers->numbers[i] = atoi(desc);
908 while (*desc && isdigit((unsigned char)*desc)) desc++;
909 }
910
911 assert(!*desc);
912
913 return state;
914}
915
916struct solver_scratch {
917 DSF *dsf;
918};
919
920static int solve_set_sflag(game_state *state, int x, int y,
921 unsigned int f, const char *why)
922{
923 int w = state->p.w, i = y*w + x;
924
925 if (state->sflags[i] & f)
926 return 0;
927 solverdebug(("square (%d,%d) -> %s: %s",
928 x, y, (f == S_TRACK ? "TRACK" : "NOTRACK"), why));
929 if (state->sflags[i] & (f == S_TRACK ? S_NOTRACK : S_TRACK)) {
930 solverdebug(("opposite flag already set there, marking IMPOSSIBLE"));
931 state->impossible = true;
932 } else
933 state->sflags[i] |= f;
934 return 1;
935}
936
937static int solve_set_eflag(game_state *state, int x, int y, int d,
938 unsigned int f, const char *why)
939{
940 int sf = S_E_FLAGS(state, x, y, d);
941
942 if (sf & f)
943 return 0;
944 solverdebug(("edge (%d,%d)/%c -> %s: %s", x, y,
945 (d == U) ? 'U' : (d == D) ? 'D' : (d == L) ? 'L' : 'R',
946 (f == S_TRACK ? "TRACK" : "NOTRACK"), why));
947 if (sf & (f == E_TRACK ? E_NOTRACK : E_TRACK)) {
948 solverdebug(("opposite flag already set there, marking IMPOSSIBLE"));
949 state->impossible = true;
950 } else
951 S_E_SET(state, x, y, d, f);
952 return 1;
953}
954
955static int solve_update_flags(game_state *state)
956{
957 int x, y, i, w = state->p.w, h = state->p.h, did = 0;
958
959 for (x = 0; x < w; x++) {
960 for (y = 0; y < h; y++) {
961 /* If a square is NOTRACK, all four edges must be. */
962 if (state->sflags[y*w + x] & S_NOTRACK) {
963 for (i = 0; i < 4; i++) {
964 unsigned int d = 1<<i;
965 did += solve_set_eflag(state, x, y, d, E_NOTRACK, "edges around NOTRACK");
966 }
967 }
968
969 /* If 3 or more edges around a square are NOTRACK, the square is. */
970 if (S_E_COUNT(state, x, y, E_NOTRACK) >= 3) {
971 did += solve_set_sflag(state, x, y, S_NOTRACK, "square has >2 NOTRACK edges");
972 }
973
974 /* If any edge around a square is TRACK, the square is. */
975 if (S_E_COUNT(state, x, y, E_TRACK) > 0) {
976 did += solve_set_sflag(state, x, y, S_TRACK, "square has TRACK edge");
977 }
978
979 /* If a square is TRACK and 2 edges are NOTRACK,
980 the other two edges must be TRACK. */
981 if ((state->sflags[y*w + x] & S_TRACK) &&
982 (S_E_COUNT(state, x, y, E_NOTRACK) == 2) &&
983 (S_E_COUNT(state, x, y, E_TRACK) < 2)) {
984 for (i = 0; i < 4; i++) {
985 unsigned int d = 1<<i;
986 if (!(S_E_FLAGS(state, x, y, d) & (E_TRACK|E_NOTRACK))) {
987 did += solve_set_eflag(state, x, y, d, E_TRACK,
988 "TRACK square/2 NOTRACK edges");
989 }
990 }
991 }
992
993 /* If a square is TRACK and 2 edges are TRACK, the other two
994 must be NOTRACK. */
995 if ((state->sflags[y*w + x] & S_TRACK) &&
996 (S_E_COUNT(state, x, y, E_TRACK) == 2) &&
997 (S_E_COUNT(state, x, y, E_NOTRACK) < 2)) {
998 for (i = 0; i < 4; i++) {
999 unsigned int d = 1<<i;
1000 if (!(S_E_FLAGS(state, x, y, d) & (E_TRACK|E_NOTRACK))) {
1001 did += solve_set_eflag(state, x, y, d, E_NOTRACK,
1002 "TRACK square/2 TRACK edges");
1003 }
1004 }
1005 }
1006 }
1007 }
1008 return did;
1009}
1010
1011static int solve_count_col(game_state *state, int col, unsigned int f)
1012{
1013 int i, n, c = 0, h = state->p.h, w = state->p.w;
1014 for (n = 0, i = col; n < h; n++, i += w) {
1015 if (state->sflags[i] & f) c++;
1016 }
1017 return c;
1018}
1019
1020static int solve_count_row(game_state *state, int row, unsigned int f)
1021{
1022 int i, n, c = 0, w = state->p.w;
1023 for (n = 0, i = w*row; n < state->p.w; n++, i++) {
1024 if (state->sflags[i] & f) c++;
1025 }
1026 return c;
1027}
1028
1029static int solve_count_clues_sub(game_state *state, int si, int id, int n,
1030 int target, const char *what)
1031{
1032 int ctrack = 0, cnotrack = 0, did = 0, j, i, w = state->p.w;
1033
1034 for (j = 0, i = si; j < n; j++, i += id) {
1035 if (state->sflags[i] & S_TRACK)
1036 ctrack++;
1037 if (state->sflags[i] & S_NOTRACK)
1038 cnotrack++;
1039 }
1040 if (ctrack == target) {
1041 /* everything that's not S_TRACK must be S_NOTRACK. */
1042 for (j = 0, i = si; j < n; j++, i += id) {
1043 if (!(state->sflags[i] & S_TRACK))
1044 did += solve_set_sflag(state, i%w, i/w, S_NOTRACK, what);
1045 }
1046 }
1047 if (cnotrack == (n-target)) {
1048 /* everything that's not S_NOTRACK must be S_TRACK. */
1049 for (j = 0, i = si; j < n; j++, i += id) {
1050 if (!(state->sflags[i] & S_NOTRACK))
1051 did += solve_set_sflag(state, i%w, i/w, S_TRACK, what);
1052 }
1053 }
1054 return did;
1055}
1056
1057static int solve_count_clues(game_state *state)
1058{
1059 int w = state->p.w, h = state->p.h, x, y, target, did = 0;
1060
1061 for (x = 0; x < w; x++) {
1062 target = state->numbers->numbers[x];
1063 did += solve_count_clues_sub(state, x, w, h, target, "col count");
1064 }
1065 for (y = 0; y < h; y++) {
1066 target = state->numbers->numbers[w+y];
1067 did += solve_count_clues_sub(state, y*w, 1, w, target, "row count");
1068 }
1069 return did;
1070}
1071
1072static int solve_check_single_sub(game_state *state, int si, int id, int n,
1073 int target, unsigned int perpf,
1074 const char *what)
1075{
1076 int ctrack = 0, nperp = 0, did = 0, j, i, w = state->p.w;
1077 int n1edge = 0, i1edge = 0, ox, oy, x, y;
1078 unsigned int impossible = 0;
1079
1080 /* For rows or columns which only have one more square to put a track in, we
1081 know the only way a new track section could be there would be to run
1082 perpendicular to the track (otherwise we'd need at least two free squares).
1083 So, if there is nowhere we can run perpendicular to the track (e.g. because
1084 we're on an edge) we know the extra track section much be on one end of an
1085 existing section. */
1086
1087 for (j = 0, i = si; j < n; j++, i += id) {
1088 if (state->sflags[i] & S_TRACK)
1089 ctrack++;
1090 impossible = S_E_DIRS(state, i%w, i/w, E_NOTRACK);
1091 if ((perpf & impossible) == 0)
1092 nperp++;
1093 if (S_E_COUNT(state, i%w, i/w, E_TRACK) <= 1) {
1094 n1edge++;
1095 i1edge = i;
1096 }
1097 }
1098 if (ctrack != (target-1)) return 0;
1099 if (nperp > 0 || n1edge != 1) return 0;
1100
1101 solverdebug(("check_single from (%d,%d): 1 match from (%d,%d)",
1102 si%w, si/w, i1edge%w, i1edge/w));
1103
1104 /* We have a match: anything that's more than 1 away from this square
1105 cannot now contain a track. */
1106 ox = i1edge%w;
1107 oy = i1edge/w;
1108 for (j = 0, i = si; j < n; j++, i += id) {
1109 x = i%w;
1110 y = i/w;
1111 if (abs(ox-x) > 1 || abs(oy-y) > 1) {
1112 if (!(state->sflags[i] & S_TRACK))
1113 did += solve_set_sflag(state, x, y, S_NOTRACK, what);
1114 }
1115 }
1116
1117 return did;
1118}
1119
1120static int solve_check_single(game_state *state)
1121{
1122 int w = state->p.w, h = state->p.h, x, y, target, did = 0;
1123
1124 for (x = 0; x < w; x++) {
1125 target = state->numbers->numbers[x];
1126 did += solve_check_single_sub(state, x, w, h, target, R|L, "single on col");
1127 }
1128 for (y = 0; y < h; y++) {
1129 target = state->numbers->numbers[w+y];
1130 did += solve_check_single_sub(state, y*w, 1, w, target, U|D, "single on row");
1131 }
1132 return did;
1133}
1134
1135static int solve_check_loose_sub(game_state *state, int si, int id, int n,
1136 int target, unsigned int perpf,
1137 const char *what)
1138{
1139 int nperp = 0, nloose = 0, e2count = 0, did = 0, i, j, k;
1140 int w = state->p.w;
1141 unsigned int parf = ALLDIR & (~perpf);
1142
1143 for (j = 0, i = si; j < n; j++, i += id) {
1144 int fcount = S_E_COUNT(state, i%w, i/w, E_TRACK);
1145 if (fcount == 2)
1146 e2count++; /* this cell has 2 definite edges */
1147 state->sflags[i] &= ~S_MARK;
1148 if (fcount == 1 && (parf & S_E_DIRS(state, i%w, i/w, E_TRACK))) {
1149 nloose++; /* this cell has a loose end (single flag set parallel
1150 to the direction of this row/column) */
1151 state->sflags[i] |= S_MARK; /* mark loose ends */
1152 }
1153 if (fcount != 2 && !(perpf & S_E_DIRS(state, i%w, i/w, E_NOTRACK)))
1154 nperp++; /* we could lay perpendicular across this cell */
1155 }
1156
1157 if (nloose > (target - e2count)) {
1158 solverdebug(("check %s from (%d,%d): more loose (%d) than empty (%d), IMPOSSIBLE",
1159 what, si%w, si/w, nloose, target-e2count));
1160 state->impossible = true;
1161 }
1162 if (nloose > 0 && nloose == (target - e2count)) {
1163 solverdebug(("check %s from (%d,%d): nloose = empty (%d), forcing loners out.",
1164 what, si%w, si/w, nloose));
1165 for (j = 0, i = si; j < n; j++, i += id) {
1166 if (!(state->sflags[i] & S_MARK))
1167 continue; /* skip non-loose ends */
1168 if (j > 0 && state->sflags[i-id] & S_MARK)
1169 continue; /* next to other loose end, could join up */
1170 if (j < (n-1) && state->sflags[i+id] & S_MARK)
1171 continue; /* ditto */
1172
1173 for (k = 0; k < 4; k++) {
1174 if ((parf & (1<<k)) &&
1175 !(S_E_DIRS(state, i%w, i/w, E_TRACK) & (1<<k))) {
1176 /* set as NOTRACK the edge parallel to the row/column that's
1177 not already set. */
1178 did += solve_set_eflag(state, i%w, i/w, 1<<k, E_NOTRACK, what);
1179 }
1180 }
1181 }
1182 }
1183 if (nloose == 1 && (target - e2count) == 2 && nperp == 0) {
1184 solverdebug(("check %s from (%d,%d): 1 loose end, 2 empty squares, forcing parallel",
1185 what, si%w, si/w));
1186 for (j = 0, i = si; j < n; j++, i += id) {
1187 if (!(state->sflags[i] & S_MARK))
1188 continue; /* skip non-loose ends */
1189 for (k = 0; k < 4; k++) {
1190 if (parf & (1<<k))
1191 did += solve_set_eflag(state, i%w, i/w, 1<<k, E_TRACK, what);
1192 }
1193 }
1194 }
1195
1196 return did;
1197}
1198
1199static int solve_check_loose_ends(game_state *state)
1200{
1201 int w = state->p.w, h = state->p.h, x, y, target, did = 0;
1202
1203 for (x = 0; x < w; x++) {
1204 target = state->numbers->numbers[x];
1205 did += solve_check_loose_sub(state, x, w, h, target, R|L, "loose on col");
1206 }
1207 for (y = 0; y < h; y++) {
1208 target = state->numbers->numbers[w+y];
1209 did += solve_check_loose_sub(state, y*w, 1, w, target, U|D, "loose on row");
1210 }
1211 return did;
1212}
1213
1214static void solve_check_neighbours_count(
1215 game_state *state, int start, int step, int n, int clueindex,
1216 bool *onefill, bool *oneempty)
1217{
1218 int to_fill = state->numbers->numbers[clueindex];
1219 int to_empty = n - to_fill;
1220 int i;
1221 for (i = 0; i < n; i++) {
1222 int p = start + i*step;
1223 if (state->sflags[p] & S_TRACK)
1224 to_fill--;
1225 if (state->sflags[p] & S_NOTRACK)
1226 to_empty--;
1227 }
1228 *onefill = (to_fill == 1);
1229 *oneempty = (to_empty == 1);
1230}
1231
1232static int solve_check_neighbours_try(game_state *state, int x, int y,
1233 int X, int Y, bool onefill,
1234 bool oneempty, unsigned dir,
1235 const char *what)
1236{
1237 int w = state->p.w, p = y*w+x, P = Y*w+X;
1238
1239 /*
1240 * We're given a neighbouring pair of squares p,P, with 'dir'
1241 * being the direction from the former to the latter. We aim to
1242 * spot situations in which, if p is a track square, then P must
1243 * also be one (because p doesn't have enough free exits to avoid
1244 * using the one that goes towards P).
1245 *
1246 * Then, if the target number of track squares on their shared
1247 * row/column says that there's only one track square left to
1248 * place, it can't be p, because P would have to be one too,
1249 * violating the clue. So in that situation we can mark p as
1250 * unfilled. Conversely, if there's only one _non_-track square
1251 * left to place, it can't be P, so we can mark P as filled.
1252 */
1253
1254 if ((state->sflags[p] | state->sflags[P]) & (S_TRACK | S_NOTRACK))
1255 return 0; /* no need: we already know something about these squares */
1256
1257 int possible_exits_except_dir = nbits[
1258 ALLDIR & ~dir & ~S_E_DIRS(state, x, y, E_NOTRACK)];
1259 if (possible_exits_except_dir >= 2)
1260 return 0; /* square p need not connect to P, even if it is filled */
1261
1262 /* OK, now we know that if p is filled, P must be filled too. */
1263
1264 int did = 0;
1265 if (onefill) {
1266 /* But at most one of them can be filled, so it can't be p. */
1267 state->sflags[p] |= S_NOTRACK;
1268 solverdebug(("square (%d,%d) -> NOTRACK: otherwise, that and (%d,%d) "
1269 "would make too many TRACK in %s", x, y, X, Y, what));
1270 did++;
1271 }
1272 if (oneempty) {
1273 /* Alternatively, at least one of them _must_ be filled, so P
1274 * must be. */
1275 state->sflags[P] |= S_TRACK;
1276 solverdebug(("square (%d,%d) -> TRACK: otherwise, that and (%d,%d) "
1277 "would make too many NOTRACK in %s", X, Y, x, y, what));
1278 did++;
1279 }
1280 return did;
1281}
1282
1283static int solve_check_neighbours(game_state *state, bool both_ways)
1284{
1285 int w = state->p.w, h = state->p.h, x, y, did = 0;
1286 bool onefill, oneempty;
1287
1288 for (x = 0; x < w; x++) {
1289 solve_check_neighbours_count(state, x, w, h, x, &onefill, &oneempty);
1290 if (!both_ways)
1291 oneempty = false; /* disable the harder version of the deduction */
1292 if (!onefill && !oneempty)
1293 continue;
1294 for (y = 0; y+1 < h; y++) {
1295 did += solve_check_neighbours_try(state, x, y, x, y+1,
1296 onefill, oneempty, D, "column");
1297 did += solve_check_neighbours_try(state, x, y+1, x, y,
1298 onefill, oneempty, U, "column");
1299 }
1300 }
1301 for (y = 0; y < h; y++) {
1302 solve_check_neighbours_count(state, y*w, 1, w, w+y,
1303 &onefill, &oneempty);
1304 if (!both_ways)
1305 oneempty = false; /* disable the harder version of the deduction */
1306 if (!onefill && !oneempty)
1307 continue;
1308 for (x = 0; x+1 < w; x++) {
1309 did += solve_check_neighbours_try(state, x, y, x+1, y,
1310 onefill, oneempty, R, "row");
1311 did += solve_check_neighbours_try(state, x+1, y, x, y,
1312 onefill, oneempty, L, "row");
1313 }
1314 }
1315 return did;
1316}
1317
1318static int solve_check_loop_sub(game_state *state, int x, int y, int dir,
1319 DSF *dsf, int startc, int endc)
1320{
1321 int w = state->p.w, h = state->p.h, i = y*w+x, j, k;
1322 bool satisfied = true;
1323
1324 j = (y+DY(dir))*w + (x+DX(dir));
1325
1326 assert(i < w*h && j < w*h);
1327
1328 if ((state->sflags[i] & S_TRACK) &&
1329 (state->sflags[j] & S_TRACK) &&
1330 !(S_E_DIRS(state, x, y, E_TRACK) & dir) &&
1331 !(S_E_DIRS(state, x, y, E_NOTRACK) & dir)) {
1332 int ic = dsf_canonify(dsf, i), jc = dsf_canonify(dsf, j);
1333 if (ic == jc) {
1334 return solve_set_eflag(state, x, y, dir, E_NOTRACK, "would close loop");
1335 }
1336 if ((ic == startc && jc == endc) || (ic == endc && jc == startc)) {
1337 solverdebug(("Adding link at (%d,%d) would join start to end", x, y));
1338 /* We mustn't join the start to the end if:
1339 - there are other bits of track that aren't attached to either end
1340 - the clues are not fully satisfied yet
1341 */
1342 for (k = 0; k < w*h; k++) {
1343 if (state->sflags[k] & S_TRACK &&
1344 dsf_canonify(dsf, k) != startc && dsf_canonify(dsf, k) != endc) {
1345 return solve_set_eflag(state, x, y, dir, E_NOTRACK,
1346 "joins start to end but misses tracks");
1347 }
1348 }
1349 for (k = 0; k < w; k++) {
1350 int target = state->numbers->numbers[k];
1351 int ntracks = solve_count_col(state, k, S_TRACK);
1352 if (ntracks < target) satisfied = false;
1353 }
1354 for (k = 0; k < h; k++) {
1355 int target = state->numbers->numbers[w+k];
1356 int ntracks = solve_count_row(state, k, S_TRACK);
1357 if (ntracks < target) satisfied = false;
1358 }
1359 if (!satisfied) {
1360 return solve_set_eflag(state, x, y, dir, E_NOTRACK,
1361 "joins start to end with incomplete clues");
1362 }
1363 }
1364 }
1365 return 0;
1366}
1367
1368static int solve_check_loop(game_state *state)
1369{
1370 int w = state->p.w, h = state->p.h, x, y, i, j, did = 0;
1371 DSF *dsf;
1372 int startc, endc;
1373
1374 /* TODO eventually we should pull this out into a solver struct and keep it
1375 updated as we connect squares. For now we recreate it every time we try
1376 this particular solver step. */
1377 dsf = dsf_new(w*h);
1378
1379 /* Work out the connectedness of the current loop set. */
1380 for (x = 0; x < w; x++) {
1381 for (y = 0; y < h; y++) {
1382 i = y*w + x;
1383 if (x < (w-1) && S_E_DIRS(state, x, y, E_TRACK) & R) {
1384 /* connection to the right... */
1385 j = y*w + (x+1);
1386 assert(i < w*h && j < w*h);
1387 dsf_merge(dsf, i, j);
1388 }
1389 if (y < (h-1) && S_E_DIRS(state, x, y, E_TRACK) & D) {
1390 /* connection down... */
1391 j = (y+1)*w + x;
1392 assert(i < w*h && j < w*h);
1393 dsf_merge(dsf, i, j);
1394 }
1395 /* NB no need to check up and left because they'll have been checked
1396 by the other side. */
1397 }
1398 }
1399
1400 startc = dsf_canonify(dsf, state->numbers->row_s*w);
1401 endc = dsf_canonify(dsf, (h-1)*w+state->numbers->col_s);
1402
1403 /* Now look at all adjacent squares that are both S_TRACK: if connecting
1404 any of them would complete a loop (i.e. they're both the same dsf class
1405 already) then that edge must be NOTRACK. */
1406 for (x = 0; x < w; x++) {
1407 for (y = 0; y < h; y++) {
1408 if (x < (w-1))
1409 did += solve_check_loop_sub(state, x, y, R, dsf, startc, endc);
1410 if (y < (h-1))
1411 did += solve_check_loop_sub(state, x, y, D, dsf, startc, endc);
1412 }
1413 }
1414
1415 dsf_free(dsf);
1416
1417 return did;
1418}
1419
1420static void solve_discount_edge(game_state *state, int x, int y, int d)
1421{
1422 if (S_E_DIRS(state, x, y, E_TRACK) & d) {
1423 assert(state->sflags[y*state->p.w + x] & S_CLUE);
1424 return; /* (only) clue squares can have outer edges set. */
1425 }
1426 solve_set_eflag(state, x, y, d, E_NOTRACK, "outer edge");
1427}
1428
1429static int solve_bridge_sub(game_state *state, int x, int y, int d,
1430 struct solver_scratch *sc)
1431{
1432 /*
1433 * Imagine a graph on the squares of the grid, with an edge
1434 * connecting neighbouring squares only if it's not yet known
1435 * whether there's a track between them.
1436 *
1437 * This function is called if the edge between x,y and X,Y is a
1438 * bridge in that graph: that is, it's not part of any loop in the
1439 * graph, or equivalently, removing it would increase the number
1440 * of connected components in the graph.
1441 *
1442 * In that situation, we can fill in the edge by a parity
1443 * argument. Construct a closed loop of edges in the grid, all of
1444 * whose states are known except this one. The track starts and
1445 * ends outside this loop, so it must cross the boundary of the
1446 * loop an even number of times. So if we count up how many times
1447 * the track is known to cross the edges of our loop, then we can
1448 * fill in the last edge in whichever way makes that number even.
1449 *
1450 * In fact, there's not even any need to go to the effort of
1451 * constructing a _single_ closed loop. The simplest thing is to
1452 * delete the bridge edge from the graph, find a connected
1453 * component of the reduced graph whose boundary includes that
1454 * edge, and take every edge separating that component from
1455 * another. This may not lead to _exactly one_ cycle - the
1456 * component could be non-simply connected and have a hole in the
1457 * middle - but that doesn't matter, because the same parity
1458 * constraint applies just as well with more than one disjoint
1459 * loop.
1460 */
1461 int w = state->p.w, h = state->p.h, wh = w*h;
1462 int X = x + DX(d), Y = y + DY(d);
1463 int xi, yi, di;
1464
1465 assert(d == D || d == R);
1466
1467 if (!sc->dsf)
1468 sc->dsf = dsf_new(wh);
1469 dsf_reinit(sc->dsf);
1470
1471 for (xi = 0; xi < w; xi++) {
1472 for (yi = 0; yi < h; yi++) {
1473 /* We expect to have been called with X,Y either to the
1474 * right of x,y or below it, not the other way round. If
1475 * that were not true, the tests in this loop to exclude
1476 * the bridge edge would have to be twice as annoying. */
1477
1478 if (yi+1 < h && !S_E_FLAGS(state, xi, yi, D) &&
1479 !(xi == x && yi == y && xi == X && yi+1 == Y))
1480 dsf_merge(sc->dsf, yi*w+xi, (yi+1)*w+xi);
1481
1482 if (xi+1 < w && !S_E_FLAGS(state, xi, yi, R) &&
1483 !(xi == x && yi == y && xi+1 == X && yi == Y))
1484 dsf_merge(sc->dsf, yi*w+xi, yi*w+(xi+1));
1485 }
1486 }
1487
1488 int component = dsf_canonify(sc->dsf, y*w+x);
1489 int parity = 0;
1490 for (xi = 0; xi < w; xi++) {
1491 for (yi = 0; yi < h; yi++) {
1492 if (dsf_canonify(sc->dsf, yi*w+xi) != component)
1493 continue;
1494 for (di = 1; di < 16; di *= 2) {
1495 int Xi = xi + DX(di), Yi = yi + DY(di);
1496 if ((Xi < 0 || Xi >= w || Yi < 0 || Yi >= h ||
1497 dsf_canonify(sc->dsf, Yi*w+Xi) != component) &&
1498 (S_E_DIRS(state, xi, yi, E_TRACK) & di))
1499 parity ^= 1;
1500 }
1501 }
1502 }
1503
1504 solve_set_eflag(state, x, y, d, parity ? E_TRACK : E_NOTRACK, "parity");
1505 return 1;
1506}
1507
1508struct solve_bridge_neighbour_ctx {
1509 game_state *state;
1510 int x, y, dirs;
1511};
1512static int solve_bridge_neighbour(int vertex, void *vctx)
1513{
1514 struct solve_bridge_neighbour_ctx *ctx =
1515 (struct solve_bridge_neighbour_ctx *)vctx;
1516 int w = ctx->state->p.w;
1517
1518 if (vertex >= 0) {
1519 ctx->x = vertex % w;
1520 ctx->y = vertex / w;
1521 ctx->dirs = ALLDIR
1522 & ~S_E_DIRS(ctx->state, ctx->x, ctx->y, E_TRACK)
1523 & ~S_E_DIRS(ctx->state, ctx->x, ctx->y, E_NOTRACK);
1524 }
1525 unsigned dir = ctx->dirs & -ctx->dirs; /* isolate lowest set bit */
1526 if (!dir)
1527 return -1;
1528 ctx->dirs &= ~dir;
1529 int xr = ctx->x + DX(dir), yr = ctx->y + DY(dir);
1530 assert(0 <= xr && xr < w);
1531 assert(0 <= yr && yr < ctx->state->p.h);
1532 return yr * w + xr;
1533}
1534
1535static int solve_check_bridge_parity(game_state *state,
1536 struct solver_scratch *sc)
1537{
1538 int w = state->p.w, h = state->p.h, wh = w*h;
1539 struct findloopstate *fls;
1540 struct solve_bridge_neighbour_ctx ctx[1];
1541 int x, y, did = 0;
1542
1543 ctx->state = state;
1544 fls = findloop_new_state(wh);
1545 findloop_run(fls, wh, solve_bridge_neighbour, ctx);
1546
1547 for (x = 0; x < w; x++) {
1548 for (y = 0; y < h; y++) {
1549 if (y+1 < h && !findloop_is_loop_edge(fls, y*w+x, (y+1)*w+x))
1550 did += solve_bridge_sub(state, x, y, D, sc);
1551 if (x+1 < w && !findloop_is_loop_edge(fls, y*w+x, y*w+(x+1)))
1552 did += solve_bridge_sub(state, x, y, R, sc);
1553 }
1554 }
1555
1556 findloop_free_state(fls);
1557
1558 return did;
1559}
1560
1561static int tracks_solve(game_state *state, int diff, int *max_diff_out)
1562{
1563 int x, y, w = state->p.w, h = state->p.h;
1564 struct solver_scratch sc[1];
1565 int max_diff = DIFF_EASY;
1566
1567 sc->dsf = NULL;
1568
1569 debug(("solve..."));
1570 state->impossible = false;
1571
1572 /* Set all the outer border edges as no-track. */
1573 for (x = 0; x < w; x++) {
1574 solve_discount_edge(state, x, 0, U);
1575 solve_discount_edge(state, x, h-1, D);
1576 }
1577 for (y = 0; y < h; y++) {
1578 solve_discount_edge(state, 0, y, L);
1579 solve_discount_edge(state, w-1, y, R);
1580 }
1581
1582 while (!state->impossible) {
1583
1584/* Can't use do ... while (0) because we need a 'continue' in this macro */
1585#define TRY(curr_diff, funcall) \
1586 if (diff >= (curr_diff) && (funcall)) { \
1587 if (max_diff < curr_diff) \
1588 max_diff = curr_diff; \
1589 continue; \
1590 } else ((void)0)
1591
1592 TRY(DIFF_EASY, solve_update_flags(state));
1593 TRY(DIFF_EASY, solve_count_clues(state));
1594 TRY(DIFF_EASY, solve_check_loop(state));
1595
1596 TRY(DIFF_TRICKY, solve_check_single(state));
1597 TRY(DIFF_TRICKY, solve_check_loose_ends(state));
1598 TRY(DIFF_TRICKY, solve_check_neighbours(state, false));
1599
1600 TRY(DIFF_HARD, solve_check_neighbours(state, true));
1601 TRY(DIFF_HARD, solve_check_bridge_parity(state, sc));
1602
1603#undef TRY
1604
1605 break;
1606 }
1607
1608 dsf_free(sc->dsf);
1609
1610 if (max_diff_out)
1611 *max_diff_out = max_diff;
1612
1613 return state->impossible ? -1 : check_completion(state, false) ? 1 : 0;
1614}
1615
1616static char *move_string_diff(const game_state *before, const game_state *after, bool issolve)
1617{
1618 int w = after->p.w, h = after->p.h, i, j;
1619 char *move = snewn(w*h*40, char), *p = move;
1620 const char *sep = "";
1621 unsigned int otf, ntf, onf, nnf;
1622
1623 if (issolve) {
1624 *p++ = 'S';
1625 sep = ";";
1626 }
1627 for (i = 0; i < w*h; i++) {
1628 otf = S_E_DIRS(before, i%w, i/w, E_TRACK);
1629 ntf = S_E_DIRS(after, i%w, i/w, E_TRACK);
1630 onf = S_E_DIRS(before, i%w, i/w, E_NOTRACK);
1631 nnf = S_E_DIRS(after, i%w, i/w, E_NOTRACK);
1632
1633 for (j = 0; j < 4; j++) {
1634 unsigned df = 1<<j;
1635 if ((otf & df) != (ntf & df)) {
1636 p += sprintf(p, "%s%c%c%d,%d", sep,
1637 (ntf & df) ? 'T' : 't', MOVECHAR(df), i%w, i/w);
1638 sep = ";";
1639 }
1640 if ((onf & df) != (nnf & df)) {
1641 p += sprintf(p, "%s%c%c%d,%d", sep,
1642 (nnf & df) ? 'N' : 'n', MOVECHAR(df), i%w, i/w);
1643 sep = ";";
1644 }
1645 }
1646
1647 if ((before->sflags[i] & S_NOTRACK) != (after->sflags[i] & S_NOTRACK)) {
1648 p += sprintf(p, "%s%cS%d,%d", sep,
1649 (after->sflags[i] & S_NOTRACK) ? 'N' : 'n', i%w, i/w);
1650 sep = ";";
1651 }
1652 if ((before->sflags[i] & S_TRACK) != (after->sflags[i] & S_TRACK)) {
1653 p += sprintf(p, "%s%cS%d,%d", sep,
1654 (after->sflags[i] & S_TRACK) ? 'T' : 't', i%w, i/w);
1655 sep = ";";
1656 }
1657 }
1658 *p++ = '\0';
1659 move = sresize(move, p - move, char);
1660
1661 return move;
1662}
1663
1664static char *solve_game(const game_state *state, const game_state *currstate,
1665 const char *aux, const char **error)
1666{
1667 game_state *solved;
1668 int ret;
1669 char *move;
1670
1671 solved = dup_game(currstate);
1672 ret = tracks_solve(solved, DIFFCOUNT, NULL);
1673 if (ret < 1) {
1674 free_game(solved);
1675 solved = dup_game(state);
1676 ret = tracks_solve(solved, DIFFCOUNT, NULL);
1677 }
1678
1679 if (ret < 1) {
1680 *error = "Unable to find solution";
1681 move = NULL;
1682 } else {
1683 move = move_string_diff(currstate, solved, true);
1684 }
1685
1686 free_game(solved);
1687 return move;
1688}
1689
1690static bool game_can_format_as_text_now(const game_params *params)
1691{
1692 return true;
1693}
1694
1695static char *game_text_format(const game_state *state)
1696{
1697 char *ret, *p;
1698 int x, y, len, w = state->p.w, h = state->p.h;
1699
1700 len = ((w*2) + 4) * ((h*2)+4) + 2;
1701 ret = snewn(len+1, char);
1702 p = ret;
1703
1704 /* top line: column clues */
1705 *p++ = ' ';
1706 *p++ = ' ';
1707 for (x = 0; x < w; x++) {
1708 *p++ = (state->numbers->numbers[x] < 10 ?
1709 '0' + state->numbers->numbers[x] :
1710 'A' + state->numbers->numbers[x] - 10);
1711 *p++ = ' ';
1712 }
1713 *p++ = '\n';
1714
1715 /* second line: top edge */
1716 *p++ = ' ';
1717 *p++ = '+';
1718 for (x = 0; x < w*2-1; x++)
1719 *p++ = '-';
1720 *p++ = '+';
1721 *p++ = '\n';
1722
1723 /* grid rows: one line of squares, one line of edges. */
1724 for (y = 0; y < h; y++) {
1725 /* grid square line */
1726 *p++ = (y == state->numbers->row_s) ? 'A' : ' ';
1727 *p++ = (y == state->numbers->row_s) ? '-' : '|';
1728
1729 for (x = 0; x < w; x++) {
1730 unsigned int f = S_E_DIRS(state, x, y, E_TRACK);
1731 if (state->sflags[y*w+x] & S_CLUE) *p++ = 'C';
1732 else if (f == LU || f == RD) *p++ = '/';
1733 else if (f == LD || f == RU) *p++ = '\\';
1734 else if (f == UD) *p++ = '|';
1735 else if (f == RL) *p++ = '-';
1736 else if (state->sflags[y*w+x] & S_NOTRACK) *p++ = 'x';
1737 else *p++ = ' ';
1738
1739 if (x < w-1) {
1740 *p++ = (f & R) ? '-' : ' ';
1741 } else
1742 *p++ = '|';
1743 }
1744 *p++ = (state->numbers->numbers[w+y] < 10 ?
1745 '0' + state->numbers->numbers[w+y] :
1746 'A' + state->numbers->numbers[w+y] - 10);
1747 *p++ = '\n';
1748
1749 if (y == h-1) continue;
1750
1751 /* edges line */
1752 *p++ = ' ';
1753 *p++ = '|';
1754 for (x = 0; x < w; x++) {
1755 unsigned int f = S_E_DIRS(state, x, y, E_TRACK);
1756 *p++ = (f & D) ? '|' : ' ';
1757 *p++ = (x < w-1) ? ' ' : '|';
1758 }
1759 *p++ = '\n';
1760 }
1761
1762 /* next line: bottom edge */
1763 *p++ = ' ';
1764 *p++ = '+';
1765 for (x = 0; x < w*2-1; x++)
1766 *p++ = (x == state->numbers->col_s*2) ? '|' : '-';
1767 *p++ = '+';
1768 *p++ = '\n';
1769
1770 /* final line: bottom clue */
1771 *p++ = ' ';
1772 *p++ = ' ';
1773 for (x = 0; x < w*2-1; x++)
1774 *p++ = (x == state->numbers->col_s*2) ? 'B' : ' ';
1775 *p++ = '\n';
1776
1777 *p = '\0';
1778 return ret;
1779}
1780
1781static void debug_state(game_state *state, const char *what) {
1782 char *sstring = game_text_format(state);
1783 debug(("%s: %s", what, sstring));
1784 sfree(sstring);
1785}
1786
1787static void dsf_update_completion(game_state *state, int ax, int ay,
1788 char dir, DSF *dsf)
1789{
1790 int w = state->p.w, ai = ay*w+ax, bx, by, bi;
1791
1792 if (!(S_E_DIRS(state, ax, ay, E_TRACK) & dir)) return;
1793 bx = ax + DX(dir);
1794 by = ay + DY(dir);
1795
1796 if (!INGRID(state, bx, by)) return;
1797 bi = by*w+bx;
1798
1799 dsf_merge(dsf, ai, bi);
1800}
1801
1802struct tracks_neighbour_ctx {
1803 game_state *state;
1804 int i, n, neighbours[4];
1805};
1806static int tracks_neighbour(int vertex, void *vctx)
1807{
1808 struct tracks_neighbour_ctx *ctx = (struct tracks_neighbour_ctx *)vctx;
1809 if (vertex >= 0) {
1810 game_state *state = ctx->state;
1811 int w = state->p.w, x = vertex % w, y = vertex / w;
1812 int dirs = S_E_DIRS(state, x, y, E_TRACK);
1813 int j;
1814
1815 ctx->i = ctx->n = 0;
1816
1817 for (j = 0; j < 4; j++) {
1818 int dir = 1<<j;
1819 if (dirs & dir) {
1820 int nx = x + DX(dir), ny = y + DY(dir);
1821 if (INGRID(state, nx, ny))
1822 ctx->neighbours[ctx->n++] = ny * w + nx;
1823 }
1824 }
1825 }
1826
1827 if (ctx->i < ctx->n)
1828 return ctx->neighbours[ctx->i++];
1829 else
1830 return -1;
1831}
1832
1833/*
1834 * The completion flash moves along the track, so we want to label
1835 * each tile with how far along the track it is. This is represented
1836 * as an eight-bit field, which is more than enough when the
1837 * completion flash is only 0.5 s long.
1838 */
1839static void set_flash_data(game_state *state)
1840{
1841 int ntrack = 0, x, y, n, d;
1842 const int w = state->p.w;
1843
1844 for (x = 0; x < w; x++)
1845 ntrack += state->numbers->numbers[x];
1846 n = 0; x = 0; y = state->numbers->row_s; d = R;
1847 do {
1848 state->sflags[y*w + x] &= ~(S_FLASH_MASK << S_FLASH_SHIFT);
1849 state->sflags[y*w + x] |=
1850 n++ * (S_FLASH_MASK / (ntrack - 1)) << S_FLASH_SHIFT;
1851 d = F(d); /* Find the direction we just arrived from. */
1852 d = S_E_DIRS(state, x, y, E_TRACK) & ~d; /* Other track from here. */
1853 x += DX(d); y += DY(d); /* Move to the next tile. */
1854 } while (INGRID(state, x, y));
1855}
1856
1857static bool check_completion(game_state *state, bool mark)
1858{
1859 int w = state->p.w, h = state->p.h, x, y, i, target;
1860 bool ret = true, pathret;
1861 int ntrack, nnotrack, ntrackcomplete;
1862 DSF *dsf;
1863 int pathclass;
1864 struct findloopstate *fls;
1865 struct tracks_neighbour_ctx ctx;
1866
1867 if (mark) {
1868 for (i = 0; i < w+h; i++) {
1869 state->num_errors[i] = 0;
1870 }
1871 for (i = 0; i < w*h; i++) {
1872 state->sflags[i] &= ~S_ERROR;
1873 if (S_E_COUNT(state, i%w, i/w, E_TRACK) > 0) {
1874 if (S_E_COUNT(state, i%w, i/w, E_TRACK) > 2) {
1875 ret = false;
1876 state->sflags[i] |= S_ERROR;
1877 }
1878 }
1879 }
1880 }
1881
1882 dsf = dsf_new(w*h);
1883
1884 for (x = 0; x < w; x++) {
1885 for (y = 0; y < h; y++) {
1886 dsf_update_completion(state, x, y, R, dsf);
1887 dsf_update_completion(state, x, y, D, dsf);
1888 }
1889 }
1890
1891 fls = findloop_new_state(w*h);
1892 ctx.state = state;
1893 if (findloop_run(fls, w*h, tracks_neighbour, &ctx)) {
1894 debug(("loop detected, not complete"));
1895 ret = false; /* no loop allowed */
1896 if (mark) {
1897 for (x = 0; x < w; x++) {
1898 for (y = 0; y < h; y++) {
1899 int u, v;
1900
1901 u = y*w + x;
1902 for (v = tracks_neighbour(u, &ctx); v >= 0;
1903 v = tracks_neighbour(-1, &ctx))
1904 if (findloop_is_loop_edge(fls, u, v))
1905 state->sflags[y*w+x] |= S_ERROR;
1906 }
1907 }
1908 }
1909 }
1910 findloop_free_state(fls);
1911
1912 if (mark) {
1913 pathclass = dsf_canonify(dsf, state->numbers->row_s*w);
1914 if (pathclass == dsf_canonify(dsf, (h-1)*w + state->numbers->col_s)) {
1915 /* We have a continuous path between the entrance and the exit: any
1916 other path must be in error. */
1917 for (i = 0; i < w*h; i++) {
1918 if ((dsf_canonify(dsf, i) != pathclass) &&
1919 ((state->sflags[i] & S_TRACK) ||
1920 (S_E_COUNT(state, i%w, i/w, E_TRACK) > 0))) {
1921 ret = false;
1922 state->sflags[i] |= S_ERROR;
1923 }
1924 }
1925 } else {
1926 /* If we _don't_ have such a path, then certainly the game
1927 * can't be in a winning state. So even if we're not
1928 * highlighting any _errors_, we certainly shouldn't
1929 * return true. */
1930 ret = false;
1931 }
1932 }
1933
1934 /*
1935 * A cell is 'complete', for the purposes of marking the game as
1936 * finished, if it has two edges marked as TRACK. But it only has
1937 * to have one edge marked as TRACK, or be filled in as trackful
1938 * without any specific edges known, to count towards checking
1939 * row/column clue errors.
1940 *
1941 * This changes if we haven't found any other errors by this
1942 * point, so the player has constructed a route from A to B. In
1943 * that case, we highlight any row/column where the actually laid
1944 * tracks don't match the clue.
1945 */
1946 pathret = ret; /* Do we have a plausible solution so far? */
1947 for (x = 0; x < w; x++) {
1948 target = state->numbers->numbers[x];
1949 ntrack = nnotrack = ntrackcomplete = 0;
1950 for (y = 0; y < h; y++) {
1951 if (S_E_COUNT(state, x, y, E_TRACK) > 0 ||
1952 state->sflags[y*w+x] & S_TRACK)
1953 ntrack++;
1954 if (S_E_COUNT(state, x, y, E_TRACK) == 2)
1955 ntrackcomplete++;
1956 if (state->sflags[y*w+x] & S_NOTRACK)
1957 nnotrack++;
1958 }
1959 if (mark) {
1960 if (ntrack > target || nnotrack > (h-target) ||
1961 (pathret && ntrackcomplete != target)) {
1962 debug(("col %d error: target %d, track %d, notrack %d, "
1963 "pathret %d, trackcomplete %d",
1964 x, target, ntrack, nnotrack, pathret, ntrackcomplete));
1965 state->num_errors[x] = 1;
1966 ret = false;
1967 }
1968 }
1969 if (ntrackcomplete != target)
1970 ret = false;
1971 }
1972 for (y = 0; y < h; y++) {
1973 target = state->numbers->numbers[w+y];
1974 ntrack = nnotrack = ntrackcomplete = 0;
1975 for (x = 0; x < w; x++) {
1976 if (S_E_COUNT(state, x, y, E_TRACK) > 0 ||
1977 state->sflags[y*w+x] & S_TRACK)
1978 ntrack++;
1979 if (S_E_COUNT(state, x, y, E_TRACK) == 2)
1980 ntrackcomplete++;
1981 if (state->sflags[y*w+x] & S_NOTRACK)
1982 nnotrack++;
1983 }
1984 if (mark) {
1985 if (ntrack > target || nnotrack > (w-target) ||
1986 (pathret && ntrackcomplete != target)) {
1987 debug(("row %d error: target %d, track %d, notrack %d, "
1988 "pathret %d, trackcomplete %d",
1989 y, target, ntrack, nnotrack, pathret, ntrackcomplete));
1990 state->num_errors[w+y] = 1;
1991 ret = false;
1992 }
1993 }
1994 if (ntrackcomplete != target)
1995 ret = false;
1996 }
1997
1998 if (mark) {
1999 state->completed = ret;
2000 if (ret) set_flash_data(state);
2001 }
2002 dsf_free(dsf);
2003 return ret;
2004}
2005
2006/* Code borrowed from Pearl. */
2007
2008struct game_ui {
2009 bool dragging, clearing, notrack;
2010 int drag_sx, drag_sy, drag_ex, drag_ey; /* drag start and end grid coords */
2011 int clickx, clicky; /* pixel position of initial click */
2012
2013 int curx, cury; /* grid position of keyboard cursor; uses half-size grid */
2014 bool cursor_active; /* true iff cursor is shown */
2015};
2016
2017static game_ui *new_ui(const game_state *state)
2018{
2019 game_ui *ui = snew(game_ui);
2020
2021 ui->clearing = false;
2022 ui->notrack = false;
2023 ui->dragging = false;
2024 ui->drag_sx = ui->drag_sy = ui->drag_ex = ui->drag_ey = -1;
2025 ui->cursor_active = getenv_bool("PUZZLES_SHOW_CURSOR", false);
2026 ui->curx = ui->cury = 1;
2027
2028 return ui;
2029}
2030
2031static void free_ui(game_ui *ui)
2032{
2033 sfree(ui);
2034}
2035
2036static void game_changed_state(game_ui *ui, const game_state *oldstate,
2037 const game_state *newstate)
2038{
2039}
2040
2041#define PREFERRED_TILE_SIZE 33
2042#define HALFSZ (ds->sz6*3)
2043#define THIRDSZ (ds->sz6*2)
2044#define TILE_SIZE (ds->sz6*6)
2045
2046#define MAX_BORDER (TILE_SIZE/8)
2047#define LINE_THICK (TILE_SIZE/16)
2048#define BORDER (ds->border)
2049#define GRID_LINE_TL (ds->grid_line_tl)
2050#define GRID_LINE_BR (ds->grid_line_br)
2051#define GRID_LINE_ALL (ds->grid_line_all)
2052
2053#define COORD(x) ( (x+1) * TILE_SIZE + BORDER )
2054#define CENTERED_COORD(x) ( COORD(x) + TILE_SIZE/2 )
2055#define FROMCOORD(x) ( ((x) < BORDER) ? -1 : ( ((x) - BORDER) / TILE_SIZE) - 1 )
2056
2057#define DS_DSHIFT 4 /* R/U/L/D shift, for drag-in-progress flags */
2058
2059#define DS_ERROR (1 << 8)
2060#define DS_CLUE (1 << 9)
2061#define DS_NOTRACK (1 << 10)
2062#define DS_FLASH (1 << 11)
2063#define DS_CURSOR (1 << 12) /* cursor in square (centre, or on edge) */
2064#define DS_TRACK (1 << 13)
2065#define DS_CLEARING (1 << 14)
2066
2067#define DS_NSHIFT 16 /* R/U/L/D shift, for no-track edge flags */
2068#define DS_CSHIFT 20 /* R/U/L/D shift, for cursor-on-edge */
2069
2070struct game_drawstate {
2071 int sz6, border, grid_line_all, grid_line_tl, grid_line_br;
2072 bool started;
2073
2074 int w, h, sz;
2075 unsigned int *flags, *flags_drag;
2076 int *num_errors;
2077};
2078
2079static void update_ui_drag(const game_state *state, game_ui *ui, int gx, int gy)
2080{
2081 int w = state->p.w, h = state->p.h;
2082 int dx = abs(ui->drag_sx - gx), dy = abs(ui->drag_sy - gy);
2083
2084 if (dy == 0) {
2085 ui->drag_ex = gx < 0 ? 0 : gx >= w ? w-1 : gx;
2086 ui->drag_ey = ui->drag_sy;
2087 ui->dragging = true;
2088 } else if (dx == 0) {
2089 ui->drag_ex = ui->drag_sx;
2090 ui->drag_ey = gy < 0 ? 0 : gy >= h ? h-1 : gy;
2091 ui->dragging = true;
2092 } else {
2093 ui->drag_ex = ui->drag_sx;
2094 ui->drag_ey = ui->drag_sy;
2095 ui->dragging = false;
2096 }
2097}
2098
2099static bool ui_can_flip_edge(const game_state *state, int x, int y, int dir,
2100 bool notrack)
2101{
2102 int w = state->p.w /*, h = state->shared->h, sz = state->shared->sz */;
2103 int x2 = x + DX(dir);
2104 int y2 = y + DY(dir);
2105 unsigned int sf1, sf2, ef;
2106
2107 if (!INGRID(state, x, y) || !INGRID(state, x2, y2))
2108 return false;
2109
2110 sf1 = state->sflags[y*w + x];
2111 sf2 = state->sflags[y2*w + x2];
2112 if ( !notrack && ((sf1 & S_CLUE) || (sf2 & S_CLUE)) )
2113 return false;
2114
2115 ef = S_E_FLAGS(state, x, y, dir);
2116 if (notrack) {
2117 /* if we're going to _set_ NOTRACK (i.e. the flag is currently unset),
2118 make sure the edge is not already set to TRACK. The adjacent squares
2119 could be set to TRACK, because we don't know which edges the general
2120 square setting refers to. */
2121 if (!(ef & E_NOTRACK) && (ef & E_TRACK))
2122 return false;
2123 } else {
2124 if (!(ef & E_TRACK)) {
2125 /* if we're going to _set_ TRACK, make sure neither adjacent square nor
2126 the edge itself is already set to NOTRACK. */
2127 if ((sf1 & S_NOTRACK) || (sf2 & S_NOTRACK) || (ef & E_NOTRACK))
2128 return false;
2129 /* if we're going to _set_ TRACK, make sure neither adjacent square has
2130 2 track flags already. */
2131 if ((S_E_COUNT(state, x, y, E_TRACK) >= 2) ||
2132 (S_E_COUNT(state, x2, y2, E_TRACK) >= 2))
2133 return false;
2134 }
2135 }
2136 return true;
2137}
2138
2139static bool ui_can_flip_square(const game_state *state, int x, int y, bool notrack)
2140{
2141 int w = state->p.w, trackc;
2142 unsigned sf;
2143
2144 if (!INGRID(state, x, y)) return false;
2145 sf = state->sflags[y*w+x];
2146 trackc = S_E_COUNT(state, x, y, E_TRACK);
2147
2148 if (sf & S_CLUE) return false;
2149
2150 if (notrack) {
2151 /* If we're setting S_NOTRACK, we cannot have either S_TRACK or any E_TRACK. */
2152 if (!(sf & S_NOTRACK) && ((sf & S_TRACK) || (trackc > 0)))
2153 return false;
2154 } else {
2155 /* If we're setting S_TRACK, we cannot have any S_NOTRACK (we could have
2156 E_NOTRACK, though, because one or two wouldn't rule out a track) */
2157 if (!(sf & S_TRACK) && (sf & S_NOTRACK))
2158 return false;
2159 }
2160 return true;
2161}
2162
2163static const char *current_key_label(const game_ui *ui,
2164 const game_state *state, int button)
2165{
2166 if (IS_CURSOR_SELECT(button) && ui->cursor_active) {
2167 int gx = ui->curx / 2, gy = ui->cury / 2;
2168 int w = state->p.w;
2169 int direction =
2170 ((ui->curx % 2) == 0) ? L : ((ui->cury % 2) == 0) ? U : 0;
2171 if (direction &&
2172 ui_can_flip_edge(state, gx, gy, direction,
2173 button == CURSOR_SELECT2)) {
2174 unsigned ef = S_E_FLAGS(state, gx, gy, direction);
2175 switch (button) {
2176 case CURSOR_SELECT: return (ef & E_TRACK) ? "Clear" : "Track";
2177 case CURSOR_SELECT2: return (ef & E_NOTRACK) ? "Clear" : "X";
2178 }
2179 }
2180 if (!direction &&
2181 ui_can_flip_square(state, gx, gy, button == CURSOR_SELECT2)) {
2182 unsigned sf = state->sflags[gy*w+gx];
2183 switch (button) {
2184 case CURSOR_SELECT: return (sf & S_TRACK) ? "Clear" : "Track";
2185 case CURSOR_SELECT2: return (sf & S_NOTRACK) ? "Clear" : "X";
2186 }
2187 }
2188 }
2189 return "";
2190}
2191
2192static char *edge_flip_str(const game_state *state, int x, int y, int dir, bool notrack, char *buf) {
2193 unsigned ef = S_E_FLAGS(state, x, y, dir);
2194 char c;
2195
2196 if (notrack)
2197 c = (ef & E_NOTRACK) ? 'n' : 'N';
2198 else
2199 c = (ef & E_TRACK) ? 't' : 'T';
2200
2201 sprintf(buf, "%c%c%d,%d", c, MOVECHAR(dir), x, y);
2202 return dupstr(buf);
2203}
2204
2205static char *square_flip_str(const game_state *state, int x, int y, bool notrack, char *buf) {
2206 unsigned f = state->sflags[y*state->p.w+x];
2207 char c;
2208
2209 if (notrack)
2210 c = (f & E_NOTRACK) ? 'n' : 'N';
2211 else
2212 c = (f & E_TRACK) ? 't' : 'T';
2213
2214 sprintf(buf, "%cS%d,%d", c, x, y);
2215 return dupstr(buf);
2216}
2217
2218#define SIGN(x) ((x<0) ? -1 : (x>0))
2219
2220static game_state *copy_and_apply_drag(const game_state *state, const game_ui *ui)
2221{
2222 game_state *after = dup_game(state);
2223 int x1, y1, x2, y2, x, y, w = state->p.w;
2224 unsigned f = ui->notrack ? S_NOTRACK : S_TRACK, ff;
2225
2226 x1 = min(ui->drag_sx, ui->drag_ex); x2 = max(ui->drag_sx, ui->drag_ex);
2227 y1 = min(ui->drag_sy, ui->drag_ey); y2 = max(ui->drag_sy, ui->drag_ey);
2228
2229 /* actually either x1 == x2, or y1 == y2, but it's easier just to code
2230 the nested loop. */
2231 for (x = x1; x <= x2; x++) {
2232 for (y = y1; y <= y2; y++) {
2233 ff = state->sflags[y*w+x];
2234 if (ui->clearing && !(ff & f))
2235 continue; /* nothing to do, clearing and already clear */
2236 else if (!ui->clearing && (ff & f))
2237 continue; /* nothing to do, setting and already set */
2238 else if (ui_can_flip_square(state, x, y, ui->notrack))
2239 after->sflags[y*w+x] ^= f;
2240 }
2241 }
2242 return after;
2243}
2244
2245#define KEY_DIRECTION(btn) (\
2246 (btn) == CURSOR_DOWN ? D : (btn) == CURSOR_UP ? U :\
2247 (btn) == CURSOR_LEFT ? L : R)
2248
2249static char *interpret_move(const game_state *state, game_ui *ui,
2250 const game_drawstate *ds,
2251 int x, int y, int button)
2252{
2253 int w = state->p.w, h = state->p.h, direction;
2254 int gx = FROMCOORD(x), gy = FROMCOORD(y);
2255 char tmpbuf[80];
2256
2257 /* --- mouse operations --- */
2258
2259 if (IS_MOUSE_DOWN(button)) {
2260 ui->cursor_active = false;
2261 ui->dragging = false;
2262
2263 if (!INGRID(state, gx, gy)) {
2264 /* can't drag from off grid */
2265 ui->drag_sx = ui->drag_sy = -1;
2266 return NULL;
2267 }
2268
2269 if (button == RIGHT_BUTTON) {
2270 ui->notrack = true;
2271 ui->clearing = state->sflags[gy*w+gx] & S_NOTRACK;
2272 } else {
2273 ui->notrack = false;
2274 ui->clearing = state->sflags[gy*w+gx] & S_TRACK;
2275 }
2276
2277 ui->clickx = x;
2278 ui->clicky = y;
2279 ui->drag_sx = ui->drag_ex = gx;
2280 ui->drag_sy = ui->drag_ey = gy;
2281
2282 return MOVE_UI_UPDATE;
2283 }
2284
2285 if (IS_MOUSE_DRAG(button)) {
2286 ui->cursor_active = false;
2287 update_ui_drag(state, ui, gx, gy);
2288 return MOVE_UI_UPDATE;
2289 }
2290
2291 if (IS_MOUSE_RELEASE(button)) {
2292 ui->cursor_active = false;
2293 if (ui->dragging &&
2294 (ui->drag_sx != ui->drag_ex || ui->drag_sy != ui->drag_ey)) {
2295 game_state *dragged = copy_and_apply_drag(state, ui);
2296 char *ret = move_string_diff(state, dragged, false);
2297
2298 ui->dragging = false;
2299 free_game(dragged);
2300
2301 return ret;
2302 } else {
2303 int cx, cy;
2304
2305 /* We might still have been dragging (and just done a one-
2306 * square drag): cancel drag, so undo doesn't make it like
2307 * a drag-in-progress. */
2308 ui->dragging = false;
2309
2310 /* Click (or tiny drag). Work out which edge we were
2311 * closest to. */
2312
2313 /*
2314 * We process clicks based on the mouse-down location,
2315 * because that's more natural for a user to carefully
2316 * control than the mouse-up.
2317 */
2318 x = ui->clickx;
2319 y = ui->clicky;
2320
2321 cx = CENTERED_COORD(gx);
2322 cy = CENTERED_COORD(gy);
2323
2324 if (!INGRID(state, gx, gy) || FROMCOORD(x) != gx || FROMCOORD(y) != gy)
2325 return MOVE_UI_UPDATE;
2326
2327 if (max(abs(x-cx),abs(y-cy)) < TILE_SIZE/4) {
2328 if (ui_can_flip_square(state, gx, gy, button == RIGHT_RELEASE))
2329 return square_flip_str(state, gx, gy, button == RIGHT_RELEASE, tmpbuf);
2330 return MOVE_UI_UPDATE;
2331 } else {
2332 if (abs(x-cx) < abs(y-cy)) {
2333 /* Closest to top/bottom edge. */
2334 direction = (y < cy) ? U : D;
2335 } else {
2336 /* Closest to left/right edge. */
2337 direction = (x < cx) ? L : R;
2338 }
2339 if (ui_can_flip_edge(state, gx, gy, direction,
2340 button == RIGHT_RELEASE))
2341 return edge_flip_str(state, gx, gy, direction,
2342 button == RIGHT_RELEASE, tmpbuf);
2343 else
2344 return MOVE_UI_UPDATE;
2345 }
2346 }
2347 }
2348
2349 /* --- cursor/keyboard operations --- */
2350
2351 if (IS_CURSOR_MOVE(button)) {
2352 int dx = (button == CURSOR_LEFT) ? -1 : ((button == CURSOR_RIGHT) ? +1 : 0);
2353 int dy = (button == CURSOR_DOWN) ? +1 : ((button == CURSOR_UP) ? -1 : 0);
2354
2355 if (!ui->cursor_active) {
2356 ui->cursor_active = true;
2357 return MOVE_UI_UPDATE;
2358 }
2359
2360 ui->curx = ui->curx + dx;
2361 ui->cury = ui->cury + dy;
2362 if ((ui->curx % 2 == 0) && (ui->cury % 2 == 0)) {
2363 /* disallow cursor on square corners: centres and edges only */
2364 ui->curx += dx; ui->cury += dy;
2365 }
2366 ui->curx = min(max(ui->curx, 1), 2*w-1);
2367 ui->cury = min(max(ui->cury, 1), 2*h-1);
2368 return MOVE_UI_UPDATE;
2369 }
2370
2371 if (IS_CURSOR_SELECT(button)) {
2372 if (!ui->cursor_active) {
2373 ui->cursor_active = true;
2374 return MOVE_UI_UPDATE;
2375 }
2376 /* click on square corner does nothing (shouldn't get here) */
2377 if ((ui->curx % 2) == 0 && (ui->cury % 2 == 0))
2378 return MOVE_UI_UPDATE;
2379
2380 gx = ui->curx / 2;
2381 gy = ui->cury / 2;
2382 direction = ((ui->curx % 2) == 0) ? L : ((ui->cury % 2) == 0) ? U : 0;
2383
2384 if (direction &&
2385 ui_can_flip_edge(state, gx, gy, direction, button == CURSOR_SELECT2))
2386 return edge_flip_str(state, gx, gy, direction, button == CURSOR_SELECT2, tmpbuf);
2387 else if (!direction &&
2388 ui_can_flip_square(state, gx, gy, button == CURSOR_SELECT2))
2389 return square_flip_str(state, gx, gy, button == CURSOR_SELECT2, tmpbuf);
2390 return MOVE_UI_UPDATE;
2391 }
2392
2393#if 0
2394 /* helps to debug the solver */
2395 if (button == 'H' || button == 'h')
2396 return dupstr("H");
2397#endif
2398
2399 return NULL;
2400}
2401
2402static game_state *execute_move(const game_state *state, const char *move)
2403{
2404 int w = state->p.w, x, y, n, i;
2405 char c, d;
2406 unsigned f;
2407 bool move_is_solve = false;
2408 game_state *ret = dup_game(state);
2409
2410 /* this is breaking the bank on GTK, which vsprintf's into a fixed-size buffer
2411 * which is 4096 bytes long. vsnprintf needs a feature-test macro to use, faff. */
2412 /*debug(("move: %s\n", move));*/
2413
2414 while (*move) {
2415 c = *move;
2416 if (c == 'S') {
2417 ret->used_solve = true;
2418 move_is_solve = true;
2419 move++;
2420 } else if (c == 'T' || c == 't' || c == 'N' || c == 'n') {
2421 /* set track, clear track; set notrack, clear notrack */
2422 move++;
2423 if (sscanf(move, "%c%d,%d%n", &d, &x, &y, &n) != 3)
2424 goto badmove;
2425 if (!INGRID(state, x, y)) goto badmove;
2426
2427 f = (c == 'T' || c == 't') ? S_TRACK : S_NOTRACK;
2428
2429 if (d == 'S') {
2430 if (!ui_can_flip_square(ret, x, y, f == S_NOTRACK) &&
2431 !move_is_solve)
2432 goto badmove;
2433 if (c == 'T' || c == 'N')
2434 ret->sflags[y*w+x] |= f;
2435 else
2436 ret->sflags[y*w+x] &= ~f;
2437 } else if (d == 'U' || d == 'D' || d == 'L' || d == 'R') {
2438 for (i = 0; i < 4; i++) {
2439 unsigned df = 1<<i;
2440
2441 if (MOVECHAR(df) == d) {
2442 if (!ui_can_flip_edge(ret, x, y, df, f == S_NOTRACK) &&
2443 !move_is_solve)
2444 goto badmove;
2445 if (c == 'T' || c == 'N')
2446 S_E_SET(ret, x, y, df, f);
2447 else
2448 S_E_CLEAR(ret, x, y, df, f);
2449 }
2450 }
2451 } else
2452 goto badmove;
2453 move += n;
2454 } else if (c == 'H') {
2455 tracks_solve(ret, DIFFCOUNT, NULL);
2456 move++;
2457 } else {
2458 goto badmove;
2459 }
2460 if (*move == ';')
2461 move++;
2462 else if (*move)
2463 goto badmove;
2464 }
2465
2466 check_completion(ret, true);
2467
2468 return ret;
2469
2470 badmove:
2471 free_game(ret);
2472 return NULL;
2473}
2474
2475/* ----------------------------------------------------------------------
2476 * Drawing routines.
2477 */
2478
2479#define FLASH_TIME 0.5F
2480
2481static void game_compute_size(const game_params *params, int tilesize,
2482 const game_ui *ui, int *x, int *y)
2483{
2484 /* Ick: fake up `ds->sz6' and `ds->border` for macro expansion purposes */
2485 struct {
2486 int sz6, border;
2487 } ads, *ds = &ads;
2488 ads.sz6 = tilesize/6;
2489 ads.border = MAX_BORDER;
2490 /*
2491 * Allow a reduced border at small tile sizes because the steps
2492 * are quite large and it's better to have a thin border than
2493 * to go down to a smaller tile size.
2494 */
2495 if (ads.border <= 5)
2496 ads.border = min(tilesize % 6, MAX_BORDER);
2497 *x = (params->w+2) * TILE_SIZE + 2 * BORDER;
2498 *y = (params->h+2) * TILE_SIZE + 2 * BORDER;
2499}
2500
2501static void game_set_size(drawing *dr, game_drawstate *ds,
2502 const game_params *params, int tilesize)
2503{
2504 ds->sz6 = tilesize/6;
2505 ds->border = MAX_BORDER;
2506 if (ds->border <= 5)
2507 ds->border = min(tilesize % 6, MAX_BORDER);
2508 ds->grid_line_all = max(LINE_THICK, 1);
2509 ds->grid_line_br = ds->grid_line_all / 2;
2510 ds->grid_line_tl = ds->grid_line_all - ds->grid_line_br;
2511}
2512
2513enum {
2514 COL_BACKGROUND, COL_TRACK_BACKGROUND,
2515 COL_GRID, COL_CLUE, COL_CURSOR,
2516 COL_TRACK, COL_TRACK_CLUE, COL_SLEEPER,
2517 COL_DRAGON, COL_DRAGOFF,
2518 COL_ERROR, COL_FLASH, COL_ERROR_BACKGROUND,
2519 NCOLOURS
2520};
2521
2522static float *game_colours(frontend *fe, int *ncolours)
2523{
2524 float *ret = snewn(3 * NCOLOURS, float);
2525 int i;
2526
2527 game_mkhighlight(fe, ret, COL_BACKGROUND, -1, COL_TRACK_BACKGROUND);
2528 colour_mix(&ret[COL_BACKGROUND*3], &ret[COL_TRACK_BACKGROUND*3], 0.5F,
2529 &ret[COL_GRID*3]);
2530
2531 for (i = 0; i < 3; i++) {
2532 ret[COL_TRACK_CLUE * 3 + i] = 0.0F;
2533 ret[COL_TRACK * 3 + i] = 0.5F;
2534 ret[COL_CLUE * 3 + i] = 0.0F;
2535 ret[COL_CURSOR * 3 + i] = 0.3F;
2536 ret[COL_ERROR_BACKGROUND * 3 + i] = 1.0F;
2537 }
2538
2539 ret[COL_SLEEPER * 3 + 0] = 0.5F;
2540 ret[COL_SLEEPER * 3 + 1] = 0.4F;
2541 ret[COL_SLEEPER * 3 + 2] = 0.1F;
2542
2543 ret[COL_ERROR * 3 + 0] = 1.0F;
2544 ret[COL_ERROR * 3 + 1] = 0.0F;
2545 ret[COL_ERROR * 3 + 2] = 0.0F;
2546
2547 ret[COL_DRAGON * 3 + 0] = 0.0F;
2548 ret[COL_DRAGON * 3 + 1] = 0.0F;
2549 ret[COL_DRAGON * 3 + 2] = 1.0F;
2550
2551 ret[COL_DRAGOFF * 3 + 0] = 0.8F;
2552 ret[COL_DRAGOFF * 3 + 1] = 0.8F;
2553 ret[COL_DRAGOFF * 3 + 2] = 1.0F;
2554
2555 ret[COL_FLASH * 3 + 0] = 1.0F;
2556 ret[COL_FLASH * 3 + 1] = 1.0F;
2557 ret[COL_FLASH * 3 + 2] = 1.0F;
2558
2559 *ncolours = NCOLOURS;
2560 return ret;
2561}
2562
2563static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2564{
2565 struct game_drawstate *ds = snew(struct game_drawstate);
2566 int i;
2567
2568 ds->sz6 = 0;
2569 ds->started = false;
2570
2571 ds->w = state->p.w;
2572 ds->h = state->p.h;
2573 ds->sz = ds->w*ds->h;
2574 ds->flags = snewn(ds->sz, unsigned int);
2575 ds->flags_drag = snewn(ds->sz, unsigned int);
2576 for (i = 0; i < ds->sz; i++)
2577 ds->flags[i] = ds->flags_drag[i] = 0;
2578
2579 ds->num_errors = snewn(ds->w+ds->h, int);
2580 for (i = 0; i < ds->w+ds->h; i++)
2581 ds->num_errors[i] = 0;
2582
2583 return ds;
2584}
2585
2586static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2587{
2588 sfree(ds->flags);
2589 sfree(ds->flags_drag);
2590 sfree(ds->num_errors);
2591 sfree(ds);
2592}
2593
2594static void draw_circle_sleepers(drawing *dr, game_drawstate *ds,
2595 float cx, float cy, float r2, float thickness, int c)
2596{
2597 float qr6 = (float)PI/12, qr3 = (float)PI/6, th, x1, y1, x2, y2;
2598 float t6 = THIRDSZ/2.0F, r1 = t6;
2599 int i;
2600
2601 for (i = 0; i < 12; i++) {
2602 th = qr6 + (i*qr3);
2603 x1 = r1*(float)cos(th);
2604 x2 = r2*(float)cos(th);
2605 y1 = r1*(float)sin(th);
2606 y2 = r2*(float)sin(th);
2607 draw_thick_line(dr, thickness, cx+x1, cy+y1, cx+x2, cy+y2, c);
2608 }
2609}
2610
2611static void draw_thick_circle_outline(drawing *dr, float thickness,
2612 float cx, float cy, float r,
2613 int colour)
2614{
2615 float circ4 = 0.5F * (float)PI * r, ang, x1, y1, x2, y2;
2616 int i, nseg;
2617
2618 nseg = (int)(circ4 / 4.0F)*4; /* ensure a quarter-circle has a whole #segs */
2619 ang = 2.0F*(float)PI / nseg;
2620
2621 for (i = 0; i < nseg; i++) {
2622 float th = ang * i, th2 = ang * (i+1);
2623 x1 = cx + r*(float)cos(th);
2624 x2 = cx + r*(float)cos(th2);
2625 y1 = cy + r*(float)sin(th);
2626 y2 = cy + r*(float)sin(th2);
2627 debug(("circ outline: x=%.2f -> %.2f, thick=%.2f\n",
2628 x1, x2, thickness));
2629 draw_thick_line(dr, thickness, x1, y1, x2, y2, colour);
2630 }
2631}
2632
2633static void draw_tracks_specific(drawing *dr, game_drawstate *ds,
2634 int x, int y, unsigned int flags,
2635 int ctrack, int csleeper)
2636{
2637 float ox = (float)COORD(x), oy = (float)COORD(y), cx, cy;
2638 float t1 = (float)TILE_SIZE, t3 = TILE_SIZE/3.0F, t6 = TILE_SIZE/6.0F;
2639 int d, i;
2640 float thick_track = TILE_SIZE/8.0F, thick_sleeper = TILE_SIZE/12.0F;
2641
2642 if (flags == LR) {
2643 for (i = 1; i <= 7; i+=2) {
2644 cx = ox + TILE_SIZE/8.0F*i;
2645 draw_thick_line(dr, thick_sleeper,
2646 cx, oy+t6, cx, oy+t6+2*t3, csleeper);
2647 }
2648 draw_thick_line(dr, thick_track, ox, oy + t3, ox + TILE_SIZE, oy + t3, ctrack);
2649 draw_thick_line(dr, thick_track, ox, oy + 2*t3, ox + TILE_SIZE, oy + 2*t3, ctrack);
2650 return;
2651 }
2652 if (flags == UD) {
2653 for (i = 1; i <= 7; i+=2) {
2654 cy = oy + TILE_SIZE/8.0F*i;
2655 draw_thick_line(dr, thick_sleeper,
2656 ox+t6, cy, ox+t6+2*t3, cy, csleeper);
2657 }
2658 debug(("vert line: x=%.2f, thick=%.2f", ox + t3, thick_track));
2659 draw_thick_line(dr, thick_track, ox + t3, oy, ox + t3, oy + TILE_SIZE, ctrack);
2660 draw_thick_line(dr, thick_track, ox + 2*t3, oy, ox + 2*t3, oy + TILE_SIZE, ctrack);
2661 return;
2662 }
2663 if (flags == UL || flags == DL || flags == UR || flags == DR) {
2664 cx = (flags & L) ? ox : ox + TILE_SIZE;
2665 cy = (flags & U) ? oy : oy + TILE_SIZE;
2666
2667 draw_circle_sleepers(dr, ds, cx, cy, (float)(5*t6), thick_sleeper, csleeper);
2668
2669 draw_thick_circle_outline(dr, thick_track, (float)cx, (float)cy,
2670 2*t3, ctrack);
2671 draw_thick_circle_outline(dr, thick_track, (float)cx, (float)cy,
2672 t3, ctrack);
2673
2674 return;
2675 }
2676
2677 for (d = 1; d < 16; d *= 2) {
2678 float ox1 = 0, ox2 = 0, oy1 = 0, oy2 = 0;
2679
2680 if (!(flags & d)) continue;
2681
2682 for (i = 1; i <= 2; i++) {
2683 if (d == L) {
2684 ox1 = 0;
2685 ox2 = thick_track;
2686 oy1 = oy2 = i*t3;
2687 } else if (d == R) {
2688 ox1 = t1;
2689 ox2 = t1 - thick_track;
2690 oy1 = oy2 = i*t3;
2691 } else if (d == U) {
2692 ox1 = ox2 = i*t3;
2693 oy1 = 0;
2694 oy2 = thick_track;
2695 } else if (d == D) {
2696 ox1 = ox2 = i*t3;
2697 oy1 = t1;
2698 oy2 = t1 - thick_track;
2699 }
2700 draw_thick_line(dr, thick_track, ox+ox1, oy+oy1, ox+ox2, oy+oy2, ctrack);
2701 }
2702 }
2703}
2704
2705static unsigned int best_bits(unsigned int flags, unsigned int flags_drag, int *col)
2706{
2707 int nb_orig = nbits[flags & ALLDIR], nb_drag = nbits[flags_drag & ALLDIR];
2708
2709 if (nb_orig > nb_drag) {
2710 *col = COL_DRAGOFF;
2711 return flags & ALLDIR;
2712 } else if (nb_orig < nb_drag) {
2713 *col = COL_DRAGON;
2714 return flags_drag & ALLDIR;
2715 }
2716 return flags & ALLDIR; /* same number of bits: no special colour. */
2717}
2718
2719static void draw_square(drawing *dr, game_drawstate *ds,
2720 int x, int y, unsigned int flags, unsigned int flags_drag)
2721{
2722 int t2 = HALFSZ, t16 = HALFSZ/4, off;
2723 int ox = COORD(x), oy = COORD(y), cx = ox + t2, cy = oy + t2, d, c;
2724 int bg = (flags & DS_TRACK) ? COL_TRACK_BACKGROUND : COL_BACKGROUND;
2725 unsigned int flags_best;
2726
2727 assert(dr);
2728
2729 /* Clip to the grid square. */
2730 clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2731
2732 /* Clear the square so that it's got an appropriately-sized border
2733 * in COL_GRID and a central area in the right background colour. */
2734 best_bits((flags & DS_TRACK) == DS_TRACK,
2735 (flags_drag & DS_TRACK) == DS_TRACK, &bg);
2736 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_GRID);
2737 draw_rect(dr, ox + GRID_LINE_TL, oy + GRID_LINE_TL,
2738 TILE_SIZE - GRID_LINE_ALL, TILE_SIZE - GRID_LINE_ALL, bg);
2739
2740 /* More outlines for clue squares. */
2741 if (flags & DS_CURSOR) {
2742 int curx, cury, curw, curh;
2743
2744 off = t16;
2745 curx = ox + off; cury = oy + off;
2746 curw = curh = TILE_SIZE - (2*off) + 1;
2747
2748 if (flags & (U << DS_CSHIFT)) {
2749 cury = oy - off; curh = 2*off + 1;
2750 } else if (flags & (D << DS_CSHIFT)) {
2751 cury = oy + TILE_SIZE - off; curh = 2*off + 1;
2752 } else if (flags & (L << DS_CSHIFT)) {
2753 curx = ox - off; curw = 2*off + 1;
2754 } else if (flags & (R << DS_CSHIFT)) {
2755 curx = ox + TILE_SIZE - off; curw = 2*off + 1;
2756 }
2757
2758 draw_rect_outline(dr, curx, cury, curw, curh, COL_CURSOR);
2759 }
2760
2761 /* Draw tracks themselves */
2762 c = (flags & DS_ERROR) ? COL_ERROR :
2763 (flags & DS_FLASH) ? COL_FLASH :
2764 (flags & DS_CLUE) ? COL_TRACK_CLUE : COL_TRACK;
2765 flags_best = best_bits(flags, flags_drag, &c);
2766 draw_tracks_specific(dr, ds, x, y, flags_best, c, COL_SLEEPER);
2767
2768 /* Draw no-track marks, if present, in square and on edges. */
2769 c = COL_TRACK;
2770 flags_best = best_bits((flags & DS_NOTRACK) == DS_NOTRACK,
2771 (flags_drag & DS_NOTRACK) == DS_NOTRACK, &c);
2772 if (flags_best) {
2773 off = HALFSZ/2;
2774 draw_thick_line(dr, LINE_THICK, cx - off, cy - off, cx + off, cy + off, c);
2775 draw_thick_line(dr, LINE_THICK, cx - off, cy + off, cx + off, cy - off, c);
2776 }
2777
2778 c = COL_TRACK;
2779 flags_best = best_bits(flags >> DS_NSHIFT, flags_drag >> DS_NSHIFT, &c);
2780 for (d = 1; d < 16; d *= 2) {
2781 off = t16;
2782 cx = ox + t2;
2783 cy = oy + t2;
2784
2785 if (flags_best & d) {
2786 cx += (d == R) ? t2 : (d == L) ? -t2 : 0;
2787 cy += (d == D) ? t2 : (d == U) ? -t2 : 0;
2788
2789 draw_thick_line(dr, LINE_THICK, cx - off, cy - off, cx + off, cy + off, c);
2790 draw_thick_line(dr, LINE_THICK, cx - off, cy + off, cx + off, cy - off, c);
2791 }
2792 }
2793
2794 unclip(dr);
2795 draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
2796}
2797
2798static void draw_clue(drawing *dr, game_drawstate *ds, int w, int clue, int i, int col, int bg)
2799{
2800 int cx, cy, tsz = TILE_SIZE/2;
2801 char buf[20];
2802
2803 if (i < w) {
2804 cx = CENTERED_COORD(i);
2805 cy = CENTERED_COORD(-1);
2806 } else {
2807 cx = CENTERED_COORD(w);
2808 cy = CENTERED_COORD(i-w);
2809 }
2810
2811 if (bg >= 0)
2812 draw_rect(dr, cx - tsz + GRID_LINE_TL, cy - tsz + GRID_LINE_TL,
2813 TILE_SIZE - GRID_LINE_ALL, TILE_SIZE - GRID_LINE_ALL, bg);
2814 sprintf(buf, "%d", clue);
2815 draw_text(dr, cx, cy, FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2816 col, buf);
2817 draw_update(dr, cx - tsz + GRID_LINE_TL, cy - tsz + GRID_LINE_TL,
2818 TILE_SIZE - GRID_LINE_ALL, TILE_SIZE - GRID_LINE_ALL);
2819}
2820
2821static void draw_loop_ends(drawing *dr, game_drawstate *ds,
2822 const game_state *state, int c)
2823{
2824 int tsz = TILE_SIZE/2;
2825
2826 draw_text(dr, CENTERED_COORD(-1), CENTERED_COORD(state->numbers->row_s),
2827 FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2828 c, "A");
2829
2830 draw_text(dr, CENTERED_COORD(state->numbers->col_s), CENTERED_COORD(state->p.h),
2831 FONT_VARIABLE, tsz, ALIGN_VCENTRE|ALIGN_HCENTRE,
2832 c, "B");
2833}
2834
2835static unsigned int s2d_flags(const game_state *state, int x, int y, const game_ui *ui)
2836{
2837 unsigned int f;
2838 int w = state->p.w;
2839
2840 f = S_E_DIRS(state, x, y, E_TRACK);
2841 f |= (S_E_DIRS(state, x, y, E_NOTRACK) << DS_NSHIFT);
2842
2843 if (state->sflags[y*w+x] & S_ERROR)
2844 f |= DS_ERROR;
2845 if (state->sflags[y*w+x] & S_CLUE)
2846 f |= DS_CLUE;
2847 if (state->sflags[y*w+x] & S_NOTRACK)
2848 f |= DS_NOTRACK;
2849 if ((state->sflags[y*w+x] & S_TRACK) || (S_E_COUNT(state, x, y, E_TRACK) > 0))
2850 f |= DS_TRACK;
2851
2852 if (ui->cursor_active) {
2853 if (ui->curx >= x*2 && ui->curx <= (x+1)*2 &&
2854 ui->cury >= y*2 && ui->cury <= (y+1)*2) {
2855 f |= DS_CURSOR;
2856 if (ui->curx == x*2) f |= (L << DS_CSHIFT);
2857 if (ui->curx == (x+1)*2) f |= (R << DS_CSHIFT);
2858 if (ui->cury == y*2) f |= (U << DS_CSHIFT);
2859 if (ui->cury == (y+1)*2) f |= (D << DS_CSHIFT);
2860 }
2861 }
2862
2863 return f;
2864}
2865
2866static void game_redraw(drawing *dr, game_drawstate *ds, const game_state *oldstate,
2867 const game_state *state, int dir, const game_ui *ui,
2868 float animtime, float flashtime)
2869{
2870 int i, x, y, flashing, w = ds->w, h = ds->h;
2871 bool force = false;
2872 game_state *drag_state = NULL;
2873
2874 if (!ds->started) {
2875 draw_loop_ends(dr, ds, state, COL_CLUE);
2876
2877 draw_rect(dr, COORD(0) - GRID_LINE_BR, COORD(0) - GRID_LINE_BR,
2878 ds->w * TILE_SIZE + GRID_LINE_ALL,
2879 ds->h * TILE_SIZE + GRID_LINE_ALL, COL_GRID);
2880
2881 draw_update(dr, 0, 0, (w+2)*TILE_SIZE + 2*BORDER, (h+2)*TILE_SIZE + 2*BORDER);
2882
2883 ds->started = true;
2884 force = true;
2885 }
2886
2887 for (i = 0; i < w+h; i++) {
2888 if (force || (state->num_errors[i] != ds->num_errors[i])) {
2889 ds->num_errors[i] = state->num_errors[i];
2890 draw_clue(dr, ds, w, state->numbers->numbers[i], i,
2891 ds->num_errors[i] ? COL_ERROR : COL_CLUE,
2892 ds->num_errors[i] ? COL_ERROR_BACKGROUND : COL_BACKGROUND);
2893 }
2894 }
2895
2896 if (ui->dragging)
2897 drag_state = copy_and_apply_drag(state, ui);
2898
2899 for (x = 0; x < w; x++) {
2900 for (y = 0; y < h; y++) {
2901 unsigned int f, f_d;
2902
2903 flashing = 0;
2904 if (flashtime > 0) {
2905 float flashpos =
2906 (state->sflags[y*w+x] >> S_FLASH_SHIFT & S_FLASH_MASK) /
2907 (float)S_FLASH_MASK;
2908 if (flashtime > FLASH_TIME / 2 * flashpos &&
2909 flashtime <= FLASH_TIME / 2 * (flashpos + 1.0F))
2910 flashing = DS_FLASH;
2911 }
2912
2913 f = s2d_flags(state, x, y, ui) | flashing;
2914 f_d = drag_state ? s2d_flags(drag_state, x, y, ui) : f;
2915
2916 if (f != ds->flags[y*w+x] || f_d != ds->flags_drag[y*w+x] || force) {
2917 ds->flags[y*w+x] = f;
2918 ds->flags_drag[y*w+x] = f_d;
2919 draw_square(dr, ds, x, y, f, f_d);
2920 }
2921 }
2922 }
2923
2924 if (drag_state) free_game(drag_state);
2925}
2926
2927static float game_anim_length(const game_state *oldstate, const game_state *newstate,
2928 int dir, game_ui *ui)
2929{
2930 return 0.0F;
2931}
2932
2933static float game_flash_length(const game_state *oldstate, const game_state *newstate,
2934 int dir, game_ui *ui)
2935{
2936 if (!oldstate->completed &&
2937 newstate->completed && !newstate->used_solve)
2938 return FLASH_TIME;
2939 else
2940 return 0.0F;
2941}
2942
2943static void game_get_cursor_location(const game_ui *ui,
2944 const game_drawstate *ds,
2945 const game_state *state,
2946 const game_params *params,
2947 int *x, int *y, int *w, int *h)
2948{
2949 if(ui->cursor_active) {
2950 int off = HALFSZ / 4;
2951 int cx = COORD(ui->curx / 2) + off;
2952 int cy = COORD(ui->cury / 2) + off;
2953 int cw, ch;
2954 cw = ch = TILE_SIZE - (2*off) + 1;
2955
2956 if(ui->curx % 2 == 0) {
2957 /* left border */
2958 cx -= off;
2959 cw = 2 * off + 1;
2960 }
2961 if(ui->cury % 2 == 0) {
2962 /* upper border */
2963 cy -= off;
2964 ch = 2 * off + 1;
2965 }
2966
2967 *x = cx;
2968 *y = cy;
2969 *w = cw;
2970 *h = ch;
2971 }
2972}
2973
2974static int game_status(const game_state *state)
2975{
2976 return state->completed ? +1 : 0;
2977}
2978
2979static void game_print_size(const game_params *params, const game_ui *ui,
2980 float *x, float *y)
2981{
2982 int pw, ph;
2983
2984 /* The Times uses 7mm squares */
2985 game_compute_size(params, 700, ui, &pw, &ph);
2986 *x = pw / 100.0F;
2987 *y = ph / 100.0F;
2988}
2989
2990static void game_print(drawing *dr, const game_state *state, const game_ui *ui,
2991 int tilesize)
2992{
2993 int w = state->p.w, h = state->p.h;
2994 int black = print_mono_colour(dr, 0), grey = print_grey_colour(dr, 0.5F);
2995 int x, y, i;
2996
2997 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2998 game_drawstate ads, *ds = &ads;
2999 game_set_size(dr, ds, NULL, tilesize);
3000
3001 /* Grid, then border (second so it is on top) */
3002 print_line_width(dr, TILE_SIZE / 24);
3003 for (x = 1; x < w; x++)
3004 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), grey);
3005 for (y = 1; y < h; y++)
3006 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), grey);
3007
3008 print_line_width(dr, TILE_SIZE / 16);
3009 draw_rect_outline(dr, COORD(0), COORD(0), w*TILE_SIZE, h*TILE_SIZE, black);
3010
3011 print_line_width(dr, TILE_SIZE / 24);
3012
3013 /* clue numbers, and loop ends */
3014 for (i = 0; i < w+h; i++)
3015 draw_clue(dr, ds, w, state->numbers->numbers[i], i, black, -1);
3016 draw_loop_ends(dr, ds, state, black);
3017
3018 /* clue tracks / solution */
3019 for (x = 0; x < w; x++) {
3020 for (y = 0; y < h; y++) {
3021 clip(dr, COORD(x), COORD(y), TILE_SIZE, TILE_SIZE);
3022 draw_tracks_specific(dr, ds, x, y, S_E_DIRS(state, x, y, E_TRACK),
3023 black, grey);
3024 unclip(dr);
3025 }
3026 }
3027}
3028
3029#ifdef COMBINED
3030#define thegame tracks
3031#endif
3032
3033const struct game thegame = {
3034 "Train Tracks", "games.tracks", "tracks",
3035 default_params,
3036 game_fetch_preset, NULL,
3037 decode_params,
3038 encode_params,
3039 free_params,
3040 dup_params,
3041 true, game_configure, custom_params,
3042 validate_params,
3043 new_game_desc,
3044 validate_desc,
3045 new_game,
3046 dup_game,
3047 free_game,
3048 true, solve_game,
3049 true, game_can_format_as_text_now, game_text_format,
3050 NULL, NULL, /* get_prefs, set_prefs */
3051 new_ui,
3052 free_ui,
3053 NULL, /* encode_ui */
3054 NULL, /* decode_ui */
3055 NULL, /* game_request_keys */
3056 game_changed_state,
3057 current_key_label,
3058 interpret_move,
3059 execute_move,
3060 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
3061 game_colours,
3062 game_new_drawstate,
3063 game_free_drawstate,
3064 game_redraw,
3065 game_anim_length,
3066 game_flash_length,
3067 game_get_cursor_location,
3068 game_status,
3069 true, false, game_print_size, game_print,
3070 false, /* wants_statusbar */
3071 false, NULL, /* timing_state */
3072 0, /* flags */
3073};
3074
3075#ifdef STANDALONE_SOLVER
3076
3077int main(int argc, char **argv)
3078{
3079 game_params *p;
3080 game_state *s;
3081 char *id = NULL, *desc;
3082 int maxdiff = DIFFCOUNT, diff_used;
3083 const char *err;
3084 bool diagnostics = false, grade = false;
3085 int retd;
3086
3087 while (--argc > 0) {
3088 char *p = *++argv;
3089 if (!strcmp(p, "-v")) {
3090 diagnostics = true;
3091 } else if (!strcmp(p, "-g")) {
3092 grade = true;
3093 } else if (!strncmp(p, "-d", 2) && p[2] && !p[3]) {
3094 int i;
3095 bool bad = true;
3096 for (i = 0; i < lenof(tracks_diffchars); i++)
3097 if (tracks_diffchars[i] == p[2]) {
3098 bad = false;
3099 maxdiff = i;
3100 break;
3101 }
3102 if (bad) {
3103 fprintf(stderr, "%s: unrecognised difficulty `%c'\n",
3104 argv[0], p[2]);
3105 return 1;
3106 }
3107 } else if (*p == '-') {
3108 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
3109 return 1;
3110 } else {
3111 id = p;
3112 }
3113 }
3114
3115 if (!id) {
3116 fprintf(stderr, "usage: %s [-v | -g] <game_id>\n", argv[0]);
3117 return 1;
3118 }
3119
3120 desc = strchr(id, ':');
3121 if (!desc) {
3122 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
3123 return 1;
3124 }
3125 *desc++ = '\0';
3126
3127 p = default_params();
3128 decode_params(p, id);
3129 err = validate_desc(p, desc);
3130 if (err) {
3131 fprintf(stderr, "%s: %s\n", argv[0], err);
3132 return 1;
3133 }
3134 s = new_game(NULL, p, desc);
3135
3136 solver_diagnostics_fp = (diagnostics ? stdout : NULL);
3137 retd = tracks_solve(s, maxdiff, &diff_used);
3138 if (retd < 0) {
3139 printf("Puzzle is inconsistent\n");
3140 } else if (grade) {
3141 printf("Difficulty rating: %s\n",
3142 (retd == 0 ? "Ambiguous" : tracks_diffnames[diff_used]));
3143 } else {
3144 char *text = game_text_format(s);
3145 fputs(text, stdout);
3146 sfree(text);
3147 if (retd == 0)
3148 printf("Could not deduce a unique solution\n");
3149 }
3150 free_game(s);
3151 free_params(p);
3152
3153 return 0;
3154}
3155
3156#endif
3157
3158/* vim: set shiftwidth=4 tabstop=8: */