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 * slant.c: Puzzle from nikoli.co.jp involving drawing a diagonal
3 * line through each square of a grid.
4 */
5
6/*
7 * In this puzzle you have a grid of squares, each of which must
8 * contain a diagonal line; you also have clue numbers placed at
9 * _points_ of that grid, which means there's a (w+1) x (h+1) array
10 * of possible clue positions.
11 *
12 * I'm therefore going to adopt a rigid convention throughout this
13 * source file of using w and h for the dimensions of the grid of
14 * squares, and W and H for the dimensions of the grid of points.
15 * Thus, W == w+1 and H == h+1 always.
16 *
17 * Clue arrays will be W*H `signed char's, and the clue at each
18 * point will be a number from 0 to 4, or -1 if there's no clue.
19 *
20 * Solution arrays will be W*H `signed char's, and the number at
21 * each point will be +1 for a forward slash (/), -1 for a
22 * backslash (\), and 0 for unknown.
23 */
24
25#include <stdio.h>
26#include <stdlib.h>
27#include <stdarg.h>
28#include <string.h>
29#include <assert.h>
30#include <ctype.h>
31#ifdef NO_TGMATH_H
32# include <math.h>
33#else
34# include <tgmath.h>
35#endif
36
37#include "puzzles.h"
38
39enum {
40 COL_BACKGROUND,
41 COL_GRID,
42 COL_INK,
43 COL_SLANT1,
44 COL_SLANT2,
45 COL_ERROR,
46 COL_CURSOR,
47 COL_FILLEDSQUARE,
48 COL_GROUNDED,
49 NCOLOURS
50};
51
52enum {
53 PREF_MOUSE_BUTTON_ORDER,
54 PREF_FADE_GROUNDED,
55 N_PREF_ITEMS
56};
57
58/*
59 * In standalone solver mode, `verbose' is a variable which can be
60 * set by command-line option; in debugging mode it's simply always
61 * true.
62 */
63#if defined STANDALONE_SOLVER
64#define SOLVER_DIAGNOSTICS
65static bool verbose = false;
66#elif defined SOLVER_DIAGNOSTICS
67#define verbose true
68#endif
69
70/*
71 * Difficulty levels. I do some macro ickery here to ensure that my
72 * enum and the various forms of my name list always match up.
73 */
74#define DIFFLIST(A) \
75 A(EASY,Easy,e) \
76 A(HARD,Hard,h)
77#define ENUM(upper,title,lower) DIFF_ ## upper,
78#define TITLE(upper,title,lower) #title,
79#define ENCODE(upper,title,lower) #lower
80#define CONFIG(upper,title,lower) ":" #title
81enum { DIFFLIST(ENUM) DIFFCOUNT };
82static char const *const slant_diffnames[] = { DIFFLIST(TITLE) };
83static char const slant_diffchars[] = DIFFLIST(ENCODE);
84#define DIFFCONFIG DIFFLIST(CONFIG)
85
86struct game_params {
87 int w, h, diff;
88};
89
90typedef struct game_clues {
91 int w, h;
92 signed char *clues;
93 int *tmpdsf;
94 int refcount;
95} game_clues;
96
97#define ERR_VERTEX 1
98#define ERR_SQUARE 2
99#define BORDER_EDGE 4 /* kind of an abuse: not an error */
100
101struct game_state {
102 struct game_params p;
103 game_clues *clues;
104 signed char *soln;
105 unsigned char *errors;
106 bool completed;
107 bool used_solve; /* used to suppress completion flash */
108};
109
110static game_params *default_params(void)
111{
112 game_params *ret = snew(game_params);
113
114 ret->w = ret->h = 8;
115 ret->diff = DIFF_EASY;
116
117 return ret;
118}
119
120static const struct game_params slant_presets[] = {
121 {5, 5, DIFF_EASY},
122 {5, 5, DIFF_HARD},
123 {8, 8, DIFF_EASY},
124 {8, 8, DIFF_HARD},
125 {12, 10, DIFF_EASY},
126 {12, 10, DIFF_HARD},
127};
128
129static bool game_fetch_preset(int i, char **name, game_params **params)
130{
131 game_params *ret;
132 char str[80];
133
134 if (i < 0 || i >= lenof(slant_presets))
135 return false;
136
137 ret = snew(game_params);
138 *ret = slant_presets[i];
139
140 sprintf(str, "%dx%d %s", ret->w, ret->h, slant_diffnames[ret->diff]);
141
142 *name = dupstr(str);
143 *params = ret;
144 return true;
145}
146
147static void free_params(game_params *params)
148{
149 sfree(params);
150}
151
152static game_params *dup_params(const game_params *params)
153{
154 game_params *ret = snew(game_params);
155 *ret = *params; /* structure copy */
156 return ret;
157}
158
159static void decode_params(game_params *ret, char const *string)
160{
161 ret->w = ret->h = atoi(string);
162 while (*string && isdigit((unsigned char)*string)) string++;
163 if (*string == 'x') {
164 string++;
165 ret->h = atoi(string);
166 while (*string && isdigit((unsigned char)*string)) string++;
167 }
168 if (*string == 'd') {
169 int i;
170 string++;
171 for (i = 0; i < DIFFCOUNT; i++)
172 if (*string == slant_diffchars[i])
173 ret->diff = i;
174 if (*string) string++;
175 }
176}
177
178static char *encode_params(const game_params *params, bool full)
179{
180 char data[256];
181
182 sprintf(data, "%dx%d", params->w, params->h);
183 if (full)
184 sprintf(data + strlen(data), "d%c", slant_diffchars[params->diff]);
185
186 return dupstr(data);
187}
188
189static config_item *game_configure(const game_params *params)
190{
191 config_item *ret;
192 char buf[80];
193
194 ret = snewn(4, config_item);
195
196 ret[0].name = "Width";
197 ret[0].type = C_STRING;
198 sprintf(buf, "%d", params->w);
199 ret[0].u.string.sval = dupstr(buf);
200
201 ret[1].name = "Height";
202 ret[1].type = C_STRING;
203 sprintf(buf, "%d", params->h);
204 ret[1].u.string.sval = dupstr(buf);
205
206 ret[2].name = "Difficulty";
207 ret[2].type = C_CHOICES;
208 ret[2].u.choices.choicenames = DIFFCONFIG;
209 ret[2].u.choices.selected = params->diff;
210
211 ret[3].name = NULL;
212 ret[3].type = C_END;
213
214 return ret;
215}
216
217static game_params *custom_params(const config_item *cfg)
218{
219 game_params *ret = snew(game_params);
220
221 ret->w = atoi(cfg[0].u.string.sval);
222 ret->h = atoi(cfg[1].u.string.sval);
223 ret->diff = cfg[2].u.choices.selected;
224
225 return ret;
226}
227
228static const char *validate_params(const game_params *params, bool full)
229{
230 /*
231 * (At least at the time of writing this comment) The grid
232 * generator is actually capable of handling even zero grid
233 * dimensions without crashing. Puzzles with a zero-area grid
234 * are a bit boring, though, because they're already solved :-)
235 * And puzzles with a dimension of 1 can't be made Hard, which
236 * means the simplest thing is to forbid them altogether.
237 */
238
239 if (params->w < 2 || params->h < 2)
240 return "Width and height must both be at least two";
241 if (params->w > INT_MAX / params->h)
242 return "Width times height must not be unreasonably large";
243
244 return NULL;
245}
246
247/*
248 * Scratch space for solver.
249 */
250struct solver_scratch {
251 /*
252 * Disjoint set forest which tracks the connected sets of
253 * points.
254 */
255 DSF *connected;
256
257 /*
258 * Counts the number of possible exits from each connected set
259 * of points. (That is, the number of possible _simultaneous_
260 * exits: an unconnected point labelled 2 has an exit count of
261 * 2 even if all four possible edges are still under
262 * consideration.)
263 */
264 int *exits;
265
266 /*
267 * Tracks whether each connected set of points includes a
268 * border point.
269 */
270 bool *border;
271
272 /*
273 * Another disjoint set forest. This one tracks _squares_ which
274 * are known to slant in the same direction.
275 */
276 DSF *equiv;
277
278 /*
279 * Stores slash values which we know for an equivalence class.
280 * When we fill in a square, we set slashval[canonify(x)] to
281 * the same value as soln[x], so that we can then spot other
282 * squares equivalent to it and fill them in immediately via
283 * their known equivalence.
284 */
285 signed char *slashval;
286
287 /*
288 * Stores possible v-shapes. This array is w by h in size, but
289 * not every bit of every entry is meaningful. The bits mean:
290 *
291 * - bit 0 for a square means that that square and the one to
292 * its right might form a v-shape between them
293 * - bit 1 for a square means that that square and the one to
294 * its right might form a ^-shape between them
295 * - bit 2 for a square means that that square and the one
296 * below it might form a >-shape between them
297 * - bit 3 for a square means that that square and the one
298 * below it might form a <-shape between them
299 *
300 * Any starting 1 or 3 clue rules out four bits in this array
301 * immediately; a 2 clue propagates any ruled-out bit past it
302 * (if the two squares on one side of a 2 cannot be a v-shape,
303 * then neither can the two on the other side be the same
304 * v-shape); we can rule out further bits during play using
305 * partially filled 2 clues; whenever a pair of squares is
306 * known not to be _either_ kind of v-shape, we can mark them
307 * as equivalent.
308 */
309 unsigned char *vbitmap;
310
311 /*
312 * Useful to have this information automatically passed to
313 * solver subroutines. (This pointer is not dynamically
314 * allocated by new_scratch and free_scratch.)
315 */
316 const signed char *clues;
317};
318
319static struct solver_scratch *new_scratch(int w, int h)
320{
321 int W = w+1, H = h+1;
322 struct solver_scratch *ret = snew(struct solver_scratch);
323 ret->connected = dsf_new(W*H);
324 ret->exits = snewn(W*H, int);
325 ret->border = snewn(W*H, bool);
326 ret->equiv = dsf_new(w*h);
327 ret->slashval = snewn(w*h, signed char);
328 ret->vbitmap = snewn(w*h, unsigned char);
329 return ret;
330}
331
332static void free_scratch(struct solver_scratch *sc)
333{
334 sfree(sc->vbitmap);
335 sfree(sc->slashval);
336 dsf_free(sc->equiv);
337 sfree(sc->border);
338 sfree(sc->exits);
339 dsf_free(sc->connected);
340 sfree(sc);
341}
342
343/*
344 * Wrapper on dsf_merge() which updates the `exits' and `border'
345 * arrays.
346 */
347static void merge_vertices(DSF *connected,
348 struct solver_scratch *sc, int i, int j)
349{
350 int exits = -1;
351 bool border = false; /* initialise to placate optimiser */
352
353 if (sc) {
354 i = dsf_canonify(connected, i);
355 j = dsf_canonify(connected, j);
356
357 /*
358 * We have used one possible exit from each of the two
359 * classes. Thus, the viable exit count of the new class is
360 * the sum of the old exit counts minus two.
361 */
362 exits = sc->exits[i] + sc->exits[j] - 2;
363
364 border = sc->border[i] || sc->border[j];
365 }
366
367 dsf_merge(connected, i, j);
368
369 if (sc) {
370 i = dsf_canonify(connected, i);
371 sc->exits[i] = exits;
372 sc->border[i] = border;
373 }
374}
375
376/*
377 * Called when we have just blocked one way out of a particular
378 * point. If that point is a non-clue point (thus has a variable
379 * number of exits), we have therefore decreased its potential exit
380 * count, so we must decrement the exit count for the group as a
381 * whole.
382 */
383static void decr_exits(struct solver_scratch *sc, int i)
384{
385 if (sc->clues[i] < 0) {
386 i = dsf_canonify(sc->connected, i);
387 sc->exits[i]--;
388 }
389}
390
391static bool fill_square(int w, int h, int x, int y, int v,
392 signed char *soln,
393 DSF *connected, struct solver_scratch *sc)
394{
395 int W = w+1 /*, H = h+1 */;
396 int ci1, ci2; /* indices of the vertices of the square we're connecting */
397 int di1, di2; /* the other two vertices, which we're disconnecting */
398
399 assert(x >= 0 && x < w && y >= 0 && y < h);
400
401 if (soln[y*w+x] == v) {
402 return true; /* do nothing */
403 }
404
405#ifdef SOLVER_DIAGNOSTICS
406 if (verbose)
407 printf(" placing %c in %d,%d\n", v == -1 ? '\\' : '/', x, y);
408#endif
409
410 if (soln[y*w+x] != 0) {
411#ifdef SOLVER_DIAGNOSTICS
412 if (verbose)
413 printf(" but there's already a %c in it!\n",
414 soln[y*w+x] == -1 ? '\\' : '/');
415 return false;
416#endif
417 }
418
419 if (v < 0) {
420 ci1 = y*W+x;
421 ci2 = (y+1)*W+(x+1);
422 di1 = y*W+(x+1);
423 di2 = (y+1)*W+x;
424 } else {
425 ci1 = y*W+(x+1);
426 ci2 = (y+1)*W+x;
427 di1 = y*W+x;
428 di2 = (y+1)*W+(x+1);
429 }
430
431 if (dsf_equivalent(connected, ci1, ci2)) {
432#ifdef SOLVER_DIAGNOSTICS
433 if (verbose)
434 printf(" but it would make a loop!\n");
435 return false;
436#endif
437 }
438
439 soln[y*w+x] = v;
440
441 if (sc) {
442 int c = dsf_canonify(sc->equiv, y*w+x);
443 sc->slashval[c] = v;
444 }
445
446 merge_vertices(connected, sc, ci1, ci2);
447 if (sc) {
448 decr_exits(sc, di1);
449 decr_exits(sc, di2);
450 }
451 return true;
452}
453
454static bool vbitmap_clear(int w, int h, struct solver_scratch *sc,
455 int x, int y, int vbits, const char *reason, ...)
456{
457 bool done_something = false;
458 int vbit;
459
460 for (vbit = 1; vbit <= 8; vbit <<= 1)
461 if (vbits & sc->vbitmap[y*w+x] & vbit) {
462 done_something = true;
463#ifdef SOLVER_DIAGNOSTICS
464 if (verbose) {
465 va_list ap;
466
467 printf("ruling out %c shape at (%d,%d)-(%d,%d) (",
468 "!v^!>!!!<"[vbit], x, y,
469 x+((vbit&0x3)!=0), y+((vbit&0xC)!=0));
470
471 va_start(ap, reason);
472 vprintf(reason, ap);
473 va_end(ap);
474
475 printf(")\n");
476 }
477#endif
478 sc->vbitmap[y*w+x] &= ~vbit;
479 }
480
481 return done_something;
482}
483
484/*
485 * Solver. Returns 0 for impossibility, 1 for success, 2 for
486 * ambiguity or failure to converge.
487 */
488static int slant_solve(int w, int h, const signed char *clues,
489 signed char *soln, struct solver_scratch *sc,
490 int difficulty)
491{
492 int W = w+1, H = h+1;
493 int x, y, i, j;
494 bool done_something;
495
496 /*
497 * Clear the output.
498 */
499 memset(soln, 0, w*h);
500
501 sc->clues = clues;
502
503 /*
504 * Establish a disjoint set forest for tracking connectedness
505 * between grid points.
506 */
507 dsf_reinit(sc->connected);
508
509 /*
510 * Establish a disjoint set forest for tracking which squares
511 * are known to slant in the same direction.
512 */
513 dsf_reinit(sc->equiv);
514
515 /*
516 * Clear the slashval array.
517 */
518 memset(sc->slashval, 0, w*h);
519
520 /*
521 * Set up the vbitmap array. Initially all types of v are possible.
522 */
523 memset(sc->vbitmap, 0xF, w*h);
524
525 /*
526 * Initialise the `exits' and `border' arrays. These are used
527 * to do second-order loop avoidance: the dual of the no loops
528 * constraint is that every point must be somehow connected to
529 * the border of the grid (otherwise there would be a solid
530 * loop around it which prevented this).
531 *
532 * I define a `dead end' to be a connected group of points
533 * which contains no border point, and which can form at most
534 * one new connection outside itself. Then I forbid placing an
535 * edge so that it connects together two dead-end groups, since
536 * this would yield a non-border-connected isolated subgraph
537 * with no further scope to extend it.
538 */
539 for (y = 0; y < H; y++)
540 for (x = 0; x < W; x++) {
541 if (y == 0 || y == H-1 || x == 0 || x == W-1)
542 sc->border[y*W+x] = true;
543 else
544 sc->border[y*W+x] = false;
545
546 if (clues[y*W+x] < 0)
547 sc->exits[y*W+x] = 4;
548 else
549 sc->exits[y*W+x] = clues[y*W+x];
550 }
551
552 /*
553 * Repeatedly try to deduce something until we can't.
554 */
555 do {
556 done_something = false;
557
558 /*
559 * Any clue point with the number of remaining lines equal
560 * to zero or to the number of remaining undecided
561 * neighbouring squares can be filled in completely.
562 */
563 for (y = 0; y < H; y++)
564 for (x = 0; x < W; x++) {
565 struct {
566 int pos, slash;
567 } neighbours[4];
568 int nneighbours;
569 int nu, nl, c, s, eq, eq2, last, meq, mj1, mj2;
570
571 if ((c = clues[y*W+x]) < 0)
572 continue;
573
574 /*
575 * We have a clue point. Start by listing its
576 * neighbouring squares, in order around the point,
577 * together with the type of slash that would be
578 * required in that square to connect to the point.
579 */
580 nneighbours = 0;
581 if (x > 0 && y > 0) {
582 neighbours[nneighbours].pos = (y-1)*w+(x-1);
583 neighbours[nneighbours].slash = -1;
584 nneighbours++;
585 }
586 if (x > 0 && y < h) {
587 neighbours[nneighbours].pos = y*w+(x-1);
588 neighbours[nneighbours].slash = +1;
589 nneighbours++;
590 }
591 if (x < w && y < h) {
592 neighbours[nneighbours].pos = y*w+x;
593 neighbours[nneighbours].slash = -1;
594 nneighbours++;
595 }
596 if (x < w && y > 0) {
597 neighbours[nneighbours].pos = (y-1)*w+x;
598 neighbours[nneighbours].slash = +1;
599 nneighbours++;
600 }
601
602 /*
603 * Count up the number of undecided neighbours, and
604 * also the number of lines already present.
605 *
606 * If we're not on DIFF_EASY, then in this loop we
607 * also track whether we've seen two adjacent empty
608 * squares belonging to the same equivalence class
609 * (meaning they have the same type of slash). If
610 * so, we count them jointly as one line.
611 */
612 nu = 0;
613 nl = c;
614 last = neighbours[nneighbours-1].pos;
615 if (soln[last] == 0)
616 eq = dsf_canonify(sc->equiv, last);
617 else
618 eq = -1;
619 meq = mj1 = mj2 = -1;
620 for (i = 0; i < nneighbours; i++) {
621 j = neighbours[i].pos;
622 s = neighbours[i].slash;
623 if (soln[j] == 0) {
624 nu++; /* undecided */
625 if (meq < 0 && difficulty > DIFF_EASY) {
626 eq2 = dsf_canonify(sc->equiv, j);
627 if (eq == eq2 && last != j) {
628 /*
629 * We've found an equivalent pair.
630 * Mark it. This also inhibits any
631 * further equivalence tracking
632 * around this square, since we can
633 * only handle one pair (and in
634 * particular we want to avoid
635 * being misled by two overlapping
636 * equivalence pairs).
637 */
638 meq = eq;
639 mj1 = last;
640 mj2 = j;
641 nl--; /* count one line */
642 nu -= 2; /* and lose two undecideds */
643 } else
644 eq = eq2;
645 }
646 } else {
647 eq = -1;
648 if (soln[j] == s)
649 nl--; /* here's a line */
650 }
651 last = j;
652 }
653
654 /*
655 * Check the counts.
656 */
657 if (nl < 0 || nl > nu) {
658 /*
659 * No consistent value for this at all!
660 */
661#ifdef SOLVER_DIAGNOSTICS
662 if (verbose)
663 printf("need %d / %d lines around clue point at %d,%d!\n",
664 nl, nu, x, y);
665#endif
666 return 0; /* impossible */
667 }
668
669 if (nu > 0 && (nl == 0 || nl == nu)) {
670#ifdef SOLVER_DIAGNOSTICS
671 if (verbose) {
672 if (meq >= 0)
673 printf("partially (since %d,%d == %d,%d) ",
674 mj1%w, mj1/w, mj2%w, mj2/w);
675 printf("%s around clue point at %d,%d\n",
676 nl ? "filling" : "emptying", x, y);
677 }
678#endif
679 for (i = 0; i < nneighbours; i++) {
680 j = neighbours[i].pos;
681 s = neighbours[i].slash;
682 if (soln[j] == 0 && j != mj1 && j != mj2) {
683 if (!fill_square(w, h, j%w, j/w, (nl ? s : -s),
684 soln, sc->connected, sc))
685 return 0; /* impossible */
686 }
687 }
688
689 done_something = true;
690 } else if (nu == 2 && nl == 1 && difficulty > DIFF_EASY) {
691 /*
692 * If we have precisely two undecided squares
693 * and precisely one line to place between
694 * them, _and_ those squares are adjacent, then
695 * we can mark them as equivalent to one
696 * another.
697 *
698 * This even applies if meq >= 0: if we have a
699 * 2 clue point and two of its neighbours are
700 * already marked equivalent, we can indeed
701 * mark the other two as equivalent.
702 *
703 * We don't bother with this on DIFF_EASY,
704 * since we wouldn't have used the results
705 * anyway.
706 */
707 last = -1;
708 for (i = 0; i < nneighbours; i++) {
709 j = neighbours[i].pos;
710 if (soln[j] == 0 && j != mj1 && j != mj2) {
711 if (last < 0)
712 last = i;
713 else if (last == i-1 || (last == 0 && i == 3))
714 break; /* found a pair */
715 }
716 }
717 if (i < nneighbours) {
718 int sv1, sv2;
719
720 assert(last >= 0);
721 /*
722 * neighbours[last] and neighbours[i] are
723 * the pair. Mark them equivalent.
724 */
725#ifdef SOLVER_DIAGNOSTICS
726 if (verbose) {
727 if (meq >= 0)
728 printf("since %d,%d == %d,%d, ",
729 mj1%w, mj1/w, mj2%w, mj2/w);
730 }
731#endif
732 mj1 = neighbours[last].pos;
733 mj2 = neighbours[i].pos;
734#ifdef SOLVER_DIAGNOSTICS
735 if (verbose)
736 printf("clue point at %d,%d implies %d,%d == %d,"
737 "%d\n", x, y, mj1%w, mj1/w, mj2%w, mj2/w);
738#endif
739 mj1 = dsf_canonify(sc->equiv, mj1);
740 sv1 = sc->slashval[mj1];
741 mj2 = dsf_canonify(sc->equiv, mj2);
742 sv2 = sc->slashval[mj2];
743 if (sv1 != 0 && sv2 != 0 && sv1 != sv2) {
744#ifdef SOLVER_DIAGNOSTICS
745 if (verbose)
746 printf("merged two equivalence classes with"
747 " different slash values!\n");
748#endif
749 return 0;
750 }
751 sv1 = sv1 ? sv1 : sv2;
752 dsf_merge(sc->equiv, mj1, mj2);
753 mj1 = dsf_canonify(sc->equiv, mj1);
754 sc->slashval[mj1] = sv1;
755 }
756 }
757 }
758
759 if (done_something)
760 continue;
761
762 /*
763 * Failing that, we now apply the second condition, which
764 * is that no square may be filled in such a way as to form
765 * a loop. Also in this loop (since it's over squares
766 * rather than points), we check slashval to see if we've
767 * already filled in another square in the same equivalence
768 * class.
769 *
770 * The slashval check is disabled on DIFF_EASY, as is dead
771 * end avoidance. Only _immediate_ loop avoidance remains.
772 */
773 for (y = 0; y < h; y++)
774 for (x = 0; x < w; x++) {
775 bool fs, bs;
776 int v, c1, c2;
777#ifdef SOLVER_DIAGNOSTICS
778 const char *reason = "<internal error>";
779#endif
780
781 if (soln[y*w+x])
782 continue; /* got this one already */
783
784 fs = false;
785 bs = false;
786
787 if (difficulty > DIFF_EASY)
788 v = sc->slashval[dsf_canonify(sc->equiv, y*w+x)];
789 else
790 v = 0;
791
792 /*
793 * Try to rule out connectivity between (x,y) and
794 * (x+1,y+1); if successful, we will deduce that we
795 * must have a forward slash.
796 */
797 c1 = dsf_canonify(sc->connected, y*W+x);
798 c2 = dsf_canonify(sc->connected, (y+1)*W+(x+1));
799 if (c1 == c2) {
800 fs = true;
801#ifdef SOLVER_DIAGNOSTICS
802 reason = "simple loop avoidance";
803#endif
804 }
805 if (difficulty > DIFF_EASY &&
806 !sc->border[c1] && !sc->border[c2] &&
807 sc->exits[c1] <= 1 && sc->exits[c2] <= 1) {
808 fs = true;
809#ifdef SOLVER_DIAGNOSTICS
810 reason = "dead end avoidance";
811#endif
812 }
813 if (v == +1) {
814 fs = true;
815#ifdef SOLVER_DIAGNOSTICS
816 reason = "equivalence to an already filled square";
817#endif
818 }
819
820 /*
821 * Now do the same between (x+1,y) and (x,y+1), to
822 * see if we are required to have a backslash.
823 */
824 c1 = dsf_canonify(sc->connected, y*W+(x+1));
825 c2 = dsf_canonify(sc->connected, (y+1)*W+x);
826 if (c1 == c2) {
827 bs = true;
828#ifdef SOLVER_DIAGNOSTICS
829 reason = "simple loop avoidance";
830#endif
831 }
832 if (difficulty > DIFF_EASY &&
833 !sc->border[c1] && !sc->border[c2] &&
834 sc->exits[c1] <= 1 && sc->exits[c2] <= 1) {
835 bs = true;
836#ifdef SOLVER_DIAGNOSTICS
837 reason = "dead end avoidance";
838#endif
839 }
840 if (v == -1) {
841 bs = true;
842#ifdef SOLVER_DIAGNOSTICS
843 reason = "equivalence to an already filled square";
844#endif
845 }
846
847 if (fs && bs) {
848 /*
849 * No consistent value for this at all!
850 */
851#ifdef SOLVER_DIAGNOSTICS
852 if (verbose)
853 printf("%d,%d has no consistent slash!\n", x, y);
854#endif
855 return 0; /* impossible */
856 }
857
858 if (fs) {
859#ifdef SOLVER_DIAGNOSTICS
860 if (verbose)
861 printf("employing %s\n", reason);
862#endif
863 if (!fill_square(w, h, x, y, +1, soln, sc->connected, sc))
864 return 0; /* impossible */
865 done_something = true;
866 } else if (bs) {
867#ifdef SOLVER_DIAGNOSTICS
868 if (verbose)
869 printf("employing %s\n", reason);
870#endif
871 if (!fill_square(w, h, x, y, -1, soln, sc->connected, sc))
872 return 0; /* impossible */
873 done_something = true;
874 }
875 }
876
877 if (done_something)
878 continue;
879
880 /*
881 * Now see what we can do with the vbitmap array. All
882 * vbitmap deductions are disabled at Easy level.
883 */
884 if (difficulty <= DIFF_EASY)
885 continue;
886
887 for (y = 0; y < h; y++)
888 for (x = 0; x < w; x++) {
889 int s, c;
890
891 /*
892 * Any line already placed in a square must rule
893 * out any type of v which contradicts it.
894 */
895 if ((s = soln[y*w+x]) != 0) {
896 if (x > 0)
897 done_something |=
898 vbitmap_clear(w, h, sc, x-1, y, (s < 0 ? 0x1 : 0x2),
899 "contradicts known edge at (%d,%d)",x,y);
900 if (x+1 < w)
901 done_something |=
902 vbitmap_clear(w, h, sc, x, y, (s < 0 ? 0x2 : 0x1),
903 "contradicts known edge at (%d,%d)",x,y);
904 if (y > 0)
905 done_something |=
906 vbitmap_clear(w, h, sc, x, y-1, (s < 0 ? 0x4 : 0x8),
907 "contradicts known edge at (%d,%d)",x,y);
908 if (y+1 < h)
909 done_something |=
910 vbitmap_clear(w, h, sc, x, y, (s < 0 ? 0x8 : 0x4),
911 "contradicts known edge at (%d,%d)",x,y);
912 }
913
914 /*
915 * If both types of v are ruled out for a pair of
916 * adjacent squares, mark them as equivalent.
917 */
918 if (x+1 < w && !(sc->vbitmap[y*w+x] & 0x3)) {
919 int n1 = y*w+x, n2 = y*w+(x+1);
920 if (dsf_canonify(sc->equiv, n1) !=
921 dsf_canonify(sc->equiv, n2)) {
922 dsf_merge(sc->equiv, n1, n2);
923 done_something = true;
924#ifdef SOLVER_DIAGNOSTICS
925 if (verbose)
926 printf("(%d,%d) and (%d,%d) must be equivalent"
927 " because both v-shapes are ruled out\n",
928 x, y, x+1, y);
929#endif
930 }
931 }
932 if (y+1 < h && !(sc->vbitmap[y*w+x] & 0xC)) {
933 int n1 = y*w+x, n2 = (y+1)*w+x;
934 if (dsf_canonify(sc->equiv, n1) !=
935 dsf_canonify(sc->equiv, n2)) {
936 dsf_merge(sc->equiv, n1, n2);
937 done_something = true;
938#ifdef SOLVER_DIAGNOSTICS
939 if (verbose)
940 printf("(%d,%d) and (%d,%d) must be equivalent"
941 " because both v-shapes are ruled out\n",
942 x, y, x, y+1);
943#endif
944 }
945 }
946
947 /*
948 * The remaining work in this loop only works
949 * around non-edge clue points.
950 */
951 if (y == 0 || x == 0)
952 continue;
953 if ((c = clues[y*W+x]) < 0)
954 continue;
955
956 /*
957 * x,y marks a clue point not on the grid edge. See
958 * if this clue point allows us to rule out any v
959 * shapes.
960 */
961
962 if (c == 1) {
963 /*
964 * A 1 clue can never have any v shape pointing
965 * at it.
966 */
967 done_something |=
968 vbitmap_clear(w, h, sc, x-1, y-1, 0x5,
969 "points at 1 clue at (%d,%d)", x, y);
970 done_something |=
971 vbitmap_clear(w, h, sc, x-1, y, 0x2,
972 "points at 1 clue at (%d,%d)", x, y);
973 done_something |=
974 vbitmap_clear(w, h, sc, x, y-1, 0x8,
975 "points at 1 clue at (%d,%d)", x, y);
976 } else if (c == 3) {
977 /*
978 * A 3 clue can never have any v shape pointing
979 * away from it.
980 */
981 done_something |=
982 vbitmap_clear(w, h, sc, x-1, y-1, 0xA,
983 "points away from 3 clue at (%d,%d)", x, y);
984 done_something |=
985 vbitmap_clear(w, h, sc, x-1, y, 0x1,
986 "points away from 3 clue at (%d,%d)", x, y);
987 done_something |=
988 vbitmap_clear(w, h, sc, x, y-1, 0x4,
989 "points away from 3 clue at (%d,%d)", x, y);
990 } else if (c == 2) {
991 /*
992 * If a 2 clue has any kind of v ruled out on
993 * one side of it, the same v is ruled out on
994 * the other side.
995 */
996 done_something |=
997 vbitmap_clear(w, h, sc, x-1, y-1,
998 (sc->vbitmap[(y )*w+(x-1)] & 0x3) ^ 0x3,
999 "propagated by 2 clue at (%d,%d)", x, y);
1000 done_something |=
1001 vbitmap_clear(w, h, sc, x-1, y-1,
1002 (sc->vbitmap[(y-1)*w+(x )] & 0xC) ^ 0xC,
1003 "propagated by 2 clue at (%d,%d)", x, y);
1004 done_something |=
1005 vbitmap_clear(w, h, sc, x-1, y,
1006 (sc->vbitmap[(y-1)*w+(x-1)] & 0x3) ^ 0x3,
1007 "propagated by 2 clue at (%d,%d)", x, y);
1008 done_something |=
1009 vbitmap_clear(w, h, sc, x, y-1,
1010 (sc->vbitmap[(y-1)*w+(x-1)] & 0xC) ^ 0xC,
1011 "propagated by 2 clue at (%d,%d)", x, y);
1012 }
1013
1014#undef CLEARBITS
1015
1016 }
1017
1018 } while (done_something);
1019
1020 /*
1021 * Solver can make no more progress. See if the grid is full.
1022 */
1023 for (i = 0; i < w*h; i++)
1024 if (!soln[i])
1025 return 2; /* failed to converge */
1026 return 1; /* success */
1027}
1028
1029/*
1030 * Filled-grid generator.
1031 */
1032static void slant_generate(int w, int h, signed char *soln, random_state *rs)
1033{
1034 int W = w+1, H = h+1;
1035 int x, y, i;
1036 DSF *connected;
1037 int *indices;
1038
1039 /*
1040 * Clear the output.
1041 */
1042 memset(soln, 0, w*h);
1043
1044 /*
1045 * Establish a disjoint set forest for tracking connectedness
1046 * between grid points.
1047 */
1048 connected = dsf_new(W*H);
1049
1050 /*
1051 * Prepare a list of the squares in the grid, and fill them in
1052 * in a random order.
1053 */
1054 indices = snewn(w*h, int);
1055 for (i = 0; i < w*h; i++)
1056 indices[i] = i;
1057 shuffle(indices, w*h, sizeof(*indices), rs);
1058
1059 /*
1060 * Fill in each one in turn.
1061 */
1062 for (i = 0; i < w*h; i++) {
1063 bool fs, bs, ok;
1064 int v;
1065
1066 y = indices[i] / w;
1067 x = indices[i] % w;
1068
1069 fs = (dsf_canonify(connected, y*W+x) ==
1070 dsf_canonify(connected, (y+1)*W+(x+1)));
1071 bs = (dsf_canonify(connected, (y+1)*W+x) ==
1072 dsf_canonify(connected, y*W+(x+1)));
1073
1074 /*
1075 * It isn't possible to get into a situation where we
1076 * aren't allowed to place _either_ type of slash in a
1077 * square. Thus, filled-grid generation never has to
1078 * backtrack.
1079 *
1080 * Proof (thanks to Gareth Taylor):
1081 *
1082 * If it were possible, it would have to be because there
1083 * was an existing path (not using this square) between the
1084 * top-left and bottom-right corners of this square, and
1085 * another between the other two. These two paths would
1086 * have to cross at some point.
1087 *
1088 * Obviously they can't cross in the middle of a square, so
1089 * they must cross by sharing a point in common. But this
1090 * isn't possible either: if you chessboard-colour all the
1091 * points on the grid, you find that any continuous
1092 * diagonal path is entirely composed of points of the same
1093 * colour. And one of our two hypothetical paths is between
1094 * two black points, and the other is between two white
1095 * points - therefore they can have no point in common. []
1096 */
1097 assert(!(fs && bs));
1098
1099 v = fs ? +1 : bs ? -1 : 2 * random_upto(rs, 2) - 1;
1100 ok = fill_square(w, h, x, y, v, soln, connected, NULL);
1101 assert(ok);
1102 }
1103
1104 sfree(indices);
1105 dsf_free(connected);
1106}
1107
1108static char *new_game_desc(const game_params *params, random_state *rs,
1109 char **aux, bool interactive)
1110{
1111 int w = params->w, h = params->h, W = w+1, H = h+1;
1112 signed char *soln, *tmpsoln, *clues;
1113 int *clueindices;
1114 struct solver_scratch *sc;
1115 int x, y, v, i, j;
1116 char *desc;
1117
1118 soln = snewn(w*h, signed char);
1119 tmpsoln = snewn(w*h, signed char);
1120 clues = snewn(W*H, signed char);
1121 clueindices = snewn(W*H, int);
1122 sc = new_scratch(w, h);
1123
1124 do {
1125 /*
1126 * Create the filled grid.
1127 */
1128 slant_generate(w, h, soln, rs);
1129
1130 /*
1131 * Fill in the complete set of clues.
1132 */
1133 for (y = 0; y < H; y++)
1134 for (x = 0; x < W; x++) {
1135 v = 0;
1136
1137 if (x > 0 && y > 0 && soln[(y-1)*w+(x-1)] == -1) v++;
1138 if (x > 0 && y < h && soln[y*w+(x-1)] == +1) v++;
1139 if (x < w && y > 0 && soln[(y-1)*w+x] == +1) v++;
1140 if (x < w && y < h && soln[y*w+x] == -1) v++;
1141
1142 clues[y*W+x] = v;
1143 }
1144
1145 /*
1146 * With all clue points filled in, all puzzles are easy: we can
1147 * simply process the clue points in lexicographic order, and
1148 * at each clue point we will always have at most one square
1149 * undecided, which we can then fill in uniquely.
1150 */
1151 assert(slant_solve(w, h, clues, tmpsoln, sc, DIFF_EASY) == 1);
1152
1153 /*
1154 * Remove as many clues as possible while retaining solubility.
1155 *
1156 * In DIFF_HARD mode, we prioritise the removal of obvious
1157 * starting points (4s, 0s, border 2s and corner 1s), on
1158 * the grounds that having as few of these as possible
1159 * seems like a good thing. In particular, we can often get
1160 * away without _any_ completely obvious starting points,
1161 * which is even better.
1162 */
1163 for (i = 0; i < W*H; i++)
1164 clueindices[i] = i;
1165 shuffle(clueindices, W*H, sizeof(*clueindices), rs);
1166 for (j = 0; j < 2; j++) {
1167 for (i = 0; i < W*H; i++) {
1168 int pass;
1169 bool yb, xb;
1170
1171 y = clueindices[i] / W;
1172 x = clueindices[i] % W;
1173 v = clues[y*W+x];
1174
1175 /*
1176 * Identify which pass we should process this point
1177 * in. If it's an obvious start point, _or_ we're
1178 * in DIFF_EASY, then it goes in pass 0; otherwise
1179 * pass 1.
1180 */
1181 xb = (x == 0 || x == W-1);
1182 yb = (y == 0 || y == H-1);
1183 if (params->diff == DIFF_EASY || v == 4 || v == 0 ||
1184 (v == 2 && (xb||yb)) || (v == 1 && xb && yb))
1185 pass = 0;
1186 else
1187 pass = 1;
1188
1189 if (pass == j) {
1190 clues[y*W+x] = -1;
1191 if (slant_solve(w, h, clues, tmpsoln, sc,
1192 params->diff) != 1)
1193 clues[y*W+x] = v; /* put it back */
1194 }
1195 }
1196 }
1197
1198 /*
1199 * And finally, verify that the grid is of _at least_ the
1200 * requested difficulty, by running the solver one level
1201 * down and verifying that it can't manage it.
1202 */
1203 } while (params->diff > 0 &&
1204 slant_solve(w, h, clues, tmpsoln, sc, params->diff - 1) <= 1);
1205
1206 /*
1207 * Now we have the clue set as it will be presented to the
1208 * user. Encode it in a game desc.
1209 */
1210 {
1211 char *p;
1212 int run, i;
1213
1214 desc = snewn(W*H+1, char);
1215 p = desc;
1216 run = 0;
1217 for (i = 0; i <= W*H; i++) {
1218 int n = (i < W*H ? clues[i] : -2);
1219
1220 if (n == -1)
1221 run++;
1222 else {
1223 if (run) {
1224 while (run > 0) {
1225 int c = 'a' - 1 + run;
1226 if (run > 26)
1227 c = 'z';
1228 *p++ = c;
1229 run -= c - ('a' - 1);
1230 }
1231 }
1232 if (n >= 0)
1233 *p++ = '0' + n;
1234 run = 0;
1235 }
1236 }
1237 assert(p - desc <= W*H);
1238 *p++ = '\0';
1239 desc = sresize(desc, p - desc, char);
1240 }
1241
1242 /*
1243 * Encode the solution as an aux_info.
1244 */
1245 {
1246 char *auxbuf;
1247 *aux = auxbuf = snewn(w*h+1, char);
1248 for (i = 0; i < w*h; i++)
1249 auxbuf[i] = soln[i] < 0 ? '\\' : '/';
1250 auxbuf[w*h] = '\0';
1251 }
1252
1253 free_scratch(sc);
1254 sfree(clueindices);
1255 sfree(clues);
1256 sfree(tmpsoln);
1257 sfree(soln);
1258
1259 return desc;
1260}
1261
1262static const char *validate_desc(const game_params *params, const char *desc)
1263{
1264 int w = params->w, h = params->h, W = w+1, H = h+1;
1265 int area = W*H;
1266 int squares = 0;
1267
1268 while (*desc) {
1269 int n = *desc++;
1270 if (n >= 'a' && n <= 'z') {
1271 squares += n - 'a' + 1;
1272 } else if (n >= '0' && n <= '4') {
1273 squares++;
1274 } else
1275 return "Invalid character in game description";
1276 }
1277
1278 if (squares < area)
1279 return "Not enough data to fill grid";
1280
1281 if (squares > area)
1282 return "Too much data to fit in grid";
1283
1284 return NULL;
1285}
1286
1287static game_state *new_game(midend *me, const game_params *params,
1288 const char *desc)
1289{
1290 int w = params->w, h = params->h, W = w+1, H = h+1;
1291 game_state *state = snew(game_state);
1292 int area = W*H;
1293 int squares = 0;
1294
1295 state->p = *params;
1296 state->soln = snewn(w*h, signed char);
1297 memset(state->soln, 0, w*h);
1298 state->completed = state->used_solve = false;
1299 state->errors = snewn(W*H, unsigned char);
1300 memset(state->errors, 0, W*H);
1301
1302 state->clues = snew(game_clues);
1303 state->clues->w = w;
1304 state->clues->h = h;
1305 state->clues->clues = snewn(W*H, signed char);
1306 state->clues->refcount = 1;
1307 state->clues->tmpdsf = snewn(W*H*2+W+H, int);
1308 memset(state->clues->clues, -1, W*H);
1309 while (*desc) {
1310 int n = *desc++;
1311 if (n >= 'a' && n <= 'z') {
1312 squares += n - 'a' + 1;
1313 } else if (n >= '0' && n <= '4') {
1314 state->clues->clues[squares++] = n - '0';
1315 } else
1316 assert(!"can't get here");
1317 }
1318 assert(squares == area);
1319
1320 return state;
1321}
1322
1323static game_state *dup_game(const game_state *state)
1324{
1325 int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
1326 game_state *ret = snew(game_state);
1327
1328 ret->p = state->p;
1329 ret->clues = state->clues;
1330 ret->clues->refcount++;
1331 ret->completed = state->completed;
1332 ret->used_solve = state->used_solve;
1333
1334 ret->soln = snewn(w*h, signed char);
1335 memcpy(ret->soln, state->soln, w*h);
1336
1337 ret->errors = snewn(W*H, unsigned char);
1338 memcpy(ret->errors, state->errors, W*H);
1339
1340 return ret;
1341}
1342
1343static void free_game(game_state *state)
1344{
1345 sfree(state->errors);
1346 sfree(state->soln);
1347 assert(state->clues);
1348 if (--state->clues->refcount <= 0) {
1349 sfree(state->clues->clues);
1350 sfree(state->clues->tmpdsf);
1351 sfree(state->clues);
1352 }
1353 sfree(state);
1354}
1355
1356/*
1357 * Utility function to return the current degree of a vertex. If
1358 * `anti' is set, it returns the number of filled-in edges
1359 * surrounding the point which _don't_ connect to it; thus 4 minus
1360 * its anti-degree is the maximum degree it could have if all the
1361 * empty spaces around it were filled in.
1362 *
1363 * (Yes, _4_ minus its anti-degree even if it's a border vertex.)
1364 *
1365 * If ret > 0, *sx and *sy are set to the coordinates of one of the
1366 * squares that contributed to it.
1367 */
1368static int vertex_degree(int w, int h, signed char *soln, int x, int y,
1369 bool anti, int *sx, int *sy)
1370{
1371 int ret = 0;
1372
1373 assert(x >= 0 && x <= w && y >= 0 && y <= h);
1374 if (x > 0 && y > 0 && soln[(y-1)*w+(x-1)] - anti < 0) {
1375 if (sx) *sx = x-1;
1376 if (sy) *sy = y-1;
1377 ret++;
1378 }
1379 if (x > 0 && y < h && soln[y*w+(x-1)] + anti > 0) {
1380 if (sx) *sx = x-1;
1381 if (sy) *sy = y;
1382 ret++;
1383 }
1384 if (x < w && y > 0 && soln[(y-1)*w+x] + anti > 0) {
1385 if (sx) *sx = x;
1386 if (sy) *sy = y-1;
1387 ret++;
1388 }
1389 if (x < w && y < h && soln[y*w+x] - anti < 0) {
1390 if (sx) *sx = x;
1391 if (sy) *sy = y;
1392 ret++;
1393 }
1394
1395 return anti ? 4 - ret : ret;
1396}
1397
1398struct slant_neighbour_ctx {
1399 const game_state *state;
1400 int i, n, neighbours[4];
1401};
1402static int slant_neighbour(int vertex, void *vctx)
1403{
1404 struct slant_neighbour_ctx *ctx = (struct slant_neighbour_ctx *)vctx;
1405
1406 if (vertex >= 0) {
1407 int w = ctx->state->p.w, h = ctx->state->p.h, W = w+1;
1408 int x = vertex % W, y = vertex / W;
1409 ctx->n = ctx->i = 0;
1410 if (x < w && y < h && ctx->state->soln[y*w+x] < 0)
1411 ctx->neighbours[ctx->n++] = (y+1)*W+(x+1);
1412 if (x > 0 && y > 0 && ctx->state->soln[(y-1)*w+(x-1)] < 0)
1413 ctx->neighbours[ctx->n++] = (y-1)*W+(x-1);
1414 if (x > 0 && y < h && ctx->state->soln[y*w+(x-1)] > 0)
1415 ctx->neighbours[ctx->n++] = (y+1)*W+(x-1);
1416 if (x < w && y > 0 && ctx->state->soln[(y-1)*w+x] > 0)
1417 ctx->neighbours[ctx->n++] = (y-1)*W+(x+1);
1418 }
1419
1420 if (ctx->i < ctx->n)
1421 return ctx->neighbours[ctx->i++];
1422 else
1423 return -1;
1424}
1425
1426static bool check_completion(game_state *state)
1427{
1428 int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
1429 int x, y;
1430 bool err = false;
1431
1432 memset(state->errors, 0, W*H);
1433
1434 /*
1435 * Detect and grounded-highlight edge-connected components in the grid.
1436 */
1437 {
1438 DSF *connected = dsf_new(W*H);
1439 unsigned root_NW;
1440 int slash;
1441 int x, y;
1442
1443 for (x = 0; x <= w; x++) {
1444 dsf_merge(connected, x, 0);
1445 dsf_merge(connected, h*W+x, 0);
1446 }
1447 for (y = 0; y <= h; y++) {
1448 dsf_merge(connected, y*W, 0);
1449 dsf_merge(connected, y*W+w, 0);
1450 }
1451
1452 for (y = 0; y < h; y++) {
1453 for (x = 0; x < w; x++) {
1454 switch (state->soln[y*w+x]) {
1455 case -1:
1456 dsf_merge(connected, y*W+x, (y+1)*W+(x+1));
1457 break;
1458 case +1:
1459 dsf_merge(connected, y*W+(x+1), (y+1)*W+x);
1460 break;
1461 default:
1462 continue;
1463 }
1464 }
1465 }
1466
1467 root_NW = dsf_canonify(connected, 0);
1468 for (y = 0; y < h; y++)
1469 for (x = 0; x < w; x++)
1470 if ((slash = state->soln[y*w+x]) && dsf_canonify(
1471 connected, y*W + x + (slash == 1 ? 1 : 0)) == root_NW)
1472 state->errors[y*w+x] |= BORDER_EDGE;
1473 dsf_free(connected);
1474 }
1475
1476 /*
1477 * Detect and error-highlight loops in the grid.
1478 */
1479 {
1480 struct findloopstate *fls = findloop_new_state(W*H);
1481 struct slant_neighbour_ctx ctx;
1482 ctx.state = state;
1483
1484 if (findloop_run(fls, W*H, slant_neighbour, &ctx))
1485 err = true;
1486 for (y = 0; y < h; y++) {
1487 for (x = 0; x < w; x++) {
1488 int u, v;
1489 if (state->soln[y*w+x] == 0) {
1490 continue;
1491 } else if (state->soln[y*w+x] > 0) {
1492 u = y*W+(x+1);
1493 v = (y+1)*W+x;
1494 } else {
1495 u = (y+1)*W+(x+1);
1496 v = y*W+x;
1497 }
1498 if (findloop_is_loop_edge(fls, u, v))
1499 state->errors[y*W+x] |= ERR_SQUARE;
1500 }
1501 }
1502
1503 findloop_free_state(fls);
1504 }
1505
1506 /*
1507 * Now go through and check the degree of each clue vertex, and
1508 * mark it with ERR_VERTEX if it cannot be fulfilled.
1509 */
1510 for (y = 0; y < H; y++)
1511 for (x = 0; x < W; x++) {
1512 int c;
1513
1514 if ((c = state->clues->clues[y*W+x]) < 0)
1515 continue;
1516
1517 /*
1518 * Check to see if there are too many connections to
1519 * this vertex _or_ too many non-connections. Either is
1520 * grounds for marking the vertex as erroneous.
1521 */
1522 if (vertex_degree(w, h, state->soln, x, y,
1523 false, NULL, NULL) > c ||
1524 vertex_degree(w, h, state->soln, x, y,
1525 true, NULL, NULL) > 4-c) {
1526 state->errors[y*W+x] |= ERR_VERTEX;
1527 err = true;
1528 }
1529 }
1530
1531 /*
1532 * Now our actual victory condition is that (a) none of the
1533 * above code marked anything as erroneous, and (b) every
1534 * square has an edge in it.
1535 */
1536
1537 if (err)
1538 return false;
1539
1540 for (y = 0; y < h; y++)
1541 for (x = 0; x < w; x++)
1542 if (state->soln[y*w+x] == 0)
1543 return false;
1544
1545 return true;
1546}
1547
1548static char *solve_game(const game_state *state, const game_state *currstate,
1549 const char *aux, const char **error)
1550{
1551 int w = state->p.w, h = state->p.h;
1552 signed char *soln;
1553 int bs, ret;
1554 bool free_soln = false;
1555 char *move, buf[80];
1556 int movelen, movesize;
1557 int x, y;
1558
1559 if (aux) {
1560 /*
1561 * If we already have the solution, save ourselves some
1562 * time.
1563 */
1564 soln = (signed char *)aux;
1565 bs = (signed char)'\\';
1566 free_soln = false;
1567 } else {
1568 struct solver_scratch *sc = new_scratch(w, h);
1569 soln = snewn(w*h, signed char);
1570 bs = -1;
1571 ret = slant_solve(w, h, state->clues->clues, soln, sc, DIFF_HARD);
1572 free_scratch(sc);
1573 if (ret != 1) {
1574 sfree(soln);
1575 if (ret == 0)
1576 *error = "This puzzle is not self-consistent";
1577 else
1578 *error = "Unable to find a unique solution for this puzzle";
1579 return NULL;
1580 }
1581 free_soln = true;
1582 }
1583
1584 /*
1585 * Construct a move string which turns the current state into
1586 * the solved state.
1587 */
1588 movesize = 256;
1589 move = snewn(movesize, char);
1590 movelen = 0;
1591 move[movelen++] = 'S';
1592 move[movelen] = '\0';
1593 for (y = 0; y < h; y++)
1594 for (x = 0; x < w; x++) {
1595 int v = (soln[y*w+x] == bs ? -1 : +1);
1596 if (state->soln[y*w+x] != v) {
1597 int len = sprintf(buf, ";%c%d,%d", (int)(v < 0 ? '\\' : '/'), x, y);
1598 if (movelen + len >= movesize) {
1599 movesize = movelen + len + 256;
1600 move = sresize(move, movesize, char);
1601 }
1602 strcpy(move + movelen, buf);
1603 movelen += len;
1604 }
1605 }
1606
1607 if (free_soln)
1608 sfree(soln);
1609
1610 return move;
1611}
1612
1613static bool game_can_format_as_text_now(const game_params *params)
1614{
1615 return true;
1616}
1617
1618static char *game_text_format(const game_state *state)
1619{
1620 int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
1621 int x, y, len;
1622 char *ret, *p;
1623
1624 /*
1625 * There are h+H rows of w+W columns.
1626 */
1627 len = (h+H) * (w+W+1) + 1;
1628 ret = snewn(len, char);
1629 p = ret;
1630
1631 for (y = 0; y < H; y++) {
1632 for (x = 0; x < W; x++) {
1633 if (state->clues->clues[y*W+x] >= 0)
1634 *p++ = state->clues->clues[y*W+x] + '0';
1635 else
1636 *p++ = '+';
1637 if (x < w)
1638 *p++ = '-';
1639 }
1640 *p++ = '\n';
1641 if (y < h) {
1642 for (x = 0; x < W; x++) {
1643 *p++ = '|';
1644 if (x < w) {
1645 if (state->soln[y*w+x] != 0)
1646 *p++ = (state->soln[y*w+x] < 0 ? '\\' : '/');
1647 else
1648 *p++ = ' ';
1649 }
1650 }
1651 *p++ = '\n';
1652 }
1653 }
1654 *p++ = '\0';
1655
1656 assert(p - ret == len);
1657 return ret;
1658}
1659
1660struct game_ui {
1661 int cur_x, cur_y;
1662 bool cur_visible;
1663
1664 /*
1665 * User preference option to swap the left and right mouse
1666 * buttons. There isn't a completely obvious mapping of left and
1667 * right buttons to the two directions of slash, and at least one
1668 * player turned out not to have the same intuition as me.
1669 */
1670 bool swap_buttons;
1671 bool fade_grounded;
1672};
1673
1674static void legacy_prefs_override(struct game_ui *ui_out)
1675{
1676 static bool initialised = false;
1677 static int swap_buttons = -1;
1678
1679 if (!initialised) {
1680 initialised = true;
1681 swap_buttons = getenv_bool("SLANT_SWAP_BUTTONS", -1);
1682 }
1683
1684 if (swap_buttons != -1)
1685 ui_out->swap_buttons = swap_buttons;
1686}
1687
1688static game_ui *new_ui(const game_state *state)
1689{
1690 game_ui *ui = snew(game_ui);
1691 ui->cur_x = ui->cur_y = 0;
1692 ui->cur_visible = getenv_bool("PUZZLES_SHOW_CURSOR", false);
1693
1694 ui->swap_buttons = false;
1695 ui->fade_grounded = false;
1696 legacy_prefs_override(ui);
1697
1698 return ui;
1699}
1700
1701static config_item *get_prefs(game_ui *ui)
1702{
1703 config_item *ret;
1704
1705 ret = snewn(N_PREF_ITEMS+1, config_item);
1706
1707 ret[PREF_MOUSE_BUTTON_ORDER].name = "Mouse button order";
1708 ret[PREF_MOUSE_BUTTON_ORDER].kw = "left-button";
1709 ret[PREF_MOUSE_BUTTON_ORDER].type = C_CHOICES;
1710 ret[PREF_MOUSE_BUTTON_ORDER].u.choices.choicenames =
1711 ":Left \\, right /:Left /, right \\";
1712 ret[PREF_MOUSE_BUTTON_ORDER].u.choices.choicekws = ":\\:/";
1713 ret[PREF_MOUSE_BUTTON_ORDER].u.choices.selected = ui->swap_buttons;
1714
1715 ret[PREF_FADE_GROUNDED].name = "Fade grounded components";
1716 ret[PREF_FADE_GROUNDED].kw = "fade-grounded";
1717 ret[PREF_FADE_GROUNDED].type = C_BOOLEAN;
1718 ret[PREF_FADE_GROUNDED].u.boolean.bval = ui->fade_grounded;
1719
1720 ret[N_PREF_ITEMS].name = NULL;
1721 ret[N_PREF_ITEMS].type = C_END;
1722
1723 return ret;
1724}
1725
1726static void set_prefs(game_ui *ui, const config_item *cfg)
1727{
1728 ui->swap_buttons = cfg[PREF_MOUSE_BUTTON_ORDER].u.choices.selected;
1729 ui->fade_grounded = cfg[PREF_FADE_GROUNDED].u.boolean.bval;
1730}
1731
1732static void free_ui(game_ui *ui)
1733{
1734 sfree(ui);
1735}
1736
1737static void game_changed_state(game_ui *ui, const game_state *oldstate,
1738 const game_state *newstate)
1739{
1740}
1741
1742static const char *current_key_label(const game_ui *ui,
1743 const game_state *state, int button)
1744{
1745 if (IS_CURSOR_SELECT(button) && ui->cur_visible) {
1746 switch (state->soln[ui->cur_y*state->p.w+ui->cur_x]) {
1747 case 0:
1748 return button == CURSOR_SELECT ? "\\" : "/";
1749 case -1:
1750 return button == CURSOR_SELECT ? "/" : "Blank";
1751 case +1:
1752 return button == CURSOR_SELECT ? "Blank" : "\\";
1753 }
1754 }
1755 return "";
1756}
1757
1758#define PREFERRED_TILESIZE 32
1759#define TILESIZE (ds->tilesize)
1760#define BORDER TILESIZE
1761#define CLUE_RADIUS (TILESIZE / 3)
1762#define CLUE_TEXTSIZE (TILESIZE / 2)
1763#define COORD(x) ( (x) * TILESIZE + BORDER )
1764#define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1765
1766#define FLASH_TIME 0.30F
1767
1768/*
1769 * Bit fields in the `grid' and `todraw' elements of the drawstate.
1770 */
1771#define BACKSLASH 0x00000001L
1772#define FORWSLASH 0x00000002L
1773#define L_T 0x00000004L
1774#define ERR_L_T 0x00000008L
1775#define L_B 0x00000010L
1776#define ERR_L_B 0x00000020L
1777#define T_L 0x00000040L
1778#define ERR_T_L 0x00000080L
1779#define T_R 0x00000100L
1780#define ERR_T_R 0x00000200L
1781#define C_TL 0x00000400L
1782#define ERR_C_TL 0x00000800L
1783#define FLASH 0x00001000L
1784#define ERRSLASH 0x00002000L
1785#define ERR_TL 0x00004000L
1786#define ERR_TR 0x00008000L
1787#define ERR_BL 0x00010000L
1788#define ERR_BR 0x00020000L
1789#define CURSOR 0x00040000L
1790#define GROUNDED 0x00080000L
1791
1792struct game_drawstate {
1793 int tilesize;
1794 long *grid;
1795 long *todraw;
1796};
1797
1798static char *interpret_move(const game_state *state, game_ui *ui,
1799 const game_drawstate *ds,
1800 int x, int y, int button)
1801{
1802 int w = state->p.w, h = state->p.h;
1803 int v;
1804 char buf[80];
1805 enum { CLOCKWISE, ANTICLOCKWISE, NONE } action = NONE;
1806
1807 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1808 if (ui->swap_buttons) {
1809 if (button == LEFT_BUTTON)
1810 button = RIGHT_BUTTON;
1811 else
1812 button = LEFT_BUTTON;
1813 }
1814 action = (button == LEFT_BUTTON) ? CLOCKWISE : ANTICLOCKWISE;
1815
1816 x = FROMCOORD(x);
1817 y = FROMCOORD(y);
1818 if (x < 0 || y < 0 || x >= w || y >= h)
1819 return MOVE_UNUSED;
1820 ui->cur_visible = false;
1821 } else if (IS_CURSOR_SELECT(button)) {
1822 if (!ui->cur_visible) {
1823 ui->cur_visible = true;
1824 return MOVE_UI_UPDATE;
1825 }
1826 x = ui->cur_x;
1827 y = ui->cur_y;
1828
1829 action = (button == CURSOR_SELECT2) ? ANTICLOCKWISE : CLOCKWISE;
1830 } else if (IS_CURSOR_MOVE(button)) {
1831 return move_cursor(button, &ui->cur_x, &ui->cur_y, w, h, false, &ui->cur_visible);
1832 } else if (button == '\\' || button == '\b' || button == '/') {
1833 int x = ui->cur_x, y = ui->cur_y;
1834 if (button == ("\\" "\b" "/")[state->soln[y*w + x] + 1])
1835 return MOVE_NO_EFFECT;
1836 sprintf(buf, "%c%d,%d", button == '\b' ? 'C' : button, x, y);
1837 return dupstr(buf);
1838 }
1839
1840 if (action != NONE) {
1841 if (action == CLOCKWISE) {
1842 /*
1843 * Left-clicking cycles blank -> \ -> / -> blank.
1844 */
1845 v = state->soln[y*w+x] - 1;
1846 if (v == -2)
1847 v = +1;
1848 } else {
1849 /*
1850 * Right-clicking cycles blank -> / -> \ -> blank.
1851 */
1852 v = state->soln[y*w+x] + 1;
1853 if (v == +2)
1854 v = -1;
1855 }
1856
1857 sprintf(buf, "%c%d,%d", (int)(v==-1 ? '\\' : v==+1 ? '/' : 'C'), x, y);
1858 return dupstr(buf);
1859 }
1860
1861 return MOVE_UNUSED;
1862}
1863
1864static game_state *execute_move(const game_state *state, const char *move)
1865{
1866 int w = state->p.w, h = state->p.h;
1867 char c;
1868 int x, y, n;
1869 game_state *ret = dup_game(state);
1870
1871 while (*move) {
1872 c = *move;
1873 if (c == 'S') {
1874 ret->used_solve = true;
1875 move++;
1876 } else if (c == '\\' || c == '/' || c == 'C') {
1877 move++;
1878 if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1879 x < 0 || y < 0 || x >= w || y >= h) {
1880 free_game(ret);
1881 return NULL;
1882 }
1883 ret->soln[y*w+x] = (c == '\\' ? -1 : c == '/' ? +1 : 0);
1884 move += n;
1885 } else {
1886 free_game(ret);
1887 return NULL;
1888 }
1889 if (*move == ';')
1890 move++;
1891 else if (*move) {
1892 free_game(ret);
1893 return NULL;
1894 }
1895 }
1896
1897 /*
1898 * We never clear the `completed' flag, but we must always
1899 * re-run the completion check because it also highlights
1900 * errors in the grid.
1901 */
1902 ret->completed = check_completion(ret) || ret->completed;
1903
1904 return ret;
1905}
1906
1907/* ----------------------------------------------------------------------
1908 * Drawing routines.
1909 */
1910
1911static void game_compute_size(const game_params *params, int tilesize,
1912 const game_ui *ui, int *x, int *y)
1913{
1914 /* fool the macros */
1915 struct dummy { int tilesize; } dummy, *ds = &dummy;
1916 dummy.tilesize = tilesize;
1917
1918 *x = 2 * BORDER + params->w * TILESIZE + 1;
1919 *y = 2 * BORDER + params->h * TILESIZE + 1;
1920}
1921
1922static void game_set_size(drawing *dr, game_drawstate *ds,
1923 const game_params *params, int tilesize)
1924{
1925 ds->tilesize = tilesize;
1926}
1927
1928static float *game_colours(frontend *fe, int *ncolours)
1929{
1930 float *ret = snewn(3 * NCOLOURS, float);
1931
1932 /* CURSOR colour is a background highlight. */
1933 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_CURSOR, -1);
1934
1935 ret[COL_FILLEDSQUARE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
1936 ret[COL_FILLEDSQUARE * 3 + 1] = ret[COL_BACKGROUND * 3 + 1];
1937 ret[COL_FILLEDSQUARE * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1938
1939 ret[COL_GRID * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.7F;
1940 ret[COL_GRID * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.7F;
1941 ret[COL_GRID * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.7F;
1942
1943 ret[COL_INK * 3 + 0] = 0.0F;
1944 ret[COL_INK * 3 + 1] = 0.0F;
1945 ret[COL_INK * 3 + 2] = 0.0F;
1946
1947 ret[COL_SLANT1 * 3 + 0] = 0.0F;
1948 ret[COL_SLANT1 * 3 + 1] = 0.0F;
1949 ret[COL_SLANT1 * 3 + 2] = 0.0F;
1950
1951 ret[COL_SLANT2 * 3 + 0] = 0.0F;
1952 ret[COL_SLANT2 * 3 + 1] = 0.0F;
1953 ret[COL_SLANT2 * 3 + 2] = 0.0F;
1954
1955 ret[COL_ERROR * 3 + 0] = 1.0F;
1956 ret[COL_ERROR * 3 + 1] = 0.0F;
1957 ret[COL_ERROR * 3 + 2] = 0.0F;
1958
1959 ret[COL_GROUNDED * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.8F;
1960 ret[COL_GROUNDED * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.8F;
1961 ret[COL_GROUNDED * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.8F;
1962
1963 *ncolours = NCOLOURS;
1964 return ret;
1965}
1966
1967static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1968{
1969 int w = state->p.w, h = state->p.h;
1970 int i;
1971 struct game_drawstate *ds = snew(struct game_drawstate);
1972
1973 ds->tilesize = 0;
1974 ds->grid = snewn((w+2)*(h+2), long);
1975 ds->todraw = snewn((w+2)*(h+2), long);
1976 for (i = 0; i < (w+2)*(h+2); i++)
1977 ds->grid[i] = ds->todraw[i] = -1;
1978
1979 return ds;
1980}
1981
1982static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1983{
1984 sfree(ds->todraw);
1985 sfree(ds->grid);
1986 sfree(ds);
1987}
1988
1989static void draw_clue(drawing *dr, game_drawstate *ds,
1990 int x, int y, long v, bool err, int bg, int colour)
1991{
1992 char p[2];
1993 int ccol = colour >= 0 ? colour : ((x ^ y) & 1) ? COL_SLANT1 : COL_SLANT2;
1994 int tcol = colour >= 0 ? colour : err ? COL_ERROR : COL_INK;
1995
1996 if (v < 0)
1997 return;
1998
1999 p[0] = (char)v + '0';
2000 p[1] = '\0';
2001 draw_circle(dr, COORD(x), COORD(y), CLUE_RADIUS,
2002 bg >= 0 ? bg : COL_BACKGROUND, ccol);
2003 draw_text(dr, COORD(x), COORD(y), FONT_VARIABLE,
2004 CLUE_TEXTSIZE, ALIGN_VCENTRE|ALIGN_HCENTRE, tcol, p);
2005}
2006
2007static void draw_tile(drawing *dr, game_drawstate *ds, game_clues *clues,
2008 int x, int y, long v)
2009{
2010 int w = clues->w, h = clues->h, W = w+1 /*, H = h+1 */;
2011 int chesscolour = (x ^ y) & 1;
2012 int fscol = chesscolour ? COL_SLANT2 : COL_SLANT1;
2013 int bscol = chesscolour ? COL_SLANT1 : COL_SLANT2;
2014
2015 clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
2016
2017 draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE,
2018 (v & FLASH) ? COL_GRID :
2019 (v & CURSOR) ? COL_CURSOR :
2020 (v & (BACKSLASH | FORWSLASH)) ? COL_FILLEDSQUARE :
2021 COL_BACKGROUND);
2022
2023 /*
2024 * Draw the grid lines.
2025 */
2026 if (x >= 0 && x < w && y >= 0)
2027 draw_rect(dr, COORD(x), COORD(y), TILESIZE+1, 1, COL_GRID);
2028 if (x >= 0 && x < w && y < h)
2029 draw_rect(dr, COORD(x), COORD(y+1), TILESIZE+1, 1, COL_GRID);
2030 if (y >= 0 && y < h && x >= 0)
2031 draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE+1, COL_GRID);
2032 if (y >= 0 && y < h && x < w)
2033 draw_rect(dr, COORD(x+1), COORD(y), 1, TILESIZE+1, COL_GRID);
2034 if (x == -1 && y == -1)
2035 draw_rect(dr, COORD(x+1), COORD(y+1), 1, 1, COL_GRID);
2036 if (x == -1 && y == h)
2037 draw_rect(dr, COORD(x+1), COORD(y), 1, 1, COL_GRID);
2038 if (x == w && y == -1)
2039 draw_rect(dr, COORD(x), COORD(y+1), 1, 1, COL_GRID);
2040 if (x == w && y == h)
2041 draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID);
2042
2043 /*
2044 * Draw the slash.
2045 */
2046 if (v & BACKSLASH) {
2047 int scol = ((v & ERRSLASH) ? COL_ERROR :
2048 (v & GROUNDED) ? COL_GROUNDED : bscol);
2049 draw_line(dr, COORD(x), COORD(y), COORD(x+1), COORD(y+1), scol);
2050 draw_line(dr, COORD(x)+1, COORD(y), COORD(x+1), COORD(y+1)-1,
2051 scol);
2052 draw_line(dr, COORD(x), COORD(y)+1, COORD(x+1)-1, COORD(y+1),
2053 scol);
2054 } else if (v & FORWSLASH) {
2055 int scol = ((v & ERRSLASH) ? COL_ERROR :
2056 (v & GROUNDED) ? COL_GROUNDED : fscol);
2057 draw_line(dr, COORD(x+1), COORD(y), COORD(x), COORD(y+1), scol);
2058 draw_line(dr, COORD(x+1)-1, COORD(y), COORD(x), COORD(y+1)-1,
2059 scol);
2060 draw_line(dr, COORD(x+1), COORD(y)+1, COORD(x)+1, COORD(y+1),
2061 scol);
2062 }
2063
2064 /*
2065 * Draw dots on the grid corners that appear if a slash is in a
2066 * neighbouring cell.
2067 */
2068 if (v & (L_T | BACKSLASH))
2069 draw_rect(dr, COORD(x), COORD(y)+1, 1, 1,
2070 (v & ERR_L_T ? COL_ERROR : bscol));
2071 if (v & (L_B | FORWSLASH))
2072 draw_rect(dr, COORD(x), COORD(y+1)-1, 1, 1,
2073 (v & ERR_L_B ? COL_ERROR : fscol));
2074 if (v & (T_L | BACKSLASH))
2075 draw_rect(dr, COORD(x)+1, COORD(y), 1, 1,
2076 (v & ERR_T_L ? COL_ERROR : bscol));
2077 if (v & (T_R | FORWSLASH))
2078 draw_rect(dr, COORD(x+1)-1, COORD(y), 1, 1,
2079 (v & ERR_T_R ? COL_ERROR : fscol));
2080 if (v & (C_TL | BACKSLASH))
2081 draw_rect(dr, COORD(x), COORD(y), 1, 1,
2082 (v & ERR_C_TL ? COL_ERROR : bscol));
2083
2084 /*
2085 * And finally the clues at the corners.
2086 */
2087 if (x >= 0 && y >= 0)
2088 draw_clue(dr, ds, x, y, clues->clues[y*W+x], v & ERR_TL, -1, -1);
2089 if (x < w && y >= 0)
2090 draw_clue(dr, ds, x+1, y, clues->clues[y*W+(x+1)], v & ERR_TR, -1, -1);
2091 if (x >= 0 && y < h)
2092 draw_clue(dr, ds, x, y+1, clues->clues[(y+1)*W+x], v & ERR_BL, -1, -1);
2093 if (x < w && y < h)
2094 draw_clue(dr, ds, x+1, y+1, clues->clues[(y+1)*W+(x+1)], v & ERR_BR,
2095 -1, -1);
2096
2097 unclip(dr);
2098 draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
2099}
2100
2101static void game_redraw(drawing *dr, game_drawstate *ds,
2102 const game_state *oldstate, const game_state *state,
2103 int dir, const game_ui *ui,
2104 float animtime, float flashtime)
2105{
2106 int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
2107 int x, y;
2108 bool flashing;
2109
2110 if (flashtime > 0)
2111 flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
2112 else
2113 flashing = false;
2114
2115 /*
2116 * Loop over the grid and work out where all the slashes are.
2117 * We need to do this because a slash in one square affects the
2118 * drawing of the next one along.
2119 */
2120 for (y = -1; y <= h; y++)
2121 for (x = -1; x <= w; x++) {
2122 if (x >= 0 && x < w && y >= 0 && y < h)
2123 ds->todraw[(y+1)*(w+2)+(x+1)] = flashing ? FLASH : 0;
2124 else
2125 ds->todraw[(y+1)*(w+2)+(x+1)] = 0;
2126 }
2127
2128 for (y = 0; y < h; y++) {
2129 for (x = 0; x < w; x++) {
2130 bool err = state->errors[y*W+x] & ERR_SQUARE;
2131
2132 if (state->soln[y*w+x] < 0) {
2133 ds->todraw[(y+1)*(w+2)+(x+1)] |= BACKSLASH;
2134 ds->todraw[(y+2)*(w+2)+(x+1)] |= T_R;
2135 ds->todraw[(y+1)*(w+2)+(x+2)] |= L_B;
2136 ds->todraw[(y+2)*(w+2)+(x+2)] |= C_TL;
2137 if (err) {
2138 ds->todraw[(y+1)*(w+2)+(x+1)] |= ERRSLASH |
2139 ERR_T_L | ERR_L_T | ERR_C_TL;
2140 ds->todraw[(y+2)*(w+2)+(x+1)] |= ERR_T_R;
2141 ds->todraw[(y+1)*(w+2)+(x+2)] |= ERR_L_B;
2142 ds->todraw[(y+2)*(w+2)+(x+2)] |= ERR_C_TL;
2143 }
2144 } else if (state->soln[y*w+x] > 0) {
2145 ds->todraw[(y+1)*(w+2)+(x+1)] |= FORWSLASH;
2146 ds->todraw[(y+1)*(w+2)+(x+2)] |= L_T | C_TL;
2147 ds->todraw[(y+2)*(w+2)+(x+1)] |= T_L | C_TL;
2148 if (err) {
2149 ds->todraw[(y+1)*(w+2)+(x+1)] |= ERRSLASH |
2150 ERR_L_B | ERR_T_R;
2151 ds->todraw[(y+1)*(w+2)+(x+2)] |= ERR_L_T | ERR_C_TL;
2152 ds->todraw[(y+2)*(w+2)+(x+1)] |= ERR_T_L | ERR_C_TL;
2153 }
2154 }
2155 if (ui->cur_visible && ui->cur_x == x && ui->cur_y == y)
2156 ds->todraw[(y+1)*(w+2)+(x+1)] |= CURSOR;
2157 }
2158 }
2159
2160 for (y = 0; y < H; y++)
2161 for (x = 0; x < W; x++)
2162 if (state->errors[y*W+x] & ERR_VERTEX) {
2163 ds->todraw[y*(w+2)+x] |= ERR_BR;
2164 ds->todraw[y*(w+2)+(x+1)] |= ERR_BL;
2165 ds->todraw[(y+1)*(w+2)+x] |= ERR_TR;
2166 ds->todraw[(y+1)*(w+2)+(x+1)] |= ERR_TL;
2167 }
2168 if (ui->fade_grounded)
2169 for (y = 0; y < h; y++)
2170 for (x = 0; x < w; x++)
2171 if (state->errors[y*w+x] & BORDER_EDGE)
2172 // dunno why but it works this way
2173 ds->todraw[(y+1)*(W+1)+(x+1)] |= GROUNDED;
2174
2175 /*
2176 * Now go through and draw the grid squares.
2177 */
2178 for (y = -1; y <= h; y++) {
2179 for (x = -1; x <= w; x++) {
2180 if (ds->todraw[(y+1)*(w+2)+(x+1)] != ds->grid[(y+1)*(w+2)+(x+1)]) {
2181 draw_tile(dr, ds, state->clues, x, y,
2182 ds->todraw[(y+1)*(w+2)+(x+1)]);
2183 ds->grid[(y+1)*(w+2)+(x+1)] = ds->todraw[(y+1)*(w+2)+(x+1)];
2184 }
2185 }
2186 }
2187}
2188
2189static float game_anim_length(const game_state *oldstate,
2190 const game_state *newstate, int dir, game_ui *ui)
2191{
2192 return 0.0F;
2193}
2194
2195static float game_flash_length(const game_state *oldstate,
2196 const game_state *newstate, int dir, game_ui *ui)
2197{
2198 if (!oldstate->completed && newstate->completed &&
2199 !oldstate->used_solve && !newstate->used_solve)
2200 return FLASH_TIME;
2201
2202 return 0.0F;
2203}
2204
2205static void game_get_cursor_location(const game_ui *ui,
2206 const game_drawstate *ds,
2207 const game_state *state,
2208 const game_params *params,
2209 int *x, int *y, int *w, int *h)
2210{
2211 if(ui->cur_visible) {
2212 *x = COORD(ui->cur_x);
2213 *y = COORD(ui->cur_y);
2214 *w = *h = TILESIZE;
2215 }
2216}
2217
2218static int game_status(const game_state *state)
2219{
2220 return state->completed ? +1 : 0;
2221}
2222
2223static void game_print_size(const game_params *params, const game_ui *ui,
2224 float *x, float *y)
2225{
2226 int pw, ph;
2227
2228 /*
2229 * I'll use 6mm squares by default.
2230 */
2231 game_compute_size(params, 600, ui, &pw, &ph);
2232 *x = pw / 100.0F;
2233 *y = ph / 100.0F;
2234}
2235
2236static void game_print(drawing *dr, const game_state *state, const game_ui *ui,
2237 int tilesize)
2238{
2239 int w = state->p.w, h = state->p.h, W = w+1;
2240 int ink = print_mono_colour(dr, 0);
2241 int paper = print_mono_colour(dr, 1);
2242 int x, y;
2243
2244 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2245 game_drawstate ads, *ds = &ads;
2246 game_set_size(dr, ds, NULL, tilesize);
2247
2248 /*
2249 * Border.
2250 */
2251 print_line_width(dr, TILESIZE / 16);
2252 draw_rect_outline(dr, COORD(0), COORD(0), w*TILESIZE, h*TILESIZE, ink);
2253
2254 /*
2255 * Grid.
2256 */
2257 print_line_width(dr, TILESIZE / 24);
2258 for (x = 1; x < w; x++)
2259 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), ink);
2260 for (y = 1; y < h; y++)
2261 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), ink);
2262
2263 /*
2264 * Solution.
2265 */
2266 print_line_width(dr, TILESIZE / 12);
2267 for (y = 0; y < h; y++)
2268 for (x = 0; x < w; x++)
2269 if (state->soln[y*w+x]) {
2270 int ly, ry;
2271 /*
2272 * To prevent nasty line-ending artefacts at
2273 * corners, I'll do something slightly cunning
2274 * here.
2275 */
2276 clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
2277 if (state->soln[y*w+x] < 0)
2278 ly = y-1, ry = y+2;
2279 else
2280 ry = y-1, ly = y+2;
2281 draw_line(dr, COORD(x-1), COORD(ly), COORD(x+2), COORD(ry),
2282 ink);
2283 unclip(dr);
2284 }
2285
2286 /*
2287 * Clues.
2288 */
2289 print_line_width(dr, TILESIZE / 24);
2290 for (y = 0; y <= h; y++)
2291 for (x = 0; x <= w; x++)
2292 draw_clue(dr, ds, x, y, state->clues->clues[y*W+x],
2293 false, paper, ink);
2294}
2295
2296#ifdef COMBINED
2297#define thegame slant
2298#endif
2299
2300const struct game thegame = {
2301 "Slant", "games.slant", "slant",
2302 default_params,
2303 game_fetch_preset, NULL,
2304 decode_params,
2305 encode_params,
2306 free_params,
2307 dup_params,
2308 true, game_configure, custom_params,
2309 validate_params,
2310 new_game_desc,
2311 validate_desc,
2312 new_game,
2313 dup_game,
2314 free_game,
2315 true, solve_game,
2316 true, game_can_format_as_text_now, game_text_format,
2317 get_prefs, set_prefs,
2318 new_ui,
2319 free_ui,
2320 NULL, /* encode_ui */
2321 NULL, /* decode_ui */
2322 NULL, /* game_request_keys */
2323 game_changed_state,
2324 current_key_label,
2325 interpret_move,
2326 execute_move,
2327 PREFERRED_TILESIZE, game_compute_size, game_set_size,
2328 game_colours,
2329 game_new_drawstate,
2330 game_free_drawstate,
2331 game_redraw,
2332 game_anim_length,
2333 game_flash_length,
2334 game_get_cursor_location,
2335 game_status,
2336 true, false, game_print_size, game_print,
2337 false, /* wants_statusbar */
2338 false, NULL, /* timing_state */
2339 0, /* flags */
2340};
2341
2342#ifdef STANDALONE_SOLVER
2343
2344#include <stdarg.h>
2345
2346int main(int argc, char **argv)
2347{
2348 game_params *p;
2349 game_state *s;
2350 char *id = NULL, *desc;
2351 const char *err;
2352 bool grade = false;
2353 int ret, diff;
2354 bool really_verbose = false;
2355 struct solver_scratch *sc;
2356
2357 while (--argc > 0) {
2358 char *p = *++argv;
2359 if (!strcmp(p, "-v")) {
2360 really_verbose = true;
2361 } else if (!strcmp(p, "-g")) {
2362 grade = true;
2363 } else if (*p == '-') {
2364 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2365 return 1;
2366 } else {
2367 id = p;
2368 }
2369 }
2370
2371 if (!id) {
2372 fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
2373 return 1;
2374 }
2375
2376 desc = strchr(id, ':');
2377 if (!desc) {
2378 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2379 return 1;
2380 }
2381 *desc++ = '\0';
2382
2383 p = default_params();
2384 decode_params(p, id);
2385 err = validate_desc(p, desc);
2386 if (err) {
2387 fprintf(stderr, "%s: %s\n", argv[0], err);
2388 return 1;
2389 }
2390 s = new_game(NULL, p, desc);
2391
2392 sc = new_scratch(p->w, p->h);
2393
2394 /*
2395 * When solving an Easy puzzle, we don't want to bother the
2396 * user with Hard-level deductions. For this reason, we grade
2397 * the puzzle internally before doing anything else.
2398 */
2399 ret = -1; /* placate optimiser */
2400 for (diff = 0; diff < DIFFCOUNT; diff++) {
2401 ret = slant_solve(p->w, p->h, s->clues->clues,
2402 s->soln, sc, diff);
2403 if (ret < 2)
2404 break;
2405 }
2406
2407 if (diff == DIFFCOUNT) {
2408 if (grade)
2409 printf("Difficulty rating: harder than Hard, or ambiguous\n");
2410 else
2411 printf("Unable to find a unique solution\n");
2412 } else {
2413 if (grade) {
2414 if (ret == 0)
2415 printf("Difficulty rating: impossible (no solution exists)\n");
2416 else if (ret == 1)
2417 printf("Difficulty rating: %s\n", slant_diffnames[diff]);
2418 } else {
2419 verbose = really_verbose;
2420 ret = slant_solve(p->w, p->h, s->clues->clues,
2421 s->soln, sc, diff);
2422 if (ret == 0) {
2423 printf("Puzzle is inconsistent\n");
2424 } else {
2425 char *str = game_text_format(s);
2426 fputs(str, stdout);
2427 sfree(str);
2428 }
2429 }
2430 }
2431
2432 free_params(p);
2433 free_game(s);
2434 free_scratch(sc);
2435
2436 return 0;
2437}
2438
2439#endif
2440
2441/* vim: set shiftwidth=4 tabstop=8: */