2 * towers.c: the puzzle also known as 'Skyscrapers'.
4 * Possible future work:
6 * - Relax the upper bound on grid size at 9?
7 * + I'd need TOCHAR and FROMCHAR macros a bit like group's, to
8 * be used wherever this code has +'0' or -'0'
9 * + the pencil marks in the drawstate would need a separate
11 * + the clues outside the grid would have to cope with being
12 * multi-digit, meaning in particular that the text formatting
13 * would become more unpleasant
14 * + most importantly, though, the solver just isn't fast
15 * enough. Even at size 9 it can't really do the solver_hard
16 * factorial-time enumeration at a sensible rate. Easy puzzles
17 * higher than that would be possible, but more latin-squarey
18 * than skyscrapery, as it were.
21 * + Allow the user to mark a clue as 'spent' in some way once
22 * it's no longer interesting (typically because no
23 * arrangement of the remaining possibilities _can_ violate
38 * Difficulty levels. I do some macro ickery here to ensure that my
39 * enum and the various forms of my name list always match up.
42 A(EASY,Easy,solver_easy,e) \
43 A(HARD,Hard,solver_hard,h) \
44 A(EXTREME,Extreme,NULL,x) \
45 A(UNREASONABLE,Unreasonable,NULL,u)
46 #define ENUM(upper,title,func,lower) DIFF_ ## upper,
47 #define TITLE(upper,title,func,lower) #title,
48 #define ENCODE(upper,title,func,lower) #lower
49 #define CONFIG(upper,title,func,lower) ":" #title
50 enum { DIFFLIST(ENUM) DIFFCOUNT };
51 static char const *const towers_diffnames[] = { DIFFLIST(TITLE) };
52 static char const towers_diffchars[] = DIFFLIST(ENCODE);
53 #define DIFFCONFIG DIFFLIST(CONFIG)
73 * An array of 4w integers, of which:
74 * - the first w run across the top
75 * - the next w across the bottom
76 * - the third w down the left
77 * - the last w down the right.
82 * An array of w*w digits.
88 * Macros to compute clue indices and coordinates.
90 #define STARTSTEP(start, step, index, w) do { \
92 start = index, step = w; \
93 else if (index < 2*w) \
94 start = (w-1)*w+(index-w), step = -w; \
95 else if (index < 3*w) \
96 start = w*(index-2*w), step = 1; \
98 start = w*(index-3*w)+(w-1), step = -1; \
100 #define CSTARTSTEP(start, step, index, w) \
101 STARTSTEP(start, step, (((index)+2*w)%(4*w)), w)
102 #define CLUEPOS(x, y, index, w) do { \
105 else if (index < 2*w) \
106 x = index-w, y = w; \
107 else if (index < 3*w) \
108 x = -1, y = index-2*w; \
110 x = w, y = index-3*w; \
113 #ifdef STANDALONE_SOLVER
114 static const char *const cluepos[] = {
115 "above column", "below column", "left of row", "right of row"
123 int *pencil; /* bitmaps using bits 1<<1..1<<n */
124 int completed, cheated;
127 static game_params *default_params(void)
129 game_params *ret = snew(game_params);
132 ret->diff = DIFF_EASY;
137 const static struct game_params towers_presets[] = {
144 { 6, DIFF_UNREASONABLE },
147 static int game_fetch_preset(int i, char **name, game_params **params)
152 if (i < 0 || i >= lenof(towers_presets))
155 ret = snew(game_params);
156 *ret = towers_presets[i]; /* structure copy */
158 sprintf(buf, "%dx%d %s", ret->w, ret->w, towers_diffnames[ret->diff]);
165 static void free_params(game_params *params)
170 static game_params *dup_params(game_params *params)
172 game_params *ret = snew(game_params);
173 *ret = *params; /* structure copy */
177 static void decode_params(game_params *params, char const *string)
179 char const *p = string;
182 while (*p && isdigit((unsigned char)*p)) p++;
187 params->diff = DIFFCOUNT+1; /* ...which is invalid */
189 for (i = 0; i < DIFFCOUNT; i++) {
190 if (*p == towers_diffchars[i])
198 static char *encode_params(game_params *params, int full)
202 sprintf(ret, "%d", params->w);
204 sprintf(ret + strlen(ret), "d%c", towers_diffchars[params->diff]);
209 static config_item *game_configure(game_params *params)
214 ret = snewn(3, config_item);
216 ret[0].name = "Grid size";
217 ret[0].type = C_STRING;
218 sprintf(buf, "%d", params->w);
219 ret[0].sval = dupstr(buf);
222 ret[1].name = "Difficulty";
223 ret[1].type = C_CHOICES;
224 ret[1].sval = DIFFCONFIG;
225 ret[1].ival = params->diff;
235 static game_params *custom_params(config_item *cfg)
237 game_params *ret = snew(game_params);
239 ret->w = atoi(cfg[0].sval);
240 ret->diff = cfg[1].ival;
245 static char *validate_params(game_params *params, int full)
247 if (params->w < 3 || params->w > 9)
248 return "Grid size must be between 3 and 9";
249 if (params->diff >= DIFFCOUNT)
250 return "Unknown difficulty rating";
254 /* ----------------------------------------------------------------------
266 static int solver_easy(struct latin_solver *solver, void *vctx)
268 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
270 int c, i, j, n, m, furthest;
271 int start, step, cstart, cstep, clue, pos, cpos;
273 #ifdef STANDALONE_SOLVER
280 * One-off loop to help get started: when a pair of facing
281 * clues sum to w+1, it must mean that the row consists of
282 * two increasing sequences back to back, so we can
283 * immediately place the highest digit by knowing the
284 * lengths of those two sequences.
286 for (c = 0; c < 3*w; c = (c == w-1 ? 2*w : c+1)) {
289 if (ctx->clues[c] && ctx->clues[c2] &&
290 ctx->clues[c] + ctx->clues[c2] == w+1) {
291 STARTSTEP(start, step, c, w);
292 CSTARTSTEP(cstart, cstep, c, w);
293 pos = start + (ctx->clues[c]-1)*step;
294 cpos = cstart + (ctx->clues[c]-1)*cstep;
295 if (solver->cube[cpos*w+w-1]) {
296 #ifdef STANDALONE_SOLVER
297 if (solver_show_working) {
298 printf("%*sfacing clues on %s %d are maximal:\n",
299 solver_recurse_depth*4, "",
300 c>=2*w ? "row" : "column", c % w + 1);
301 printf("%*s placing %d at (%d,%d)\n",
302 solver_recurse_depth*4, "",
303 w, pos%w+1, pos/w+1);
306 latin_solver_place(solver, pos%w, pos/w, w);
319 * Go over every clue doing reasonably simple heuristic
322 for (c = 0; c < 4*w; c++) {
323 clue = ctx->clues[c];
326 STARTSTEP(start, step, c, w);
327 CSTARTSTEP(cstart, cstep, c, w);
329 /* Find the location of each number in the row. */
330 for (i = 0; i < w; i++)
331 ctx->dscratch[i] = w;
332 for (i = 0; i < w; i++)
333 if (solver->grid[start+i*step])
334 ctx->dscratch[solver->grid[start+i*step]-1] = i;
338 for (i = w; i >= 1; i--) {
339 if (ctx->dscratch[i-1] == w) {
341 } else if (ctx->dscratch[i-1] < furthest) {
342 furthest = ctx->dscratch[i-1];
347 if (clue == n+1 && furthest > 1) {
348 #ifdef STANDALONE_SOLVER
349 if (solver_show_working)
350 sprintf(prefix, "%*sclue %s %d is nearly filled:\n",
351 solver_recurse_depth*4, "",
352 cluepos[c/w], c%w+1);
354 prefix[0] = '\0'; /* placate optimiser */
357 * We can already see an increasing sequence of the very
358 * highest numbers, of length one less than that
359 * specified in the clue. All of those numbers _must_ be
360 * part of the clue sequence, so the number right next
361 * to the clue must be the final one - i.e. it must be
362 * bigger than any of the numbers between it and m. This
363 * allows us to rule out small numbers in that square.
365 * (This is a generalisation of the obvious deduction
366 * that when you see a clue saying 1, it must be right
367 * next to the largest possible number; and similarly,
368 * when you see a clue saying 2 opposite that, it must
369 * be right next to the second-largest.)
371 j = furthest-1; /* number of small numbers we can rule out */
372 for (i = 1; i <= w && j > 0; i++) {
373 if (ctx->dscratch[i-1] < w && ctx->dscratch[i-1] >= furthest)
374 continue; /* skip this number, it's elsewhere */
376 if (solver->cube[cstart*w+i-1]) {
377 #ifdef STANDALONE_SOLVER
378 if (solver_show_working) {
379 printf("%s%*s ruling out %d at (%d,%d)\n",
380 prefix, solver_recurse_depth*4, "",
381 i, start%w+1, start/w+1);
385 solver->cube[cstart*w+i-1] = 0;
394 #ifdef STANDALONE_SOLVER
395 if (solver_show_working)
396 sprintf(prefix, "%*slower bounds for clue %s %d:\n",
397 solver_recurse_depth*4, "",
398 cluepos[c/w], c%w+1);
400 prefix[0] = '\0'; /* placate optimiser */
404 for (n = w; n > 0; n--) {
406 * The largest number cannot occur in the first (clue-1)
407 * squares of the row, or else there wouldn't be space
408 * for a sufficiently long increasing sequence which it
409 * terminated. The second-largest number (not counting
410 * any that are known to be on the far side of a larger
411 * number and hence excluded from this sequence) cannot
412 * occur in the first (clue-2) squares, similarly, and
416 if (ctx->dscratch[n-1] < w) {
417 for (m = n+1; m < w; m++)
418 if (ctx->dscratch[m] < ctx->dscratch[n-1])
421 continue; /* this number doesn't count */
424 for (j = 0; j < clue - i - 1; j++)
425 if (solver->cube[(cstart + j*cstep)*w+n-1]) {
426 #ifdef STANDALONE_SOLVER
427 if (solver_show_working) {
428 int pos = start+j*step;
429 printf("%s%*s ruling out %d at (%d,%d)\n",
430 prefix, solver_recurse_depth*4, "",
431 n, pos%w+1, pos/w+1);
435 solver->cube[(cstart + j*cstep)*w+n-1] = 0;
448 static int solver_hard(struct latin_solver *solver, void *vctx)
450 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
452 int c, i, j, n, best, clue, start, step, ret;
454 #ifdef STANDALONE_SOLVER
459 * Go over every clue analysing all possibilities.
461 for (c = 0; c < 4*w; c++) {
462 clue = ctx->clues[c];
465 CSTARTSTEP(start, step, c, w);
467 for (i = 0; i < w; i++)
468 ctx->iscratch[i] = 0;
471 * Instead of a tedious physical recursion, I iterate in the
472 * scratch array through all possibilities. At any given
473 * moment, i indexes the element of the box that will next
477 ctx->dscratch[i] = 0;
484 * Find the next valid value for cell i.
486 int limit = (n == clue ? best : w);
487 int pos = start + step * i;
488 for (j = ctx->dscratch[i] + 1; j <= limit; j++) {
489 if (bitmap & (1L << j))
490 continue; /* used this one already */
491 if (!solver->cube[pos*w+j-1])
492 continue; /* ruled out already */
499 /* No valid values left; drop back. */
502 break; /* overall iteration is finished */
503 bitmap &= ~(1L << ctx->dscratch[i]);
504 if (ctx->dscratch[i] == best) {
507 for (j = 0; j < i; j++)
508 if (best < ctx->dscratch[j])
509 best = ctx->dscratch[j];
512 /* Got a valid value; store it and move on. */
514 ctx->dscratch[i++] = j;
519 ctx->dscratch[i] = 0;
523 for (j = 0; j < w; j++)
524 ctx->iscratch[j] |= 1L << ctx->dscratch[j];
527 bitmap &= ~(1L << ctx->dscratch[i]);
528 if (ctx->dscratch[i] == best) {
531 for (j = 0; j < i; j++)
532 if (best < ctx->dscratch[j])
533 best = ctx->dscratch[j];
538 #ifdef STANDALONE_SOLVER
539 if (solver_show_working)
540 sprintf(prefix, "%*sexhaustive analysis of clue %s %d:\n",
541 solver_recurse_depth*4, "",
542 cluepos[c/w], c%w+1);
544 prefix[0] = '\0'; /* placate optimiser */
549 for (i = 0; i < w; i++) {
550 int pos = start + step * i;
551 for (j = 1; j <= w; j++) {
552 if (solver->cube[pos*w+j-1] &&
553 !(ctx->iscratch[i] & (1L << j))) {
554 #ifdef STANDALONE_SOLVER
555 if (solver_show_working) {
556 printf("%s%*s ruling out %d at (%d,%d)\n",
557 prefix, solver_recurse_depth*4, "",
558 j, pos/w+1, pos%w+1);
562 solver->cube[pos*w+j-1] = 0;
568 * Once we find one clue we can do something with in
569 * this way, revert to trying easier deductions, so as
570 * not to generate solver diagnostics that make the
571 * problem look harder than it is.
581 #define SOLVER(upper,title,func,lower) func,
582 static usersolver_t const towers_solvers[] = { DIFFLIST(SOLVER) };
584 static int solver(int w, int *clues, digit *soln, int maxdiff)
587 struct solver_ctx ctx;
593 ctx.iscratch = snewn(w, long);
594 ctx.dscratch = snewn(w+1, int);
596 ret = latin_solver(soln, w, maxdiff,
597 DIFF_EASY, DIFF_HARD, DIFF_EXTREME,
598 DIFF_EXTREME, DIFF_UNREASONABLE,
599 towers_solvers, &ctx, NULL, NULL);
607 /* ----------------------------------------------------------------------
611 static char *new_game_desc(game_params *params, random_state *rs,
612 char **aux, int interactive)
614 int w = params->w, a = w*w;
615 digit *grid, *soln, *soln2;
618 int diff = params->diff;
622 * Difficulty exceptions: some combinations of size and
623 * difficulty cannot be satisfied, because all puzzles of at
624 * most that difficulty are actually even easier.
626 * Remember to re-test this whenever a change is made to the
629 * I tested it using the following shell command:
633 echo -n "./towers --generate 1 ${i}d${d}: "
634 perl -e 'alarm 30; exec @ARGV' ./towers --generate 1 ${i}d${d} >/dev/null \
639 * Of course, it's better to do that after taking the exceptions
640 * _out_, so as to detect exceptions that should be removed as
641 * well as those which should be added.
643 if (diff > DIFF_HARD && w <= 3)
647 clues = snewn(4*w, int);
648 soln = snewn(a, digit);
649 soln2 = snewn(a, digit);
650 order = snewn(max(4*w,a), int);
654 * Construct a latin square to be the solution.
657 grid = latin_generate(w, rs);
662 for (i = 0; i < 4*w; i++) {
663 int start, step, j, k, best;
664 STARTSTEP(start, step, i, w);
666 for (j = 0; j < w; j++) {
667 if (grid[start+j*step] > best) {
668 best = grid[start+j*step];
676 * Remove the grid numbers and then the clues, one by one,
677 * for as long as the game remains soluble at the given
680 memcpy(soln, grid, a);
682 if (diff == DIFF_EASY && w <= 5) {
684 * Special case: for Easy-mode grids that are small
685 * enough, it's nice to be able to find completely empty
689 ret = solver(w, clues, soln2, diff);
694 for (i = 0; i < a; i++)
696 shuffle(order, a, sizeof(*order), rs);
697 for (i = 0; i < a; i++) {
700 memcpy(soln2, grid, a);
702 ret = solver(w, clues, soln2, diff);
707 if (diff > DIFF_EASY) { /* leave all clues on Easy mode */
708 for (i = 0; i < 4*w; i++)
710 shuffle(order, 4*w, sizeof(*order), rs);
711 for (i = 0; i < 4*w; i++) {
715 memcpy(soln2, grid, a);
717 ret = solver(w, clues, soln2, diff);
724 * See if the game can be solved at the specified difficulty
725 * level, but not at the one below.
727 memcpy(soln2, grid, a);
728 ret = solver(w, clues, soln2, diff);
730 continue; /* go round again */
733 * We've got a usable puzzle!
739 * Encode the puzzle description.
741 desc = snewn(40*a, char);
743 for (i = 0; i < 4*w; i++) {
744 p += sprintf(p, "%s%.0d", i?"/":"", clues[i]);
746 for (i = 0; i < a; i++)
754 for (i = 0; i <= a; i++) {
755 int n = (i < a ? grid[i] : -1);
762 int thisrun = min(run, 26);
763 *p++ = thisrun - 1 + 'a';
768 * If there's a number in the very top left or
769 * bottom right, there's no point putting an
770 * unnecessary _ before or after it.
776 p += sprintf(p, "%d", n);
782 desc = sresize(desc, p - desc, char);
785 * Encode the solution.
787 *aux = snewn(a+2, char);
789 for (i = 0; i < a; i++)
790 (*aux)[i+1] = '0' + soln[i];
802 /* ----------------------------------------------------------------------
806 static char *validate_desc(game_params *params, char *desc)
808 int w = params->w, a = w*w;
809 const char *p = desc;
813 * Verify that the right number of clues are given, and that
816 for (i = 0; i < 4*w; i++) {
818 return "Too few clues for grid size";
822 return "Expected commas between clues";
826 if (isdigit((unsigned char)*p)) {
828 while (*p && isdigit((unsigned char)*p)) p++;
830 if (clue <= 0 || clue > w)
831 return "Clue number out of range";
835 return "Too many clues for grid size";
839 * Verify that the right amount of grid data is given, and
840 * that any grid elements provided are in range.
847 if (c >= 'a' && c <= 'z') {
848 squares += c - 'a' + 1;
849 } else if (c == '_') {
851 } else if (c > '0' && c <= '9') {
853 if (val < 1 || val > w)
854 return "Out-of-range number in grid description";
856 while (*p && isdigit((unsigned char)*p)) p++;
858 return "Invalid character in game description";
862 return "Not enough data to fill grid";
865 return "Too much data to fit in grid";
871 static game_state *new_game(midend *me, game_params *params, char *desc)
873 int w = params->w, a = w*w;
874 game_state *state = snew(game_state);
875 const char *p = desc;
878 state->par = *params; /* structure copy */
879 state->clues = snew(struct clues);
880 state->clues->refcount = 1;
882 state->clues->clues = snewn(4*w, int);
883 state->clues->immutable = snewn(a, digit);
884 state->grid = snewn(a, digit);
885 state->pencil = snewn(a, int);
887 for (i = 0; i < a; i++) {
889 state->pencil[i] = 0;
892 memset(state->clues->immutable, 0, a);
894 for (i = 0; i < 4*w; i++) {
899 if (*p && isdigit((unsigned char)*p)) {
900 state->clues->clues[i] = atoi(p);
901 while (*p && isdigit((unsigned char)*p)) p++;
903 state->clues->clues[i] = 0;
911 if (c >= 'a' && c <= 'z') {
913 } else if (c == '_') {
915 } else if (c > '0' && c <= '9') {
917 assert(val >= 1 && val <= w);
919 state->grid[pos] = state->clues->immutable[pos] = val;
921 while (*p && isdigit((unsigned char)*p)) p++;
923 assert(!"Corrupt game description");
929 state->completed = state->cheated = FALSE;
934 static game_state *dup_game(game_state *state)
936 int w = state->par.w, a = w*w;
937 game_state *ret = snew(game_state);
939 ret->par = state->par; /* structure copy */
941 ret->clues = state->clues;
942 ret->clues->refcount++;
944 ret->grid = snewn(a, digit);
945 ret->pencil = snewn(a, int);
946 memcpy(ret->grid, state->grid, a*sizeof(digit));
947 memcpy(ret->pencil, state->pencil, a*sizeof(int));
949 ret->completed = state->completed;
950 ret->cheated = state->cheated;
955 static void free_game(game_state *state)
958 sfree(state->pencil);
959 if (--state->clues->refcount <= 0) {
960 sfree(state->clues->immutable);
961 sfree(state->clues->clues);
967 static char *solve_game(game_state *state, game_state *currstate,
968 char *aux, char **error)
970 int w = state->par.w, a = w*w;
978 soln = snewn(a, digit);
979 memcpy(soln, state->clues->immutable, a);
981 ret = solver(w, state->clues->clues, soln, DIFFCOUNT-1);
983 if (ret == diff_impossible) {
984 *error = "No solution exists for this puzzle";
986 } else if (ret == diff_ambiguous) {
987 *error = "Multiple solutions exist for this puzzle";
990 out = snewn(a+2, char);
992 for (i = 0; i < a; i++)
993 out[i+1] = '0' + soln[i];
1001 static int game_can_format_as_text_now(game_params *params)
1006 static char *game_text_format(game_state *state)
1008 int w = state->par.w /* , a = w*w */;
1016 * - a top clue row, consisting of three spaces, then w clue
1017 * digits with spaces between (total 2*w+3 chars including
1019 * - a blank line (one newline)
1020 * - w main rows, consisting of a left clue digit, two spaces,
1021 * w grid digits with spaces between, two spaces and a right
1022 * clue digit (total 2*w+6 chars each including newline)
1023 * - a blank line (one newline)
1024 * - a bottom clue row (same as top clue row)
1025 * - terminating NUL.
1027 * Total size is therefore 2*(2*w+3) + 2 + w*(2*w+6) + 1
1030 total = 2*w*w + 10*w + 9;
1031 ret = snewn(total, char);
1035 *p++ = ' '; *p++ = ' ';
1036 for (x = 0; x < w; x++) {
1038 *p++ = (state->clues->clues[x] ? '0' + state->clues->clues[x] : ' ');
1046 for (y = 0; y < w; y++) {
1047 *p++ = (state->clues->clues[y+2*w] ? '0' + state->clues->clues[y+2*w] :
1050 for (x = 0; x < w; x++) {
1052 *p++ = (state->grid[y*w+x] ? '0' + state->grid[y*w+x] : ' ');
1054 *p++ = ' '; *p++ = ' ';
1055 *p++ = (state->clues->clues[y+3*w] ? '0' + state->clues->clues[y+3*w] :
1063 /* Bottom clue row. */
1064 *p++ = ' '; *p++ = ' ';
1065 for (x = 0; x < w; x++) {
1067 *p++ = (state->clues->clues[x+w] ? '0' + state->clues->clues[x+w] :
1073 assert(p == ret + total);
1080 * These are the coordinates of the currently highlighted
1081 * square on the grid, if hshow = 1.
1085 * This indicates whether the current highlight is a
1086 * pencil-mark one or a real one.
1090 * This indicates whether or not we're showing the highlight
1091 * (used to be hx = hy = -1); important so that when we're
1092 * using the cursor keys it doesn't keep coming back at a
1093 * fixed position. When hshow = 1, pressing a valid number
1094 * or letter key or Space will enter that number or letter in the grid.
1098 * This indicates whether we're using the highlight as a cursor;
1099 * it means that it doesn't vanish on a keypress, and that it is
1100 * allowed on immutable squares.
1105 static game_ui *new_ui(game_state *state)
1107 game_ui *ui = snew(game_ui);
1109 ui->hx = ui->hy = 0;
1110 ui->hpencil = ui->hshow = ui->hcursor = 0;
1115 static void free_ui(game_ui *ui)
1120 static char *encode_ui(game_ui *ui)
1125 static void decode_ui(game_ui *ui, char *encoding)
1129 static void game_changed_state(game_ui *ui, game_state *oldstate,
1130 game_state *newstate)
1132 int w = newstate->par.w;
1134 * We prevent pencil-mode highlighting of a filled square, unless
1135 * we're using the cursor keys. So if the user has just filled in
1136 * a square which we had a pencil-mode highlight in (by Undo, or
1137 * by Redo, or by Solve), then we cancel the highlight.
1139 if (ui->hshow && ui->hpencil && !ui->hcursor &&
1140 newstate->grid[ui->hy * w + ui->hx] != 0) {
1145 #define PREFERRED_TILESIZE 48
1146 #define TILESIZE (ds->tilesize)
1147 #define BORDER (TILESIZE * 9 / 8)
1148 #define COORD(x) ((x)*TILESIZE + BORDER)
1149 #define FROMCOORD(x) (((x)+(TILESIZE-BORDER)) / TILESIZE - 1)
1151 #define FLASH_TIME 0.4F
1153 #define DF_PENCIL_SHIFT 16
1154 #define DF_ERROR 0x8000
1155 #define DF_HIGHLIGHT 0x4000
1156 #define DF_HIGHLIGHT_PENCIL 0x2000
1157 #define DF_IMMUTABLE 0x1000
1158 #define DF_PLAYAREA 0x0800
1159 #define DF_DIGIT_MASK 0x00FF
1161 struct game_drawstate {
1168 static int check_errors(game_state *state, int *errors)
1170 int w = state->par.w /*, a = w*w */;
1171 int W = w+2, A = W*W; /* the errors array is (w+2) square */
1172 int *clues = state->clues->clues;
1173 digit *grid = state->grid;
1174 int i, x, y, errs = FALSE;
1177 assert(w < lenof(tmp));
1180 for (i = 0; i < A; i++)
1183 for (y = 0; y < w; y++) {
1184 unsigned long mask = 0, errmask = 0;
1185 for (x = 0; x < w; x++) {
1186 unsigned long bit = 1UL << grid[y*w+x];
1187 errmask |= (mask & bit);
1191 if (mask != (1L << (w+1)) - (1L << 1)) {
1195 for (x = 0; x < w; x++)
1196 if (errmask & (1UL << grid[y*w+x]))
1197 errors[(y+1)*W+(x+1)] = TRUE;
1202 for (x = 0; x < w; x++) {
1203 unsigned long mask = 0, errmask = 0;
1204 for (y = 0; y < w; y++) {
1205 unsigned long bit = 1UL << grid[y*w+x];
1206 errmask |= (mask & bit);
1210 if (mask != (1 << (w+1)) - (1 << 1)) {
1214 for (y = 0; y < w; y++)
1215 if (errmask & (1UL << grid[y*w+x]))
1216 errors[(y+1)*W+(x+1)] = TRUE;
1221 for (i = 0; i < 4*w; i++) {
1222 int start, step, j, k, n, best;
1223 STARTSTEP(start, step, i, w);
1230 for (j = 0; j < w; j++) {
1231 int number = grid[start+j*step];
1233 break; /* can't tell what happens next */
1234 if (number > best) {
1240 if (n > clues[i] || (j == w && n < clues[i])) {
1243 CLUEPOS(x, y, i, w);
1244 errors[(y+1)*W+(x+1)] = TRUE;
1253 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1254 int x, int y, int button)
1256 int w = state->par.w;
1260 button &= ~MOD_MASK;
1265 if (tx >= 0 && tx < w && ty >= 0 && ty < w) {
1266 if (button == LEFT_BUTTON) {
1267 if (tx == ui->hx && ty == ui->hy &&
1268 ui->hshow && ui->hpencil == 0) {
1273 ui->hshow = !state->clues->immutable[ty*w+tx];
1277 return ""; /* UI activity occurred */
1279 if (button == RIGHT_BUTTON) {
1281 * Pencil-mode highlighting for non filled squares.
1283 if (state->grid[ty*w+tx] == 0) {
1284 if (tx == ui->hx && ty == ui->hy &&
1285 ui->hshow && ui->hpencil) {
1297 return ""; /* UI activity occurred */
1300 if (IS_CURSOR_MOVE(button)) {
1301 move_cursor(button, &ui->hx, &ui->hy, w, w, 0);
1302 ui->hshow = ui->hcursor = 1;
1306 (button == CURSOR_SELECT)) {
1307 ui->hpencil = 1 - ui->hpencil;
1313 ((button >= '0' && button <= '9' && button - '0' <= w) ||
1314 button == CURSOR_SELECT2 || button == '\b')) {
1315 int n = button - '0';
1316 if (button == CURSOR_SELECT2 || button == '\b')
1320 * Can't make pencil marks in a filled square. This can only
1321 * become highlighted if we're using cursor keys.
1323 if (ui->hpencil && state->grid[ui->hy*w+ui->hx])
1327 * Can't do anything to an immutable square.
1329 if (state->clues->immutable[ui->hy*w+ui->hx])
1332 sprintf(buf, "%c%d,%d,%d",
1333 (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n);
1335 if (!ui->hcursor) ui->hshow = 0;
1340 if (button == 'M' || button == 'm')
1346 static game_state *execute_move(game_state *from, char *move)
1348 int w = from->par.w, a = w*w;
1352 if (move[0] == 'S') {
1353 ret = dup_game(from);
1354 ret->completed = ret->cheated = TRUE;
1356 for (i = 0; i < a; i++) {
1357 if (move[i+1] < '1' || move[i+1] > '0'+w) {
1361 ret->grid[i] = move[i+1] - '0';
1365 if (move[a+1] != '\0') {
1371 } else if ((move[0] == 'P' || move[0] == 'R') &&
1372 sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
1373 x >= 0 && x < w && y >= 0 && y < w && n >= 0 && n <= w) {
1374 if (from->clues->immutable[y*w+x])
1377 ret = dup_game(from);
1378 if (move[0] == 'P' && n > 0) {
1379 ret->pencil[y*w+x] ^= 1L << n;
1381 ret->grid[y*w+x] = n;
1382 ret->pencil[y*w+x] = 0;
1384 if (!ret->completed && !check_errors(ret, NULL))
1385 ret->completed = TRUE;
1388 } else if (move[0] == 'M') {
1390 * Fill in absolutely all pencil marks everywhere. (I
1391 * wouldn't use this for actual play, but it's a handy
1392 * starting point when following through a set of
1393 * diagnostics output by the standalone solver.)
1395 ret = dup_game(from);
1396 for (i = 0; i < a; i++) {
1398 ret->pencil[i] = (1L << (w+1)) - (1L << 1);
1402 return NULL; /* couldn't parse move string */
1405 /* ----------------------------------------------------------------------
1409 #define SIZE(w) ((w) * TILESIZE + 2*BORDER)
1411 static void game_compute_size(game_params *params, int tilesize,
1414 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1415 struct { int tilesize; } ads, *ds = &ads;
1416 ads.tilesize = tilesize;
1418 *x = *y = SIZE(params->w);
1421 static void game_set_size(drawing *dr, game_drawstate *ds,
1422 game_params *params, int tilesize)
1424 ds->tilesize = tilesize;
1427 static float *game_colours(frontend *fe, int *ncolours)
1429 float *ret = snewn(3 * NCOLOURS, float);
1431 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1433 ret[COL_GRID * 3 + 0] = 0.0F;
1434 ret[COL_GRID * 3 + 1] = 0.0F;
1435 ret[COL_GRID * 3 + 2] = 0.0F;
1437 ret[COL_USER * 3 + 0] = 0.0F;
1438 ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1439 ret[COL_USER * 3 + 2] = 0.0F;
1441 ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0];
1442 ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1];
1443 ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2];
1445 ret[COL_ERROR * 3 + 0] = 1.0F;
1446 ret[COL_ERROR * 3 + 1] = 0.0F;
1447 ret[COL_ERROR * 3 + 2] = 0.0F;
1449 ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1450 ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1451 ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1453 *ncolours = NCOLOURS;
1457 static const char *const minus_signs[] = { "\xE2\x88\x92", "-" };
1458 static const char *const times_signs[] = { "\xC3\x97", "*" };
1459 static const char *const divide_signs[] = { "\xC3\xB7", "/" };
1461 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1463 int w = state->par.w /*, a = w*w */;
1464 struct game_drawstate *ds = snew(struct game_drawstate);
1468 ds->started = FALSE;
1469 ds->tiles = snewn((w+2)*(w+2), long);
1470 for (i = 0; i < (w+2)*(w+2); i++)
1472 ds->errtmp = snewn((w+2)*(w+2), int);
1477 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1484 static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues,
1485 int x, int y, long tile)
1487 int w = clues->w /* , a = w*w */;
1492 tx = BORDER + x * TILESIZE + 1;
1493 ty = BORDER + y * TILESIZE + 1;
1497 cw = tw = TILESIZE-1;
1498 ch = th = TILESIZE-1;
1500 clip(dr, cx, cy, cw, ch);
1502 /* background needs erasing */
1503 draw_rect(dr, cx, cy, cw, ch,
1504 (tile & DF_HIGHLIGHT) ? COL_HIGHLIGHT : COL_BACKGROUND);
1506 /* pencil-mode highlight */
1507 if (tile & DF_HIGHLIGHT_PENCIL) {
1511 coords[2] = cx+cw/2;
1514 coords[5] = cy+ch/2;
1515 draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1518 /* new number needs drawing? */
1519 if (tile & DF_DIGIT_MASK) {
1521 str[0] = (tile & DF_DIGIT_MASK) + '0';
1522 draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2, FONT_VARIABLE,
1523 (tile & DF_PLAYAREA ? TILESIZE/2 : TILESIZE*2/5),
1524 ALIGN_VCENTRE | ALIGN_HCENTRE,
1525 (tile & DF_ERROR) ? COL_ERROR :
1526 (x < 0 || y < 0 || x >= w || y >= w) ? COL_GRID :
1527 (tile & DF_IMMUTABLE) ? COL_GRID : COL_USER, str);
1532 int pw, ph, minph, pbest, fontsize;
1534 /* Count the pencil marks required. */
1535 for (i = 1, npencil = 0; i <= w; i++)
1536 if (tile & (1L << (i + DF_PENCIL_SHIFT)))
1543 * Determine the bounding rectangle within which we're going
1544 * to put the pencil marks.
1546 /* Start with the whole square */
1553 * We arrange our pencil marks in a grid layout, with
1554 * the number of rows and columns adjusted to allow the
1555 * maximum font size.
1557 * So now we work out what the grid size ought to be.
1562 for (pw = 3; pw < max(npencil,4); pw++) {
1565 ph = (npencil + pw - 1) / pw;
1566 ph = max(ph, minph);
1567 fw = (pr - pl) / (float)pw;
1568 fh = (pb - pt) / (float)ph;
1570 if (fs > bestsize) {
1577 ph = (npencil + pw - 1) / pw;
1578 ph = max(ph, minph);
1581 * Now we've got our grid dimensions, work out the pixel
1582 * size of a grid element, and round it to the nearest
1583 * pixel. (We don't want rounding errors to make the
1584 * grid look uneven at low pixel sizes.)
1586 fontsize = min((pr - pl) / pw, (pb - pt) / ph);
1589 * Centre the resulting figure in the square.
1591 pl = tx + (TILESIZE - fontsize * pw) / 2;
1592 pt = ty + (TILESIZE - fontsize * ph) / 2;
1595 * Now actually draw the pencil marks.
1597 for (i = 1, j = 0; i <= w; i++)
1598 if (tile & (1L << (i + DF_PENCIL_SHIFT))) {
1599 int dx = j % pw, dy = j / pw;
1603 draw_text(dr, pl + fontsize * (2*dx+1) / 2,
1604 pt + fontsize * (2*dy+1) / 2,
1605 FONT_VARIABLE, fontsize,
1606 ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
1614 draw_update(dr, cx, cy, cw, ch);
1617 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1618 game_state *state, int dir, game_ui *ui,
1619 float animtime, float flashtime)
1621 int w = state->par.w /*, a = w*w */;
1626 * The initial contents of the window are not guaranteed and
1627 * can vary with front ends. To be on the safe side, all
1628 * games should start by drawing a big background-colour
1629 * rectangle covering the whole window.
1631 draw_rect(dr, 0, 0, SIZE(w), SIZE(w), COL_BACKGROUND);
1634 * Big containing rectangle.
1636 draw_rect(dr, COORD(0), COORD(0),
1637 w*TILESIZE+1, w*TILESIZE+1,
1640 draw_update(dr, 0, 0, SIZE(w), SIZE(w));
1645 check_errors(state, ds->errtmp);
1650 for (i = 0; i < 4*w; i++) {
1651 long tile = state->clues->clues[i];
1656 CLUEPOS(x, y, i, w);
1658 if (ds->errtmp[(y+1)*(w+2)+(x+1)])
1661 if (ds->tiles[(y+1)*(w+2)+(x+1)] != tile) {
1662 ds->tiles[(y+1)*(w+2)+(x+1)] = tile;
1663 draw_tile(dr, ds, state->clues, x, y, tile);
1668 * Draw the main grid.
1670 for (y = 0; y < w; y++) {
1671 for (x = 0; x < w; x++) {
1672 long tile = DF_PLAYAREA;
1674 if (state->grid[y*w+x])
1675 tile |= state->grid[y*w+x];
1677 tile |= (long)state->pencil[y*w+x] << DF_PENCIL_SHIFT;
1679 if (ui->hshow && ui->hx == x && ui->hy == y)
1680 tile |= (ui->hpencil ? DF_HIGHLIGHT_PENCIL : DF_HIGHLIGHT);
1682 if (state->clues->immutable[y*w+x])
1683 tile |= DF_IMMUTABLE;
1685 if (flashtime > 0 &&
1686 (flashtime <= FLASH_TIME/3 ||
1687 flashtime >= FLASH_TIME*2/3))
1688 tile |= DF_HIGHLIGHT; /* completion flash */
1690 if (ds->errtmp[(y+1)*(w+2)+(x+1)])
1693 if (ds->tiles[(y+1)*(w+2)+(x+1)] != tile) {
1694 ds->tiles[(y+1)*(w+2)+(x+1)] = tile;
1695 draw_tile(dr, ds, state->clues, x, y, tile);
1701 static float game_anim_length(game_state *oldstate, game_state *newstate,
1702 int dir, game_ui *ui)
1707 static float game_flash_length(game_state *oldstate, game_state *newstate,
1708 int dir, game_ui *ui)
1710 if (!oldstate->completed && newstate->completed &&
1711 !oldstate->cheated && !newstate->cheated)
1716 static int game_timing_state(game_state *state, game_ui *ui)
1718 if (state->completed)
1723 static void game_print_size(game_params *params, float *x, float *y)
1728 * We use 9mm squares by default, like Solo.
1730 game_compute_size(params, 900, &pw, &ph);
1735 static void game_print(drawing *dr, game_state *state, int tilesize)
1737 int w = state->par.w;
1738 int ink = print_mono_colour(dr, 0);
1741 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1742 game_drawstate ads, *ds = &ads;
1743 game_set_size(dr, ds, NULL, tilesize);
1748 print_line_width(dr, 3 * TILESIZE / 40);
1749 draw_rect_outline(dr, BORDER, BORDER, w*TILESIZE, w*TILESIZE, ink);
1754 for (x = 1; x < w; x++) {
1755 print_line_width(dr, TILESIZE / 40);
1756 draw_line(dr, BORDER+x*TILESIZE, BORDER,
1757 BORDER+x*TILESIZE, BORDER+w*TILESIZE, ink);
1759 for (y = 1; y < w; y++) {
1760 print_line_width(dr, TILESIZE / 40);
1761 draw_line(dr, BORDER, BORDER+y*TILESIZE,
1762 BORDER+w*TILESIZE, BORDER+y*TILESIZE, ink);
1768 for (i = 0; i < 4*w; i++) {
1771 if (!state->clues->clues[i])
1774 CLUEPOS(x, y, i, w);
1776 sprintf (str, "%d", state->clues->clues[i]);
1778 draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2,
1779 BORDER + y*TILESIZE + TILESIZE/2,
1780 FONT_VARIABLE, TILESIZE/2,
1781 ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
1785 * Numbers for the solution, if any.
1787 for (y = 0; y < w; y++)
1788 for (x = 0; x < w; x++)
1789 if (state->grid[y*w+x]) {
1792 str[0] = state->grid[y*w+x] + '0';
1793 draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2,
1794 BORDER + y*TILESIZE + TILESIZE/2,
1795 FONT_VARIABLE, TILESIZE/2,
1796 ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
1801 #define thegame towers
1804 const struct game thegame = {
1805 "Towers", "games.towers", "towers",
1812 TRUE, game_configure, custom_params,
1820 TRUE, game_can_format_as_text_now, game_text_format,
1828 PREFERRED_TILESIZE, game_compute_size, game_set_size,
1831 game_free_drawstate,
1835 TRUE, FALSE, game_print_size, game_print,
1836 FALSE, /* wants_statusbar */
1837 FALSE, game_timing_state,
1838 REQUIRE_RBUTTON | REQUIRE_NUMPAD, /* flags */
1841 #ifdef STANDALONE_SOLVER
1845 int main(int argc, char **argv)
1849 char *id = NULL, *desc, *err;
1851 int ret, diff, really_show_working = FALSE;
1853 while (--argc > 0) {
1855 if (!strcmp(p, "-v")) {
1856 really_show_working = TRUE;
1857 } else if (!strcmp(p, "-g")) {
1859 } else if (*p == '-') {
1860 fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
1868 fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
1872 desc = strchr(id, ':');
1874 fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
1879 p = default_params();
1880 decode_params(p, id);
1881 err = validate_desc(p, desc);
1883 fprintf(stderr, "%s: %s\n", argv[0], err);
1886 s = new_game(NULL, p, desc);
1889 * When solving an Easy puzzle, we don't want to bother the
1890 * user with Hard-level deductions. For this reason, we grade
1891 * the puzzle internally before doing anything else.
1893 ret = -1; /* placate optimiser */
1894 solver_show_working = FALSE;
1895 for (diff = 0; diff < DIFFCOUNT; diff++) {
1896 memcpy(s->grid, s->clues->immutable, p->w * p->w);
1897 ret = solver(p->w, s->clues->clues, s->grid, diff);
1902 if (diff == DIFFCOUNT) {
1904 printf("Difficulty rating: ambiguous\n");
1906 printf("Unable to find a unique solution\n");
1909 if (ret == diff_impossible)
1910 printf("Difficulty rating: impossible (no solution exists)\n");
1912 printf("Difficulty rating: %s\n", towers_diffnames[ret]);
1914 solver_show_working = really_show_working;
1915 memcpy(s->grid, s->clues->immutable, p->w * p->w);
1916 ret = solver(p->w, s->clues->clues, s->grid, diff);
1918 printf("Puzzle is inconsistent\n");
1920 fputs(game_text_format(s), stdout);
1929 /* vim: set shiftwidth=4 tabstop=8: */