palisade.c

   1 /* -*- indent-tabs-mode: nil; tab-width: 1000 -*- */
   2
   3 /*
   4  * palisade.c: Nikoli's `Five Cells' puzzle.
   5  *
   6  * See http://nikoli.co.jp/en/puzzles/five_cells.html
   7  */
   8
   9 /* TODO:
  10  *
  11  * - better solver: implement the sketched-out deductions
  12  *
  13  * - improve the victory flash?
  14  *    - the LINE_NOs look ugly against COL_FLASH.
  15  *    - white-blink the edges (instead), a la loopy?
  16  */
  17
  18 #include <assert.h>
  19 #include <ctype.h>
  20 #include <stdarg.h>
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24
  25 #include "puzzles.h"
  26
  27 #define setmem(ptr, byte, len) memset((ptr), (byte), (len) * sizeof (ptr)[0])
  28 #define scopy(dst, src, len) memcpy((dst), (src), (len) * sizeof (dst)[0])
  29 #define dupmem(p, n) memcpy(smalloc(n * sizeof (*p)), p, n * sizeof (*p))
  30 #define snewa(ptr, len) (ptr) = smalloc((len) * sizeof (*ptr))
  31 #define clone(ptr) (dupmem((ptr), 1))
  32
  33 static char *string(int n, const char *fmt, ...)
  34 {
  35     va_list va;
  36     char *ret;
  37     int m;
  38     va_start(va, fmt);
  39     m = vsprintf(snewa(ret, n + 1), fmt, va);
  40     va_end(va);
  41     if (m > n) fatal("memory corruption");
  42     return ret;
  43 }
  44
  45 struct game_params {
  46     int w, h, k;
  47 };
  48
  49 typedef char clue;
  50 typedef unsigned char borderflag;
  51
  52 typedef struct shared_state {
  53     game_params params;
  54     clue *clues;
  55     int refcount;
  56 } shared_state;
  57
  58 struct game_state {
  59     shared_state *shared;
  60     borderflag *borders; /* length w*h */
  61
  62     unsigned int completed: 1;
  63     unsigned int cheated: 1;
  64 };
  65
  66 #define DEFAULT_PRESET 0
  67 static struct game_params presets[] = {
  68     {5, 5, 5}, {8, 6, 6}, {10, 8, 8}, {15, 12, 10}
  69     /* I definitely want 5x5n5 since that gives "Five Cells" its name.
  70      * But how about the others?  By which criteria do I choose? */
  71 };
  72
  73 static game_params *default_params(void)
  74 {
  75     return clone(&presets[DEFAULT_PRESET]);
  76 }
  77
  78 static int game_fetch_preset(int i, char **name, game_params **params)
  79 {
  80     if (i < 0 || i >= lenof(presets)) return FALSE;
  81
  82     *params = clone(&presets[i]);
  83     *name = string(60, "%d x %d, regions of size %d",
  84                    presets[i].w, presets[i].h, presets[i].k);
  85
  86     return TRUE;
  87 }
  88
  89 static void free_params(game_params *params)
  90 {
  91     sfree(params);
  92 }
  93
  94 static game_params *dup_params(const game_params *params)
  95 {
  96     return clone(params);
  97 }
  98
  99 static void decode_params(game_params *params, char const *string)
 100 {
 101     params->w = params->h = params->k = atoi(string);
 102     while (*string && isdigit((unsigned char)*string)) ++string;
 103     if (*string == 'x') {
 104         params->h = atoi(++string);
 105         while (*string && isdigit((unsigned char)*string)) ++string;
 106     }
 107     if (*string == 'n') params->k = atoi(++string);
 108 }
 109
 110 static char *encode_params(const game_params *params, int full)
 111 {
 112     return string(40, "%dx%dn%d", params->w, params->h, params->k);
 113 }
 114
 115 #define CONFIG(i, nm, ty, iv, sv) \
 116     (ret[i].name = nm, ret[i].type = ty, ret[i].ival = iv, ret[i].sval = sv)
 117
 118 static config_item *game_configure(const game_params *params)
 119 {
 120     config_item *ret = snewn(4, config_item);
 121
 122     CONFIG(0, "Width",       C_STRING, 0, string(20, "%d", params->w));
 123     CONFIG(1, "Height",      C_STRING, 0, string(20, "%d", params->h));
 124     CONFIG(2, "Region size", C_STRING, 0, string(20, "%d", params->k));
 125     CONFIG(3, NULL,          C_END,    0, NULL);
 126
 127     return ret;
 128 }
 129
 130 static game_params *custom_params(const config_item *cfg)
 131 {
 132     game_params *params = snew(game_params);
 133
 134     params->w = atoi(cfg[0].sval);
 135     params->h = atoi(cfg[1].sval);
 136     params->k = atoi(cfg[2].sval);
 137
 138     return params;
 139 }
 140
 141 /* +---+  <<  The one possible domino (up to symmetry).      +---+---+
 142  * | 3 |                                                     | 3 | 3 |
 143  * |   |   If two dominos are adjacent as depicted here  >>  +---+---+
 144  * | 3 |   then it's ambiguous whether the edge between      | 3 | 3 |
 145  * +---+   the dominos is horizontal or vertical.            +---+---+
 146  */
 147
 148 static char *validate_params(const game_params *params, int full)
 149 {
 150     int w = params->w, h = params->h, k = params->k, wh = w * h;
 151
 152     if (k < 1) return "Region size must be at least one";
 153     if (w < 1) return "Width must be at least one";
 154     if (h < 1) return "Height must be at least one";
 155     if (wh % k) return "Region size must divide grid area";
 156
 157     if (!full) return NULL; /* succeed partial validation */
 158
 159     /* MAYBE FIXME: we (just?) don't have the UI for winning these. */
 160     if (k == wh) return "Region size must be less than the grid area";
 161     assert (k < wh); /* or wh % k != 0 */
 162
 163     if (k == 2 && w != 1 && h != 1)
 164         return "Region size can't be two unless width or height is one";
 165
 166     return NULL; /* succeed full validation */
 167 }
 168
 169 /* --- Solver ------------------------------------------------------- */
 170
 171 /* the solver may write at will to these arrays, but shouldn't free them */
 172 /* it's up to the client to dup/free as needed */
 173 typedef struct solver_ctx {
 174     const game_params *params;  /* also in shared_state */
 175     clue *clues;                /* also in shared_state */
 176     borderflag *borders;        /* also in game_state */
 177     int *dsf;                   /* particular to the solver */
 178 } solver_ctx;
 179
 180 /* Deductions:
 181  *
 182  * - If two adjacent clues do not have a border between them, this
 183  *   gives a lower limit on the size of their region (which is also an
 184  *   upper limit if both clues are 3).  Rule out any non-border which
 185  *   would make its region either too large or too small.
 186  *
 187  * - If a clue, k, is adjacent to k borders or (4 - k) non-borders,
 188  *   the remaining edges incident to the clue are readily decided.
 189  *
 190  * - If a region has only one other region (e.g. square) to grow into
 191  *   and it's not of full size yet, grow it into that one region.
 192  *
 193  * - If two regions are adjacent and their combined size would be too
 194  *   large, put an edge between them.
 195  *
 196  * - If a border is adjacent to two non-borders, its last vertex-mate
 197  *   must also be a border.  If a maybe-border is adjacent to three
 198  *   nonborders, the maybe-border is a non-border.
 199  *
 200  * - If a clue square is adjacent to several squares belonging to the
 201  *   same region, and enabling (disabling) those borders would violate
 202  *   the clue, those borders must be disabled (enabled).
 203  *
 204  * - If there's a path crossing only non-borders between two squares,
 205  *   the maybe-border between them is a non-border.
 206  *   (This is implicitly computed in the dsf representation)
 207  */
 208
 209 /* TODO deductions:
 210  *
 211  * If a vertex is adjacent to a LINE_YES and (4-3)*LINE_NO, at least
 212  * one of the last two edges are LINE_YES.  If they're adjacent to a
 213  * 1, then the other two edges incident to that 1 are LINE_NO.
 214  *
 215  * For each square: set all as unknown, then for each k-omino and each
 216  * way of placing it on that square, if that way is consistent with
 217  * the board, mark its edges and interior as possible LINE_YES and
 218  * LINE_NO, respectively.  When all k-ominos are through, see what
 219  * isn't possible and remove those impossibilities from the board.
 220  * (Sounds pretty nasty for k > 4 or so.)
 221  *
 222  * A black-bordered subregion must have a size divisible by k.  So,
 223  * draw a graph with one node per dsf component and edges between
 224  * those dsf components which have adjacent squares.  Identify cut
 225  * vertices and edges.  If a cut-vertex-delimited component contains a
 226  * number of squares not divisible by k, cut vertex not included, then
 227  * the cut vertex must belong to the component.  If it has exactly one
 228  * edge _out_ of the component, the line(s) corresponding to that edge
 229  * are all LINE_YES (i.e. a BORDER()).
 230  * (This sounds complicated, but visually it is rather easy.)
 231  *
 232  * [Look at loopy and see how the at-least/-most k out of m edges
 233  * thing is done.  See how it is propagated across multiple squares.]
 234  */
 235
 236 #define EMPTY (~0)
 237
 238 #define BIT(i) (1 << (i))
 239 #define BORDER(i) BIT(i)
 240 #define BORDER_U BORDER(0)
 241 #define BORDER_R BORDER(1)
 242 #define BORDER_D BORDER(2)
 243 #define BORDER_L BORDER(3)
 244 #define FLIP(i) ((i) ^ 2)
 245 #define BORDER_MASK (BORDER_U|BORDER_R|BORDER_D|BORDER_L)
 246 #define DISABLED(border) ((border) << 4)
 247 #define UNDISABLED(border) ((border) >> 4)
 248
 249 static const int dx[4] = { 0, +1,  0, -1};
 250 static const int dy[4] = {-1,  0, +1,  0};
 251 static const int bitcount[16] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
 252 /* bitcount[x & BORDER_MASK] == number of enabled borders */
 253
 254 #define COMPUTE_J (-1)
 255
 256 static void connect(solver_ctx *ctx, int i, int j)
 257 {
 258     dsf_merge(ctx->dsf, i, j);
 259 }
 260
 261 static int connected(solver_ctx *ctx, int i, int j, int dir)
 262 {
 263     if (j == COMPUTE_J) j = i + dx[dir] + ctx->params->w*dy[dir];
 264     return dsf_canonify(ctx->dsf, i) == dsf_canonify(ctx->dsf, j);
 265 }
 266
 267 static void disconnect(solver_ctx *ctx, int i, int j, int dir)
 268 {
 269     if (j == COMPUTE_J) j = i + dx[dir] + ctx->params->w*dy[dir];
 270     ctx->borders[i] |= BORDER(dir);
 271     ctx->borders[j] |= BORDER(FLIP(dir));
 272 }
 273
 274 static int disconnected(solver_ctx *ctx, int i, int j, int dir)
 275 {
 276     assert (j == COMPUTE_J || j == i + dx[dir] + ctx->params->w*dy[dir]);
 277     return ctx->borders[i] & BORDER(dir);
 278 }
 279
 280 static int maybe(solver_ctx *ctx, int i, int j, int dir)
 281 {
 282     assert (j == COMPUTE_J || j == i + dx[dir] + ctx->params->w*dy[dir]);
 283     return !disconnected(ctx, i, j, dir) && !connected(ctx, i, j, dir);
 284     /* the ordering is important: disconnected works for invalid
 285      * squares (i.e. out of bounds), connected doesn't. */
 286 }
 287
 288 static void solver_connected_clues_versus_region_size(solver_ctx *ctx)
 289 {
 290     int w = ctx->params->w, h = ctx->params->h, wh = w*h, i, dir;
 291
 292     /* If i is connected to j and i has borders with p of the
 293      * remaining three squares and j with q of the remaining three
 294      * squares, then the region has size at least 1+(3-p) + 1+(3-q).
 295      * If p = q = 3 then the region has size exactly 2. */
 296
 297     for (i = 0; i < wh; ++i) {
 298         if (ctx->clues[i] == EMPTY) continue;
 299         for (dir = 0; dir < 4; ++dir) {
 300             int j = i + dx[dir] + w*dy[dir];
 301             if (disconnected(ctx, i, j, dir)) continue;
 302             if (ctx->clues[j] == EMPTY) continue;
 303             if ((8 - ctx->clues[i] - ctx->clues[j] > ctx->params->k) ||
 304                 (ctx->clues[i] == 3 && ctx->clues[j] == 3 &&
 305                  ctx->params->k != 2))
 306             {
 307                 disconnect(ctx, i, j, dir);
 308                 /* changed = TRUE, but this is a one-shot... */
 309             }
 310         }
 311     }
 312 }
 313
 314 static int solver_number_exhausted(solver_ctx *ctx)
 315 {
 316     int w = ctx->params->w, h = ctx->params->h, wh = w*h, i, dir, off;
 317     int changed = FALSE;
 318
 319     for (i = 0; i < wh; ++i) {
 320         if (ctx->clues[i] == EMPTY) continue;
 321
 322         if (bitcount[(ctx->borders[i] & BORDER_MASK)] == ctx->clues[i]) {
 323             for (dir = 0; dir < 4; ++dir) {
 324                 int j = i + dx[dir] + w*dy[dir];
 325                 if (!maybe(ctx, i, j, dir)) continue;
 326                 connect(ctx, i, j);
 327                 changed = TRUE;
 328             }
 329             continue;
 330         }
 331
 332         for (off = dir = 0; dir < 4; ++dir) {
 333             int j = i + dx[dir] + w*dy[dir];
 334             if (!disconnected(ctx, i, j, dir) && connected(ctx, i, j, dir))
 335                 ++off; /* ^^^ bounds checking before ^^^^^ */
 336         }
 337
 338         if (ctx->clues[i] == 4 - off)
 339             for (dir = 0; dir < 4; ++dir) {
 340                 int j = i + dx[dir] + w*dy[dir];
 341                 if (!maybe(ctx, i, j, dir)) continue;
 342                 disconnect(ctx, i, j, dir);
 343                 changed = TRUE;
 344             }
 345     }
 346
 347     return changed;
 348 }
 349
 350 static int solver_not_too_big(solver_ctx *ctx)
 351 {
 352     int w = ctx->params->w, h = ctx->params->h, wh = w*h, i, dir;
 353     int changed = FALSE;
 354
 355     for (i = 0; i < wh; ++i) {
 356         int size = dsf_size(ctx->dsf, i);
 357         for (dir = 0; dir < 4; ++dir) {
 358             int j = i + dx[dir] + w*dy[dir];
 359             if (!maybe(ctx, i, j, dir)) continue;
 360             if (size + dsf_size(ctx->dsf, j) <= ctx->params->k) continue;
 361             disconnect(ctx, i, j, dir);
 362             changed = TRUE;
 363         }
 364     }
 365
 366     return changed;
 367 }
 368
 369 static int solver_not_too_small(solver_ctx *ctx)
 370 {
 371     int w = ctx->params->w, h = ctx->params->h, wh = w*h, i, dir;
 372     int *outs, k = ctx->params->k, ci, changed = FALSE;
 373
 374     snewa(outs, wh);
 375     setmem(outs, -1, wh);
 376
 377     for (i = 0; i < wh; ++i) {
 378         ci = dsf_canonify(ctx->dsf, i);
 379         if (dsf_size(ctx->dsf, ci) == k) continue;
 380         for (dir = 0; dir < 4; ++dir) {
 381             int j = i + dx[dir] + w*dy[dir];
 382             if (!maybe(ctx, i, j, dir)) continue;
 383             if (outs[ci] == -1) outs[ci] = dsf_canonify(ctx->dsf, j);
 384             else if (outs[ci] != dsf_canonify(ctx->dsf, j)) outs[ci] = -2;
 385         }
 386     }
 387
 388     for (i = 0; i < wh; ++i) {
 389         int j = outs[i];
 390         if (i != dsf_canonify(ctx->dsf, i)) continue;
 391         if (j < 0) continue;
 392         connect(ctx, i, j); /* only one place for i to grow */
 393         changed = TRUE;
 394     }
 395
 396     sfree(outs);
 397     return changed;
 398 }
 399
 400 static int solver_no_dangling_edges(solver_ctx *ctx)
 401 {
 402     int w = ctx->params->w, h = ctx->params->h, r, c;
 403     int changed = FALSE;
 404
 405     /* for each vertex */
 406     for (r = 1; r < h; ++r)
 407         for (c = 1; c < w; ++c) {
 408             int i = r * w + c, j = i - w - 1, noline = 0, dir;
 409             int squares[4], e = -1, f = -1, de = -1, df = -1;
 410
 411             /* feels hacky: I align these with BORDER_[U0 R1 D2 L3] */
 412             squares[1] = squares[2] = j;
 413             squares[0] = squares[3] = i;
 414
 415             /* for each edge adjacent to the vertex */
 416             for (dir = 0; dir < 4; ++dir)
 417                 if (!connected(ctx, squares[dir], COMPUTE_J, dir)) {
 418                     df = dir;
 419                     f = squares[df];
 420                     if (e != -1) continue;
 421                     e = f;
 422                     de = df;
 423                 } else ++noline;
 424
 425             if (4 - noline == 1) {
 426                 assert (e != -1);
 427                 disconnect(ctx, e, COMPUTE_J, de);
 428                 changed = TRUE;
 429                 continue;
 430             }
 431
 432             if (4 - noline != 2) continue;
 433
 434             assert (e != -1);
 435             assert (f != -1);
 436
 437             if (ctx->borders[e] & BORDER(de)) {
 438                 if (!(ctx->borders[f] & BORDER(df))) {
 439                     disconnect(ctx, f, COMPUTE_J, df);
 440                     changed = TRUE;
 441                 }
 442             } else if (ctx->borders[f] & BORDER(df)) {
 443                 disconnect(ctx, e, COMPUTE_J, de);
 444                 changed = TRUE;
 445             }
 446         }
 447
 448     return changed;
 449 }
 450
 451 static int solver_equivalent_edges(solver_ctx *ctx)
 452 {
 453     int w = ctx->params->w, h = ctx->params->h, wh = w*h, i, dirj;
 454     int changed = FALSE;
 455
 456     /* if a square is adjacent to two connected squares, the two
 457      * borders (i,j) and (i,k) are either both on or both off. */
 458
 459     for (i = 0; i < wh; ++i) {
 460         int n_on = 0, n_off = 0;
 461         if (ctx->clues[i] < 1 || ctx->clues[i] > 3) continue;
 462
 463         if (ctx->clues[i] == 2 /* don't need it otherwise */)
 464             for (dirj = 0; dirj < 4; ++dirj) {
 465                 int j = i + dx[dirj] + w*dy[dirj];
 466                 if (disconnected(ctx, i, j, dirj)) ++n_on;
 467                 else if (connected(ctx, i, j, dirj)) ++n_off;
 468             }
 469
 470         for (dirj = 0; dirj < 4; ++dirj) {
 471             int j = i + dx[dirj] + w*dy[dirj], dirk;
 472             if (!maybe(ctx, i, j, dirj)) continue;
 473
 474             for (dirk = dirj + 1; dirk < 4; ++dirk) {
 475                 int k = i + dx[dirk] + w*dy[dirk];
 476                 if (!maybe(ctx, i, k, dirk)) continue;
 477                 if (!connected(ctx, j, k, -1)) continue;
 478
 479                 if (n_on + 2 > ctx->clues[i]) {
 480                     connect(ctx, i, j);
 481                     connect(ctx, i, k);
 482                     changed = TRUE;
 483                 } else if (n_off + 2 > 4 - ctx->clues[i]) {
 484                     disconnect(ctx, i, j, dirj);
 485                     disconnect(ctx, i, k, dirk);
 486                     changed = TRUE;
 487                 }
 488             }
 489         }
 490     }
 491
 492     return changed;
 493 }
 494
 495 #define UNVISITED 6
 496
 497 /* build connected components in `dsf', along the lines of `borders'. */
 498 static void dfs_dsf(int i, int w, borderflag *border, int *dsf, int black)
 499 {
 500     int dir;
 501     for (dir = 0; dir < 4; ++dir) {
 502         int ii = i + dx[dir] + w*dy[dir], bdir = BORDER(dir);
 503         if (black ? (border[i] & bdir) : !(border[i] & DISABLED(bdir)))
 504             continue;
 505         if (dsf[ii] != UNVISITED) continue;
 506         dsf_merge(dsf, i, ii);
 507         dfs_dsf(ii, w, border, dsf, black);
 508     }
 509 }
 510
 511 static int is_solved(const game_params *params, clue *clues,
 512                      borderflag *border)
 513 {
 514     int wh = params->w * params->h, k = params->k, *dsf = snew_dsf(wh), i;
 515
 516     assert (dsf[0] == UNVISITED); /* check: UNVISITED and dsf.c match up */
 517
 518     for (i = 0; i < wh; ++i) {
 519         if (dsf[i] == UNVISITED) dfs_dsf(i, params->w, border, dsf, TRUE);
 520         if (dsf_size(dsf, i) != k) goto error;
 521         if (clues[i] == EMPTY) continue;
 522         if (clues[i] != bitcount[border[i] & BORDER_MASK]) goto error;
 523     }
 524
 525     sfree(dsf);
 526     return TRUE;
 527
 528 error:
 529     sfree(dsf);
 530     return FALSE;
 531 }
 532
 533 static int solver(const game_params *params, clue *clues, borderflag *borders)
 534 {
 535     int w = params->w, h = params->h, wh = w*h, changed;
 536     solver_ctx ctx;
 537
 538     ctx.params = params;
 539     ctx.clues = clues;
 540     ctx.borders = borders;
 541     ctx.dsf = snew_dsf(wh);
 542
 543     solver_connected_clues_versus_region_size(&ctx); /* idempotent */
 544     do {
 545         changed  = FALSE;
 546         changed |= solver_number_exhausted(&ctx);
 547         changed |= solver_not_too_big(&ctx);
 548         changed |= solver_not_too_small(&ctx);
 549         changed |= solver_no_dangling_edges(&ctx);
 550         changed |= solver_equivalent_edges(&ctx);
 551     } while (changed);
 552
 553     sfree(ctx.dsf);
 554
 555     return is_solved(params, clues, borders);
 556 }
 557
 558 /* --- Generator ---------------------------------------------------- */
 559
 560 static void init_borders(int w, int h, borderflag *borders)
 561 {
 562     int r, c;
 563     setmem(borders, 0, w*h);
 564     for (c = 0; c < w; ++c) {
 565         borders[c] |= BORDER_U;
 566         borders[w*h-1 - c] |= BORDER_D;
 567     }
 568     for (r = 0; r < h; ++r) {
 569         borders[r*w] |= BORDER_L;
 570         borders[w*h-1 - r*w] |= BORDER_R;
 571     }
 572 }
 573
 574 #define OUT_OF_BOUNDS(x, y, w, h) \
 575     ((x) < 0 || (x) >= (w) || (y) < 0 || (y) >= (h))
 576
 577 #define xshuffle(ptr, len, rs) shuffle((ptr), (len), sizeof (ptr)[0], (rs))
 578
 579 static char *new_game_desc(const game_params *params, random_state *rs,
 580                            char **aux, int interactive)
 581 {
 582     int w = params->w, h = params->h, wh = w*h, k = params->k;
 583
 584     clue *numbers = snewn(wh + 1, clue), *p;
 585     borderflag *rim = snewn(wh, borderflag);
 586     borderflag *scratch_borders = snewn(wh, borderflag);
 587
 588     char *soln = snewa(*aux, wh + 2);
 589     int *shuf = snewn(wh, int);
 590     int *dsf = NULL, i, r, c;
 591
 592     int attempts = 0;
 593
 594     for (i = 0; i < wh; ++i) shuf[i] = i;
 595     xshuffle(shuf, wh, rs);
 596
 597     init_borders(w, h, rim);
 598
 599     assert (!('@' & BORDER_MASK));
 600     *soln++ = 'S';
 601     soln[wh] = '\0';
 602
 603     do {
 604         ++attempts;
 605         setmem(soln, '@', wh);
 606
 607         sfree(dsf);
 608         dsf = divvy_rectangle(w, h, k, rs);
 609
 610         for (r = 0; r < h; ++r)
 611             for (c = 0; c < w; ++c) {
 612                 int i = r * w + c, dir;
 613                 numbers[i] = 0;
 614                 for (dir = 0; dir < 4; ++dir) {
 615                     int rr = r + dy[dir], cc = c + dx[dir], ii = rr * w + cc;
 616                     if (OUT_OF_BOUNDS(cc, rr, w, h) ||
 617                         dsf_canonify(dsf, i) != dsf_canonify(dsf, ii)) {
 618                         ++numbers[i];
 619                         soln[i] |= BORDER(dir);
 620                     }
 621                 }
 622             }
 623
 624         scopy(scratch_borders, rim, wh);
 625     } while (!solver(params, numbers, scratch_borders));
 626
 627     for (i = 0; i < wh; ++i) {
 628         int j = shuf[i];
 629         clue copy = numbers[j];
 630
 631         scopy(scratch_borders, rim, wh);
 632         numbers[j] = EMPTY; /* strip away unnecssary clues */
 633         if (!solver(params, numbers, scratch_borders))
 634             numbers[j] = copy;
 635     }
 636
 637     numbers[wh] = '\0';
 638
 639     sfree(scratch_borders);
 640     sfree(rim);
 641     sfree(shuf);
 642     sfree(dsf);
 643
 644     p = numbers;
 645     r = 0;
 646     for (i = 0; i < wh; ++i) {
 647         if (numbers[i] != EMPTY) {
 648             while (r) {
 649                 while (r > 26) {
 650                     *p++ = 'z';
 651                     r -= 26;
 652                 }
 653                 *p++ = 'a'-1 + r;
 654                 r = 0;
 655             }
 656             *p++ = '0' + numbers[i];
 657         } else ++r;
 658     }
 659     *p++ = '\0';
 660
 661     return sresize(numbers, p - numbers, clue);
 662 }
 663
 664 static char *validate_desc(const game_params *params, const char *desc)
 665 {
 666
 667     int w = params->w, h = params->h, wh = w*h, squares = 0;
 668
 669     for (/* nop */; *desc; ++desc) {
 670         if (islower(*desc)) {
 671             squares += *desc - 'a' + 1;
 672         } else if (isdigit(*desc)) {
 673             if (*desc > '4') {
 674                 static char buf[] = "Invalid (too large) number: '5'";
 675                 assert (isdigit(buf[lenof(buf) - 3]));
 676                 buf[lenof(buf) - 3] = *desc; /* ... or 6, 7, 8, 9 :-) */
 677                 return buf;
 678             }
 679             ++squares;
 680         } else if (isprint(*desc)) {
 681             static char buf[] = "Invalid character in data: '?'";
 682             buf[lenof(buf) - 3] = *desc;
 683             return buf;
 684         } else return "Invalid (unprintable) character in data";
 685     }
 686
 687     if (squares > wh) return "Data describes too many squares";
 688
 689     return NULL;
 690 }
 691
 692 static game_state *new_game(midend *me, const game_params *params,
 693                             const char *desc)
 694 {
 695     int w = params->w, h = params->h, wh = w*h, i;
 696     game_state *state = snew(game_state);
 697
 698     state->shared = snew(shared_state);
 699     state->shared->refcount = 1;
 700     state->shared->params = *params; /* struct copy */
 701     snewa(state->shared->clues, wh);
 702
 703     setmem(state->shared->clues, EMPTY, wh);
 704     for (i = 0; *desc; ++desc) {
 705         if (isdigit(*desc)) state->shared->clues[i++] = *desc - '0';
 706         else if (isalpha(*desc)) i += *desc - 'a' + 1;
 707     }
 708
 709     snewa(state->borders, wh);
 710     init_borders(w, h, state->borders);
 711
 712     state->completed = (params->k == wh);
 713     state->cheated = FALSE;
 714
 715     return state;
 716 }
 717
 718 static game_state *dup_game(const game_state *state)
 719 {
 720     int wh = state->shared->params.w * state->shared->params.h;
 721     game_state *ret = snew(game_state);
 722
 723     ret->borders = dupmem(state->borders, wh);
 724
 725     ret->shared = state->shared;
 726     ++ret->shared->refcount;
 727
 728     ret->completed = state->completed;
 729     ret->cheated = state->cheated;
 730
 731     return ret;
 732 }
 733
 734 static void free_game(game_state *state)
 735 {
 736     if (--state->shared->refcount == 0) {
 737         sfree(state->shared->clues);
 738         sfree(state->shared);
 739     }
 740     sfree(state->borders);
 741     sfree(state);
 742 }
 743
 744 static char *solve_game(const game_state *state, const game_state *currstate,
 745                         const char *aux, char **error)
 746 {
 747     int w = state->shared->params.w, h = state->shared->params.h, wh = w*h;
 748     borderflag *move;
 749
 750     if (aux) return dupstr(aux);
 751
 752     snewa(move, wh + 2);
 753
 754     move[0] = 'S';
 755     init_borders(w, h, move + 1);
 756     move[wh + 1] = '\0';
 757
 758     if (solver(&state->shared->params, state->shared->clues, move + 1))
 759         return (char *) move;
 760
 761     *error = "Sorry, I can't solve this puzzle";
 762     sfree(move);
 763     return NULL;
 764
 765     {
 766         /* compile-time-assert (borderflag is-a-kind-of char).
 767          *
 768          * depends on zero-size arrays being disallowed.  GCC says
 769          * ISO C forbids this, pointing to [-Werror=edantic].  Also,
 770          * it depends on type-checking of (obviously) dead code. */
 771         borderflag b[sizeof (borderflag) == sizeof (char)];
 772         char c = b[0]; b[0] = c;
 773         /* we could at least in principle put this anywhere, but it
 774          * seems silly to not put it where the assumption is used. */
 775     }
 776 }
 777
 778 static int game_can_format_as_text_now(const game_params *params)
 779 {
 780     return TRUE;
 781 }
 782
 783 static char *game_text_format(const game_state *state)
 784 {
 785     int w = state->shared->params.w, h = state->shared->params.h, r, c;
 786     int cw = 4, ch = 2, gw = cw*w + 2, gh = ch * h + 1, len = gw * gh;
 787     char *board;
 788
 789     setmem(snewa(board, len + 1), ' ', len);
 790     for (r = 0; r < h; ++r) {
 791         for (c = 0; c < w; ++c) {
 792             int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2;
 793             int i = r * w + c, clue = state->shared->clues[i];
 794
 795             if (clue != EMPTY) board[center] = '0' + clue;
 796
 797             board[cell] = '+';
 798
 799             if (state->borders[i] & BORDER_U)
 800                 setmem(board + cell + 1, '-', cw - 1);
 801             else if (state->borders[i] & DISABLED(BORDER_U))
 802                 board[cell + cw / 2] = 'x';
 803
 804             if (state->borders[i] & BORDER_L)
 805                 board[cell + gw] = '|';
 806             else if (state->borders[i] & DISABLED(BORDER_L))
 807                 board[cell + gw] = 'x';
 808         }
 809
 810         for (c = 0; c < ch; ++c) {
 811             board[(r*ch + c)*gw + gw - 2] = c ? '|' : '+';
 812             board[(r*ch + c)*gw + gw - 1] = '\n';
 813         }
 814     }
 815
 816     scopy(board + len - gw, board, gw);
 817     board[len] = '\0';
 818
 819     return board;
 820 }
 821
 822 struct game_ui {
 823     int x, y;
 824     unsigned int show: 1;
 825 };
 826
 827 static game_ui *new_ui(const game_state *state)
 828 {
 829     game_ui *ui = snew(game_ui);
 830     ui->x = ui->y = 0;
 831     ui->show = FALSE;
 832     return ui;
 833 }
 834
 835 static void free_ui(game_ui *ui)
 836 {
 837     sfree(ui);
 838 }
 839
 840 static char *encode_ui(const game_ui *ui)
 841 {
 842     return NULL;
 843 }
 844
 845 static void decode_ui(game_ui *ui, const char *encoding)
 846 {
 847     assert (encoding == NULL);
 848 }
 849
 850 static void game_changed_state(game_ui *ui, const game_state *oldstate,
 851                                const game_state *newstate)
 852 {
 853 }
 854
 855 typedef unsigned short dsflags;
 856
 857 struct game_drawstate {
 858     int tilesize;
 859     dsflags *grid;
 860 };
 861
 862 #define TILESIZE (ds->tilesize)
 863 #define MARGIN (ds->tilesize / 2)
 864 #define WIDTH (1 + (TILESIZE >= 16) + (TILESIZE >= 32) + (TILESIZE >= 64))
 865 #define CENTER ((ds->tilesize / 2) + WIDTH/2)
 866
 867 #define FROMCOORD(x) (((x) - MARGIN) / TILESIZE)
 868
 869 enum {MAYBE_LEFT, MAYBE_RIGHT, ON_LEFT, ON_RIGHT, OFF_LEFT, OFF_RIGHT};
 870
 871 static char *interpret_move(const game_state *state, game_ui *ui,
 872                             const game_drawstate *ds, int x, int y, int button)
 873 {
 874     int w = state->shared->params.w, h = state->shared->params.h;
 875     int control = button & MOD_CTRL, shift = button & MOD_SHFT;
 876
 877     button &= ~MOD_MASK;
 878
 879     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
 880         int gx = FROMCOORD(x), gy = FROMCOORD(y), possible = BORDER_MASK;
 881         int px = (x - MARGIN) % TILESIZE, py = (y - MARGIN) % TILESIZE;
 882         int hx, hy, dir, i;
 883
 884         if (OUT_OF_BOUNDS(gx, gy, w, h)) return NULL;
 885
 886         ui->x = gx;
 887         ui->y = gy;
 888
 889         /* find edge closest to click point */
 890         possible &=~ (2*px < TILESIZE ? BORDER_R : BORDER_L);
 891         possible &=~ (2*py < TILESIZE ? BORDER_D : BORDER_U);
 892         px = min(px, TILESIZE - px);
 893         py = min(py, TILESIZE - py);
 894         possible &=~ (px < py ? (BORDER_U|BORDER_D) : (BORDER_L|BORDER_R));
 895
 896         for (dir = 0; dir < 4 && BORDER(dir) != possible; ++dir);
 897         if (dir == 4) return NULL; /* there's not exactly one such edge */
 898
 899         hx = gx + dx[dir];
 900         hy = gy + dy[dir];
 901
 902         if (OUT_OF_BOUNDS(hx, hy, w, h)) return NULL;
 903
 904         ui->show = FALSE;
 905
 906         i = gy * w + gx;
 907         switch ((button == RIGHT_BUTTON) |
 908                 ((state->borders[i] & BORDER(dir)) >> dir << 1) |
 909                 ((state->borders[i] & DISABLED(BORDER(dir))) >> dir >> 2)) {
 910
 911         case MAYBE_LEFT:
 912         case ON_LEFT:
 913         case ON_RIGHT:
 914             return string(80, "F%d,%d,%dF%d,%d,%d",
 915                           gx, gy, BORDER(dir),
 916                           hx, hy, BORDER(FLIP(dir)));
 917
 918         case MAYBE_RIGHT:
 919         case OFF_LEFT:
 920         case OFF_RIGHT:
 921             return string(80, "F%d,%d,%dF%d,%d,%d",
 922                           gx, gy, DISABLED(BORDER(dir)),
 923                           hx, hy, DISABLED(BORDER(FLIP(dir))));
 924         }
 925     }
 926
 927     if (IS_CURSOR_MOVE(button)) {
 928         ui->show = TRUE;
 929         if (control || shift) {
 930             borderflag flag = 0, newflag;
 931             int dir, i =  ui->y * w + ui->x;
 932             x = ui->x;
 933             y = ui->y;
 934             move_cursor(button, &x, &y, w, h, FALSE);
 935             if (OUT_OF_BOUNDS(x, y, w, h)) return NULL;
 936
 937             for (dir = 0; dir < 4; ++dir)
 938                 if (dx[dir] == x - ui->x && dy[dir] == y - ui->y) break;
 939             if (dir == 4) return NULL; /* how the ... ?! */
 940
 941             if (control) flag |= BORDER(dir);
 942             if (shift) flag |= DISABLED(BORDER(dir));
 943
 944             newflag = state->borders[i] ^ flag;
 945             if (newflag & BORDER(dir) && newflag & DISABLED(BORDER(dir)))
 946                 return NULL;
 947
 948             newflag = 0;
 949             if (control) newflag |= BORDER(FLIP(dir));
 950             if (shift) newflag |= DISABLED(BORDER(FLIP(dir)));
 951             return string(80, "F%d,%d,%dF%d,%d,%d",
 952                           ui->x, ui->y, flag, x, y, newflag);
 953         } else {
 954             move_cursor(button, &ui->x, &ui->y, w, h, FALSE);
 955             return "";
 956         }
 957     }
 958
 959     return NULL;
 960 }
 961
 962 static game_state *execute_move(const game_state *state, const char *move)
 963 {
 964     int w = state->shared->params.w, h = state->shared->params.h, wh = w * h;
 965     game_state *ret = dup_game(state);
 966     int nchars, x, y, flag;
 967
 968     if (*move == 'S') {
 969         int i;
 970         ++move;
 971         for (i = 0; i < wh && move[i]; ++i)
 972             ret->borders[i] =
 973                 (move[i] & BORDER_MASK) | DISABLED(~move[i] & BORDER_MASK);
 974         if (i < wh || move[i]) return NULL; /* leaks `ret', then we die */
 975         ret->cheated = ret->completed = TRUE;
 976         return ret;
 977     }
 978
 979     while (sscanf(move, "F%d,%d,%d%n", &x, &y, &flag, &nchars) == 3 &&
 980            !OUT_OF_BOUNDS(x, y, w, h)) {
 981         move += nchars;
 982         ret->borders[y*w + x] ^= flag;
 983     }
 984
 985     if (*move) return NULL; /* leaks `ret', then we die */
 986
 987     if (!ret->completed)
 988         ret->completed = is_solved(&ret->shared->params, ret->shared->clues,
 989                                    ret->borders);
 990
 991     return ret;
 992 }
 993
 994 /* --- Drawing routines --------------------------------------------- */
 995
 996 static void game_compute_size(const game_params *params, int tilesize,
 997                               int *x, int *y)
 998 {
 999     *x = (params->w + 1) * tilesize;
1000     *y = (params->h + 1) * tilesize;
1001 }
1002
1003 static void game_set_size(drawing *dr, game_drawstate *ds,
1004                           const game_params *params, int tilesize)
1005 {
1006     ds->tilesize = tilesize;
1007 }
1008
1009 enum {
1010     COL_BACKGROUND,
1011     COL_FLASH,
1012     COL_GRID,
1013     COL_CLUE = COL_GRID,
1014     COL_LINE_YES = COL_GRID,
1015     COL_LINE_MAYBE,
1016     COL_LINE_NO,
1017     COL_ERROR,
1018
1019     NCOLOURS
1020 };
1021
1022 #define COLOUR(i, r, g, b) \
1023    ((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b)))
1024 #define DARKER 0.9F
1025
1026 static float *game_colours(frontend *fe, int *ncolours)
1027 {
1028     float *ret = snewn(3 * NCOLOURS, float);
1029
1030     game_mkhighlight(fe, ret, COL_BACKGROUND, -1, COL_FLASH);
1031
1032     COLOUR(COL_GRID,   0.0F, 0.0F, 0.0F); /* black */
1033     COLOUR(COL_ERROR,  1.0F, 0.0F, 0.0F); /* red */
1034
1035     COLOUR(COL_LINE_MAYBE, /* yellow */
1036            ret[COL_BACKGROUND*3 + 0] * DARKER,
1037            ret[COL_BACKGROUND*3 + 1] * DARKER,
1038            0.0F);
1039
1040     COLOUR(COL_LINE_NO,
1041            ret[COL_BACKGROUND*3 + 0] * DARKER,
1042            ret[COL_BACKGROUND*3 + 1] * DARKER,
1043            ret[COL_BACKGROUND*3 + 2] * DARKER);
1044
1045     *ncolours = NCOLOURS;
1046     return ret;
1047 }
1048 #undef COLOUR
1049
1050 #define BORDER_ERROR(x) ((x) << 8)
1051 #define F_ERROR_U BORDER_ERROR(BORDER_U) /* BIT( 8) */
1052 #define F_ERROR_R BORDER_ERROR(BORDER_R) /* BIT( 9) */
1053 #define F_ERROR_D BORDER_ERROR(BORDER_D) /* BIT(10) */
1054 #define F_ERROR_L BORDER_ERROR(BORDER_L) /* BIT(11) */
1055 #define F_ERROR_CLUE BIT(12)
1056 #define F_FLASH BIT(13)
1057 #define F_CURSOR BIT(14)
1058
1059 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1060 {
1061     struct game_drawstate *ds = snew(struct game_drawstate);
1062
1063     ds->tilesize = 0;
1064     ds->grid = NULL;
1065
1066     return ds;
1067 }
1068
1069 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1070 {
1071     sfree(ds->grid);
1072     sfree(ds);
1073 }
1074
1075 #define COLOUR(border)                                                  \
1076     (flags & BORDER_ERROR((border)) ? COL_ERROR :                       \
1077      flags & (border)               ? COL_LINE_YES :                    \
1078      flags & DISABLED((border))     ? COL_LINE_NO :                     \
1079                                       COL_LINE_MAYBE)
1080
1081 static void draw_tile(drawing *dr, game_drawstate *ds, int r, int c,
1082                       dsflags flags, int clue)
1083 {
1084     int x = MARGIN + TILESIZE * c, y = MARGIN + TILESIZE * r;
1085
1086     clip(dr, x, y, TILESIZE + WIDTH, TILESIZE + WIDTH); /* { */
1087
1088     draw_rect(dr, x + WIDTH, y + WIDTH, TILESIZE - WIDTH, TILESIZE - WIDTH,
1089               (flags & F_FLASH ? COL_FLASH : COL_BACKGROUND));
1090
1091     if (flags & F_CURSOR)
1092         draw_rect_corners(dr, x + CENTER, y + CENTER, TILESIZE / 3, COL_GRID);
1093
1094     if (clue != EMPTY) {
1095         char buf[2];
1096         buf[0] = '0' + clue;
1097         buf[1] = '\0';
1098         draw_text(dr, x + CENTER, y + CENTER, FONT_VARIABLE,
1099                   TILESIZE / 2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1100                   (flags & F_ERROR_CLUE ? COL_ERROR : COL_CLUE), buf);
1101     }
1102
1103
1104 #define ts TILESIZE
1105 #define w WIDTH
1106     draw_rect(dr, x + w,  y,      ts - w, w,      COLOUR(BORDER_U));
1107     draw_rect(dr, x + ts, y + w,  w,      ts - w, COLOUR(BORDER_R));
1108     draw_rect(dr, x + w,  y + ts, ts - w, w,      COLOUR(BORDER_D));
1109     draw_rect(dr, x,      y + w,  w,      ts - w, COLOUR(BORDER_L));
1110 #undef ts
1111 #undef w
1112
1113     unclip(dr); /* } */
1114     draw_update(dr, x, y, TILESIZE + WIDTH, TILESIZE + WIDTH);
1115 }
1116
1117 #define FLASH_TIME 0.7F
1118
1119 static void game_redraw(drawing *dr, game_drawstate *ds,
1120                         const game_state *oldstate, const game_state *state,
1121                         int dir, const game_ui *ui,
1122                         float animtime, float flashtime)
1123 {
1124     int w = state->shared->params.w, h = state->shared->params.h, wh = w*h;
1125     int r, c, i, flash = ((int) (flashtime * 5 / FLASH_TIME)) % 2;
1126     int *black_border_dsf = snew_dsf(wh), *yellow_border_dsf = snew_dsf(wh);
1127     int k = state->shared->params.k;
1128
1129     if (!ds->grid) {
1130         char buf[40];
1131         int bgw = (w+1) * ds->tilesize, bgh = (h+1) * ds->tilesize;
1132         draw_rect(dr, 0, 0, bgw, bgh, COL_BACKGROUND);
1133
1134         for (r = 0; r <= h; ++r)
1135             for (c = 0; c <= w; ++c)
1136                 draw_rect(dr, MARGIN + TILESIZE * c, MARGIN + TILESIZE * r,
1137                           WIDTH, WIDTH, COL_GRID);
1138         draw_update(dr, 0, 0, bgw, bgh);
1139
1140         snewa(ds->grid, wh);
1141         setmem(ds->grid, ~0, wh);
1142
1143         sprintf(buf, "Region size: %d", state->shared->params.k);
1144         status_bar(dr, buf);
1145     }
1146
1147     for (i = 0; i < wh; ++i) {
1148         if (black_border_dsf[i] == UNVISITED)
1149             dfs_dsf(i, w, state->borders, black_border_dsf, TRUE);
1150         if (yellow_border_dsf[i] == UNVISITED)
1151             dfs_dsf(i, w, state->borders, yellow_border_dsf, FALSE);
1152     }
1153
1154     for (r = 0; r < h; ++r)
1155         for (c = 0; c < w; ++c) {
1156             int i = r * w + c, clue = state->shared->clues[i], flags, dir;
1157             int on = bitcount[state->borders[i] & BORDER_MASK];
1158             int off = bitcount[(state->borders[i] >> 4) & BORDER_MASK];
1159
1160             flags = state->borders[i];
1161
1162             if (flash) flags |= F_FLASH;
1163
1164             if (clue != EMPTY && (on > clue || clue > 4 - off))
1165                 flags |= F_ERROR_CLUE;
1166
1167             if (ui->show && ui->x == c && ui->y == r)
1168                 flags |= F_CURSOR;
1169
1170             /* border errors */
1171             for (dir = 0; dir < 4; ++dir) {
1172                 int rr = r + dy[dir], cc = c + dx[dir], ii = rr * w + cc;
1173
1174                 if (OUT_OF_BOUNDS(cc, rr, w, h)) continue;
1175
1176                 /* we draw each border twice, except the outermost
1177                  * big border, so we have to check for errors on
1178                  * both sides of each border.*/
1179                 if (/* region too large */
1180                     ((dsf_size(yellow_border_dsf, i) > k ||
1181                       dsf_size(yellow_border_dsf, ii) > k) &&
1182                      (dsf_canonify(yellow_border_dsf, i) !=
1183                       dsf_canonify(yellow_border_dsf, ii)))
1184
1185                     ||
1186                     /* region too small */
1187                     ((dsf_size(black_border_dsf, i) < k ||
1188                       dsf_size(black_border_dsf, ii) < k) &&
1189                      dsf_canonify(black_border_dsf, i) !=
1190                      dsf_canonify(black_border_dsf, ii))
1191
1192                     ||
1193                     /* dangling borders within a single region */
1194                     ((state->borders[i] & BORDER(dir)) &&
1195                      /* we know it's a single region because there's a
1196                       * path crossing no border from i to ii... */
1197                      (dsf_canonify(yellow_border_dsf, i) ==
1198                       dsf_canonify(yellow_border_dsf, ii) ||
1199                       /* or because any such border would be an error */
1200                       (dsf_size(black_border_dsf, i) <= k &&
1201                        dsf_canonify(black_border_dsf, i) ==
1202                        dsf_canonify(black_border_dsf, ii)))))
1203
1204                     flags |= BORDER_ERROR(BORDER(dir));
1205             }
1206
1207             if (flags == ds->grid[i]) continue;
1208             ds->grid[i] = flags;
1209             draw_tile(dr, ds, r, c, ds->grid[i], clue);
1210         }
1211
1212     sfree(black_border_dsf);
1213     sfree(yellow_border_dsf);
1214 }
1215
1216 static float game_anim_length(const game_state *oldstate,
1217                               const game_state *newstate,
1218                               int dir, game_ui *ui)
1219 {
1220     return 0.0F;
1221 }
1222
1223 static float game_flash_length(const game_state *oldstate,
1224                                const game_state *newstate,
1225                                int dir, game_ui *ui)
1226 {
1227     if (newstate->completed && !newstate->cheated && !oldstate->completed)
1228         return FLASH_TIME;
1229     return 0.0F;
1230 }
1231
1232 static int game_status(const game_state *state)
1233 {
1234     return state->completed ? +1 : 0;
1235 }
1236
1237 static int game_timing_state(const game_state *state, game_ui *ui)
1238 {
1239     assert (!"this shouldn't get called");
1240     return 0;                          /* placate optimiser */
1241 }
1242
1243 static void game_print_size(const game_params *params, float *x, float *y)
1244 {
1245     int pw, ph;
1246
1247     game_compute_size(params, 700, &pw, &ph); /* 7mm, like loopy */
1248
1249     *x = pw / 100.0F;
1250     *y = ph / 100.0F;
1251 }
1252
1253 static void print_line(drawing *dr, int x1, int y1, int x2, int y2,
1254                        int colour, int full)
1255 {
1256     if (!full) {
1257         int i, subdivisions = 8;
1258         for (i = 1; i < subdivisions; ++i) {
1259             int x = (x1 * (subdivisions - i) + x2 * i) / subdivisions;
1260             int y = (y1 * (subdivisions - i) + y2 * i) / subdivisions;
1261             draw_circle(dr, x, y, 3, colour, colour);
1262         }
1263     } else draw_line(dr, x1, y1, x2, y2, colour);
1264 }
1265
1266 static void game_print(drawing *dr, const game_state *state, int tilesize)
1267 {
1268     int w = state->shared->params.w, h = state->shared->params.h;
1269     int ink = print_mono_colour(dr, 0);
1270     game_drawstate for_tilesize_macros, *ds = &for_tilesize_macros;
1271     int r, c;
1272
1273     ds->tilesize = tilesize;
1274
1275     for (r = 0; r < h; ++r)
1276         for (c = 0; c < w; ++c) {
1277             int x = MARGIN + TILESIZE * c, y = MARGIN + TILESIZE * r;
1278             int i = r * w + c, clue = state->shared->clues[i];
1279
1280             if (clue != EMPTY) {
1281                 char buf[2];
1282                 buf[0] = '0' + clue;
1283                 buf[1] = '\0';
1284                 draw_text(dr, x + CENTER, y + CENTER, FONT_VARIABLE,
1285                           TILESIZE / 2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1286                           ink, buf);
1287             }
1288
1289 #define ts TILESIZE
1290 #define FULL(DIR) (state->borders[i] & (BORDER_ ## DIR))
1291             print_line(dr, x,      y,      x + ts, y,      ink, FULL(U));
1292             print_line(dr, x + ts, y,      x + ts, y + ts, ink, FULL(R));
1293             print_line(dr, x,      y + ts, x + ts, y + ts, ink, FULL(D));
1294             print_line(dr, x,      y,      x,      y + ts, ink, FULL(L));
1295 #undef ts
1296 #undef FULL
1297         }
1298
1299     for (r = 1; r < h; ++r)
1300         for (c = 1; c < w; ++c) {
1301             int j = r * w + c, i = j - 1 - w;
1302             int x = MARGIN + TILESIZE * c, y = MARGIN + TILESIZE * r;
1303             if (state->borders[i] & (BORDER_D|BORDER_R)) continue;
1304             if (state->borders[j] & (BORDER_U|BORDER_L)) continue;
1305             draw_circle(dr, x, y, 3, ink, ink);
1306         }
1307 }
1308
1309 #ifdef COMBINED
1310 #define thegame palisade
1311 #endif
1312
1313 const struct game thegame = {
1314     "Palisade", "games.palisade", "palisade",
1315     default_params,
1316     game_fetch_preset,
1317     decode_params,
1318     encode_params,
1319     free_params,
1320     dup_params,
1321     TRUE, game_configure, custom_params,
1322     validate_params,
1323     new_game_desc,
1324     validate_desc,
1325     new_game,
1326     dup_game,
1327     free_game,
1328     TRUE, solve_game,
1329     TRUE, game_can_format_as_text_now, game_text_format,
1330     new_ui,
1331     free_ui,
1332     encode_ui,
1333     decode_ui,
1334     game_changed_state,
1335     interpret_move,
1336     execute_move,
1337     48, game_compute_size, game_set_size,
1338     game_colours,
1339     game_new_drawstate,
1340     game_free_drawstate,
1341     game_redraw,
1342     game_anim_length,
1343     game_flash_length,
1344     game_status,
1345     TRUE, FALSE, game_print_size, game_print,
1346     TRUE,                                     /* wants_statusbar */
1347     FALSE, game_timing_state,
1348     0,                                         /* flags */
1349 };