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