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 w = params->w, h = params->h, wh = w*h, k = params->k;
 515     int i, x, y;
 516     int *dsf = snew_dsf(wh);
 517
 518     assert (dsf[0] == UNVISITED); /* check: UNVISITED and dsf.c match up */
 519
 520     /*
 521      * A game is solved if:
 522      *
 523      *  - the borders drawn on the grid divide it into connected
 524      *    components such that every square is in a component of the
 525      *    correct size
 526      *  - the borders also satisfy the clue set
 527      */
 528     for (i = 0; i < wh; ++i) {
 529         if (dsf[i] == UNVISITED) dfs_dsf(i, params->w, border, dsf, TRUE);
 530         if (dsf_size(dsf, i) != k) goto error;
 531         if (clues[i] == EMPTY) continue;
 532         if (clues[i] != bitcount[border[i] & BORDER_MASK]) goto error;
 533     }
 534
 535     /*
 536      * ... and thirdly:
 537      *
 538      *  - there are no *stray* borders, in that every border is
 539      *    actually part of the division between two components.
 540      *    Otherwise you could cheat by finding a subdivision which did
 541      *    not *exceed* any clue square's counter, and then adding a
 542      *    few extra edges.
 543      */
 544     for (y = 0; y < h; y++) {
 545         for (x = 0; x < w; x++) {
 546             if (x+1 < w && (border[y*w+x] & BORDER_R) &&
 547                 dsf_canonify(dsf, y*w+x) == dsf_canonify(dsf, y*w+(x+1)))
 548                 goto error;
 549             if (y+1 < h && (border[y*w+x] & BORDER_D) &&
 550                 dsf_canonify(dsf, y*w+x) == dsf_canonify(dsf, (y+1)*w+x))
 551                 goto error;
 552         }
 553     }
 554
 555     sfree(dsf);
 556     return TRUE;
 557
 558 error:
 559     sfree(dsf);
 560     return FALSE;
 561 }
 562
 563 static int solver(const game_params *params, clue *clues, borderflag *borders)
 564 {
 565     int w = params->w, h = params->h, wh = w*h, changed;
 566     solver_ctx ctx;
 567
 568     ctx.params = params;
 569     ctx.clues = clues;
 570     ctx.borders = borders;
 571     ctx.dsf = snew_dsf(wh);
 572
 573     solver_connected_clues_versus_region_size(&ctx); /* idempotent */
 574     do {
 575         changed  = FALSE;
 576         changed |= solver_number_exhausted(&ctx);
 577         changed |= solver_not_too_big(&ctx);
 578         changed |= solver_not_too_small(&ctx);
 579         changed |= solver_no_dangling_edges(&ctx);
 580         changed |= solver_equivalent_edges(&ctx);
 581     } while (changed);
 582
 583     sfree(ctx.dsf);
 584
 585     return is_solved(params, clues, borders);
 586 }
 587
 588 /* --- Generator ---------------------------------------------------- */
 589
 590 static void init_borders(int w, int h, borderflag *borders)
 591 {
 592     int r, c;
 593     setmem(borders, 0, w*h);
 594     for (c = 0; c < w; ++c) {
 595         borders[c] |= BORDER_U;
 596         borders[w*h-1 - c] |= BORDER_D;
 597     }
 598     for (r = 0; r < h; ++r) {
 599         borders[r*w] |= BORDER_L;
 600         borders[w*h-1 - r*w] |= BORDER_R;
 601     }
 602 }
 603
 604 #define OUT_OF_BOUNDS(x, y, w, h) \
 605     ((x) < 0 || (x) >= (w) || (y) < 0 || (y) >= (h))
 606
 607 #define xshuffle(ptr, len, rs) shuffle((ptr), (len), sizeof (ptr)[0], (rs))
 608
 609 static char *new_game_desc(const game_params *params, random_state *rs,
 610                            char **aux, int interactive)
 611 {
 612     int w = params->w, h = params->h, wh = w*h, k = params->k;
 613
 614     clue *numbers = snewn(wh + 1, clue), *p;
 615     borderflag *rim = snewn(wh, borderflag);
 616     borderflag *scratch_borders = snewn(wh, borderflag);
 617
 618     char *soln = snewa(*aux, wh + 2);
 619     int *shuf = snewn(wh, int);
 620     int *dsf = NULL, i, r, c;
 621
 622     int attempts = 0;
 623
 624     for (i = 0; i < wh; ++i) shuf[i] = i;
 625     xshuffle(shuf, wh, rs);
 626
 627     init_borders(w, h, rim);
 628
 629     assert (!('@' & BORDER_MASK));
 630     *soln++ = 'S';
 631     soln[wh] = '\0';
 632
 633     do {
 634         ++attempts;
 635         setmem(soln, '@', wh);
 636
 637         sfree(dsf);
 638         dsf = divvy_rectangle(w, h, k, rs);
 639
 640         for (r = 0; r < h; ++r)
 641             for (c = 0; c < w; ++c) {
 642                 int i = r * w + c, dir;
 643                 numbers[i] = 0;
 644                 for (dir = 0; dir < 4; ++dir) {
 645                     int rr = r + dy[dir], cc = c + dx[dir], ii = rr * w + cc;
 646                     if (OUT_OF_BOUNDS(cc, rr, w, h) ||
 647                         dsf_canonify(dsf, i) != dsf_canonify(dsf, ii)) {
 648                         ++numbers[i];
 649                         soln[i] |= BORDER(dir);
 650                     }
 651                 }
 652             }
 653
 654         scopy(scratch_borders, rim, wh);
 655     } while (!solver(params, numbers, scratch_borders));
 656
 657     for (i = 0; i < wh; ++i) {
 658         int j = shuf[i];
 659         clue copy = numbers[j];
 660
 661         scopy(scratch_borders, rim, wh);
 662         numbers[j] = EMPTY; /* strip away unnecssary clues */
 663         if (!solver(params, numbers, scratch_borders))
 664             numbers[j] = copy;
 665     }
 666
 667     numbers[wh] = '\0';
 668
 669     sfree(scratch_borders);
 670     sfree(rim);
 671     sfree(shuf);
 672     sfree(dsf);
 673
 674     p = numbers;
 675     r = 0;
 676     for (i = 0; i < wh; ++i) {
 677         if (numbers[i] != EMPTY) {
 678             while (r) {
 679                 while (r > 26) {
 680                     *p++ = 'z';
 681                     r -= 26;
 682                 }
 683                 *p++ = 'a'-1 + r;
 684                 r = 0;
 685             }
 686             *p++ = '0' + numbers[i];
 687         } else ++r;
 688     }
 689     *p++ = '\0';
 690
 691     return sresize(numbers, p - numbers, clue);
 692 }
 693
 694 static char *validate_desc(const game_params *params, const char *desc)
 695 {
 696
 697     int w = params->w, h = params->h, wh = w*h, squares = 0;
 698
 699     for (/* nop */; *desc; ++desc) {
 700         if (islower((unsigned char)*desc)) {
 701             squares += *desc - 'a' + 1;
 702         } else if (isdigit((unsigned char)*desc)) {
 703             if (*desc > '4') {
 704                 static char buf[] = "Invalid (too large) number: '5'";
 705                 assert (isdigit((unsigned char)buf[lenof(buf) - 3]));
 706                 buf[lenof(buf) - 3] = *desc; /* ... or 6, 7, 8, 9 :-) */
 707                 return buf;
 708             }
 709             ++squares;
 710         } else if (isprint((unsigned char)*desc)) {
 711             static char buf[] = "Invalid character in data: '?'";
 712             buf[lenof(buf) - 3] = *desc;
 713             return buf;
 714         } else return "Invalid (unprintable) character in data";
 715     }
 716
 717     if (squares > wh) return "Data describes too many squares";
 718
 719     return NULL;
 720 }
 721
 722 static game_state *new_game(midend *me, const game_params *params,
 723                             const char *desc)
 724 {
 725     int w = params->w, h = params->h, wh = w*h, i;
 726     game_state *state = snew(game_state);
 727
 728     state->shared = snew(shared_state);
 729     state->shared->refcount = 1;
 730     state->shared->params = *params; /* struct copy */
 731     snewa(state->shared->clues, wh);
 732
 733     setmem(state->shared->clues, EMPTY, wh);
 734     for (i = 0; *desc; ++desc) {
 735         if (isdigit((unsigned char)*desc)) state->shared->clues[i++] = *desc - '0';
 736         else if (isalpha((unsigned char)*desc)) i += *desc - 'a' + 1;
 737     }
 738
 739     snewa(state->borders, wh);
 740     init_borders(w, h, state->borders);
 741
 742     state->completed = (params->k == wh);
 743     state->cheated = FALSE;
 744
 745     return state;
 746 }
 747
 748 static game_state *dup_game(const game_state *state)
 749 {
 750     int wh = state->shared->params.w * state->shared->params.h;
 751     game_state *ret = snew(game_state);
 752
 753     ret->borders = dupmem(state->borders, wh);
 754
 755     ret->shared = state->shared;
 756     ++ret->shared->refcount;
 757
 758     ret->completed = state->completed;
 759     ret->cheated = state->cheated;
 760
 761     return ret;
 762 }
 763
 764 static void free_game(game_state *state)
 765 {
 766     if (--state->shared->refcount == 0) {
 767         sfree(state->shared->clues);
 768         sfree(state->shared);
 769     }
 770     sfree(state->borders);
 771     sfree(state);
 772 }
 773
 774 static char *solve_game(const game_state *state, const game_state *currstate,
 775                         const char *aux, char **error)
 776 {
 777     int w = state->shared->params.w, h = state->shared->params.h, wh = w*h;
 778     borderflag *move;
 779
 780     if (aux) return dupstr(aux);
 781
 782     snewa(move, wh + 2);
 783
 784     move[0] = 'S';
 785     init_borders(w, h, move + 1);
 786     move[wh + 1] = '\0';
 787
 788     if (solver(&state->shared->params, state->shared->clues, move + 1)) {
 789         int i;
 790         for (i = 0; i < wh; i++)
 791             move[i+1] |= '@';          /* turn into sensible ASCII */
 792         return (char *) move;
 793     }
 794
 795     *error = "Sorry, I can't solve this puzzle";
 796     sfree(move);
 797     return NULL;
 798
 799     {
 800         /* compile-time-assert (borderflag is-a-kind-of char).
 801          *
 802          * depends on zero-size arrays being disallowed.  GCC says
 803          * ISO C forbids this, pointing to [-Werror=edantic].  Also,
 804          * it depends on type-checking of (obviously) dead code. */
 805         borderflag b[sizeof (borderflag) == sizeof (char)];
 806         char c = b[0]; b[0] = c;
 807         /* we could at least in principle put this anywhere, but it
 808          * seems silly to not put it where the assumption is used. */
 809     }
 810 }
 811
 812 static int game_can_format_as_text_now(const game_params *params)
 813 {
 814     return TRUE;
 815 }
 816
 817 static char *game_text_format(const game_state *state)
 818 {
 819     int w = state->shared->params.w, h = state->shared->params.h, r, c;
 820     int cw = 4, ch = 2, gw = cw*w + 2, gh = ch * h + 1, len = gw * gh;
 821     char *board;
 822
 823     setmem(snewa(board, len + 1), ' ', len);
 824     for (r = 0; r < h; ++r) {
 825         for (c = 0; c < w; ++c) {
 826             int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2;
 827             int i = r * w + c, clue = state->shared->clues[i];
 828
 829             if (clue != EMPTY) board[center] = '0' + clue;
 830
 831             board[cell] = '+';
 832
 833             if (state->borders[i] & BORDER_U)
 834                 setmem(board + cell + 1, '-', cw - 1);
 835             else if (state->borders[i] & DISABLED(BORDER_U))
 836                 board[cell + cw / 2] = 'x';
 837
 838             if (state->borders[i] & BORDER_L)
 839                 board[cell + gw] = '|';
 840             else if (state->borders[i] & DISABLED(BORDER_L))
 841                 board[cell + gw] = 'x';
 842         }
 843
 844         for (c = 0; c < ch; ++c) {
 845             board[(r*ch + c)*gw + gw - 2] = c ? '|' : '+';
 846             board[(r*ch + c)*gw + gw - 1] = '\n';
 847         }
 848     }
 849
 850     scopy(board + len - gw, board, gw);
 851     board[len] = '\0';
 852
 853     return board;
 854 }
 855
 856 struct game_ui {
 857     int x, y;
 858     unsigned int show: 1;
 859 };
 860
 861 static game_ui *new_ui(const game_state *state)
 862 {
 863     game_ui *ui = snew(game_ui);
 864     ui->x = ui->y = 0;
 865     ui->show = FALSE;
 866     return ui;
 867 }
 868
 869 static void free_ui(game_ui *ui)
 870 {
 871     sfree(ui);
 872 }
 873
 874 static char *encode_ui(const game_ui *ui)
 875 {
 876     return NULL;
 877 }
 878
 879 static void decode_ui(game_ui *ui, const char *encoding)
 880 {
 881     assert (encoding == NULL);
 882 }
 883
 884 static void game_changed_state(game_ui *ui, const game_state *oldstate,
 885                                const game_state *newstate)
 886 {
 887 }
 888
 889 typedef unsigned short dsflags;
 890
 891 struct game_drawstate {
 892     int tilesize;
 893     dsflags *grid;
 894 };
 895
 896 #define TILESIZE (ds->tilesize)
 897 #define MARGIN (ds->tilesize / 2)
 898 #define WIDTH (1 + (TILESIZE >= 16) + (TILESIZE >= 32) + (TILESIZE >= 64))
 899 #define CENTER ((ds->tilesize / 2) + WIDTH/2)
 900
 901 #define FROMCOORD(x) (((x) - MARGIN) / TILESIZE)
 902
 903 enum {MAYBE_LEFT, MAYBE_RIGHT, ON_LEFT, ON_RIGHT, OFF_LEFT, OFF_RIGHT};
 904
 905 static char *interpret_move(const game_state *state, game_ui *ui,
 906                             const game_drawstate *ds, int x, int y, int button)
 907 {
 908     int w = state->shared->params.w, h = state->shared->params.h;
 909     int control = button & MOD_CTRL, shift = button & MOD_SHFT;
 910
 911     button &= ~MOD_MASK;
 912
 913     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
 914         int gx = FROMCOORD(x), gy = FROMCOORD(y), possible = BORDER_MASK;
 915         int px = (x - MARGIN) % TILESIZE, py = (y - MARGIN) % TILESIZE;
 916         int hx, hy, dir, i;
 917
 918         if (OUT_OF_BOUNDS(gx, gy, w, h)) return NULL;
 919
 920         ui->x = gx;
 921         ui->y = gy;
 922
 923         /* find edge closest to click point */
 924         possible &=~ (2*px < TILESIZE ? BORDER_R : BORDER_L);
 925         possible &=~ (2*py < TILESIZE ? BORDER_D : BORDER_U);
 926         px = min(px, TILESIZE - px);
 927         py = min(py, TILESIZE - py);
 928         possible &=~ (px < py ? (BORDER_U|BORDER_D) : (BORDER_L|BORDER_R));
 929
 930         for (dir = 0; dir < 4 && BORDER(dir) != possible; ++dir);
 931         if (dir == 4) return NULL; /* there's not exactly one such edge */
 932
 933         hx = gx + dx[dir];
 934         hy = gy + dy[dir];
 935
 936         if (OUT_OF_BOUNDS(hx, hy, w, h)) return NULL;
 937
 938         ui->show = FALSE;
 939
 940         i = gy * w + gx;
 941         switch ((button == RIGHT_BUTTON) |
 942                 ((state->borders[i] & BORDER(dir)) >> dir << 1) |
 943                 ((state->borders[i] & DISABLED(BORDER(dir))) >> dir >> 2)) {
 944
 945         case MAYBE_LEFT:
 946         case ON_LEFT:
 947         case ON_RIGHT:
 948             return string(80, "F%d,%d,%dF%d,%d,%d",
 949                           gx, gy, BORDER(dir),
 950                           hx, hy, BORDER(FLIP(dir)));
 951
 952         case MAYBE_RIGHT:
 953         case OFF_LEFT:
 954         case OFF_RIGHT:
 955             return string(80, "F%d,%d,%dF%d,%d,%d",
 956                           gx, gy, DISABLED(BORDER(dir)),
 957                           hx, hy, DISABLED(BORDER(FLIP(dir))));
 958         }
 959     }
 960
 961     if (IS_CURSOR_MOVE(button)) {
 962         ui->show = TRUE;
 963         if (control || shift) {
 964             borderflag flag = 0, newflag;
 965             int dir, i =  ui->y * w + ui->x;
 966             x = ui->x;
 967             y = ui->y;
 968             move_cursor(button, &x, &y, w, h, FALSE);
 969             if (OUT_OF_BOUNDS(x, y, w, h)) return NULL;
 970
 971             for (dir = 0; dir < 4; ++dir)
 972                 if (dx[dir] == x - ui->x && dy[dir] == y - ui->y) break;
 973             if (dir == 4) return NULL; /* how the ... ?! */
 974
 975             if (control) flag |= BORDER(dir);
 976             if (shift) flag |= DISABLED(BORDER(dir));
 977
 978             newflag = state->borders[i] ^ flag;
 979             if (newflag & BORDER(dir) && newflag & DISABLED(BORDER(dir)))
 980                 return NULL;
 981
 982             newflag = 0;
 983             if (control) newflag |= BORDER(FLIP(dir));
 984             if (shift) newflag |= DISABLED(BORDER(FLIP(dir)));
 985             return string(80, "F%d,%d,%dF%d,%d,%d",
 986                           ui->x, ui->y, flag, x, y, newflag);
 987         } else {
 988             move_cursor(button, &ui->x, &ui->y, w, h, FALSE);
 989             return "";
 990         }
 991     }
 992
 993     return NULL;
 994 }
 995
 996 static game_state *execute_move(const game_state *state, const char *move)
 997 {
 998     int w = state->shared->params.w, h = state->shared->params.h, wh = w * h;
 999     game_state *ret = dup_game(state);
1000     int nchars, x, y, flag;
1001
1002     if (*move == 'S') {
1003         int i;
1004         ++move;
1005         for (i = 0; i < wh && move[i]; ++i)
1006             ret->borders[i] =
1007                 (move[i] & BORDER_MASK) | DISABLED(~move[i] & BORDER_MASK);
1008         if (i < wh || move[i]) return NULL; /* leaks `ret', then we die */
1009         ret->cheated = ret->completed = TRUE;
1010         return ret;
1011     }
1012
1013     while (sscanf(move, "F%d,%d,%d%n", &x, &y, &flag, &nchars) == 3 &&
1014            !OUT_OF_BOUNDS(x, y, w, h)) {
1015         move += nchars;
1016         ret->borders[y*w + x] ^= flag;
1017     }
1018
1019     if (*move) return NULL; /* leaks `ret', then we die */
1020
1021     if (!ret->completed)
1022         ret->completed = is_solved(&ret->shared->params, ret->shared->clues,
1023                                    ret->borders);
1024
1025     return ret;
1026 }
1027
1028 /* --- Drawing routines --------------------------------------------- */
1029
1030 static void game_compute_size(const game_params *params, int tilesize,
1031                               int *x, int *y)
1032 {
1033     *x = (params->w + 1) * tilesize;
1034     *y = (params->h + 1) * tilesize;
1035 }
1036
1037 static void game_set_size(drawing *dr, game_drawstate *ds,
1038                           const game_params *params, int tilesize)
1039 {
1040     ds->tilesize = tilesize;
1041 }
1042
1043 enum {
1044     COL_BACKGROUND,
1045     COL_FLASH,
1046     COL_GRID,
1047     COL_CLUE = COL_GRID,
1048     COL_LINE_YES = COL_GRID,
1049     COL_LINE_MAYBE,
1050     COL_LINE_NO,
1051     COL_ERROR,
1052
1053     NCOLOURS
1054 };
1055
1056 #define COLOUR(i, r, g, b) \
1057    ((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b)))
1058 #define DARKER 0.9F
1059
1060 static float *game_colours(frontend *fe, int *ncolours)
1061 {
1062     float *ret = snewn(3 * NCOLOURS, float);
1063
1064     game_mkhighlight(fe, ret, COL_BACKGROUND, -1, COL_FLASH);
1065
1066     COLOUR(COL_GRID,   0.0F, 0.0F, 0.0F); /* black */
1067     COLOUR(COL_ERROR,  1.0F, 0.0F, 0.0F); /* red */
1068
1069     COLOUR(COL_LINE_MAYBE, /* yellow */
1070            ret[COL_BACKGROUND*3 + 0] * DARKER,
1071            ret[COL_BACKGROUND*3 + 1] * DARKER,
1072            0.0F);
1073
1074     COLOUR(COL_LINE_NO,
1075            ret[COL_BACKGROUND*3 + 0] * DARKER,
1076            ret[COL_BACKGROUND*3 + 1] * DARKER,
1077            ret[COL_BACKGROUND*3 + 2] * DARKER);
1078
1079     *ncolours = NCOLOURS;
1080     return ret;
1081 }
1082 #undef COLOUR
1083
1084 #define BORDER_ERROR(x) ((x) << 8)
1085 #define F_ERROR_U BORDER_ERROR(BORDER_U) /* BIT( 8) */
1086 #define F_ERROR_R BORDER_ERROR(BORDER_R) /* BIT( 9) */
1087 #define F_ERROR_D BORDER_ERROR(BORDER_D) /* BIT(10) */
1088 #define F_ERROR_L BORDER_ERROR(BORDER_L) /* BIT(11) */
1089 #define F_ERROR_CLUE BIT(12)
1090 #define F_FLASH BIT(13)
1091 #define F_CURSOR BIT(14)
1092
1093 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1094 {
1095     struct game_drawstate *ds = snew(struct game_drawstate);
1096
1097     ds->tilesize = 0;
1098     ds->grid = NULL;
1099
1100     return ds;
1101 }
1102
1103 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1104 {
1105     sfree(ds->grid);
1106     sfree(ds);
1107 }
1108
1109 #define COLOUR(border)                                                  \
1110     (flags & BORDER_ERROR((border)) ? COL_ERROR :                       \
1111      flags & (border)               ? COL_LINE_YES :                    \
1112      flags & DISABLED((border))     ? COL_LINE_NO :                     \
1113                                       COL_LINE_MAYBE)
1114
1115 static void draw_tile(drawing *dr, game_drawstate *ds, int r, int c,
1116                       dsflags flags, int clue)
1117 {
1118     int x = MARGIN + TILESIZE * c, y = MARGIN + TILESIZE * r;
1119
1120     clip(dr, x, y, TILESIZE + WIDTH, TILESIZE + WIDTH); /* { */
1121
1122     draw_rect(dr, x + WIDTH, y + WIDTH, TILESIZE - WIDTH, TILESIZE - WIDTH,
1123               (flags & F_FLASH ? COL_FLASH : COL_BACKGROUND));
1124
1125     if (flags & F_CURSOR)
1126         draw_rect_corners(dr, x + CENTER, y + CENTER, TILESIZE / 3, COL_GRID);
1127
1128     if (clue != EMPTY) {
1129         char buf[2];
1130         buf[0] = '0' + clue;
1131         buf[1] = '\0';
1132         draw_text(dr, x + CENTER, y + CENTER, FONT_VARIABLE,
1133                   TILESIZE / 2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1134                   (flags & F_ERROR_CLUE ? COL_ERROR : COL_CLUE), buf);
1135     }
1136
1137
1138 #define ts TILESIZE
1139 #define w WIDTH
1140     draw_rect(dr, x + w,  y,      ts - w, w,      COLOUR(BORDER_U));
1141     draw_rect(dr, x + ts, y + w,  w,      ts - w, COLOUR(BORDER_R));
1142     draw_rect(dr, x + w,  y + ts, ts - w, w,      COLOUR(BORDER_D));
1143     draw_rect(dr, x,      y + w,  w,      ts - w, COLOUR(BORDER_L));
1144 #undef ts
1145 #undef w
1146
1147     unclip(dr); /* } */
1148     draw_update(dr, x, y, TILESIZE + WIDTH, TILESIZE + WIDTH);
1149 }
1150
1151 #define FLASH_TIME 0.7F
1152
1153 static void game_redraw(drawing *dr, game_drawstate *ds,
1154                         const game_state *oldstate, const game_state *state,
1155                         int dir, const game_ui *ui,
1156                         float animtime, float flashtime)
1157 {
1158     int w = state->shared->params.w, h = state->shared->params.h, wh = w*h;
1159     int r, c, i, flash = ((int) (flashtime * 5 / FLASH_TIME)) % 2;
1160     int *black_border_dsf = snew_dsf(wh), *yellow_border_dsf = snew_dsf(wh);
1161     int k = state->shared->params.k;
1162
1163     if (!ds->grid) {
1164         char buf[40];
1165         int bgw = (w+1) * ds->tilesize, bgh = (h+1) * ds->tilesize;
1166         draw_rect(dr, 0, 0, bgw, bgh, COL_BACKGROUND);
1167
1168         for (r = 0; r <= h; ++r)
1169             for (c = 0; c <= w; ++c)
1170                 draw_rect(dr, MARGIN + TILESIZE * c, MARGIN + TILESIZE * r,
1171                           WIDTH, WIDTH, COL_GRID);
1172         draw_update(dr, 0, 0, bgw, bgh);
1173
1174         snewa(ds->grid, wh);
1175         setmem(ds->grid, ~0, wh);
1176
1177         sprintf(buf, "Region size: %d", state->shared->params.k);
1178         status_bar(dr, buf);
1179     }
1180
1181     for (i = 0; i < wh; ++i) {
1182         if (black_border_dsf[i] == UNVISITED)
1183             dfs_dsf(i, w, state->borders, black_border_dsf, TRUE);
1184         if (yellow_border_dsf[i] == UNVISITED)
1185             dfs_dsf(i, w, state->borders, yellow_border_dsf, FALSE);
1186     }
1187
1188     for (r = 0; r < h; ++r)
1189         for (c = 0; c < w; ++c) {
1190             int i = r * w + c, clue = state->shared->clues[i], flags, dir;
1191             int on = bitcount[state->borders[i] & BORDER_MASK];
1192             int off = bitcount[(state->borders[i] >> 4) & BORDER_MASK];
1193
1194             flags = state->borders[i];
1195
1196             if (flash) flags |= F_FLASH;
1197
1198             if (clue != EMPTY && (on > clue || clue > 4 - off))
1199                 flags |= F_ERROR_CLUE;
1200
1201             if (ui->show && ui->x == c && ui->y == r)
1202                 flags |= F_CURSOR;
1203
1204             /* border errors */
1205             for (dir = 0; dir < 4; ++dir) {
1206                 int rr = r + dy[dir], cc = c + dx[dir], ii = rr * w + cc;
1207
1208                 if (OUT_OF_BOUNDS(cc, rr, w, h)) continue;
1209
1210                 /* we draw each border twice, except the outermost
1211                  * big border, so we have to check for errors on
1212                  * both sides of each border.*/
1213                 if (/* region too large */
1214                     ((dsf_size(yellow_border_dsf, i) > k ||
1215                       dsf_size(yellow_border_dsf, ii) > k) &&
1216                      (dsf_canonify(yellow_border_dsf, i) !=
1217                       dsf_canonify(yellow_border_dsf, ii)))
1218
1219                     ||
1220                     /* region too small */
1221                     ((dsf_size(black_border_dsf, i) < k ||
1222                       dsf_size(black_border_dsf, ii) < k) &&
1223                      dsf_canonify(black_border_dsf, i) !=
1224                      dsf_canonify(black_border_dsf, ii))
1225
1226                     ||
1227                     /* dangling borders within a single region */
1228                     ((state->borders[i] & BORDER(dir)) &&
1229                      /* we know it's a single region because there's a
1230                       * path crossing no border from i to ii... */
1231                      (dsf_canonify(yellow_border_dsf, i) ==
1232                       dsf_canonify(yellow_border_dsf, ii) ||
1233                       /* or because any such border would be an error */
1234                       (dsf_size(black_border_dsf, i) <= k &&
1235                        dsf_canonify(black_border_dsf, i) ==
1236                        dsf_canonify(black_border_dsf, ii)))))
1237
1238                     flags |= BORDER_ERROR(BORDER(dir));
1239             }
1240
1241             if (flags == ds->grid[i]) continue;
1242             ds->grid[i] = flags;
1243             draw_tile(dr, ds, r, c, ds->grid[i], clue);
1244         }
1245
1246     sfree(black_border_dsf);
1247     sfree(yellow_border_dsf);
1248 }
1249
1250 static float game_anim_length(const game_state *oldstate,
1251                               const game_state *newstate,
1252                               int dir, game_ui *ui)
1253 {
1254     return 0.0F;
1255 }
1256
1257 static float game_flash_length(const game_state *oldstate,
1258                                const game_state *newstate,
1259                                int dir, game_ui *ui)
1260 {
1261     if (newstate->completed && !newstate->cheated && !oldstate->completed)
1262         return FLASH_TIME;
1263     return 0.0F;
1264 }
1265
1266 static int game_status(const game_state *state)
1267 {
1268     return state->completed ? +1 : 0;
1269 }
1270
1271 static int game_timing_state(const game_state *state, game_ui *ui)
1272 {
1273     assert (!"this shouldn't get called");
1274     return 0;                          /* placate optimiser */
1275 }
1276
1277 static void game_print_size(const game_params *params, float *x, float *y)
1278 {
1279     int pw, ph;
1280
1281     game_compute_size(params, 700, &pw, &ph); /* 7mm, like loopy */
1282
1283     *x = pw / 100.0F;
1284     *y = ph / 100.0F;
1285 }
1286
1287 static void print_line(drawing *dr, int x1, int y1, int x2, int y2,
1288                        int colour, int full)
1289 {
1290     if (!full) {
1291         int i, subdivisions = 8;
1292         for (i = 1; i < subdivisions; ++i) {
1293             int x = (x1 * (subdivisions - i) + x2 * i) / subdivisions;
1294             int y = (y1 * (subdivisions - i) + y2 * i) / subdivisions;
1295             draw_circle(dr, x, y, 3, colour, colour);
1296         }
1297     } else draw_line(dr, x1, y1, x2, y2, colour);
1298 }
1299
1300 static void game_print(drawing *dr, const game_state *state, int tilesize)
1301 {
1302     int w = state->shared->params.w, h = state->shared->params.h;
1303     int ink = print_mono_colour(dr, 0);
1304     game_drawstate for_tilesize_macros, *ds = &for_tilesize_macros;
1305     int r, c;
1306
1307     ds->tilesize = tilesize;
1308
1309     for (r = 0; r < h; ++r)
1310         for (c = 0; c < w; ++c) {
1311             int x = MARGIN + TILESIZE * c, y = MARGIN + TILESIZE * r;
1312             int i = r * w + c, clue = state->shared->clues[i];
1313
1314             if (clue != EMPTY) {
1315                 char buf[2];
1316                 buf[0] = '0' + clue;
1317                 buf[1] = '\0';
1318                 draw_text(dr, x + CENTER, y + CENTER, FONT_VARIABLE,
1319                           TILESIZE / 2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1320                           ink, buf);
1321             }
1322
1323 #define ts TILESIZE
1324 #define FULL(DIR) (state->borders[i] & (BORDER_ ## DIR))
1325             print_line(dr, x,      y,      x + ts, y,      ink, FULL(U));
1326             print_line(dr, x + ts, y,      x + ts, y + ts, ink, FULL(R));
1327             print_line(dr, x,      y + ts, x + ts, y + ts, ink, FULL(D));
1328             print_line(dr, x,      y,      x,      y + ts, ink, FULL(L));
1329 #undef ts
1330 #undef FULL
1331         }
1332
1333     for (r = 1; r < h; ++r)
1334         for (c = 1; c < w; ++c) {
1335             int j = r * w + c, i = j - 1 - w;
1336             int x = MARGIN + TILESIZE * c, y = MARGIN + TILESIZE * r;
1337             if (state->borders[i] & (BORDER_D|BORDER_R)) continue;
1338             if (state->borders[j] & (BORDER_U|BORDER_L)) continue;
1339             draw_circle(dr, x, y, 3, ink, ink);
1340         }
1341 }
1342
1343 #ifdef COMBINED
1344 #define thegame palisade
1345 #endif
1346
1347 const struct game thegame = {
1348     "Palisade", "games.palisade", "palisade",
1349     default_params,
1350     game_fetch_preset,
1351     decode_params,
1352     encode_params,
1353     free_params,
1354     dup_params,
1355     TRUE, game_configure, custom_params,
1356     validate_params,
1357     new_game_desc,
1358     validate_desc,
1359     new_game,
1360     dup_game,
1361     free_game,
1362     TRUE, solve_game,
1363     TRUE, game_can_format_as_text_now, game_text_format,
1364     new_ui,
1365     free_ui,
1366     encode_ui,
1367     decode_ui,
1368     game_changed_state,
1369     interpret_move,
1370     execute_move,
1371     48, game_compute_size, game_set_size,
1372     game_colours,
1373     game_new_drawstate,
1374     game_free_drawstate,
1375     game_redraw,
1376     game_anim_length,
1377     game_flash_length,
1378     game_status,
1379     TRUE, FALSE, game_print_size, game_print,
1380     TRUE,                                     /* wants_statusbar */
1381     FALSE, game_timing_state,
1382     0,                                         /* flags */
1383 };