chiark / gitweb /
Support for loading games in Javascript puzzles.
[sgt-puzzles.git] / towers.c
1 /*
2  * towers.c: the puzzle also known as 'Skyscrapers'.
3  *
4  * Possible future work:
5  *
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
10  *       word to live in
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.
19  */
20
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <assert.h>
25 #include <ctype.h>
26 #include <math.h>
27
28 #include "puzzles.h"
29 #include "latin.h"
30
31 /*
32  * Difficulty levels. I do some macro ickery here to ensure that my
33  * enum and the various forms of my name list always match up.
34  */
35 #define DIFFLIST(A) \
36     A(EASY,Easy,solver_easy,e) \
37     A(HARD,Hard,solver_hard,h) \
38     A(EXTREME,Extreme,NULL,x) \
39     A(UNREASONABLE,Unreasonable,NULL,u)
40 #define ENUM(upper,title,func,lower) DIFF_ ## upper,
41 #define TITLE(upper,title,func,lower) #title,
42 #define ENCODE(upper,title,func,lower) #lower
43 #define CONFIG(upper,title,func,lower) ":" #title
44 enum { DIFFLIST(ENUM) DIFFCOUNT };
45 static char const *const towers_diffnames[] = { DIFFLIST(TITLE) };
46 static char const towers_diffchars[] = DIFFLIST(ENCODE);
47 #define DIFFCONFIG DIFFLIST(CONFIG)
48
49 enum {
50     COL_BACKGROUND,
51     COL_GRID,
52     COL_USER,
53     COL_HIGHLIGHT,
54     COL_ERROR,
55     COL_PENCIL,
56     COL_DONE,
57     NCOLOURS
58 };
59
60 struct game_params {
61     int w, diff;
62 };
63
64 struct clues {
65     int refcount;
66     int w;
67     /*
68      * An array of 4w integers, of which:
69      *  - the first w run across the top
70      *  - the next w across the bottom
71      *  - the third w down the left
72      *  - the last w down the right.
73      */
74     int *clues;
75
76     /*
77      * An array of w*w digits.
78      */
79     digit *immutable;
80 };
81
82 /*
83  * Macros to compute clue indices and coordinates.
84  */
85 #define STARTSTEP(start, step, index, w) do { \
86     if (index < w) \
87         start = index, step = w; \
88     else if (index < 2*w) \
89         start = (w-1)*w+(index-w), step = -w; \
90     else if (index < 3*w) \
91         start = w*(index-2*w), step = 1; \
92     else \
93         start = w*(index-3*w)+(w-1), step = -1; \
94 } while (0)
95 #define CSTARTSTEP(start, step, index, w) \
96     STARTSTEP(start, step, (((index)+2*w)%(4*w)), w)
97 #define CLUEPOS(x, y, index, w) do { \
98     if (index < w) \
99         x = index, y = -1; \
100     else if (index < 2*w) \
101         x = index-w, y = w; \
102     else if (index < 3*w) \
103         x = -1, y = index-2*w; \
104     else \
105         x = w, y = index-3*w; \
106 } while (0)
107
108 #ifdef STANDALONE_SOLVER
109 static const char *const cluepos[] = {
110     "above column", "below column", "left of row", "right of row"
111 };
112 #endif
113
114 struct game_state {
115     game_params par;
116     struct clues *clues;
117     unsigned char *clues_done;
118     digit *grid;
119     int *pencil;                       /* bitmaps using bits 1<<1..1<<n */
120     int completed, cheated;
121 };
122
123 static game_params *default_params(void)
124 {
125     game_params *ret = snew(game_params);
126
127     ret->w = 5;
128     ret->diff = DIFF_EASY;
129
130     return ret;
131 }
132
133 const static struct game_params towers_presets[] = {
134     {  4, DIFF_EASY         },
135     {  5, DIFF_EASY         },
136     {  5, DIFF_HARD         },
137     {  6, DIFF_EASY         },
138     {  6, DIFF_HARD         },
139     {  6, DIFF_EXTREME      },
140     {  6, DIFF_UNREASONABLE },
141 };
142
143 static int game_fetch_preset(int i, char **name, game_params **params)
144 {
145     game_params *ret;
146     char buf[80];
147
148     if (i < 0 || i >= lenof(towers_presets))
149         return FALSE;
150
151     ret = snew(game_params);
152     *ret = towers_presets[i]; /* structure copy */
153
154     sprintf(buf, "%dx%d %s", ret->w, ret->w, towers_diffnames[ret->diff]);
155
156     *name = dupstr(buf);
157     *params = ret;
158     return TRUE;
159 }
160
161 static void free_params(game_params *params)
162 {
163     sfree(params);
164 }
165
166 static game_params *dup_params(const game_params *params)
167 {
168     game_params *ret = snew(game_params);
169     *ret = *params;                    /* structure copy */
170     return ret;
171 }
172
173 static void decode_params(game_params *params, char const *string)
174 {
175     char const *p = string;
176
177     params->w = atoi(p);
178     while (*p && isdigit((unsigned char)*p)) p++;
179
180     if (*p == 'd') {
181         int i;
182         p++;
183         params->diff = DIFFCOUNT+1; /* ...which is invalid */
184         if (*p) {
185             for (i = 0; i < DIFFCOUNT; i++) {
186                 if (*p == towers_diffchars[i])
187                     params->diff = i;
188             }
189             p++;
190         }
191     }
192 }
193
194 static char *encode_params(const game_params *params, int full)
195 {
196     char ret[80];
197
198     sprintf(ret, "%d", params->w);
199     if (full)
200         sprintf(ret + strlen(ret), "d%c", towers_diffchars[params->diff]);
201
202     return dupstr(ret);
203 }
204
205 static config_item *game_configure(const game_params *params)
206 {
207     config_item *ret;
208     char buf[80];
209
210     ret = snewn(3, config_item);
211
212     ret[0].name = "Grid size";
213     ret[0].type = C_STRING;
214     sprintf(buf, "%d", params->w);
215     ret[0].sval = dupstr(buf);
216     ret[0].ival = 0;
217
218     ret[1].name = "Difficulty";
219     ret[1].type = C_CHOICES;
220     ret[1].sval = DIFFCONFIG;
221     ret[1].ival = params->diff;
222
223     ret[2].name = NULL;
224     ret[2].type = C_END;
225     ret[2].sval = NULL;
226     ret[2].ival = 0;
227
228     return ret;
229 }
230
231 static game_params *custom_params(const config_item *cfg)
232 {
233     game_params *ret = snew(game_params);
234
235     ret->w = atoi(cfg[0].sval);
236     ret->diff = cfg[1].ival;
237
238     return ret;
239 }
240
241 static char *validate_params(const game_params *params, int full)
242 {
243     if (params->w < 3 || params->w > 9)
244         return "Grid size must be between 3 and 9";
245     if (params->diff >= DIFFCOUNT)
246         return "Unknown difficulty rating";
247     return NULL;
248 }
249
250 /* ----------------------------------------------------------------------
251  * Solver.
252  */
253
254 struct solver_ctx {
255     int w, diff;
256     int started;
257     int *clues;
258     long *iscratch;
259     int *dscratch;
260 };
261
262 static int solver_easy(struct latin_solver *solver, void *vctx)
263 {
264     struct solver_ctx *ctx = (struct solver_ctx *)vctx;
265     int w = ctx->w;
266     int c, i, j, n, m, furthest;
267     int start, step, cstart, cstep, clue, pos, cpos;
268     int ret = 0;
269 #ifdef STANDALONE_SOLVER
270     char prefix[256];
271 #endif
272
273     if (!ctx->started) {
274         ctx->started = TRUE;
275         /*
276          * One-off loop to help get started: when a pair of facing
277          * clues sum to w+1, it must mean that the row consists of
278          * two increasing sequences back to back, so we can
279          * immediately place the highest digit by knowing the
280          * lengths of those two sequences.
281          */
282         for (c = 0; c < 3*w; c = (c == w-1 ? 2*w : c+1)) {
283             int c2 = c + w;
284
285             if (ctx->clues[c] && ctx->clues[c2] &&
286                 ctx->clues[c] + ctx->clues[c2] == w+1) {
287                 STARTSTEP(start, step, c, w);
288                 CSTARTSTEP(cstart, cstep, c, w);
289                 pos = start + (ctx->clues[c]-1)*step;
290                 cpos = cstart + (ctx->clues[c]-1)*cstep;
291                 if (solver->cube[cpos*w+w-1]) {
292 #ifdef STANDALONE_SOLVER
293                     if (solver_show_working) {
294                         printf("%*sfacing clues on %s %d are maximal:\n",
295                                solver_recurse_depth*4, "",
296                                c>=2*w ? "row" : "column", c % w + 1);
297                         printf("%*s  placing %d at (%d,%d)\n",
298                                solver_recurse_depth*4, "",
299                                w, pos%w+1, pos/w+1);
300                     }
301 #endif
302                     latin_solver_place(solver, pos%w, pos/w, w);
303                     ret = 1;
304                 } else {
305                     ret = -1;
306                 }
307             }
308         }
309
310         if (ret)
311             return ret;
312     }
313
314     /*
315      * Go over every clue doing reasonably simple heuristic
316      * deductions.
317      */
318     for (c = 0; c < 4*w; c++) {
319         clue = ctx->clues[c];
320         if (!clue)
321             continue;
322         STARTSTEP(start, step, c, w);
323         CSTARTSTEP(cstart, cstep, c, w);
324
325         /* Find the location of each number in the row. */
326         for (i = 0; i < w; i++)
327             ctx->dscratch[i] = w;
328         for (i = 0; i < w; i++)
329             if (solver->grid[start+i*step])
330                 ctx->dscratch[solver->grid[start+i*step]-1] = i;
331
332         n = m = 0;
333         furthest = w;
334         for (i = w; i >= 1; i--) {
335             if (ctx->dscratch[i-1] == w) {
336                 break;
337             } else if (ctx->dscratch[i-1] < furthest) {
338                 furthest = ctx->dscratch[i-1];
339                 m = i;
340                 n++;
341             }
342         }
343         if (clue == n+1 && furthest > 1) {
344 #ifdef STANDALONE_SOLVER
345             if (solver_show_working)
346                 sprintf(prefix, "%*sclue %s %d is nearly filled:\n",
347                         solver_recurse_depth*4, "",
348                         cluepos[c/w], c%w+1);
349             else
350                 prefix[0] = '\0';              /* placate optimiser */
351 #endif
352             /*
353              * We can already see an increasing sequence of the very
354              * highest numbers, of length one less than that
355              * specified in the clue. All of those numbers _must_ be
356              * part of the clue sequence, so the number right next
357              * to the clue must be the final one - i.e. it must be
358              * bigger than any of the numbers between it and m. This
359              * allows us to rule out small numbers in that square.
360              *
361              * (This is a generalisation of the obvious deduction
362              * that when you see a clue saying 1, it must be right
363              * next to the largest possible number; and similarly,
364              * when you see a clue saying 2 opposite that, it must
365              * be right next to the second-largest.)
366              */
367             j = furthest-1;  /* number of small numbers we can rule out */
368             for (i = 1; i <= w && j > 0; i++) {
369                 if (ctx->dscratch[i-1] < w && ctx->dscratch[i-1] >= furthest)
370                     continue;          /* skip this number, it's elsewhere */
371                 j--;
372                 if (solver->cube[cstart*w+i-1]) {
373 #ifdef STANDALONE_SOLVER
374                     if (solver_show_working) {
375                         printf("%s%*s  ruling out %d at (%d,%d)\n",
376                                prefix, solver_recurse_depth*4, "",
377                                i, start%w+1, start/w+1);
378                         prefix[0] = '\0';
379                     }
380 #endif
381                     solver->cube[cstart*w+i-1] = 0;
382                     ret = 1;
383                 }
384             }
385         }
386
387         if (ret)
388             return ret;
389
390 #ifdef STANDALONE_SOLVER
391             if (solver_show_working)
392                 sprintf(prefix, "%*slower bounds for clue %s %d:\n",
393                         solver_recurse_depth*4, "",
394                         cluepos[c/w], c%w+1);
395             else
396                 prefix[0] = '\0';              /* placate optimiser */
397 #endif
398
399         i = 0;
400         for (n = w; n > 0; n--) {
401             /*
402              * The largest number cannot occur in the first (clue-1)
403              * squares of the row, or else there wouldn't be space
404              * for a sufficiently long increasing sequence which it
405              * terminated. The second-largest number (not counting
406              * any that are known to be on the far side of a larger
407              * number and hence excluded from this sequence) cannot
408              * occur in the first (clue-2) squares, similarly, and
409              * so on.
410              */
411
412             if (ctx->dscratch[n-1] < w) {
413                 for (m = n+1; m < w; m++)
414                     if (ctx->dscratch[m] < ctx->dscratch[n-1])
415                         break;
416                 if (m < w)
417                     continue;          /* this number doesn't count */
418             }
419
420             for (j = 0; j < clue - i - 1; j++)
421                 if (solver->cube[(cstart + j*cstep)*w+n-1]) {
422 #ifdef STANDALONE_SOLVER
423                     if (solver_show_working) {
424                         int pos = start+j*step;
425                         printf("%s%*s  ruling out %d at (%d,%d)\n",
426                                prefix, solver_recurse_depth*4, "",
427                                n, pos%w+1, pos/w+1);
428                         prefix[0] = '\0';
429                     }
430 #endif
431                     solver->cube[(cstart + j*cstep)*w+n-1] = 0;
432                     ret = 1;
433                 }
434             i++;
435         }
436     }
437
438     if (ret)
439         return ret;
440
441     return 0;
442 }
443
444 static int solver_hard(struct latin_solver *solver, void *vctx)
445 {
446     struct solver_ctx *ctx = (struct solver_ctx *)vctx;
447     int w = ctx->w;
448     int c, i, j, n, best, clue, start, step, ret;
449     long bitmap;
450 #ifdef STANDALONE_SOLVER
451     char prefix[256];
452 #endif
453
454     /*
455      * Go over every clue analysing all possibilities.
456      */
457     for (c = 0; c < 4*w; c++) {
458         clue = ctx->clues[c];
459         if (!clue)
460             continue;
461         CSTARTSTEP(start, step, c, w);
462
463         for (i = 0; i < w; i++)
464             ctx->iscratch[i] = 0;
465
466         /*
467          * Instead of a tedious physical recursion, I iterate in the
468          * scratch array through all possibilities. At any given
469          * moment, i indexes the element of the box that will next
470          * be incremented.
471          */
472         i = 0;
473         ctx->dscratch[i] = 0;
474         best = n = 0;
475         bitmap = 0;
476
477         while (1) {
478             if (i < w) {
479                 /*
480                  * Find the next valid value for cell i.
481                  */
482                 int limit = (n == clue ? best : w);
483                 int pos = start + step * i;
484                 for (j = ctx->dscratch[i] + 1; j <= limit; j++) {
485                     if (bitmap & (1L << j))
486                         continue;      /* used this one already */
487                     if (!solver->cube[pos*w+j-1])
488                         continue;      /* ruled out already */
489
490                     /* Found one. */
491                     break;
492                 }
493
494                 if (j > limit) {
495                     /* No valid values left; drop back. */
496                     i--;
497                     if (i < 0)
498                         break;         /* overall iteration is finished */
499                     bitmap &= ~(1L << ctx->dscratch[i]);
500                     if (ctx->dscratch[i] == best) {
501                         n--;
502                         best = 0;
503                         for (j = 0; j < i; j++)
504                             if (best < ctx->dscratch[j])
505                                 best = ctx->dscratch[j];
506                     }
507                 } else {
508                     /* Got a valid value; store it and move on. */
509                     bitmap |= 1L << j;
510                     ctx->dscratch[i++] = j;
511                     if (j > best) {
512                         best = j;
513                         n++;
514                     }
515                     ctx->dscratch[i] = 0;
516                 }
517             } else {
518                 if (n == clue) {
519                     for (j = 0; j < w; j++)
520                         ctx->iscratch[j] |= 1L << ctx->dscratch[j];
521                 }
522                 i--;
523                 bitmap &= ~(1L << ctx->dscratch[i]);
524                 if (ctx->dscratch[i] == best) {
525                     n--;
526                     best = 0;
527                     for (j = 0; j < i; j++)
528                         if (best < ctx->dscratch[j])
529                             best = ctx->dscratch[j];
530                 }
531             }
532         }
533
534 #ifdef STANDALONE_SOLVER
535         if (solver_show_working)
536             sprintf(prefix, "%*sexhaustive analysis of clue %s %d:\n",
537                     solver_recurse_depth*4, "",
538                     cluepos[c/w], c%w+1);
539         else
540             prefix[0] = '\0';          /* placate optimiser */
541 #endif
542
543         ret = 0;
544
545         for (i = 0; i < w; i++) {
546             int pos = start + step * i;
547             for (j = 1; j <= w; j++) {
548                 if (solver->cube[pos*w+j-1] &&
549                     !(ctx->iscratch[i] & (1L << j))) {
550 #ifdef STANDALONE_SOLVER
551                     if (solver_show_working) {
552                         printf("%s%*s  ruling out %d at (%d,%d)\n",
553                                prefix, solver_recurse_depth*4, "",
554                                j, pos/w+1, pos%w+1);
555                         prefix[0] = '\0';
556                     }
557 #endif
558                     solver->cube[pos*w+j-1] = 0;
559                     ret = 1;
560                 }
561             }
562
563             /*
564              * Once we find one clue we can do something with in
565              * this way, revert to trying easier deductions, so as
566              * not to generate solver diagnostics that make the
567              * problem look harder than it is.
568              */
569             if (ret)
570                 return ret;
571         }
572     }
573
574     return 0;
575 }
576
577 #define SOLVER(upper,title,func,lower) func,
578 static usersolver_t const towers_solvers[] = { DIFFLIST(SOLVER) };
579
580 static int solver(int w, int *clues, digit *soln, int maxdiff)
581 {
582     int ret;
583     struct solver_ctx ctx;
584
585     ctx.w = w;
586     ctx.diff = maxdiff;
587     ctx.clues = clues;
588     ctx.started = FALSE;
589     ctx.iscratch = snewn(w, long);
590     ctx.dscratch = snewn(w+1, int);
591
592     ret = latin_solver(soln, w, maxdiff,
593                        DIFF_EASY, DIFF_HARD, DIFF_EXTREME,
594                        DIFF_EXTREME, DIFF_UNREASONABLE,
595                        towers_solvers, &ctx, NULL, NULL);
596
597     sfree(ctx.iscratch);
598     sfree(ctx.dscratch);
599
600     return ret;
601 }
602
603 /* ----------------------------------------------------------------------
604  * Grid generation.
605  */
606
607 static char *new_game_desc(const game_params *params, random_state *rs,
608                            char **aux, int interactive)
609 {
610     int w = params->w, a = w*w;
611     digit *grid, *soln, *soln2;
612     int *clues, *order;
613     int i, ret;
614     int diff = params->diff;
615     char *desc, *p;
616
617     /*
618      * Difficulty exceptions: some combinations of size and
619      * difficulty cannot be satisfied, because all puzzles of at
620      * most that difficulty are actually even easier.
621      *
622      * Remember to re-test this whenever a change is made to the
623      * solver logic!
624      *
625      * I tested it using the following shell command:
626
627 for d in e h x u; do
628   for i in {3..9}; do
629     echo -n "./towers --generate 1 ${i}d${d}: "
630     perl -e 'alarm 30; exec @ARGV' ./towers --generate 1 ${i}d${d} >/dev/null \
631       && echo ok
632   done
633 done
634
635      * Of course, it's better to do that after taking the exceptions
636      * _out_, so as to detect exceptions that should be removed as
637      * well as those which should be added.
638      */
639     if (diff > DIFF_HARD && w <= 3)
640         diff = DIFF_HARD;
641
642     grid = NULL;
643     clues = snewn(4*w, int);
644     soln = snewn(a, digit);
645     soln2 = snewn(a, digit);
646     order = snewn(max(4*w,a), int);
647
648     while (1) {
649         /*
650          * Construct a latin square to be the solution.
651          */
652         sfree(grid);
653         grid = latin_generate(w, rs);
654
655         /*
656          * Fill in the clues.
657          */
658         for (i = 0; i < 4*w; i++) {
659             int start, step, j, k, best;
660             STARTSTEP(start, step, i, w);
661             k = best = 0;
662             for (j = 0; j < w; j++) {
663                 if (grid[start+j*step] > best) {
664                     best = grid[start+j*step];
665                     k++;
666                 }
667             }
668             clues[i] = k;
669         }
670
671         /*
672          * Remove the grid numbers and then the clues, one by one,
673          * for as long as the game remains soluble at the given
674          * difficulty.
675          */
676         memcpy(soln, grid, a);
677
678         if (diff == DIFF_EASY && w <= 5) {
679             /*
680              * Special case: for Easy-mode grids that are small
681              * enough, it's nice to be able to find completely empty
682              * grids.
683              */
684             memset(soln2, 0, a);
685             ret = solver(w, clues, soln2, diff);
686             if (ret > diff)
687                 continue;
688         }
689
690         for (i = 0; i < a; i++)
691             order[i] = i;
692         shuffle(order, a, sizeof(*order), rs);
693         for (i = 0; i < a; i++) {
694             int j = order[i];
695
696             memcpy(soln2, grid, a);
697             soln2[j] = 0;
698             ret = solver(w, clues, soln2, diff);
699             if (ret <= diff)
700                 grid[j] = 0;
701         }
702
703         if (diff > DIFF_EASY) {        /* leave all clues on Easy mode */
704             for (i = 0; i < 4*w; i++)
705                 order[i] = i;
706             shuffle(order, 4*w, sizeof(*order), rs);
707             for (i = 0; i < 4*w; i++) {
708                 int j = order[i];
709                 int clue = clues[j];
710
711                 memcpy(soln2, grid, a);
712                 clues[j] = 0;
713                 ret = solver(w, clues, soln2, diff);
714                 if (ret > diff)
715                     clues[j] = clue;
716             }
717         }
718
719         /*
720          * See if the game can be solved at the specified difficulty
721          * level, but not at the one below.
722          */
723         memcpy(soln2, grid, a);
724         ret = solver(w, clues, soln2, diff);
725         if (ret != diff)
726             continue;                  /* go round again */
727
728         /*
729          * We've got a usable puzzle!
730          */
731         break;
732     }
733
734     /*
735      * Encode the puzzle description.
736      */
737     desc = snewn(40*a, char);
738     p = desc;
739     for (i = 0; i < 4*w; i++) {
740         if (i)
741             *p++ = '/';
742         if (clues[i])
743             p += sprintf(p, "%d", clues[i]);
744     }
745     for (i = 0; i < a; i++)
746         if (grid[i])
747             break;
748     if (i < a) {
749         int run = 0;
750
751         *p++ = ',';
752
753         for (i = 0; i <= a; i++) {
754             int n = (i < a ? grid[i] : -1);
755
756             if (!n)
757                 run++;
758             else {
759                 if (run) {
760                     while (run > 0) {
761                         int thisrun = min(run, 26);
762                         *p++ = thisrun - 1 + 'a';
763                         run -= thisrun;
764                     }
765                 } else {
766                     /*
767                      * If there's a number in the very top left or
768                      * bottom right, there's no point putting an
769                      * unnecessary _ before or after it.
770                      */
771                     if (i > 0 && n > 0)
772                         *p++ = '_';
773                 }
774                 if (n > 0)
775                     p += sprintf(p, "%d", n);
776                 run = 0;
777             }
778         }
779     }
780     *p++ = '\0';
781     desc = sresize(desc, p - desc, char);
782
783     /*
784      * Encode the solution.
785      */
786     *aux = snewn(a+2, char);
787     (*aux)[0] = 'S';
788     for (i = 0; i < a; i++)
789         (*aux)[i+1] = '0' + soln[i];
790     (*aux)[a+1] = '\0';
791
792     sfree(grid);
793     sfree(clues);
794     sfree(soln);
795     sfree(soln2);
796     sfree(order);
797
798     return desc;
799 }
800
801 /* ----------------------------------------------------------------------
802  * Gameplay.
803  */
804
805 static char *validate_desc(const game_params *params, const char *desc)
806 {
807     int w = params->w, a = w*w;
808     const char *p = desc;
809     int i, clue;
810
811     /*
812      * Verify that the right number of clues are given, and that
813      * they're in range.
814      */
815     for (i = 0; i < 4*w; i++) {
816         if (!*p)
817             return "Too few clues for grid size";
818
819         if (i > 0) {
820             if (*p != '/')
821                 return "Expected commas between clues";
822             p++;
823         }
824
825         if (isdigit((unsigned char)*p)) {
826             clue = atoi(p);
827             while (*p && isdigit((unsigned char)*p)) p++;
828
829             if (clue <= 0 || clue > w)
830                 return "Clue number out of range";
831         }
832     }
833     if (*p == '/')
834         return "Too many clues for grid size";
835
836     if (*p == ',') {
837         /*
838          * Verify that the right amount of grid data is given, and
839          * that any grid elements provided are in range.
840          */
841         int squares = 0;
842
843         p++;
844         while (*p) {
845             int c = *p++;
846             if (c >= 'a' && c <= 'z') {
847                 squares += c - 'a' + 1;
848             } else if (c == '_') {
849                 /* do nothing */;
850             } else if (c > '0' && c <= '9') {
851                 int val = atoi(p-1);
852                 if (val < 1 || val > w)
853                     return "Out-of-range number in grid description";
854                 squares++;
855                 while (*p && isdigit((unsigned char)*p)) p++;
856             } else
857                 return "Invalid character in game description";
858         }
859
860         if (squares < a)
861             return "Not enough data to fill grid";
862
863         if (squares > a)
864             return "Too much data to fit in grid";
865     }
866
867     return NULL;
868 }
869
870 static game_state *new_game(midend *me, const game_params *params,
871                             const char *desc)
872 {
873     int w = params->w, a = w*w;
874     game_state *state = snew(game_state);
875     const char *p = desc;
876     int i;
877
878     state->par = *params;              /* structure copy */
879     state->clues = snew(struct clues);
880     state->clues->refcount = 1;
881     state->clues->w = w;
882     state->clues->clues = snewn(4*w, int);
883     state->clues->immutable = snewn(a, digit);
884     state->grid = snewn(a, digit);
885     state->clues_done = snewn(4*w, unsigned char);
886     state->pencil = snewn(a, int);
887
888     for (i = 0; i < a; i++) {
889         state->grid[i] = 0;
890         state->pencil[i] = 0;
891     }
892
893     memset(state->clues->immutable, 0, a);
894     memset(state->clues_done, 0, 4*w*sizeof(unsigned char));
895
896     for (i = 0; i < 4*w; i++) {
897         if (i > 0) {
898             assert(*p == '/');
899             p++;
900         }
901         if (*p && isdigit((unsigned char)*p)) {
902             state->clues->clues[i] = atoi(p);
903             while (*p && isdigit((unsigned char)*p)) p++;
904         } else
905             state->clues->clues[i] = 0;
906     }
907
908     if (*p == ',') {
909         int pos = 0;
910         p++;
911         while (*p) {
912             int c = *p++;
913             if (c >= 'a' && c <= 'z') {
914                 pos += c - 'a' + 1;
915             } else if (c == '_') {
916                 /* do nothing */;
917             } else if (c > '0' && c <= '9') {
918                 int val = atoi(p-1);
919                 assert(val >= 1 && val <= w);
920                 assert(pos < a);
921                 state->grid[pos] = state->clues->immutable[pos] = val;
922                 pos++;
923                 while (*p && isdigit((unsigned char)*p)) p++;
924             } else
925                 assert(!"Corrupt game description");
926         }
927         assert(pos == a);
928     }
929     assert(!*p);
930
931     state->completed = state->cheated = FALSE;
932
933     return state;
934 }
935
936 static game_state *dup_game(const game_state *state)
937 {
938     int w = state->par.w, a = w*w;
939     game_state *ret = snew(game_state);
940
941     ret->par = state->par;             /* structure copy */
942
943     ret->clues = state->clues;
944     ret->clues->refcount++;
945
946     ret->grid = snewn(a, digit);
947     ret->pencil = snewn(a, int);
948     ret->clues_done = snewn(4*w, unsigned char);
949     memcpy(ret->grid, state->grid, a*sizeof(digit));
950     memcpy(ret->pencil, state->pencil, a*sizeof(int));
951     memcpy(ret->clues_done, state->clues_done, 4*w*sizeof(unsigned char));
952
953     ret->completed = state->completed;
954     ret->cheated = state->cheated;
955
956     return ret;
957 }
958
959 static void free_game(game_state *state)
960 {
961     sfree(state->grid);
962     sfree(state->pencil);
963     sfree(state->clues_done);
964     if (--state->clues->refcount <= 0) {
965         sfree(state->clues->immutable);
966         sfree(state->clues->clues);
967         sfree(state->clues);
968     }
969     sfree(state);
970 }
971
972 static char *solve_game(const game_state *state, const game_state *currstate,
973                         const char *aux, char **error)
974 {
975     int w = state->par.w, a = w*w;
976     int i, ret;
977     digit *soln;
978     char *out;
979
980     if (aux)
981         return dupstr(aux);
982
983     soln = snewn(a, digit);
984     memcpy(soln, state->clues->immutable, a);
985
986     ret = solver(w, state->clues->clues, soln, DIFFCOUNT-1);
987
988     if (ret == diff_impossible) {
989         *error = "No solution exists for this puzzle";
990         out = NULL;
991     } else if (ret == diff_ambiguous) {
992         *error = "Multiple solutions exist for this puzzle";
993         out = NULL;
994     } else {
995         out = snewn(a+2, char);
996         out[0] = 'S';
997         for (i = 0; i < a; i++)
998             out[i+1] = '0' + soln[i];
999         out[a+1] = '\0';
1000     }
1001
1002     sfree(soln);
1003     return out;
1004 }
1005
1006 static int game_can_format_as_text_now(const game_params *params)
1007 {
1008     return TRUE;
1009 }
1010
1011 static char *game_text_format(const game_state *state)
1012 {
1013     int w = state->par.w /* , a = w*w */;
1014     char *ret;
1015     char *p;
1016     int x, y;
1017     int total;
1018
1019     /*
1020      * We have:
1021      *  - a top clue row, consisting of three spaces, then w clue
1022      *    digits with spaces between (total 2*w+3 chars including
1023      *    newline)
1024      *  - a blank line (one newline)
1025      *  - w main rows, consisting of a left clue digit, two spaces,
1026      *    w grid digits with spaces between, two spaces and a right
1027      *    clue digit (total 2*w+6 chars each including newline)
1028      *  - a blank line (one newline)
1029      *  - a bottom clue row (same as top clue row)
1030      *  - terminating NUL.
1031      *
1032      * Total size is therefore 2*(2*w+3) + 2 + w*(2*w+6) + 1
1033      * = 2w^2+10w+9.
1034      */
1035     total = 2*w*w + 10*w + 9;
1036     ret = snewn(total, char);
1037     p = ret;
1038
1039     /* Top clue row. */
1040     *p++ = ' '; *p++ = ' ';
1041     for (x = 0; x < w; x++) {
1042         *p++ = ' ';
1043         *p++ = (state->clues->clues[x] ? '0' + state->clues->clues[x] : ' ');
1044     }
1045     *p++ = '\n';
1046
1047     /* Blank line. */
1048     *p++ = '\n';
1049
1050     /* Main grid. */
1051     for (y = 0; y < w; y++) {
1052         *p++ = (state->clues->clues[y+2*w] ? '0' + state->clues->clues[y+2*w] :
1053                 ' ');
1054         *p++ = ' ';
1055         for (x = 0; x < w; x++) {
1056             *p++ = ' ';
1057             *p++ = (state->grid[y*w+x] ? '0' + state->grid[y*w+x] : ' ');
1058         }
1059         *p++ = ' '; *p++ = ' ';
1060         *p++ = (state->clues->clues[y+3*w] ? '0' + state->clues->clues[y+3*w] :
1061                 ' ');
1062         *p++ = '\n';
1063     }
1064
1065     /* Blank line. */
1066     *p++ = '\n';
1067
1068     /* Bottom clue row. */
1069     *p++ = ' '; *p++ = ' ';
1070     for (x = 0; x < w; x++) {
1071         *p++ = ' ';
1072         *p++ = (state->clues->clues[x+w] ? '0' + state->clues->clues[x+w] :
1073                 ' ');
1074     }
1075     *p++ = '\n';
1076
1077     *p++ = '\0';
1078     assert(p == ret + total);
1079
1080     return ret;
1081 }
1082
1083 struct game_ui {
1084     /*
1085      * These are the coordinates of the currently highlighted
1086      * square on the grid, if hshow = 1.
1087      */
1088     int hx, hy;
1089     /*
1090      * This indicates whether the current highlight is a
1091      * pencil-mark one or a real one.
1092      */
1093     int hpencil;
1094     /*
1095      * This indicates whether or not we're showing the highlight
1096      * (used to be hx = hy = -1); important so that when we're
1097      * using the cursor keys it doesn't keep coming back at a
1098      * fixed position. When hshow = 1, pressing a valid number
1099      * or letter key or Space will enter that number or letter in the grid.
1100      */
1101     int hshow;
1102     /*
1103      * This indicates whether we're using the highlight as a cursor;
1104      * it means that it doesn't vanish on a keypress, and that it is
1105      * allowed on immutable squares.
1106      */
1107     int hcursor;
1108 };
1109
1110 static game_ui *new_ui(const game_state *state)
1111 {
1112     game_ui *ui = snew(game_ui);
1113
1114     ui->hx = ui->hy = 0;
1115     ui->hpencil = ui->hshow = ui->hcursor = 0;
1116
1117     return ui;
1118 }
1119
1120 static void free_ui(game_ui *ui)
1121 {
1122     sfree(ui);
1123 }
1124
1125 static char *encode_ui(const game_ui *ui)
1126 {
1127     return NULL;
1128 }
1129
1130 static void decode_ui(game_ui *ui, const char *encoding)
1131 {
1132 }
1133
1134 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1135                                const game_state *newstate)
1136 {
1137     int w = newstate->par.w;
1138     /*
1139      * We prevent pencil-mode highlighting of a filled square, unless
1140      * we're using the cursor keys. So if the user has just filled in
1141      * a square which we had a pencil-mode highlight in (by Undo, or
1142      * by Redo, or by Solve), then we cancel the highlight.
1143      */
1144     if (ui->hshow && ui->hpencil && !ui->hcursor &&
1145         newstate->grid[ui->hy * w + ui->hx] != 0) {
1146         ui->hshow = 0;
1147     }
1148 }
1149
1150 #define PREFERRED_TILESIZE 48
1151 #define TILESIZE (ds->tilesize)
1152 #define BORDER (TILESIZE * 9 / 8)
1153 #define COORD(x) ((x)*TILESIZE + BORDER)
1154 #define FROMCOORD(x) (((x)+(TILESIZE-BORDER)) / TILESIZE - 1)
1155
1156 /* These always return positive values, though y offsets are actually -ve */
1157 #define X_3D_DISP(height, w) ((height) * TILESIZE / (8 * (w)))
1158 #define Y_3D_DISP(height, w) ((height) * TILESIZE / (4 * (w)))
1159
1160 #define FLASH_TIME 0.4F
1161
1162 #define DF_PENCIL_SHIFT 16
1163 #define DF_CLUE_DONE 0x10000
1164 #define DF_ERROR 0x8000
1165 #define DF_HIGHLIGHT 0x4000
1166 #define DF_HIGHLIGHT_PENCIL 0x2000
1167 #define DF_IMMUTABLE 0x1000
1168 #define DF_PLAYAREA 0x0800
1169 #define DF_DIGIT_MASK 0x00FF
1170
1171 struct game_drawstate {
1172     int tilesize;
1173     int three_d;                /* default 3D graphics are user-disableable */
1174     int started;
1175     long *tiles;                       /* (w+2)*(w+2) temp space */
1176     long *drawn;                       /* (w+2)*(w+2)*4: current drawn data */
1177     int *errtmp;
1178 };
1179
1180 static int check_errors(const game_state *state, int *errors)
1181 {
1182     int w = state->par.w /*, a = w*w */;
1183     int W = w+2, A = W*W;              /* the errors array is (w+2) square */
1184     int *clues = state->clues->clues;
1185     digit *grid = state->grid;
1186     int i, x, y, errs = FALSE;
1187     int tmp[32];
1188
1189     assert(w < lenof(tmp));
1190
1191     if (errors)
1192         for (i = 0; i < A; i++)
1193             errors[i] = 0;
1194
1195     for (y = 0; y < w; y++) {
1196         unsigned long mask = 0, errmask = 0;
1197         for (x = 0; x < w; x++) {
1198             unsigned long bit = 1UL << grid[y*w+x];
1199             errmask |= (mask & bit);
1200             mask |= bit;
1201         }
1202
1203         if (mask != (1L << (w+1)) - (1L << 1)) {
1204             errs = TRUE;
1205             errmask &= ~1UL;
1206             if (errors) {
1207                 for (x = 0; x < w; x++)
1208                     if (errmask & (1UL << grid[y*w+x]))
1209                         errors[(y+1)*W+(x+1)] = TRUE;
1210             }
1211         }
1212     }
1213
1214     for (x = 0; x < w; x++) {
1215         unsigned long mask = 0, errmask = 0;
1216         for (y = 0; y < w; y++) {
1217             unsigned long bit = 1UL << grid[y*w+x];
1218             errmask |= (mask & bit);
1219             mask |= bit;
1220         }
1221
1222         if (mask != (1 << (w+1)) - (1 << 1)) {
1223             errs = TRUE;
1224             errmask &= ~1UL;
1225             if (errors) {
1226                 for (y = 0; y < w; y++)
1227                     if (errmask & (1UL << grid[y*w+x]))
1228                         errors[(y+1)*W+(x+1)] = TRUE;
1229             }
1230         }
1231     }
1232
1233     for (i = 0; i < 4*w; i++) {
1234         int start, step, j, n, best;
1235         STARTSTEP(start, step, i, w);
1236
1237         if (!clues[i])
1238             continue;
1239
1240         best = n = 0;
1241         for (j = 0; j < w; j++) {
1242             int number = grid[start+j*step];
1243             if (!number)
1244                 break;                 /* can't tell what happens next */
1245             if (number > best) {
1246                 best = number;
1247                 n++;
1248             }
1249         }
1250
1251         if (n > clues[i] || (best == w && n < clues[i]) ||
1252             (best < w && n == clues[i])) {
1253             if (errors) {
1254                 int x, y;
1255                 CLUEPOS(x, y, i, w);
1256                 errors[(y+1)*W+(x+1)] = TRUE;
1257             }
1258             errs = TRUE;
1259         }
1260     }
1261
1262     return errs;
1263 }
1264
1265 static int clue_index(const game_state *state, int x, int y)
1266 {
1267     int w = state->par.w;
1268
1269     if (x == -1 || x == w)
1270         return w * (x == -1 ? 2 : 3) + y;
1271     else if (y == -1 || y == w)
1272         return (y == -1 ? 0 : w) + x;
1273
1274     return -1;
1275 }
1276
1277 static int is_clue(const game_state *state, int x, int y)
1278 {
1279     int w = state->par.w;
1280
1281     if (((x == -1 || x == w) && y >= 0 && y < w) ||
1282         ((y == -1 || y == w) && x >= 0 && x < w))
1283     {
1284         if (state->clues->clues[clue_index(state, x, y)] & DF_DIGIT_MASK)
1285             return TRUE;
1286     }
1287
1288     return FALSE;
1289 }
1290
1291 static char *interpret_move(const game_state *state, game_ui *ui,
1292                             const game_drawstate *ds,
1293                             int x, int y, int button)
1294 {
1295     int w = state->par.w;
1296     int shift_or_control = button & (MOD_SHFT | MOD_CTRL);
1297     int tx, ty;
1298     char buf[80];
1299
1300     button &= ~MOD_MASK;
1301
1302     tx = FROMCOORD(x);
1303     ty = FROMCOORD(y);
1304
1305     if (ds->three_d) {
1306         /*
1307          * In 3D mode, just locating the mouse click in the natural
1308          * square grid may not be sufficient to tell which tower the
1309          * user clicked on. Investigate the _tops_ of the nearby
1310          * towers to see if a click on one grid square was actually
1311          * a click on a tower protruding into that region from
1312          * another.
1313          */
1314         int dx, dy;
1315         for (dy = 0; dy <= 1; dy++)
1316             for (dx = 0; dx >= -1; dx--) {
1317                 int cx = tx + dx, cy = ty + dy;
1318                 if (cx >= 0 && cx < w && cy >= 0 && cy < w) {
1319                     int height = state->grid[cy*w+cx];
1320                     int bx = COORD(cx), by = COORD(cy);
1321                     int ox = bx + X_3D_DISP(height, w);
1322                     int oy = by - Y_3D_DISP(height, w);
1323                     if (/* on top face? */
1324                         (x - ox >= 0 && x - ox < TILESIZE &&
1325                          y - oy >= 0 && y - oy < TILESIZE) ||
1326                         /* in triangle between top-left corners? */
1327                         (ox > bx && x >= bx && x <= ox && y <= by &&
1328                          (by-y) * (ox-bx) <= (by-oy) * (x-bx)) ||
1329                         /* in triangle between bottom-right corners? */
1330                         (ox > bx && x >= bx+TILESIZE && x <= ox+TILESIZE &&
1331                          y >= oy+TILESIZE &&
1332                          (by-y+TILESIZE)*(ox-bx) >= (by-oy)*(x-bx-TILESIZE))) {
1333                         tx = cx;
1334                         ty = cy;
1335                     }
1336                 }
1337             }
1338     }
1339
1340     if (tx >= 0 && tx < w && ty >= 0 && ty < w) {
1341         if (button == LEFT_BUTTON) {
1342             if (tx == ui->hx && ty == ui->hy &&
1343                 ui->hshow && ui->hpencil == 0) {
1344                 ui->hshow = 0;
1345             } else {
1346                 ui->hx = tx;
1347                 ui->hy = ty;
1348                 ui->hshow = !state->clues->immutable[ty*w+tx];
1349                 ui->hpencil = 0;
1350             }
1351             ui->hcursor = 0;
1352             return "";                 /* UI activity occurred */
1353         }
1354         if (button == RIGHT_BUTTON) {
1355             /*
1356              * Pencil-mode highlighting for non filled squares.
1357              */
1358             if (state->grid[ty*w+tx] == 0) {
1359                 if (tx == ui->hx && ty == ui->hy &&
1360                     ui->hshow && ui->hpencil) {
1361                     ui->hshow = 0;
1362                 } else {
1363                     ui->hpencil = 1;
1364                     ui->hx = tx;
1365                     ui->hy = ty;
1366                     ui->hshow = 1;
1367                 }
1368             } else {
1369                 ui->hshow = 0;
1370             }
1371             ui->hcursor = 0;
1372             return "";                 /* UI activity occurred */
1373         }
1374     } else if (button == LEFT_BUTTON) {
1375         if (is_clue(state, tx, ty)) {
1376             sprintf(buf, "%c%d,%d", 'D', tx, ty);
1377             return dupstr(buf);
1378         }
1379     }
1380     if (IS_CURSOR_MOVE(button)) {
1381         if (shift_or_control) {
1382             int x = ui->hx, y = ui->hy;
1383             switch (button) {
1384             case CURSOR_LEFT:   x = -1; break;
1385             case CURSOR_RIGHT:  x =  w; break;
1386             case CURSOR_UP:     y = -1; break;
1387             case CURSOR_DOWN:   y =  w; break;
1388             }
1389             if (is_clue(state, x, y)) {
1390                 sprintf(buf, "%c%d,%d", 'D', x, y);
1391                 return dupstr(buf);
1392             }
1393             return NULL;
1394         }
1395         move_cursor(button, &ui->hx, &ui->hy, w, w, 0);
1396         ui->hshow = ui->hcursor = 1;
1397         return "";
1398     }
1399     if (ui->hshow &&
1400         (button == CURSOR_SELECT)) {
1401         ui->hpencil = 1 - ui->hpencil;
1402         ui->hcursor = 1;
1403         return "";
1404     }
1405
1406     if (ui->hshow &&
1407         ((button >= '0' && button <= '9' && button - '0' <= w) ||
1408          button == CURSOR_SELECT2 || button == '\b')) {
1409         int n = button - '0';
1410         if (button == CURSOR_SELECT2 || button == '\b')
1411             n = 0;
1412
1413         /*
1414          * Can't make pencil marks in a filled square. This can only
1415          * become highlighted if we're using cursor keys.
1416          */
1417         if (ui->hpencil && state->grid[ui->hy*w+ui->hx])
1418             return NULL;
1419
1420         /*
1421          * Can't do anything to an immutable square.
1422          */
1423         if (state->clues->immutable[ui->hy*w+ui->hx])
1424             return NULL;
1425
1426         sprintf(buf, "%c%d,%d,%d",
1427                 (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n);
1428
1429         if (!ui->hcursor) ui->hshow = 0;
1430
1431         return dupstr(buf);
1432     }
1433
1434     if (button == 'M' || button == 'm')
1435         return dupstr("M");
1436
1437     return NULL;
1438 }
1439
1440 static game_state *execute_move(const game_state *from, const char *move)
1441 {
1442     int w = from->par.w, a = w*w;
1443     game_state *ret = dup_game(from);
1444     int x, y, i, n;
1445
1446     if (move[0] == 'S') {
1447         ret->completed = ret->cheated = TRUE;
1448
1449         for (i = 0; i < a; i++) {
1450             if (move[i+1] < '1' || move[i+1] > '0'+w)
1451                 goto badmove;
1452             ret->grid[i] = move[i+1] - '0';
1453             ret->pencil[i] = 0;
1454         }
1455
1456         if (move[a+1] != '\0')
1457             goto badmove;
1458
1459         return ret;
1460     } else if ((move[0] == 'P' || move[0] == 'R') &&
1461         sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
1462         x >= 0 && x < w && y >= 0 && y < w && n >= 0 && n <= w) {
1463         if (from->clues->immutable[y*w+x])
1464             goto badmove;
1465
1466         if (move[0] == 'P' && n > 0) {
1467             ret->pencil[y*w+x] ^= 1L << n;
1468         } else {
1469             ret->grid[y*w+x] = n;
1470             ret->pencil[y*w+x] = 0;
1471
1472             if (!ret->completed && !check_errors(ret, NULL))
1473                 ret->completed = TRUE;
1474         }
1475         return ret;
1476     } else if (move[0] == 'M') {
1477         /*
1478          * Fill in absolutely all pencil marks everywhere. (I
1479          * wouldn't use this for actual play, but it's a handy
1480          * starting point when following through a set of
1481          * diagnostics output by the standalone solver.)
1482          */
1483         for (i = 0; i < a; i++) {
1484             if (!ret->grid[i])
1485                 ret->pencil[i] = (1L << (w+1)) - (1L << 1);
1486         }
1487         return ret;
1488     } else if (move[0] == 'D' && sscanf(move+1, "%d,%d", &x, &y) == 2 &&
1489                is_clue(from, x, y)) {
1490         int index = clue_index(from, x, y);
1491         ret->clues_done[index] = !ret->clues_done[index];
1492         return ret;
1493     }
1494
1495   badmove:
1496     /* couldn't parse move string */
1497     free_game(ret);
1498     return NULL;
1499 }
1500
1501 /* ----------------------------------------------------------------------
1502  * Drawing routines.
1503  */
1504
1505 #define SIZE(w) ((w) * TILESIZE + 2*BORDER)
1506
1507 static void game_compute_size(const game_params *params, int tilesize,
1508                               int *x, int *y)
1509 {
1510     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1511     struct { int tilesize; } ads, *ds = &ads;
1512     ads.tilesize = tilesize;
1513
1514     *x = *y = SIZE(params->w);
1515 }
1516
1517 static void game_set_size(drawing *dr, game_drawstate *ds,
1518                           const game_params *params, int tilesize)
1519 {
1520     ds->tilesize = tilesize;
1521 }
1522
1523 static float *game_colours(frontend *fe, int *ncolours)
1524 {
1525     float *ret = snewn(3 * NCOLOURS, float);
1526
1527     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1528
1529     ret[COL_GRID * 3 + 0] = 0.0F;
1530     ret[COL_GRID * 3 + 1] = 0.0F;
1531     ret[COL_GRID * 3 + 2] = 0.0F;
1532
1533     ret[COL_USER * 3 + 0] = 0.0F;
1534     ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1535     ret[COL_USER * 3 + 2] = 0.0F;
1536
1537     ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0];
1538     ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1];
1539     ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2];
1540
1541     ret[COL_ERROR * 3 + 0] = 1.0F;
1542     ret[COL_ERROR * 3 + 1] = 0.0F;
1543     ret[COL_ERROR * 3 + 2] = 0.0F;
1544
1545     ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1546     ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1547     ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1548
1549     ret[COL_DONE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 1.5F;
1550     ret[COL_DONE * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 1.5F;
1551     ret[COL_DONE * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 1.5F;
1552
1553     *ncolours = NCOLOURS;
1554     return ret;
1555 }
1556
1557 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1558 {
1559     int w = state->par.w /*, a = w*w */;
1560     struct game_drawstate *ds = snew(struct game_drawstate);
1561     int i;
1562
1563     ds->tilesize = 0;
1564     ds->three_d = !getenv("TOWERS_2D");
1565     ds->started = FALSE;
1566     ds->tiles = snewn((w+2)*(w+2), long);
1567     ds->drawn = snewn((w+2)*(w+2)*4, long);
1568     for (i = 0; i < (w+2)*(w+2)*4; i++)
1569         ds->drawn[i] = -1;
1570     ds->errtmp = snewn((w+2)*(w+2), int);
1571
1572     return ds;
1573 }
1574
1575 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1576 {
1577     sfree(ds->errtmp);
1578     sfree(ds->tiles);
1579     sfree(ds->drawn);
1580     sfree(ds);
1581 }
1582
1583 static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues,
1584                       int x, int y, long tile)
1585 {
1586     int w = clues->w /* , a = w*w */;
1587     int tx, ty, bg;
1588     char str[64];
1589
1590     tx = COORD(x);
1591     ty = COORD(y);
1592
1593     bg = (tile & DF_HIGHLIGHT) ? COL_HIGHLIGHT : COL_BACKGROUND;
1594
1595     /* draw tower */
1596     if (ds->three_d && (tile & DF_PLAYAREA) && (tile & DF_DIGIT_MASK)) {
1597         int coords[8];
1598         int xoff = X_3D_DISP(tile & DF_DIGIT_MASK, w);
1599         int yoff = Y_3D_DISP(tile & DF_DIGIT_MASK, w);
1600
1601         /* left face of tower */
1602         coords[0] = tx;
1603         coords[1] = ty - 1;
1604         coords[2] = tx;
1605         coords[3] = ty + TILESIZE - 1;
1606         coords[4] = coords[2] + xoff;
1607         coords[5] = coords[3] - yoff;
1608         coords[6] = coords[0] + xoff;
1609         coords[7] = coords[1] - yoff;
1610         draw_polygon(dr, coords, 4, bg, COL_GRID);
1611
1612         /* bottom face of tower */
1613         coords[0] = tx + TILESIZE;
1614         coords[1] = ty + TILESIZE - 1;
1615         coords[2] = tx;
1616         coords[3] = ty + TILESIZE - 1;
1617         coords[4] = coords[2] + xoff;
1618         coords[5] = coords[3] - yoff;
1619         coords[6] = coords[0] + xoff;
1620         coords[7] = coords[1] - yoff;
1621         draw_polygon(dr, coords, 4, bg, COL_GRID);
1622
1623         /* now offset all subsequent drawing to the top of the tower */
1624         tx += xoff;
1625         ty -= yoff;
1626     }
1627
1628     /* erase background */
1629     draw_rect(dr, tx, ty, TILESIZE, TILESIZE, bg);
1630
1631     /* pencil-mode highlight */
1632     if (tile & DF_HIGHLIGHT_PENCIL) {
1633         int coords[6];
1634         coords[0] = tx;
1635         coords[1] = ty;
1636         coords[2] = tx+TILESIZE/2;
1637         coords[3] = ty;
1638         coords[4] = tx;
1639         coords[5] = ty+TILESIZE/2;
1640         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1641     }
1642
1643     /* draw box outline */
1644     if (tile & DF_PLAYAREA) {
1645         int coords[8];
1646         coords[0] = tx;
1647         coords[1] = ty - 1;
1648         coords[2] = tx + TILESIZE;
1649         coords[3] = ty - 1;
1650         coords[4] = tx + TILESIZE;
1651         coords[5] = ty + TILESIZE - 1;
1652         coords[6] = tx;
1653         coords[7] = ty + TILESIZE - 1;
1654         draw_polygon(dr, coords, 4, -1, COL_GRID);
1655     }
1656
1657     /* new number needs drawing? */
1658     if (tile & DF_DIGIT_MASK) {
1659         int color;
1660
1661         str[1] = '\0';
1662         str[0] = (tile & DF_DIGIT_MASK) + '0';
1663
1664         if (tile & DF_ERROR)
1665             color = COL_ERROR;
1666         else if (tile & DF_CLUE_DONE)
1667             color = COL_DONE;
1668         else if (x < 0 || y < 0 || x >= w || y >= w)
1669             color = COL_GRID;
1670         else if (tile & DF_IMMUTABLE)
1671             color = COL_GRID;
1672         else
1673             color = COL_USER;
1674
1675         draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2, FONT_VARIABLE,
1676                   (tile & DF_PLAYAREA ? TILESIZE/2 : TILESIZE*2/5),
1677                   ALIGN_VCENTRE | ALIGN_HCENTRE, color, str);
1678     } else {
1679         int i, j, npencil;
1680         int pl, pr, pt, pb;
1681         float bestsize;
1682         int pw, ph, minph, pbest, fontsize;
1683
1684         /* Count the pencil marks required. */
1685         for (i = 1, npencil = 0; i <= w; i++)
1686             if (tile & (1L << (i + DF_PENCIL_SHIFT)))
1687                 npencil++;
1688         if (npencil) {
1689
1690             minph = 2;
1691
1692             /*
1693              * Determine the bounding rectangle within which we're going
1694              * to put the pencil marks.
1695              */
1696             /* Start with the whole square, minus space for impinging towers */
1697             pl = tx + (ds->three_d ? X_3D_DISP(w,w) : 0);
1698             pr = tx + TILESIZE;
1699             pt = ty;
1700             pb = ty + TILESIZE - (ds->three_d ? Y_3D_DISP(w,w) : 0);
1701
1702             /*
1703              * We arrange our pencil marks in a grid layout, with
1704              * the number of rows and columns adjusted to allow the
1705              * maximum font size.
1706              *
1707              * So now we work out what the grid size ought to be.
1708              */
1709             bestsize = 0.0;
1710             pbest = 0;
1711             /* Minimum */
1712             for (pw = 3; pw < max(npencil,4); pw++) {
1713                 float fw, fh, fs;
1714
1715                 ph = (npencil + pw - 1) / pw;
1716                 ph = max(ph, minph);
1717                 fw = (pr - pl) / (float)pw;
1718                 fh = (pb - pt) / (float)ph;
1719                 fs = min(fw, fh);
1720                 if (fs > bestsize) {
1721                     bestsize = fs;
1722                     pbest = pw;
1723                 }
1724             }
1725             assert(pbest > 0);
1726             pw = pbest;
1727             ph = (npencil + pw - 1) / pw;
1728             ph = max(ph, minph);
1729
1730             /*
1731              * Now we've got our grid dimensions, work out the pixel
1732              * size of a grid element, and round it to the nearest
1733              * pixel. (We don't want rounding errors to make the
1734              * grid look uneven at low pixel sizes.)
1735              */
1736             fontsize = min((pr - pl) / pw, (pb - pt) / ph);
1737
1738             /*
1739              * Centre the resulting figure in the square.
1740              */
1741             pl = pl + (pr - pl - fontsize * pw) / 2;
1742             pt = pt + (pb - pt - fontsize * ph) / 2;
1743
1744             /*
1745              * Now actually draw the pencil marks.
1746              */
1747             for (i = 1, j = 0; i <= w; i++)
1748                 if (tile & (1L << (i + DF_PENCIL_SHIFT))) {
1749                     int dx = j % pw, dy = j / pw;
1750
1751                     str[1] = '\0';
1752                     str[0] = i + '0';
1753                     draw_text(dr, pl + fontsize * (2*dx+1) / 2,
1754                               pt + fontsize * (2*dy+1) / 2,
1755                               FONT_VARIABLE, fontsize,
1756                               ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
1757                     j++;
1758                 }
1759         }
1760     }
1761 }
1762
1763 static void game_redraw(drawing *dr, game_drawstate *ds,
1764                         const game_state *oldstate, const game_state *state,
1765                         int dir, const game_ui *ui,
1766                         float animtime, float flashtime)
1767 {
1768     int w = state->par.w /*, a = w*w */;
1769     int i, x, y;
1770
1771     if (!ds->started) {
1772         /*
1773          * The initial contents of the window are not guaranteed and
1774          * can vary with front ends. To be on the safe side, all
1775          * games should start by drawing a big background-colour
1776          * rectangle covering the whole window.
1777          */
1778         draw_rect(dr, 0, 0, SIZE(w), SIZE(w), COL_BACKGROUND);
1779
1780         draw_update(dr, 0, 0, SIZE(w), SIZE(w));
1781
1782         ds->started = TRUE;
1783     }
1784
1785     check_errors(state, ds->errtmp);
1786
1787     /*
1788      * Work out what data each tile should contain.
1789      */
1790     for (i = 0; i < (w+2)*(w+2); i++)
1791         ds->tiles[i] = 0;              /* completely blank square */
1792     /* The clue squares... */
1793     for (i = 0; i < 4*w; i++) {
1794         long tile = state->clues->clues[i];
1795
1796         CLUEPOS(x, y, i, w);
1797
1798         if (ds->errtmp[(y+1)*(w+2)+(x+1)])
1799             tile |= DF_ERROR;
1800         else if (state->clues_done[i])
1801             tile |= DF_CLUE_DONE;
1802
1803         ds->tiles[(y+1)*(w+2)+(x+1)] = tile;
1804     }
1805     /* ... and the main grid. */
1806     for (y = 0; y < w; y++) {
1807         for (x = 0; x < w; x++) {
1808             long tile = DF_PLAYAREA;
1809
1810             if (state->grid[y*w+x])
1811                 tile |= state->grid[y*w+x];
1812             else
1813                 tile |= (long)state->pencil[y*w+x] << DF_PENCIL_SHIFT;
1814
1815             if (ui->hshow && ui->hx == x && ui->hy == y)
1816                 tile |= (ui->hpencil ? DF_HIGHLIGHT_PENCIL : DF_HIGHLIGHT);
1817
1818             if (state->clues->immutable[y*w+x])
1819                 tile |= DF_IMMUTABLE;
1820
1821             if (flashtime > 0 &&
1822                 (flashtime <= FLASH_TIME/3 ||
1823                  flashtime >= FLASH_TIME*2/3))
1824                 tile |= DF_HIGHLIGHT;  /* completion flash */
1825
1826             if (ds->errtmp[(y+1)*(w+2)+(x+1)])
1827                 tile |= DF_ERROR;
1828
1829             ds->tiles[(y+1)*(w+2)+(x+1)] = tile;
1830         }
1831     }
1832
1833     /*
1834      * Now actually draw anything that needs to be changed.
1835      */
1836     for (y = 0; y < w+2; y++) {
1837         for (x = 0; x < w+2; x++) {
1838             long tl, tr, bl, br;
1839             int i = y*(w+2)+x;
1840
1841             tr = ds->tiles[y*(w+2)+x];
1842             tl = (x == 0 ? 0 : ds->tiles[y*(w+2)+(x-1)]);
1843             br = (y == w+1 ? 0 : ds->tiles[(y+1)*(w+2)+x]);
1844             bl = (x == 0 || y == w+1 ? 0 : ds->tiles[(y+1)*(w+2)+(x-1)]);
1845
1846             if (ds->drawn[i*4] != tl || ds->drawn[i*4+1] != tr ||
1847                 ds->drawn[i*4+2] != bl || ds->drawn[i*4+3] != br) {
1848                 clip(dr, COORD(x-1), COORD(y-1), TILESIZE, TILESIZE);
1849
1850                 draw_tile(dr, ds, state->clues, x-1, y-1, tr);
1851                 if (x > 0)
1852                     draw_tile(dr, ds, state->clues, x-2, y-1, tl);
1853                 if (y <= w)
1854                     draw_tile(dr, ds, state->clues, x-1, y, br);
1855                 if (x > 0 && y <= w)
1856                     draw_tile(dr, ds, state->clues, x-2, y, bl);
1857
1858                 unclip(dr);
1859                 draw_update(dr, COORD(x-1), COORD(y-1), TILESIZE, TILESIZE);
1860
1861                 ds->drawn[i*4] = tl;
1862                 ds->drawn[i*4+1] = tr;
1863                 ds->drawn[i*4+2] = bl;
1864                 ds->drawn[i*4+3] = br;
1865             }
1866         }
1867     }
1868 }
1869
1870 static float game_anim_length(const game_state *oldstate,
1871                               const game_state *newstate, int dir, game_ui *ui)
1872 {
1873     return 0.0F;
1874 }
1875
1876 static float game_flash_length(const game_state *oldstate,
1877                                const game_state *newstate, int dir, game_ui *ui)
1878 {
1879     if (!oldstate->completed && newstate->completed &&
1880         !oldstate->cheated && !newstate->cheated)
1881         return FLASH_TIME;
1882     return 0.0F;
1883 }
1884
1885 static int game_status(const game_state *state)
1886 {
1887     return state->completed ? +1 : 0;
1888 }
1889
1890 static int game_timing_state(const game_state *state, game_ui *ui)
1891 {
1892     if (state->completed)
1893         return FALSE;
1894     return TRUE;
1895 }
1896
1897 static void game_print_size(const game_params *params, float *x, float *y)
1898 {
1899     int pw, ph;
1900
1901     /*
1902      * We use 9mm squares by default, like Solo.
1903      */
1904     game_compute_size(params, 900, &pw, &ph);
1905     *x = pw / 100.0F;
1906     *y = ph / 100.0F;
1907 }
1908
1909 static void game_print(drawing *dr, const game_state *state, int tilesize)
1910 {
1911     int w = state->par.w;
1912     int ink = print_mono_colour(dr, 0);
1913     int i, x, y;
1914
1915     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1916     game_drawstate ads, *ds = &ads;
1917     game_set_size(dr, ds, NULL, tilesize);
1918
1919     /*
1920      * Border.
1921      */
1922     print_line_width(dr, 3 * TILESIZE / 40);
1923     draw_rect_outline(dr, BORDER, BORDER, w*TILESIZE, w*TILESIZE, ink);
1924
1925     /*
1926      * Main grid.
1927      */
1928     for (x = 1; x < w; x++) {
1929         print_line_width(dr, TILESIZE / 40);
1930         draw_line(dr, BORDER+x*TILESIZE, BORDER,
1931                   BORDER+x*TILESIZE, BORDER+w*TILESIZE, ink);
1932     }
1933     for (y = 1; y < w; y++) {
1934         print_line_width(dr, TILESIZE / 40);
1935         draw_line(dr, BORDER, BORDER+y*TILESIZE,
1936                   BORDER+w*TILESIZE, BORDER+y*TILESIZE, ink);
1937     }
1938
1939     /*
1940      * Clues.
1941      */
1942     for (i = 0; i < 4*w; i++) {
1943         char str[128];
1944
1945         if (!state->clues->clues[i])
1946             continue;
1947
1948         CLUEPOS(x, y, i, w);
1949
1950         sprintf (str, "%d", state->clues->clues[i]);
1951
1952         draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2,
1953                   BORDER + y*TILESIZE + TILESIZE/2,
1954                   FONT_VARIABLE, TILESIZE/2,
1955                   ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
1956     }
1957
1958     /*
1959      * Numbers for the solution, if any.
1960      */
1961     for (y = 0; y < w; y++)
1962         for (x = 0; x < w; x++)
1963             if (state->grid[y*w+x]) {
1964                 char str[2];
1965                 str[1] = '\0';
1966                 str[0] = state->grid[y*w+x] + '0';
1967                 draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2,
1968                           BORDER + y*TILESIZE + TILESIZE/2,
1969                           FONT_VARIABLE, TILESIZE/2,
1970                           ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
1971             }
1972 }
1973
1974 #ifdef COMBINED
1975 #define thegame towers
1976 #endif
1977
1978 const struct game thegame = {
1979     "Towers", "games.towers", "towers",
1980     default_params,
1981     game_fetch_preset, NULL,
1982     decode_params,
1983     encode_params,
1984     free_params,
1985     dup_params,
1986     TRUE, game_configure, custom_params,
1987     validate_params,
1988     new_game_desc,
1989     validate_desc,
1990     new_game,
1991     dup_game,
1992     free_game,
1993     TRUE, solve_game,
1994     TRUE, game_can_format_as_text_now, game_text_format,
1995     new_ui,
1996     free_ui,
1997     encode_ui,
1998     decode_ui,
1999     game_changed_state,
2000     interpret_move,
2001     execute_move,
2002     PREFERRED_TILESIZE, game_compute_size, game_set_size,
2003     game_colours,
2004     game_new_drawstate,
2005     game_free_drawstate,
2006     game_redraw,
2007     game_anim_length,
2008     game_flash_length,
2009     game_status,
2010     TRUE, FALSE, game_print_size, game_print,
2011     FALSE,                             /* wants_statusbar */
2012     FALSE, game_timing_state,
2013     REQUIRE_RBUTTON | REQUIRE_NUMPAD,  /* flags */
2014 };
2015
2016 #ifdef STANDALONE_SOLVER
2017
2018 #include <stdarg.h>
2019
2020 int main(int argc, char **argv)
2021 {
2022     game_params *p;
2023     game_state *s;
2024     char *id = NULL, *desc, *err;
2025     int grade = FALSE;
2026     int ret, diff, really_show_working = FALSE;
2027
2028     while (--argc > 0) {
2029         char *p = *++argv;
2030         if (!strcmp(p, "-v")) {
2031             really_show_working = TRUE;
2032         } else if (!strcmp(p, "-g")) {
2033             grade = TRUE;
2034         } else if (*p == '-') {
2035             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
2036             return 1;
2037         } else {
2038             id = p;
2039         }
2040     }
2041
2042     if (!id) {
2043         fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
2044         return 1;
2045     }
2046
2047     desc = strchr(id, ':');
2048     if (!desc) {
2049         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2050         return 1;
2051     }
2052     *desc++ = '\0';
2053
2054     p = default_params();
2055     decode_params(p, id);
2056     err = validate_desc(p, desc);
2057     if (err) {
2058         fprintf(stderr, "%s: %s\n", argv[0], err);
2059         return 1;
2060     }
2061     s = new_game(NULL, p, desc);
2062
2063     /*
2064      * When solving an Easy puzzle, we don't want to bother the
2065      * user with Hard-level deductions. For this reason, we grade
2066      * the puzzle internally before doing anything else.
2067      */
2068     ret = -1;                          /* placate optimiser */
2069     solver_show_working = FALSE;
2070     for (diff = 0; diff < DIFFCOUNT; diff++) {
2071         memcpy(s->grid, s->clues->immutable, p->w * p->w);
2072         ret = solver(p->w, s->clues->clues, s->grid, diff);
2073         if (ret <= diff)
2074             break;
2075     }
2076
2077     if (diff == DIFFCOUNT) {
2078         if (grade)
2079             printf("Difficulty rating: ambiguous\n");
2080         else
2081             printf("Unable to find a unique solution\n");
2082     } else {
2083         if (grade) {
2084             if (ret == diff_impossible)
2085                 printf("Difficulty rating: impossible (no solution exists)\n");
2086             else
2087                 printf("Difficulty rating: %s\n", towers_diffnames[ret]);
2088         } else {
2089             solver_show_working = really_show_working;
2090             memcpy(s->grid, s->clues->immutable, p->w * p->w);
2091             ret = solver(p->w, s->clues->clues, s->grid, diff);
2092             if (ret != diff)
2093                 printf("Puzzle is inconsistent\n");
2094             else
2095                 fputs(game_text_format(s), stdout);
2096         }
2097     }
2098
2099     return 0;
2100 }
2101
2102 #endif
2103
2104 /* vim: set shiftwidth=4 tabstop=8: */