2 * slant.c: Puzzle from nikoli.co.jp involving drawing a diagonal
3 * line through each square of a grid.
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.
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.
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.
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.
45 * In standalone solver mode, `verbose' is a variable which can be
46 * set by command-line option; in debugging mode it's simply always
49 #if defined STANDALONE_SOLVER
50 #define SOLVER_DIAGNOSTICS
52 #elif defined SOLVER_DIAGNOSTICS
57 * Difficulty levels. I do some macro ickery here to ensure that my
58 * enum and the various forms of my name list always match up.
63 #define ENUM(upper,title,lower) DIFF_ ## upper,
64 #define TITLE(upper,title,lower) #title,
65 #define ENCODE(upper,title,lower) #lower
66 #define CONFIG(upper,title,lower) ":" #title
67 enum { DIFFLIST(ENUM) DIFFCOUNT };
68 static char const *const slant_diffnames[] = { DIFFLIST(TITLE) };
69 static char const slant_diffchars[] = DIFFLIST(ENCODE);
70 #define DIFFCONFIG DIFFLIST(CONFIG)
76 typedef struct game_clues {
90 unsigned char *errors;
92 int used_solve; /* used to suppress completion flash */
95 static game_params *default_params(void)
97 game_params *ret = snew(game_params);
100 ret->diff = DIFF_EASY;
105 static const struct game_params slant_presets[] = {
114 static int game_fetch_preset(int i, char **name, game_params **params)
119 if (i < 0 || i >= lenof(slant_presets))
122 ret = snew(game_params);
123 *ret = slant_presets[i];
125 sprintf(str, "%dx%d %s", ret->w, ret->h, slant_diffnames[ret->diff]);
132 static void free_params(game_params *params)
137 static game_params *dup_params(game_params *params)
139 game_params *ret = snew(game_params);
140 *ret = *params; /* structure copy */
144 static void decode_params(game_params *ret, char const *string)
146 ret->w = ret->h = atoi(string);
147 while (*string && isdigit((unsigned char)*string)) string++;
148 if (*string == 'x') {
150 ret->h = atoi(string);
151 while (*string && isdigit((unsigned char)*string)) string++;
153 if (*string == 'd') {
156 for (i = 0; i < DIFFCOUNT; i++)
157 if (*string == slant_diffchars[i])
159 if (*string) string++;
163 static char *encode_params(game_params *params, int full)
167 sprintf(data, "%dx%d", params->w, params->h);
169 sprintf(data + strlen(data), "d%c", slant_diffchars[params->diff]);
174 static config_item *game_configure(game_params *params)
179 ret = snewn(4, config_item);
181 ret[0].name = "Width";
182 ret[0].type = C_STRING;
183 sprintf(buf, "%d", params->w);
184 ret[0].sval = dupstr(buf);
187 ret[1].name = "Height";
188 ret[1].type = C_STRING;
189 sprintf(buf, "%d", params->h);
190 ret[1].sval = dupstr(buf);
193 ret[2].name = "Difficulty";
194 ret[2].type = C_CHOICES;
195 ret[2].sval = DIFFCONFIG;
196 ret[2].ival = params->diff;
206 static game_params *custom_params(config_item *cfg)
208 game_params *ret = snew(game_params);
210 ret->w = atoi(cfg[0].sval);
211 ret->h = atoi(cfg[1].sval);
212 ret->diff = cfg[2].ival;
217 static char *validate_params(game_params *params, int full)
220 * (At least at the time of writing this comment) The grid
221 * generator is actually capable of handling even zero grid
222 * dimensions without crashing. Puzzles with a zero-area grid
223 * are a bit boring, though, because they're already solved :-)
224 * And puzzles with a dimension of 1 can't be made Hard, which
225 * means the simplest thing is to forbid them altogether.
228 if (params->w < 2 || params->h < 2)
229 return "Width and height must both be at least two";
235 * Scratch space for solver.
237 struct solver_scratch {
239 * Disjoint set forest which tracks the connected sets of
245 * Counts the number of possible exits from each connected set
246 * of points. (That is, the number of possible _simultaneous_
247 * exits: an unconnected point labelled 2 has an exit count of
248 * 2 even if all four possible edges are still under
254 * Tracks whether each connected set of points includes a
257 unsigned char *border;
260 * Another disjoint set forest. This one tracks _squares_ which
261 * are known to slant in the same direction.
266 * Stores slash values which we know for an equivalence class.
267 * When we fill in a square, we set slashval[canonify(x)] to
268 * the same value as soln[x], so that we can then spot other
269 * squares equivalent to it and fill them in immediately via
270 * their known equivalence.
272 signed char *slashval;
275 * Useful to have this information automatically passed to
276 * solver subroutines. (This pointer is not dynamically
277 * allocated by new_scratch and free_scratch.)
279 const signed char *clues;
282 static struct solver_scratch *new_scratch(int w, int h)
284 int W = w+1, H = h+1;
285 struct solver_scratch *ret = snew(struct solver_scratch);
286 ret->connected = snewn(W*H, int);
287 ret->exits = snewn(W*H, int);
288 ret->border = snewn(W*H, unsigned char);
289 ret->equiv = snewn(w*h, int);
290 ret->slashval = snewn(w*h, signed char);
294 static void free_scratch(struct solver_scratch *sc)
300 sfree(sc->connected);
305 * Wrapper on dsf_merge() which updates the `exits' and `border'
308 static void merge_vertices(int *connected,
309 struct solver_scratch *sc, int i, int j)
311 int exits = -1, border = FALSE; /* initialise to placate optimiser */
314 i = dsf_canonify(connected, i);
315 j = dsf_canonify(connected, j);
318 * We have used one possible exit from each of the two
319 * classes. Thus, the viable exit count of the new class is
320 * the sum of the old exit counts minus two.
322 exits = sc->exits[i] + sc->exits[j] - 2;
324 border = sc->border[i] || sc->border[j];
327 dsf_merge(connected, i, j);
330 i = dsf_canonify(connected, i);
331 sc->exits[i] = exits;
332 sc->border[i] = border;
337 * Called when we have just blocked one way out of a particular
338 * point. If that point is a non-clue point (thus has a variable
339 * number of exits), we have therefore decreased its potential exit
340 * count, so we must decrement the exit count for the group as a
343 static void decr_exits(struct solver_scratch *sc, int i)
345 if (sc->clues[i] < 0) {
346 i = dsf_canonify(sc->connected, i);
351 static void fill_square(int w, int h, int x, int y, int v,
353 int *connected, struct solver_scratch *sc)
355 int W = w+1 /*, H = h+1 */;
357 assert(x >= 0 && x < w && y >= 0 && y < h);
359 if (soln[y*w+x] != 0) {
360 return; /* do nothing */
363 #ifdef SOLVER_DIAGNOSTICS
365 printf(" placing %c in %d,%d\n", v == -1 ? '\\' : '/', x, y);
371 int c = dsf_canonify(sc->equiv, y*w+x);
376 merge_vertices(connected, sc, y*W+x, (y+1)*W+(x+1));
378 decr_exits(sc, y*W+(x+1));
379 decr_exits(sc, (y+1)*W+x);
382 merge_vertices(connected, sc, y*W+(x+1), (y+1)*W+x);
384 decr_exits(sc, y*W+x);
385 decr_exits(sc, (y+1)*W+(x+1));
391 * Solver. Returns 0 for impossibility, 1 for success, 2 for
392 * ambiguity or failure to converge.
394 static int slant_solve(int w, int h, const signed char *clues,
395 signed char *soln, struct solver_scratch *sc,
398 int W = w+1, H = h+1;
405 memset(soln, 0, w*h);
410 * Establish a disjoint set forest for tracking connectedness
411 * between grid points.
413 for (i = 0; i < W*H; i++)
414 sc->connected[i] = i; /* initially all distinct */
417 * Establish a disjoint set forest for tracking which squares
418 * are known to slant in the same direction.
420 for (i = 0; i < w*h; i++)
421 sc->equiv[i] = i; /* initially all distinct */
424 * Clear the slashval array.
426 memset(sc->slashval, 0, w*h);
429 * Initialise the `exits' and `border' arrays. Theses is used
430 * to do second-order loop avoidance: the dual of the no loops
431 * constraint is that every point must be somehow connected to
432 * the border of the grid (otherwise there would be a solid
433 * loop around it which prevented this).
435 * I define a `dead end' to be a connected group of points
436 * which contains no border point, and which can form at most
437 * one new connection outside itself. Then I forbid placing an
438 * edge so that it connects together two dead-end groups, since
439 * this would yield a non-border-connected isolated subgraph
440 * with no further scope to extend it.
442 for (y = 0; y < H; y++)
443 for (x = 0; x < W; x++) {
444 if (y == 0 || y == H-1 || x == 0 || x == W-1)
445 sc->border[y*W+x] = TRUE;
447 sc->border[y*W+x] = FALSE;
449 if (clues[y*W+x] < 0)
450 sc->exits[y*W+x] = 4;
452 sc->exits[y*W+x] = clues[y*W+x];
456 * Make a one-off preliminary pass over the grid looking for
457 * starting-point arrangements. The ones we need to spot are:
459 * - two adjacent 1s in the centre of the grid imply that each
460 * one's single line points towards the other. (If either 1
461 * were connected on the far side, the two squares shared
462 * between the 1s would both link to the other 1 as a
463 * consequence of neither linking to the first.) Thus, we
464 * can fill in the four squares around them.
466 * - dually, two adjacent 3s imply that each one's _non_-line
467 * points towards the other.
469 * - if the pair of 1s and 3s is not _adjacent_ but is
470 * separated by one or more 2s, the reasoning still applies.
472 * This is more advanced than just spotting obvious starting
473 * squares such as central 4s and edge 2s, so we disable it on
476 * (I don't like this loop; it feels grubby to me. My
477 * mathematical intuition feels there ought to be some more
478 * general deductive form which contains this loop as a special
479 * case, but I can't bring it to mind right now.)
481 if (difficulty > DIFF_EASY) {
482 for (y = 1; y+1 < H; y++)
483 for (x = 1; x+1 < W; x++) {
484 int v = clues[y*W+x], s, x2, y2, dx, dy;
485 if (v != 1 && v != 3)
487 /* Slash value of the square up and left of (x,y). */
488 s = (v == 1 ? +1 : -1);
490 /* Look in each direction once. */
491 for (dy = 0; dy < 2; dy++) {
495 if (x2+1 >= W || y2+1 >= H)
496 continue; /* too close to the border */
497 while (x2+dx+1 < W && y2+dy+1 < H && clues[y2*W+x2] == 2)
499 if (clues[y2*W+x2] == v) {
500 #ifdef SOLVER_DIAGNOSTICS
502 printf("found adjacent %ds at %d,%d and %d,%d\n",
505 fill_square(w, h, x-1, y-1, s, soln,
507 fill_square(w, h, x-1+dy, y-1+dx, -s, soln,
509 fill_square(w, h, x2, y2, s, soln,
511 fill_square(w, h, x2-dy, y2-dx, -s, soln,
519 * Repeatedly try to deduce something until we can't.
522 done_something = FALSE;
525 * Any clue point with the number of remaining lines equal
526 * to zero or to the number of remaining undecided
527 * neighbouring squares can be filled in completely.
529 for (y = 0; y < H; y++)
530 for (x = 0; x < W; x++) {
535 int nu, nl, c, s, eq, eq2, last, meq, mj1, mj2;
537 if ((c = clues[y*W+x]) < 0)
541 * We have a clue point. Start by listing its
542 * neighbouring squares, in order around the point,
543 * together with the type of slash that would be
544 * required in that square to connect to the point.
547 if (x > 0 && y > 0) {
548 neighbours[nneighbours].pos = (y-1)*w+(x-1);
549 neighbours[nneighbours].slash = -1;
552 if (x > 0 && y < h) {
553 neighbours[nneighbours].pos = y*w+(x-1);
554 neighbours[nneighbours].slash = +1;
557 if (x < w && y < h) {
558 neighbours[nneighbours].pos = y*w+x;
559 neighbours[nneighbours].slash = -1;
562 if (x < w && y > 0) {
563 neighbours[nneighbours].pos = (y-1)*w+x;
564 neighbours[nneighbours].slash = +1;
569 * Count up the number of undecided neighbours, and
570 * also the number of lines already present.
572 * If we're not on DIFF_EASY, then in this loop we
573 * also track whether we've seen two adjacent empty
574 * squares belonging to the same equivalence class
575 * (meaning they have the same type of slash). If
576 * so, we count them jointly as one line.
580 last = neighbours[nneighbours-1].pos;
582 eq = dsf_canonify(sc->equiv, last);
585 meq = mj1 = mj2 = -1;
586 for (i = 0; i < nneighbours; i++) {
587 j = neighbours[i].pos;
588 s = neighbours[i].slash;
590 nu++; /* undecided */
591 if (meq < 0 && difficulty > DIFF_EASY) {
592 eq2 = dsf_canonify(sc->equiv, j);
593 if (eq == eq2 && last != j) {
595 * We've found an equivalent pair.
596 * Mark it. This also inhibits any
597 * further equivalence tracking
598 * around this square, since we can
599 * only handle one pair (and in
600 * particular we want to avoid
601 * being misled by two overlapping
602 * equivalence pairs).
607 nl--; /* count one line */
608 nu -= 2; /* and lose two undecideds */
615 nl--; /* here's a line */
623 if (nl < 0 || nl > nu) {
625 * No consistent value for this at all!
627 #ifdef SOLVER_DIAGNOSTICS
629 printf("need %d / %d lines around clue point at %d,%d!\n",
632 return 0; /* impossible */
635 if (nu > 0 && (nl == 0 || nl == nu)) {
636 #ifdef SOLVER_DIAGNOSTICS
639 printf("partially (since %d,%d == %d,%d) ",
640 mj1%w, mj1/w, mj2%w, mj2/w);
641 printf("%s around clue point at %d,%d\n",
642 nl ? "filling" : "emptying", x, y);
645 for (i = 0; i < nneighbours; i++) {
646 j = neighbours[i].pos;
647 s = neighbours[i].slash;
648 if (soln[j] == 0 && j != mj1 && j != mj2)
649 fill_square(w, h, j%w, j/w, (nl ? s : -s), soln,
653 done_something = TRUE;
654 } else if (nu == 2 && nl == 1 && difficulty > DIFF_EASY) {
656 * If we have precisely two undecided squares
657 * and precisely one line to place between
658 * them, _and_ those squares are adjacent, then
659 * we can mark them as equivalent to one
662 * This even applies if meq >= 0: if we have a
663 * 2 clue point and two of its neighbours are
664 * already marked equivalent, we can indeed
665 * mark the other two as equivalent.
667 * We don't bother with this on DIFF_EASY,
668 * since we wouldn't have used the results
672 for (i = 0; i < nneighbours; i++) {
673 j = neighbours[i].pos;
674 if (soln[j] == 0 && j != mj1 && j != mj2) {
677 else if (last == i-1 || (last == 0 && i == 3))
678 break; /* found a pair */
681 if (i < nneighbours) {
686 * neighbours[last] and neighbours[i] are
687 * the pair. Mark them equivalent.
689 #ifdef SOLVER_DIAGNOSTICS
692 printf("since %d,%d == %d,%d, ",
693 mj1%w, mj1/w, mj2%w, mj2/w);
696 mj1 = neighbours[last].pos;
697 mj2 = neighbours[i].pos;
698 #ifdef SOLVER_DIAGNOSTICS
700 printf("clue point at %d,%d implies %d,%d == %d,"
701 "%d\n", x, y, mj1%w, mj1/w, mj2%w, mj2/w);
703 mj1 = dsf_canonify(sc->equiv, mj1);
704 sv1 = sc->slashval[mj1];
705 mj2 = dsf_canonify(sc->equiv, mj2);
706 sv2 = sc->slashval[mj2];
707 if (sv1 != 0 && sv2 != 0 && sv1 != sv2) {
708 #ifdef SOLVER_DIAGNOSTICS
710 printf("merged two equivalence classes with"
711 " different slash values!\n");
715 sv1 = sv1 ? sv1 : sv2;
716 dsf_merge(sc->equiv, mj1, mj2);
717 mj1 = dsf_canonify(sc->equiv, mj1);
718 sc->slashval[mj1] = sv1;
727 * Failing that, we now apply the second condition, which
728 * is that no square may be filled in such a way as to form
729 * a loop. Also in this loop (since it's over squares
730 * rather than points), we check slashval to see if we've
731 * already filled in another square in the same equivalence
734 * The slashval check is disabled on DIFF_EASY, as is dead
735 * end avoidance. Only _immediate_ loop avoidance remains.
737 for (y = 0; y < h; y++)
738 for (x = 0; x < w; x++) {
741 #ifdef SOLVER_DIAGNOSTICS
742 char *reason = "<internal error>";
746 continue; /* got this one already */
751 if (difficulty > DIFF_EASY)
752 v = sc->slashval[dsf_canonify(sc->equiv, y*w+x)];
757 * Try to rule out connectivity between (x,y) and
758 * (x+1,y+1); if successful, we will deduce that we
759 * must have a forward slash.
761 c1 = dsf_canonify(sc->connected, y*W+x);
762 c2 = dsf_canonify(sc->connected, (y+1)*W+(x+1));
765 #ifdef SOLVER_DIAGNOSTICS
766 reason = "simple loop avoidance";
769 if (difficulty > DIFF_EASY &&
770 !sc->border[c1] && !sc->border[c2] &&
771 sc->exits[c1] <= 1 && sc->exits[c2] <= 1) {
773 #ifdef SOLVER_DIAGNOSTICS
774 reason = "dead end avoidance";
779 #ifdef SOLVER_DIAGNOSTICS
780 reason = "equivalence to an already filled square";
785 * Now do the same between (x+1,y) and (x,y+1), to
786 * see if we are required to have a backslash.
788 c1 = dsf_canonify(sc->connected, y*W+(x+1));
789 c2 = dsf_canonify(sc->connected, (y+1)*W+x);
792 #ifdef SOLVER_DIAGNOSTICS
793 reason = "simple loop avoidance";
796 if (difficulty > DIFF_EASY &&
797 !sc->border[c1] && !sc->border[c2] &&
798 sc->exits[c1] <= 1 && sc->exits[c2] <= 1) {
800 #ifdef SOLVER_DIAGNOSTICS
801 reason = "dead end avoidance";
806 #ifdef SOLVER_DIAGNOSTICS
807 reason = "equivalence to an already filled square";
813 * No consistent value for this at all!
815 #ifdef SOLVER_DIAGNOSTICS
817 printf("%d,%d has no consistent slash!\n", x, y);
819 return 0; /* impossible */
823 #ifdef SOLVER_DIAGNOSTICS
825 printf("employing %s\n", reason);
827 fill_square(w, h, x, y, +1, soln, sc->connected, sc);
828 done_something = TRUE;
830 #ifdef SOLVER_DIAGNOSTICS
832 printf("employing %s\n", reason);
834 fill_square(w, h, x, y, -1, soln, sc->connected, sc);
835 done_something = TRUE;
839 } while (done_something);
842 * Solver can make no more progress. See if the grid is full.
844 for (i = 0; i < w*h; i++)
846 return 2; /* failed to converge */
847 return 1; /* success */
851 * Filled-grid generator.
853 static void slant_generate(int w, int h, signed char *soln, random_state *rs)
855 int W = w+1, H = h+1;
857 int *connected, *indices;
862 memset(soln, 0, w*h);
865 * Establish a disjoint set forest for tracking connectedness
866 * between grid points.
868 connected = snewn(W*H, int);
869 for (i = 0; i < W*H; i++)
870 connected[i] = i; /* initially all distinct */
873 * Prepare a list of the squares in the grid, and fill them in
876 indices = snewn(w*h, int);
877 for (i = 0; i < w*h; i++)
879 shuffle(indices, w*h, sizeof(*indices), rs);
882 * Fill in each one in turn.
884 for (i = 0; i < w*h; i++) {
890 fs = (dsf_canonify(connected, y*W+x) ==
891 dsf_canonify(connected, (y+1)*W+(x+1)));
892 bs = (dsf_canonify(connected, (y+1)*W+x) ==
893 dsf_canonify(connected, y*W+(x+1)));
896 * It isn't possible to get into a situation where we
897 * aren't allowed to place _either_ type of slash in a
898 * square. Thus, filled-grid generation never has to
901 * Proof (thanks to Gareth Taylor):
903 * If it were possible, it would have to be because there
904 * was an existing path (not using this square) between the
905 * top-left and bottom-right corners of this square, and
906 * another between the other two. These two paths would
907 * have to cross at some point.
909 * Obviously they can't cross in the middle of a square, so
910 * they must cross by sharing a point in common. But this
911 * isn't possible either: if you chessboard-colour all the
912 * points on the grid, you find that any continuous
913 * diagonal path is entirely composed of points of the same
914 * colour. And one of our two hypothetical paths is between
915 * two black points, and the other is between two white
916 * points - therefore they can have no point in common. []
920 v = fs ? +1 : bs ? -1 : 2 * random_upto(rs, 2) - 1;
921 fill_square(w, h, x, y, v, soln, connected, NULL);
928 static char *new_game_desc(game_params *params, random_state *rs,
929 char **aux, int interactive)
931 int w = params->w, h = params->h, W = w+1, H = h+1;
932 signed char *soln, *tmpsoln, *clues;
934 struct solver_scratch *sc;
938 soln = snewn(w*h, signed char);
939 tmpsoln = snewn(w*h, signed char);
940 clues = snewn(W*H, signed char);
941 clueindices = snewn(W*H, int);
942 sc = new_scratch(w, h);
946 * Create the filled grid.
948 slant_generate(w, h, soln, rs);
951 * Fill in the complete set of clues.
953 for (y = 0; y < H; y++)
954 for (x = 0; x < W; x++) {
957 if (x > 0 && y > 0 && soln[(y-1)*w+(x-1)] == -1) v++;
958 if (x > 0 && y < h && soln[y*w+(x-1)] == +1) v++;
959 if (x < w && y > 0 && soln[(y-1)*w+x] == +1) v++;
960 if (x < w && y < h && soln[y*w+x] == -1) v++;
966 * With all clue points filled in, all puzzles are easy: we can
967 * simply process the clue points in lexicographic order, and
968 * at each clue point we will always have at most one square
969 * undecided, which we can then fill in uniquely.
971 assert(slant_solve(w, h, clues, tmpsoln, sc, DIFF_EASY) == 1);
974 * Remove as many clues as possible while retaining solubility.
976 * In DIFF_HARD mode, we prioritise the removal of obvious
977 * starting points (4s, 0s, border 2s and corner 1s), on
978 * the grounds that having as few of these as possible
979 * seems like a good thing. In particular, we can often get
980 * away without _any_ completely obvious starting points,
981 * which is even better.
983 for (i = 0; i < W*H; i++)
985 shuffle(clueindices, W*H, sizeof(*clueindices), rs);
986 for (j = 0; j < 2; j++) {
987 for (i = 0; i < W*H; i++) {
990 y = clueindices[i] / W;
991 x = clueindices[i] % W;
995 * Identify which pass we should process this point
996 * in. If it's an obvious start point, _or_ we're
997 * in DIFF_EASY, then it goes in pass 0; otherwise
1000 xb = (x == 0 || x == W-1);
1001 yb = (y == 0 || y == H-1);
1002 if (params->diff == DIFF_EASY || v == 4 || v == 0 ||
1003 (v == 2 && (xb||yb)) || (v == 1 && xb && yb))
1010 if (slant_solve(w, h, clues, tmpsoln, sc,
1012 clues[y*W+x] = v; /* put it back */
1018 * And finally, verify that the grid is of _at least_ the
1019 * requested difficulty, by running the solver one level
1020 * down and verifying that it can't manage it.
1022 } while (params->diff > 0 &&
1023 slant_solve(w, h, clues, tmpsoln, sc, params->diff - 1) <= 1);
1026 * Now we have the clue set as it will be presented to the
1027 * user. Encode it in a game desc.
1033 desc = snewn(W*H+1, char);
1036 for (i = 0; i <= W*H; i++) {
1037 int n = (i < W*H ? clues[i] : -2);
1044 int c = 'a' - 1 + run;
1048 run -= c - ('a' - 1);
1056 assert(p - desc <= W*H);
1058 desc = sresize(desc, p - desc, char);
1062 * Encode the solution as an aux_info.
1066 *aux = auxbuf = snewn(w*h+1, char);
1067 for (i = 0; i < w*h; i++)
1068 auxbuf[i] = soln[i] < 0 ? '\\' : '/';
1081 static char *validate_desc(game_params *params, char *desc)
1083 int w = params->w, h = params->h, W = w+1, H = h+1;
1089 if (n >= 'a' && n <= 'z') {
1090 squares += n - 'a' + 1;
1091 } else if (n >= '0' && n <= '4') {
1094 return "Invalid character in game description";
1098 return "Not enough data to fill grid";
1101 return "Too much data to fit in grid";
1106 static game_state *new_game(midend *me, game_params *params, char *desc)
1108 int w = params->w, h = params->h, W = w+1, H = h+1;
1109 game_state *state = snew(game_state);
1114 state->soln = snewn(w*h, signed char);
1115 memset(state->soln, 0, w*h);
1116 state->completed = state->used_solve = FALSE;
1117 state->errors = snewn(W*H, unsigned char);
1118 memset(state->errors, 0, W*H);
1120 state->clues = snew(game_clues);
1121 state->clues->w = w;
1122 state->clues->h = h;
1123 state->clues->clues = snewn(W*H, signed char);
1124 state->clues->refcount = 1;
1125 state->clues->tmpsoln = snewn(w*h, signed char);
1126 memset(state->clues->clues, -1, W*H);
1129 if (n >= 'a' && n <= 'z') {
1130 squares += n - 'a' + 1;
1131 } else if (n >= '0' && n <= '4') {
1132 state->clues->clues[squares++] = n - '0';
1134 assert(!"can't get here");
1136 assert(squares == area);
1141 static game_state *dup_game(game_state *state)
1143 int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
1144 game_state *ret = snew(game_state);
1147 ret->clues = state->clues;
1148 ret->clues->refcount++;
1149 ret->completed = state->completed;
1150 ret->used_solve = state->used_solve;
1152 ret->soln = snewn(w*h, signed char);
1153 memcpy(ret->soln, state->soln, w*h);
1155 ret->errors = snewn(W*H, unsigned char);
1156 memcpy(ret->errors, state->errors, W*H);
1161 static void free_game(game_state *state)
1163 sfree(state->errors);
1165 assert(state->clues);
1166 if (--state->clues->refcount <= 0) {
1167 sfree(state->clues->clues);
1168 sfree(state->clues->tmpsoln);
1169 sfree(state->clues);
1175 * Utility function to return the current degree of a vertex. If
1176 * `anti' is set, it returns the number of filled-in edges
1177 * surrounding the point which _don't_ connect to it; thus 4 minus
1178 * its anti-degree is the maximum degree it could have if all the
1179 * empty spaces around it were filled in.
1181 * (Yes, _4_ minus its anti-degree even if it's a border vertex.)
1183 * If ret > 0, *sx and *sy are set to the coordinates of one of the
1184 * squares that contributed to it.
1186 static int vertex_degree(int w, int h, signed char *soln, int x, int y,
1187 int anti, int *sx, int *sy)
1191 assert(x >= 0 && x <= w && y >= 0 && y <= h);
1192 if (x > 0 && y > 0 && soln[(y-1)*w+(x-1)] - anti < 0) {
1197 if (x > 0 && y < h && soln[y*w+(x-1)] + anti > 0) {
1202 if (x < w && y > 0 && soln[(y-1)*w+x] + anti > 0) {
1207 if (x < w && y < h && soln[y*w+x] - anti < 0) {
1213 return anti ? 4 - ret : ret;
1216 static int check_completion(game_state *state)
1218 int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
1219 int x, y, err = FALSE;
1222 memset(state->errors, 0, W*H);
1225 * An easy way to do loop checking would be by means of the
1226 * same dsf technique we've used elsewhere (loop over all edges
1227 * in the grid, joining vertices together into equivalence
1228 * classes when connected by an edge, and raise the alarm when
1229 * an edge joins two already-equivalent vertices). However, a
1230 * better approach is to repeatedly remove the single edge
1231 * connecting to any degree-1 vertex, and then see if there are
1232 * any edges left over; if so, precisely those edges are part
1233 * of loops, which means we can highlight them as errors for
1236 * We use the `tmpsoln' scratch space in the shared clues
1237 * structure, to avoid mallocing too often.
1239 ts = state->clues->tmpsoln;
1240 memcpy(ts, state->soln, w*h);
1241 for (y = 0; y < H; y++)
1242 for (x = 0; x < W; x++) {
1246 * Every time we disconnect a vertex like this, there
1247 * is precisely one other vertex which might have
1248 * become degree 1; so we follow the trail as far as it
1249 * leads. This ensures that we don't have to make more
1250 * than one loop over the grid, because whenever a
1251 * degree-1 vertex comes into existence somewhere we've
1252 * already looked, we immediately remove it again.
1253 * Hence one loop over the grid is adequate; and
1254 * moreover, this algorithm visits every vertex at most
1255 * twice (once in the loop and possibly once more as a
1256 * result of following a trail) so it has linear time
1257 * in the area of the grid.
1259 while (vertex_degree(w, h, ts, vx, vy, FALSE, &sx, &sy) == 1) {
1261 vx = vx + 1 + (sx - vx) * 2;
1262 vy = vy + 1 + (sy - vy) * 2;
1267 * Now mark any remaining edges with ERR_SQUARE.
1269 for (y = 0; y < h; y++)
1270 for (x = 0; x < w; x++)
1272 state->errors[y*W+x] |= ERR_SQUARE;
1277 * Now go through and check the degree of each clue vertex, and
1278 * mark it with ERR_VERTEX if it cannot be fulfilled.
1280 for (y = 0; y < H; y++)
1281 for (x = 0; x < W; x++) {
1284 if ((c = state->clues->clues[y*W+x]) < 0)
1288 * Check to see if there are too many connections to
1289 * this vertex _or_ too many non-connections. Either is
1290 * grounds for marking the vertex as erroneous.
1292 if (vertex_degree(w, h, state->soln, x, y,
1293 FALSE, NULL, NULL) > c ||
1294 vertex_degree(w, h, state->soln, x, y,
1295 TRUE, NULL, NULL) > 4-c) {
1296 state->errors[y*W+x] |= ERR_VERTEX;
1302 * Now our actual victory condition is that (a) none of the
1303 * above code marked anything as erroneous, and (b) every
1304 * square has an edge in it.
1310 for (y = 0; y < h; y++)
1311 for (x = 0; x < w; x++)
1312 if (state->soln[y*w+x] == 0)
1318 static char *solve_game(game_state *state, game_state *currstate,
1319 char *aux, char **error)
1321 int w = state->p.w, h = state->p.h;
1324 int free_soln = FALSE;
1325 char *move, buf[80];
1326 int movelen, movesize;
1331 * If we already have the solution, save ourselves some
1334 soln = (signed char *)aux;
1335 bs = (signed char)'\\';
1338 struct solver_scratch *sc = new_scratch(w, h);
1339 soln = snewn(w*h, signed char);
1341 ret = slant_solve(w, h, state->clues->clues, soln, sc, DIFF_HARD);
1346 *error = "This puzzle is not self-consistent";
1348 *error = "Unable to find a unique solution for this puzzle";
1355 * Construct a move string which turns the current state into
1359 move = snewn(movesize, char);
1361 move[movelen++] = 'S';
1362 move[movelen] = '\0';
1363 for (y = 0; y < h; y++)
1364 for (x = 0; x < w; x++) {
1365 int v = (soln[y*w+x] == bs ? -1 : +1);
1366 if (state->soln[y*w+x] != v) {
1367 int len = sprintf(buf, ";%c%d,%d", (int)(v < 0 ? '\\' : '/'), x, y);
1368 if (movelen + len >= movesize) {
1369 movesize = movelen + len + 256;
1370 move = sresize(move, movesize, char);
1372 strcpy(move + movelen, buf);
1383 static char *game_text_format(game_state *state)
1385 int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
1390 * There are h+H rows of w+W columns.
1392 len = (h+H) * (w+W+1) + 1;
1393 ret = snewn(len, char);
1396 for (y = 0; y < H; y++) {
1397 for (x = 0; x < W; x++) {
1398 if (state->clues->clues[y*W+x] >= 0)
1399 *p++ = state->clues->clues[y*W+x] + '0';
1407 for (x = 0; x < W; x++) {
1410 if (state->soln[y*w+x] != 0)
1411 *p++ = (state->soln[y*w+x] < 0 ? '\\' : '/');
1421 assert(p - ret == len);
1425 static game_ui *new_ui(game_state *state)
1430 static void free_ui(game_ui *ui)
1434 static char *encode_ui(game_ui *ui)
1439 static void decode_ui(game_ui *ui, char *encoding)
1443 static void game_changed_state(game_ui *ui, game_state *oldstate,
1444 game_state *newstate)
1448 #define PREFERRED_TILESIZE 32
1449 #define TILESIZE (ds->tilesize)
1450 #define BORDER TILESIZE
1451 #define CLUE_RADIUS (TILESIZE / 3)
1452 #define CLUE_TEXTSIZE (TILESIZE / 2)
1453 #define COORD(x) ( (x) * TILESIZE + BORDER )
1454 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1456 #define FLASH_TIME 0.30F
1459 * Bit fields in the `grid' and `todraw' elements of the drawstate.
1461 #define BACKSLASH 0x00000001L
1462 #define FORWSLASH 0x00000002L
1463 #define L_T 0x00000004L
1464 #define ERR_L_T 0x00000008L
1465 #define L_B 0x00000010L
1466 #define ERR_L_B 0x00000020L
1467 #define T_L 0x00000040L
1468 #define ERR_T_L 0x00000080L
1469 #define T_R 0x00000100L
1470 #define ERR_T_R 0x00000200L
1471 #define C_TL 0x00000400L
1472 #define ERR_C_TL 0x00000800L
1473 #define FLASH 0x00001000L
1474 #define ERRSLASH 0x00002000L
1475 #define ERR_TL 0x00004000L
1476 #define ERR_TR 0x00008000L
1477 #define ERR_BL 0x00010000L
1478 #define ERR_BR 0x00020000L
1480 struct game_drawstate {
1487 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1488 int x, int y, int button)
1490 int w = state->p.w, h = state->p.h;
1492 if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
1497 * This is an utterly awful hack which I should really sort out
1498 * by means of a proper configuration mechanism. One Slant
1499 * player has observed that they prefer the mouse buttons to
1500 * function exactly the opposite way round, so here's a
1501 * mechanism for environment-based configuration. I cache the
1502 * result in a global variable - yuck! - to avoid repeated
1506 static int swap_buttons = -1;
1507 if (swap_buttons < 0) {
1508 char *env = getenv("SLANT_SWAP_BUTTONS");
1509 swap_buttons = (env && (env[0] == 'y' || env[0] == 'Y'));
1512 if (button == LEFT_BUTTON)
1513 button = RIGHT_BUTTON;
1515 button = LEFT_BUTTON;
1521 if (x < 0 || y < 0 || x >= w || y >= h)
1524 if (button == LEFT_BUTTON) {
1526 * Left-clicking cycles blank -> \ -> / -> blank.
1528 v = state->soln[y*w+x] - 1;
1533 * Right-clicking cycles blank -> / -> \ -> blank.
1535 v = state->soln[y*w+x] + 1;
1540 sprintf(buf, "%c%d,%d", (int)(v==-1 ? '\\' : v==+1 ? '/' : 'C'), x, y);
1547 static game_state *execute_move(game_state *state, char *move)
1549 int w = state->p.w, h = state->p.h;
1552 game_state *ret = dup_game(state);
1557 ret->used_solve = TRUE;
1559 } else if (c == '\\' || c == '/' || c == 'C') {
1561 if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
1562 x < 0 || y < 0 || x >= w || y >= h) {
1566 ret->soln[y*w+x] = (c == '\\' ? -1 : c == '/' ? +1 : 0);
1581 * We never clear the `completed' flag, but we must always
1582 * re-run the completion check because it also highlights
1583 * errors in the grid.
1585 ret->completed = check_completion(ret) || ret->completed;
1590 /* ----------------------------------------------------------------------
1594 static void game_compute_size(game_params *params, int tilesize,
1597 /* fool the macros */
1598 struct dummy { int tilesize; } dummy = { tilesize }, *ds = &dummy;
1600 *x = 2 * BORDER + params->w * TILESIZE + 1;
1601 *y = 2 * BORDER + params->h * TILESIZE + 1;
1604 static void game_set_size(drawing *dr, game_drawstate *ds,
1605 game_params *params, int tilesize)
1607 ds->tilesize = tilesize;
1610 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
1612 float *ret = snewn(3 * NCOLOURS, float);
1614 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1616 ret[COL_GRID * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.7F;
1617 ret[COL_GRID * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.7F;
1618 ret[COL_GRID * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.7F;
1620 ret[COL_INK * 3 + 0] = 0.0F;
1621 ret[COL_INK * 3 + 1] = 0.0F;
1622 ret[COL_INK * 3 + 2] = 0.0F;
1624 ret[COL_SLANT1 * 3 + 0] = 0.0F;
1625 ret[COL_SLANT1 * 3 + 1] = 0.0F;
1626 ret[COL_SLANT1 * 3 + 2] = 0.0F;
1628 ret[COL_SLANT2 * 3 + 0] = 0.0F;
1629 ret[COL_SLANT2 * 3 + 1] = 0.0F;
1630 ret[COL_SLANT2 * 3 + 2] = 0.0F;
1632 ret[COL_ERROR * 3 + 0] = 1.0F;
1633 ret[COL_ERROR * 3 + 1] = 0.0F;
1634 ret[COL_ERROR * 3 + 2] = 0.0F;
1636 *ncolours = NCOLOURS;
1640 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1642 int w = state->p.w, h = state->p.h;
1644 struct game_drawstate *ds = snew(struct game_drawstate);
1647 ds->started = FALSE;
1648 ds->grid = snewn((w+2)*(h+2), long);
1649 ds->todraw = snewn((w+2)*(h+2), long);
1650 for (i = 0; i < (w+2)*(h+2); i++)
1651 ds->grid[i] = ds->todraw[i] = -1;
1656 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1663 static void draw_clue(drawing *dr, game_drawstate *ds,
1664 int x, int y, long v, long err, int bg, int colour)
1667 int ccol = colour >= 0 ? colour : ((x ^ y) & 1) ? COL_SLANT1 : COL_SLANT2;
1668 int tcol = colour >= 0 ? colour : err ? COL_ERROR : COL_INK;
1675 draw_circle(dr, COORD(x), COORD(y), CLUE_RADIUS,
1676 bg >= 0 ? bg : COL_BACKGROUND, ccol);
1677 draw_text(dr, COORD(x), COORD(y), FONT_VARIABLE,
1678 CLUE_TEXTSIZE, ALIGN_VCENTRE|ALIGN_HCENTRE, tcol, p);
1681 static void draw_tile(drawing *dr, game_drawstate *ds, game_clues *clues,
1682 int x, int y, long v)
1684 int w = clues->w, h = clues->h, W = w+1 /*, H = h+1 */;
1685 int chesscolour = (x ^ y) & 1;
1686 int fscol = chesscolour ? COL_SLANT2 : COL_SLANT1;
1687 int bscol = chesscolour ? COL_SLANT1 : COL_SLANT2;
1689 clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
1691 draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE,
1692 (v & FLASH) ? COL_GRID : COL_BACKGROUND);
1695 * Draw the grid lines.
1697 if (x >= 0 && x < w && y >= 0)
1698 draw_rect(dr, COORD(x), COORD(y), TILESIZE+1, 1, COL_GRID);
1699 if (x >= 0 && x < w && y < h)
1700 draw_rect(dr, COORD(x), COORD(y+1), TILESIZE+1, 1, COL_GRID);
1701 if (y >= 0 && y < h && x >= 0)
1702 draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE+1, COL_GRID);
1703 if (y >= 0 && y < h && x < w)
1704 draw_rect(dr, COORD(x+1), COORD(y), 1, TILESIZE+1, COL_GRID);
1705 if (x == -1 && y == -1)
1706 draw_rect(dr, COORD(x+1), COORD(y+1), 1, 1, COL_GRID);
1707 if (x == -1 && y == h)
1708 draw_rect(dr, COORD(x+1), COORD(y), 1, 1, COL_GRID);
1709 if (x == w && y == -1)
1710 draw_rect(dr, COORD(x), COORD(y+1), 1, 1, COL_GRID);
1711 if (x == w && y == h)
1712 draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID);
1717 if (v & BACKSLASH) {
1718 int scol = (v & ERRSLASH) ? COL_ERROR : bscol;
1719 draw_line(dr, COORD(x), COORD(y), COORD(x+1), COORD(y+1), scol);
1720 draw_line(dr, COORD(x)+1, COORD(y), COORD(x+1), COORD(y+1)-1,
1722 draw_line(dr, COORD(x), COORD(y)+1, COORD(x+1)-1, COORD(y+1),
1724 } else if (v & FORWSLASH) {
1725 int scol = (v & ERRSLASH) ? COL_ERROR : fscol;
1726 draw_line(dr, COORD(x+1), COORD(y), COORD(x), COORD(y+1), scol);
1727 draw_line(dr, COORD(x+1)-1, COORD(y), COORD(x), COORD(y+1)-1,
1729 draw_line(dr, COORD(x+1), COORD(y)+1, COORD(x)+1, COORD(y+1),
1734 * Draw dots on the grid corners that appear if a slash is in a
1735 * neighbouring cell.
1737 if (v & (L_T | BACKSLASH))
1738 draw_rect(dr, COORD(x), COORD(y)+1, 1, 1,
1739 (v & ERR_L_T ? COL_ERROR : bscol));
1740 if (v & (L_B | FORWSLASH))
1741 draw_rect(dr, COORD(x), COORD(y+1)-1, 1, 1,
1742 (v & ERR_L_B ? COL_ERROR : fscol));
1743 if (v & (T_L | BACKSLASH))
1744 draw_rect(dr, COORD(x)+1, COORD(y), 1, 1,
1745 (v & ERR_T_L ? COL_ERROR : bscol));
1746 if (v & (T_R | FORWSLASH))
1747 draw_rect(dr, COORD(x+1)-1, COORD(y), 1, 1,
1748 (v & ERR_T_R ? COL_ERROR : fscol));
1749 if (v & (C_TL | BACKSLASH))
1750 draw_rect(dr, COORD(x), COORD(y), 1, 1,
1751 (v & ERR_C_TL ? COL_ERROR : bscol));
1754 * And finally the clues at the corners.
1756 if (x >= 0 && y >= 0)
1757 draw_clue(dr, ds, x, y, clues->clues[y*W+x], v & ERR_TL, -1, -1);
1758 if (x < w && y >= 0)
1759 draw_clue(dr, ds, x+1, y, clues->clues[y*W+(x+1)], v & ERR_TR, -1, -1);
1760 if (x >= 0 && y < h)
1761 draw_clue(dr, ds, x, y+1, clues->clues[(y+1)*W+x], v & ERR_BL, -1, -1);
1763 draw_clue(dr, ds, x+1, y+1, clues->clues[(y+1)*W+(x+1)], v & ERR_BR,
1767 draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
1770 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1771 game_state *state, int dir, game_ui *ui,
1772 float animtime, float flashtime)
1774 int w = state->p.w, h = state->p.h, W = w+1, H = h+1;
1779 flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
1785 game_compute_size(&state->p, TILESIZE, &ww, &wh);
1786 draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND);
1787 draw_update(dr, 0, 0, ww, wh);
1792 * Loop over the grid and work out where all the slashes are.
1793 * We need to do this because a slash in one square affects the
1794 * drawing of the next one along.
1796 for (y = -1; y <= h; y++)
1797 for (x = -1; x <= w; x++) {
1798 if (x >= 0 && x < w && y >= 0 && y < h)
1799 ds->todraw[(y+1)*(w+2)+(x+1)] = flashing ? FLASH : 0;
1801 ds->todraw[(y+1)*(w+2)+(x+1)] = 0;
1804 for (y = 0; y < h; y++) {
1805 for (x = 0; x < w; x++) {
1806 int err = state->errors[y*W+x] & ERR_SQUARE;
1808 if (state->soln[y*w+x] < 0) {
1809 ds->todraw[(y+1)*(w+2)+(x+1)] |= BACKSLASH;
1810 ds->todraw[(y+2)*(w+2)+(x+1)] |= T_R;
1811 ds->todraw[(y+1)*(w+2)+(x+2)] |= L_B;
1812 ds->todraw[(y+2)*(w+2)+(x+2)] |= C_TL;
1814 ds->todraw[(y+1)*(w+2)+(x+1)] |= ERRSLASH |
1815 ERR_T_L | ERR_L_T | ERR_C_TL;
1816 ds->todraw[(y+2)*(w+2)+(x+1)] |= ERR_T_R;
1817 ds->todraw[(y+1)*(w+2)+(x+2)] |= ERR_L_B;
1818 ds->todraw[(y+2)*(w+2)+(x+2)] |= ERR_C_TL;
1820 } else if (state->soln[y*w+x] > 0) {
1821 ds->todraw[(y+1)*(w+2)+(x+1)] |= FORWSLASH;
1822 ds->todraw[(y+1)*(w+2)+(x+2)] |= L_T | C_TL;
1823 ds->todraw[(y+2)*(w+2)+(x+1)] |= T_L | C_TL;
1825 ds->todraw[(y+1)*(w+2)+(x+1)] |= ERRSLASH |
1827 ds->todraw[(y+1)*(w+2)+(x+2)] |= ERR_L_T | ERR_C_TL;
1828 ds->todraw[(y+2)*(w+2)+(x+1)] |= ERR_T_L | ERR_C_TL;
1834 for (y = 0; y < H; y++)
1835 for (x = 0; x < W; x++)
1836 if (state->errors[y*W+x] & ERR_VERTEX) {
1837 ds->todraw[y*(w+2)+x] |= ERR_BR;
1838 ds->todraw[y*(w+2)+(x+1)] |= ERR_BL;
1839 ds->todraw[(y+1)*(w+2)+x] |= ERR_TR;
1840 ds->todraw[(y+1)*(w+2)+(x+1)] |= ERR_TL;
1844 * Now go through and draw the grid squares.
1846 for (y = -1; y <= h; y++) {
1847 for (x = -1; x <= w; x++) {
1848 if (ds->todraw[(y+1)*(w+2)+(x+1)] != ds->grid[(y+1)*(w+2)+(x+1)]) {
1849 draw_tile(dr, ds, state->clues, x, y,
1850 ds->todraw[(y+1)*(w+2)+(x+1)]);
1851 ds->grid[(y+1)*(w+2)+(x+1)] = ds->todraw[(y+1)*(w+2)+(x+1)];
1857 static float game_anim_length(game_state *oldstate, game_state *newstate,
1858 int dir, game_ui *ui)
1863 static float game_flash_length(game_state *oldstate, game_state *newstate,
1864 int dir, game_ui *ui)
1866 if (!oldstate->completed && newstate->completed &&
1867 !oldstate->used_solve && !newstate->used_solve)
1873 static int game_wants_statusbar(void)
1878 static int game_timing_state(game_state *state, game_ui *ui)
1883 static void game_print_size(game_params *params, float *x, float *y)
1888 * I'll use 6mm squares by default.
1890 game_compute_size(params, 600, &pw, &ph);
1895 static void game_print(drawing *dr, game_state *state, int tilesize)
1897 int w = state->p.w, h = state->p.h, W = w+1;
1898 int ink = print_mono_colour(dr, 0);
1899 int paper = print_mono_colour(dr, 1);
1902 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1903 game_drawstate ads, *ds = &ads;
1904 ads.tilesize = tilesize;
1909 print_line_width(dr, TILESIZE / 16);
1910 draw_rect_outline(dr, COORD(0), COORD(0), w*TILESIZE, h*TILESIZE, ink);
1915 print_line_width(dr, TILESIZE / 24);
1916 for (x = 1; x < w; x++)
1917 draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), ink);
1918 for (y = 1; y < h; y++)
1919 draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), ink);
1924 print_line_width(dr, TILESIZE / 12);
1925 for (y = 0; y < h; y++)
1926 for (x = 0; x < w; x++)
1927 if (state->soln[y*w+x]) {
1930 * To prevent nasty line-ending artefacts at
1931 * corners, I'll do something slightly cunning
1934 clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
1935 if (state->soln[y*w+x] < 0)
1939 draw_line(dr, COORD(x-1), COORD(ly), COORD(x+2), COORD(ry),
1947 print_line_width(dr, TILESIZE / 24);
1948 for (y = 0; y <= h; y++)
1949 for (x = 0; x <= w; x++)
1950 draw_clue(dr, ds, x, y, state->clues->clues[y*W+x],
1955 #define thegame slant
1958 const struct game thegame = {
1959 "Slant", "games.slant",
1966 TRUE, game_configure, custom_params,
1974 TRUE, game_text_format,
1982 PREFERRED_TILESIZE, game_compute_size, game_set_size,
1985 game_free_drawstate,
1989 TRUE, FALSE, game_print_size, game_print,
1990 game_wants_statusbar,
1991 FALSE, game_timing_state,
1992 0, /* mouse_priorities */
1995 #ifdef STANDALONE_SOLVER
1999 int main(int argc, char **argv)
2003 char *id = NULL, *desc, *err;
2005 int ret, diff, really_verbose = FALSE;
2006 struct solver_scratch *sc;
2008 while (--argc > 0) {
2010 if (!strcmp(p, "-v")) {
2011 really_verbose = TRUE;
2012 } else if (!strcmp(p, "-g")) {
2014 } else if (*p == '-') {
2015 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2023 fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
2027 desc = strchr(id, ':');
2029 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2034 p = default_params();
2035 decode_params(p, id);
2036 err = validate_desc(p, desc);
2038 fprintf(stderr, "%s: %s\n", argv[0], err);
2041 s = new_game(NULL, p, desc);
2043 sc = new_scratch(p->w, p->h);
2046 * When solving an Easy puzzle, we don't want to bother the
2047 * user with Hard-level deductions. For this reason, we grade
2048 * the puzzle internally before doing anything else.
2050 ret = -1; /* placate optimiser */
2051 for (diff = 0; diff < DIFFCOUNT; diff++) {
2052 ret = slant_solve(p->w, p->h, s->clues->clues,
2058 if (diff == DIFFCOUNT) {
2060 printf("Difficulty rating: harder than Hard, or ambiguous\n");
2062 printf("Unable to find a unique solution\n");
2066 printf("Difficulty rating: impossible (no solution exists)\n");
2068 printf("Difficulty rating: %s\n", slant_diffnames[diff]);
2070 verbose = really_verbose;
2071 ret = slant_solve(p->w, p->h, s->clues->clues,
2074 printf("Puzzle is inconsistent\n");
2076 fputs(game_text_format(s), stdout);