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         int i;
 760         for (i = 0; i < wh; i++)
 761             move[i+1] |= '@';          /* turn into sensible ASCII */
 762         return (char *) move;
 763     }
 764
 765     *error = "Sorry, I can't solve this puzzle";
 766     sfree(move);
 767     return NULL;
 768
 769     {
 770         /* compile-time-assert (borderflag is-a-kind-of char).
 771          *
 772          * depends on zero-size arrays being disallowed.  GCC says
 773          * ISO C forbids this, pointing to [-Werror=edantic].  Also,
 774          * it depends on type-checking of (obviously) dead code. */
 775         borderflag b[sizeof (borderflag) == sizeof (char)];
 776         char c = b[0]; b[0] = c;
 777         /* we could at least in principle put this anywhere, but it
 778          * seems silly to not put it where the assumption is used. */
 779     }
 780 }
 781
 782 static int game_can_format_as_text_now(const game_params *params)
 783 {
 784     return TRUE;
 785 }
 786
 787 static char *game_text_format(const game_state *state)
 788 {
 789     int w = state->shared->params.w, h = state->shared->params.h, r, c;
 790     int cw = 4, ch = 2, gw = cw*w + 2, gh = ch * h + 1, len = gw * gh;
 791     char *board;
 792
 793     setmem(snewa(board, len + 1), ' ', len);
 794     for (r = 0; r < h; ++r) {
 795         for (c = 0; c < w; ++c) {
 796             int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2;
 797             int i = r * w + c, clue = state->shared->clues[i];
 798
 799             if (clue != EMPTY) board[center] = '0' + clue;
 800
 801             board[cell] = '+';
 802
 803             if (state->borders[i] & BORDER_U)
 804                 setmem(board + cell + 1, '-', cw - 1);
 805             else if (state->borders[i] & DISABLED(BORDER_U))
 806                 board[cell + cw / 2] = 'x';
 807
 808             if (state->borders[i] & BORDER_L)
 809                 board[cell + gw] = '|';
 810             else if (state->borders[i] & DISABLED(BORDER_L))
 811                 board[cell + gw] = 'x';
 812         }
 813
 814         for (c = 0; c < ch; ++c) {
 815             board[(r*ch + c)*gw + gw - 2] = c ? '|' : '+';
 816             board[(r*ch + c)*gw + gw - 1] = '\n';
 817         }
 818     }
 819
 820     scopy(board + len - gw, board, gw);
 821     board[len] = '\0';
 822
 823     return board;
 824 }
 825
 826 struct game_ui {
 827     int x, y;
 828     unsigned int show: 1;
 829 };
 830
 831 static game_ui *new_ui(const game_state *state)
 832 {
 833     game_ui *ui = snew(game_ui);
 834     ui->x = ui->y = 0;
 835     ui->show = FALSE;
 836     return ui;
 837 }
 838
 839 static void free_ui(game_ui *ui)
 840 {
 841     sfree(ui);
 842 }
 843
 844 static char *encode_ui(const game_ui *ui)
 845 {
 846     return NULL;
 847 }
 848
 849 static void decode_ui(game_ui *ui, const char *encoding)
 850 {
 851     assert (encoding == NULL);
 852 }
 853
 854 static void game_changed_state(game_ui *ui, const game_state *oldstate,
 855                                const game_state *newstate)
 856 {
 857 }
 858
 859 typedef unsigned short dsflags;
 860
 861 struct game_drawstate {
 862     int tilesize;
 863     dsflags *grid;
 864 };
 865
 866 #define TILESIZE (ds->tilesize)
 867 #define MARGIN (ds->tilesize / 2)
 868 #define WIDTH (1 + (TILESIZE >= 16) + (TILESIZE >= 32) + (TILESIZE >= 64))
 869 #define CENTER ((ds->tilesize / 2) + WIDTH/2)
 870
 871 #define FROMCOORD(x) (((x) - MARGIN) / TILESIZE)
 872
 873 enum {MAYBE_LEFT, MAYBE_RIGHT, ON_LEFT, ON_RIGHT, OFF_LEFT, OFF_RIGHT};
 874
 875 static char *interpret_move(const game_state *state, game_ui *ui,
 876                             const game_drawstate *ds, int x, int y, int button)
 877 {
 878     int w = state->shared->params.w, h = state->shared->params.h;
 879     int control = button & MOD_CTRL, shift = button & MOD_SHFT;
 880
 881     button &= ~MOD_MASK;
 882
 883     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
 884         int gx = FROMCOORD(x), gy = FROMCOORD(y), possible = BORDER_MASK;
 885         int px = (x - MARGIN) % TILESIZE, py = (y - MARGIN) % TILESIZE;
 886         int hx, hy, dir, i;
 887
 888         if (OUT_OF_BOUNDS(gx, gy, w, h)) return NULL;
 889
 890         ui->x = gx;
 891         ui->y = gy;
 892
 893         /* find edge closest to click point */
 894         possible &=~ (2*px < TILESIZE ? BORDER_R : BORDER_L);
 895         possible &=~ (2*py < TILESIZE ? BORDER_D : BORDER_U);
 896         px = min(px, TILESIZE - px);
 897         py = min(py, TILESIZE - py);
 898         possible &=~ (px < py ? (BORDER_U|BORDER_D) : (BORDER_L|BORDER_R));
 899
 900         for (dir = 0; dir < 4 && BORDER(dir) != possible; ++dir);
 901         if (dir == 4) return NULL; /* there's not exactly one such edge */
 902
 903         hx = gx + dx[dir];
 904         hy = gy + dy[dir];
 905
 906         if (OUT_OF_BOUNDS(hx, hy, w, h)) return NULL;
 907
 908         ui->show = FALSE;
 909
 910         i = gy * w + gx;
 911         switch ((button == RIGHT_BUTTON) |
 912                 ((state->borders[i] & BORDER(dir)) >> dir << 1) |
 913                 ((state->borders[i] & DISABLED(BORDER(dir))) >> dir >> 2)) {
 914
 915         case MAYBE_LEFT:
 916         case ON_LEFT:
 917         case ON_RIGHT:
 918             return string(80, "F%d,%d,%dF%d,%d,%d",
 919                           gx, gy, BORDER(dir),
 920                           hx, hy, BORDER(FLIP(dir)));
 921
 922         case MAYBE_RIGHT:
 923         case OFF_LEFT:
 924         case OFF_RIGHT:
 925             return string(80, "F%d,%d,%dF%d,%d,%d",
 926                           gx, gy, DISABLED(BORDER(dir)),
 927                           hx, hy, DISABLED(BORDER(FLIP(dir))));
 928         }
 929     }
 930
 931     if (IS_CURSOR_MOVE(button)) {
 932         ui->show = TRUE;
 933         if (control || shift) {
 934             borderflag flag = 0, newflag;
 935             int dir, i =  ui->y * w + ui->x;
 936             x = ui->x;
 937             y = ui->y;
 938             move_cursor(button, &x, &y, w, h, FALSE);
 939             if (OUT_OF_BOUNDS(x, y, w, h)) return NULL;
 940
 941             for (dir = 0; dir < 4; ++dir)
 942                 if (dx[dir] == x - ui->x && dy[dir] == y - ui->y) break;
 943             if (dir == 4) return NULL; /* how the ... ?! */
 944
 945             if (control) flag |= BORDER(dir);
 946             if (shift) flag |= DISABLED(BORDER(dir));
 947
 948             newflag = state->borders[i] ^ flag;
 949             if (newflag & BORDER(dir) && newflag & DISABLED(BORDER(dir)))
 950                 return NULL;
 951
 952             newflag = 0;
 953             if (control) newflag |= BORDER(FLIP(dir));
 954             if (shift) newflag |= DISABLED(BORDER(FLIP(dir)));
 955             return string(80, "F%d,%d,%dF%d,%d,%d",
 956                           ui->x, ui->y, flag, x, y, newflag);
 957         } else {
 958             move_cursor(button, &ui->x, &ui->y, w, h, FALSE);
 959             return "";
 960         }
 961     }
 962
 963     return NULL;
 964 }
 965
 966 static game_state *execute_move(const game_state *state, const char *move)
 967 {
 968     int w = state->shared->params.w, h = state->shared->params.h, wh = w * h;
 969     game_state *ret = dup_game(state);
 970     int nchars, x, y, flag;
 971
 972     if (*move == 'S') {
 973         int i;
 974         ++move;
 975         for (i = 0; i < wh && move[i]; ++i)
 976             ret->borders[i] =
 977                 (move[i] & BORDER_MASK) | DISABLED(~move[i] & BORDER_MASK);
 978         if (i < wh || move[i]) return NULL; /* leaks `ret', then we die */
 979         ret->cheated = ret->completed = TRUE;
 980         return ret;
 981     }
 982
 983     while (sscanf(move, "F%d,%d,%d%n", &x, &y, &flag, &nchars) == 3 &&
 984            !OUT_OF_BOUNDS(x, y, w, h)) {
 985         move += nchars;
 986         ret->borders[y*w + x] ^= flag;
 987     }
 988
 989     if (*move) return NULL; /* leaks `ret', then we die */
 990
 991     if (!ret->completed)
 992         ret->completed = is_solved(&ret->shared->params, ret->shared->clues,
 993                                    ret->borders);
 994
 995     return ret;
 996 }
 997
 998 /* --- Drawing routines --------------------------------------------- */
 999
1000 static void game_compute_size(const game_params *params, int tilesize,
1001                               int *x, int *y)
1002 {
1003     *x = (params->w + 1) * tilesize;
1004     *y = (params->h + 1) * tilesize;
1005 }
1006
1007 static void game_set_size(drawing *dr, game_drawstate *ds,
1008                           const game_params *params, int tilesize)
1009 {
1010     ds->tilesize = tilesize;
1011 }
1012
1013 enum {
1014     COL_BACKGROUND,
1015     COL_FLASH,
1016     COL_GRID,
1017     COL_CLUE = COL_GRID,
1018     COL_LINE_YES = COL_GRID,
1019     COL_LINE_MAYBE,
1020     COL_LINE_NO,
1021     COL_ERROR,
1022
1023     NCOLOURS
1024 };
1025
1026 #define COLOUR(i, r, g, b) \
1027    ((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b)))
1028 #define DARKER 0.9F
1029
1030 static float *game_colours(frontend *fe, int *ncolours)
1031 {
1032     float *ret = snewn(3 * NCOLOURS, float);
1033
1034     game_mkhighlight(fe, ret, COL_BACKGROUND, -1, COL_FLASH);
1035
1036     COLOUR(COL_GRID,   0.0F, 0.0F, 0.0F); /* black */
1037     COLOUR(COL_ERROR,  1.0F, 0.0F, 0.0F); /* red */
1038
1039     COLOUR(COL_LINE_MAYBE, /* yellow */
1040            ret[COL_BACKGROUND*3 + 0] * DARKER,
1041            ret[COL_BACKGROUND*3 + 1] * DARKER,
1042            0.0F);
1043
1044     COLOUR(COL_LINE_NO,
1045            ret[COL_BACKGROUND*3 + 0] * DARKER,
1046            ret[COL_BACKGROUND*3 + 1] * DARKER,
1047            ret[COL_BACKGROUND*3 + 2] * DARKER);
1048
1049     *ncolours = NCOLOURS;
1050     return ret;
1051 }
1052 #undef COLOUR
1053
1054 #define BORDER_ERROR(x) ((x) << 8)
1055 #define F_ERROR_U BORDER_ERROR(BORDER_U) /* BIT( 8) */
1056 #define F_ERROR_R BORDER_ERROR(BORDER_R) /* BIT( 9) */
1057 #define F_ERROR_D BORDER_ERROR(BORDER_D) /* BIT(10) */
1058 #define F_ERROR_L BORDER_ERROR(BORDER_L) /* BIT(11) */
1059 #define F_ERROR_CLUE BIT(12)
1060 #define F_FLASH BIT(13)
1061 #define F_CURSOR BIT(14)
1062
1063 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1064 {
1065     struct game_drawstate *ds = snew(struct game_drawstate);
1066
1067     ds->tilesize = 0;
1068     ds->grid = NULL;
1069
1070     return ds;
1071 }
1072
1073 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1074 {
1075     sfree(ds->grid);
1076     sfree(ds);
1077 }
1078
1079 #define COLOUR(border)                                                  \
1080     (flags & BORDER_ERROR((border)) ? COL_ERROR :                       \
1081      flags & (border)               ? COL_LINE_YES :                    \
1082      flags & DISABLED((border))     ? COL_LINE_NO :                     \
1083                                       COL_LINE_MAYBE)
1084
1085 static void draw_tile(drawing *dr, game_drawstate *ds, int r, int c,
1086                       dsflags flags, int clue)
1087 {
1088     int x = MARGIN + TILESIZE * c, y = MARGIN + TILESIZE * r;
1089
1090     clip(dr, x, y, TILESIZE + WIDTH, TILESIZE + WIDTH); /* { */
1091
1092     draw_rect(dr, x + WIDTH, y + WIDTH, TILESIZE - WIDTH, TILESIZE - WIDTH,
1093               (flags & F_FLASH ? COL_FLASH : COL_BACKGROUND));
1094
1095     if (flags & F_CURSOR)
1096         draw_rect_corners(dr, x + CENTER, y + CENTER, TILESIZE / 3, COL_GRID);
1097
1098     if (clue != EMPTY) {
1099         char buf[2];
1100         buf[0] = '0' + clue;
1101         buf[1] = '\0';
1102         draw_text(dr, x + CENTER, y + CENTER, FONT_VARIABLE,
1103                   TILESIZE / 2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1104                   (flags & F_ERROR_CLUE ? COL_ERROR : COL_CLUE), buf);
1105     }
1106
1107
1108 #define ts TILESIZE
1109 #define w WIDTH
1110     draw_rect(dr, x + w,  y,      ts - w, w,      COLOUR(BORDER_U));
1111     draw_rect(dr, x + ts, y + w,  w,      ts - w, COLOUR(BORDER_R));
1112     draw_rect(dr, x + w,  y + ts, ts - w, w,      COLOUR(BORDER_D));
1113     draw_rect(dr, x,      y + w,  w,      ts - w, COLOUR(BORDER_L));
1114 #undef ts
1115 #undef w
1116
1117     unclip(dr); /* } */
1118     draw_update(dr, x, y, TILESIZE + WIDTH, TILESIZE + WIDTH);
1119 }
1120
1121 #define FLASH_TIME 0.7F
1122
1123 static void game_redraw(drawing *dr, game_drawstate *ds,
1124                         const game_state *oldstate, const game_state *state,
1125                         int dir, const game_ui *ui,
1126                         float animtime, float flashtime)
1127 {
1128     int w = state->shared->params.w, h = state->shared->params.h, wh = w*h;
1129     int r, c, i, flash = ((int) (flashtime * 5 / FLASH_TIME)) % 2;
1130     int *black_border_dsf = snew_dsf(wh), *yellow_border_dsf = snew_dsf(wh);
1131     int k = state->shared->params.k;
1132
1133     if (!ds->grid) {
1134         char buf[40];
1135         int bgw = (w+1) * ds->tilesize, bgh = (h+1) * ds->tilesize;
1136         draw_rect(dr, 0, 0, bgw, bgh, COL_BACKGROUND);
1137
1138         for (r = 0; r <= h; ++r)
1139             for (c = 0; c <= w; ++c)
1140                 draw_rect(dr, MARGIN + TILESIZE * c, MARGIN + TILESIZE * r,
1141                           WIDTH, WIDTH, COL_GRID);
1142         draw_update(dr, 0, 0, bgw, bgh);
1143
1144         snewa(ds->grid, wh);
1145         setmem(ds->grid, ~0, wh);
1146
1147         sprintf(buf, "Region size: %d", state->shared->params.k);
1148         status_bar(dr, buf);
1149     }
1150
1151     for (i = 0; i < wh; ++i) {
1152         if (black_border_dsf[i] == UNVISITED)
1153             dfs_dsf(i, w, state->borders, black_border_dsf, TRUE);
1154         if (yellow_border_dsf[i] == UNVISITED)
1155             dfs_dsf(i, w, state->borders, yellow_border_dsf, FALSE);
1156     }
1157
1158     for (r = 0; r < h; ++r)
1159         for (c = 0; c < w; ++c) {
1160             int i = r * w + c, clue = state->shared->clues[i], flags, dir;
1161             int on = bitcount[state->borders[i] & BORDER_MASK];
1162             int off = bitcount[(state->borders[i] >> 4) & BORDER_MASK];
1163
1164             flags = state->borders[i];
1165
1166             if (flash) flags |= F_FLASH;
1167
1168             if (clue != EMPTY && (on > clue || clue > 4 - off))
1169                 flags |= F_ERROR_CLUE;
1170
1171             if (ui->show && ui->x == c && ui->y == r)
1172                 flags |= F_CURSOR;
1173
1174             /* border errors */
1175             for (dir = 0; dir < 4; ++dir) {
1176                 int rr = r + dy[dir], cc = c + dx[dir], ii = rr * w + cc;
1177
1178                 if (OUT_OF_BOUNDS(cc, rr, w, h)) continue;
1179
1180                 /* we draw each border twice, except the outermost
1181                  * big border, so we have to check for errors on
1182                  * both sides of each border.*/
1183                 if (/* region too large */
1184                     ((dsf_size(yellow_border_dsf, i) > k ||
1185                       dsf_size(yellow_border_dsf, ii) > k) &&
1186                      (dsf_canonify(yellow_border_dsf, i) !=
1187                       dsf_canonify(yellow_border_dsf, ii)))
1188
1189                     ||
1190                     /* region too small */
1191                     ((dsf_size(black_border_dsf, i) < k ||
1192                       dsf_size(black_border_dsf, ii) < k) &&
1193                      dsf_canonify(black_border_dsf, i) !=
1194                      dsf_canonify(black_border_dsf, ii))
1195
1196                     ||
1197                     /* dangling borders within a single region */
1198                     ((state->borders[i] & BORDER(dir)) &&
1199                      /* we know it's a single region because there's a
1200                       * path crossing no border from i to ii... */
1201                      (dsf_canonify(yellow_border_dsf, i) ==
1202                       dsf_canonify(yellow_border_dsf, ii) ||
1203                       /* or because any such border would be an error */
1204                       (dsf_size(black_border_dsf, i) <= k &&
1205                        dsf_canonify(black_border_dsf, i) ==
1206                        dsf_canonify(black_border_dsf, ii)))))
1207
1208                     flags |= BORDER_ERROR(BORDER(dir));
1209             }
1210
1211             if (flags == ds->grid[i]) continue;
1212             ds->grid[i] = flags;
1213             draw_tile(dr, ds, r, c, ds->grid[i], clue);
1214         }
1215
1216     sfree(black_border_dsf);
1217     sfree(yellow_border_dsf);
1218 }
1219
1220 static float game_anim_length(const game_state *oldstate,
1221                               const game_state *newstate,
1222                               int dir, game_ui *ui)
1223 {
1224     return 0.0F;
1225 }
1226
1227 static float game_flash_length(const game_state *oldstate,
1228                                const game_state *newstate,
1229                                int dir, game_ui *ui)
1230 {
1231     if (newstate->completed && !newstate->cheated && !oldstate->completed)
1232         return FLASH_TIME;
1233     return 0.0F;
1234 }
1235
1236 static int game_status(const game_state *state)
1237 {
1238     return state->completed ? +1 : 0;
1239 }
1240
1241 static int game_timing_state(const game_state *state, game_ui *ui)
1242 {
1243     assert (!"this shouldn't get called");
1244     return 0;                          /* placate optimiser */
1245 }
1246
1247 static void game_print_size(const game_params *params, float *x, float *y)
1248 {
1249     int pw, ph;
1250
1251     game_compute_size(params, 700, &pw, &ph); /* 7mm, like loopy */
1252
1253     *x = pw / 100.0F;
1254     *y = ph / 100.0F;
1255 }
1256
1257 static void print_line(drawing *dr, int x1, int y1, int x2, int y2,
1258                        int colour, int full)
1259 {
1260     if (!full) {
1261         int i, subdivisions = 8;
1262         for (i = 1; i < subdivisions; ++i) {
1263             int x = (x1 * (subdivisions - i) + x2 * i) / subdivisions;
1264             int y = (y1 * (subdivisions - i) + y2 * i) / subdivisions;
1265             draw_circle(dr, x, y, 3, colour, colour);
1266         }
1267     } else draw_line(dr, x1, y1, x2, y2, colour);
1268 }
1269
1270 static void game_print(drawing *dr, const game_state *state, int tilesize)
1271 {
1272     int w = state->shared->params.w, h = state->shared->params.h;
1273     int ink = print_mono_colour(dr, 0);
1274     game_drawstate for_tilesize_macros, *ds = &for_tilesize_macros;
1275     int r, c;
1276
1277     ds->tilesize = tilesize;
1278
1279     for (r = 0; r < h; ++r)
1280         for (c = 0; c < w; ++c) {
1281             int x = MARGIN + TILESIZE * c, y = MARGIN + TILESIZE * r;
1282             int i = r * w + c, clue = state->shared->clues[i];
1283
1284             if (clue != EMPTY) {
1285                 char buf[2];
1286                 buf[0] = '0' + clue;
1287                 buf[1] = '\0';
1288                 draw_text(dr, x + CENTER, y + CENTER, FONT_VARIABLE,
1289                           TILESIZE / 2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1290                           ink, buf);
1291             }
1292
1293 #define ts TILESIZE
1294 #define FULL(DIR) (state->borders[i] & (BORDER_ ## DIR))
1295             print_line(dr, x,      y,      x + ts, y,      ink, FULL(U));
1296             print_line(dr, x + ts, y,      x + ts, y + ts, ink, FULL(R));
1297             print_line(dr, x,      y + ts, x + ts, y + ts, ink, FULL(D));
1298             print_line(dr, x,      y,      x,      y + ts, ink, FULL(L));
1299 #undef ts
1300 #undef FULL
1301         }
1302
1303     for (r = 1; r < h; ++r)
1304         for (c = 1; c < w; ++c) {
1305             int j = r * w + c, i = j - 1 - w;
1306             int x = MARGIN + TILESIZE * c, y = MARGIN + TILESIZE * r;
1307             if (state->borders[i] & (BORDER_D|BORDER_R)) continue;
1308             if (state->borders[j] & (BORDER_U|BORDER_L)) continue;
1309             draw_circle(dr, x, y, 3, ink, ink);
1310         }
1311 }
1312
1313 #ifdef COMBINED
1314 #define thegame palisade
1315 #endif
1316
1317 const struct game thegame = {
1318     "Palisade", "games.palisade", "palisade",
1319     default_params,
1320     game_fetch_preset,
1321     decode_params,
1322     encode_params,
1323     free_params,
1324     dup_params,
1325     TRUE, game_configure, custom_params,
1326     validate_params,
1327     new_game_desc,
1328     validate_desc,
1329     new_game,
1330     dup_game,
1331     free_game,
1332     TRUE, solve_game,
1333     TRUE, game_can_format_as_text_now, game_text_format,
1334     new_ui,
1335     free_ui,
1336     encode_ui,
1337     decode_ui,
1338     game_changed_state,
1339     interpret_move,
1340     execute_move,
1341     48, game_compute_size, game_set_size,
1342     game_colours,
1343     game_new_drawstate,
1344     game_free_drawstate,
1345     game_redraw,
1346     game_anim_length,
1347     game_flash_length,
1348     game_status,
1349     TRUE, FALSE, game_print_size, game_print,
1350     TRUE,                                     /* wants_statusbar */
1351     FALSE, game_timing_state,
1352     0,                                         /* flags */
1353 };