flip.c

   1 /*
   2  * flip.c: Puzzle involving lighting up all the squares on a grid,
   3  * where each click toggles an overlapping set of lights.
   4  */
   5
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8 #include <string.h>
   9 #include <assert.h>
  10 #include <ctype.h>
  11 #include <math.h>
  12
  13 #include "puzzles.h"
  14 #include "tree234.h"
  15
  16 enum {
  17     COL_BACKGROUND,
  18     COL_WRONG,
  19     COL_RIGHT,
  20     COL_GRID,
  21     COL_DIAG,
  22     COL_HINT,
  23     COL_CURSOR,
  24     NCOLOURS
  25 };
  26
  27 #define PREFERRED_TILE_SIZE 48
  28 #define TILE_SIZE (ds->tilesize)
  29 #define BORDER    (TILE_SIZE / 2)
  30 #define COORD(x)  ( (x) * TILE_SIZE + BORDER )
  31 #define FROMCOORD(x)  ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
  32
  33 #define ANIM_TIME 0.25F
  34 #define FLASH_FRAME 0.07F
  35
  36 /*
  37  * Possible ways to decide which lights are toggled by each click.
  38  * Essentially, each of these describes a means of inventing a
  39  * matrix over GF(2).
  40  */
  41 enum {
  42     CROSSES, RANDOM
  43 };
  44
  45 struct game_params {
  46     int w, h;
  47     int matrix_type;
  48 };
  49
  50 /*
  51  * This structure is shared between all the game_states describing
  52  * a particular game, so it's reference-counted.
  53  */
  54 struct matrix {
  55     int refcount;
  56     unsigned char *matrix;             /* array of (w*h) by (w*h) */
  57 };
  58
  59 struct game_state {
  60     int w, h;
  61     int moves, completed, cheated, hints_active;
  62     unsigned char *grid;               /* array of w*h */
  63     struct matrix *matrix;
  64 };
  65
  66 static game_params *default_params(void)
  67 {
  68     game_params *ret = snew(game_params);
  69
  70     ret->w = ret->h = 5;
  71     ret->matrix_type = CROSSES;
  72
  73     return ret;
  74 }
  75
  76 static const struct game_params flip_presets[] = {
  77     {3, 3, CROSSES},
  78     {4, 4, CROSSES},
  79     {5, 5, CROSSES},
  80     {3, 3, RANDOM},
  81     {4, 4, RANDOM},
  82     {5, 5, RANDOM},
  83 };
  84
  85 static int game_fetch_preset(int i, char **name, game_params **params)
  86 {
  87     game_params *ret;
  88     char str[80];
  89
  90     if (i < 0 || i >= lenof(flip_presets))
  91         return FALSE;
  92
  93     ret = snew(game_params);
  94     *ret = flip_presets[i];
  95
  96     sprintf(str, "%dx%d %s", ret->w, ret->h,
  97             ret->matrix_type == CROSSES ? "Crosses" : "Random");
  98
  99     *name = dupstr(str);
 100     *params = ret;
 101     return TRUE;
 102 }
 103
 104 static void free_params(game_params *params)
 105 {
 106     sfree(params);
 107 }
 108
 109 static game_params *dup_params(const game_params *params)
 110 {
 111     game_params *ret = snew(game_params);
 112     *ret = *params;                    /* structure copy */
 113     return ret;
 114 }
 115
 116 static void decode_params(game_params *ret, char const *string)
 117 {
 118     ret->w = ret->h = atoi(string);
 119     while (*string && isdigit((unsigned char)*string)) string++;
 120     if (*string == 'x') {
 121         string++;
 122         ret->h = atoi(string);
 123         while (*string && isdigit((unsigned char)*string)) string++;
 124     }
 125     if (*string == 'r') {
 126         string++;
 127         ret->matrix_type = RANDOM;
 128     } else if (*string == 'c') {
 129         string++;
 130         ret->matrix_type = CROSSES;
 131     }
 132 }
 133
 134 static char *encode_params(const game_params *params, int full)
 135 {
 136     char data[256];
 137
 138     sprintf(data, "%dx%d%s", params->w, params->h,
 139             !full ? "" : params->matrix_type == CROSSES ? "c" : "r");
 140
 141     return dupstr(data);
 142 }
 143
 144 static config_item *game_configure(const game_params *params)
 145 {
 146     config_item *ret = snewn(4, config_item);
 147     char buf[80];
 148
 149     ret[0].name = "Width";
 150     ret[0].type = C_STRING;
 151     sprintf(buf, "%d", params->w);
 152     ret[0].u.string.sval = dupstr(buf);
 153
 154     ret[1].name = "Height";
 155     ret[1].type = C_STRING;
 156     sprintf(buf, "%d", params->h);
 157     ret[1].u.string.sval = dupstr(buf);
 158
 159     ret[2].name = "Shape type";
 160     ret[2].type = C_CHOICES;
 161     ret[2].u.choices.choicenames = ":Crosses:Random";
 162     ret[2].u.choices.selected = params->matrix_type;
 163
 164     ret[3].name = NULL;
 165     ret[3].type = C_END;
 166
 167     return ret;
 168 }
 169
 170 static game_params *custom_params(const config_item *cfg)
 171 {
 172     game_params *ret = snew(game_params);
 173
 174     ret->w = atoi(cfg[0].u.string.sval);
 175     ret->h = atoi(cfg[1].u.string.sval);
 176     ret->matrix_type = cfg[2].u.choices.selected;
 177
 178     return ret;
 179 }
 180
 181 static char *validate_params(const game_params *params, int full)
 182 {
 183     if (params->w <= 0 || params->h <= 0)
 184         return "Width and height must both be greater than zero";
 185     return NULL;
 186 }
 187
 188 static char *encode_bitmap(unsigned char *bmp, int len)
 189 {
 190     int slen = (len + 3) / 4;
 191     char *ret;
 192     int i;
 193
 194     ret = snewn(slen + 1, char);
 195     for (i = 0; i < slen; i++) {
 196         int j, v;
 197         v = 0;
 198         for (j = 0; j < 4; j++)
 199             if (i*4+j < len && bmp[i*4+j])
 200                 v |= 8 >> j;
 201         ret[i] = "0123456789abcdef"[v];
 202     }
 203     ret[slen] = '\0';
 204     return ret;
 205 }
 206
 207 static void decode_bitmap(unsigned char *bmp, int len, const char *hex)
 208 {
 209     int slen = (len + 3) / 4;
 210     int i;
 211
 212     for (i = 0; i < slen; i++) {
 213         int j, v, c = hex[i];
 214         if (c >= '0' && c <= '9')
 215             v = c - '0';
 216         else if (c >= 'A' && c <= 'F')
 217             v = c - 'A' + 10;
 218         else if (c >= 'a' && c <= 'f')
 219             v = c - 'a' + 10;
 220         else
 221             v = 0;                     /* shouldn't happen */
 222         for (j = 0; j < 4; j++) {
 223             if (i*4+j < len) {
 224                 if (v & (8 >> j))
 225                     bmp[i*4+j] = 1;
 226                 else
 227                     bmp[i*4+j] = 0;
 228             }
 229         }
 230     }
 231 }
 232
 233 /*
 234  * Structure used during random matrix generation, and a compare
 235  * function to permit storage in a tree234.
 236  */
 237 struct sq {
 238     int cx, cy;                        /* coords of click square */
 239     int x, y;                          /* coords of output square */
 240     /*
 241      * Number of click squares which currently affect this output
 242      * square.
 243      */
 244     int coverage;
 245     /*
 246      * Number of output squares currently affected by this click
 247      * square.
 248      */
 249     int ominosize;
 250 };
 251 #define SORT(field) do { \
 252     if (a->field < b->field) \
 253         return -1; \
 254     else if (a->field > b->field) \
 255         return +1; \
 256 } while (0)
 257 /*
 258  * Compare function for choosing the next square to add. We must
 259  * sort by coverage, then by omino size, then everything else.
 260  */
 261 static int sqcmp_pick(void *av, void *bv)
 262 {
 263     struct sq *a = (struct sq *)av;
 264     struct sq *b = (struct sq *)bv;
 265     SORT(coverage);
 266     SORT(ominosize);
 267     SORT(cy);
 268     SORT(cx);
 269     SORT(y);
 270     SORT(x);
 271     return 0;
 272 }
 273 /*
 274  * Compare function for adjusting the coverage figures after a
 275  * change. We sort first by coverage and output square, then by
 276  * everything else.
 277  */
 278 static int sqcmp_cov(void *av, void *bv)
 279 {
 280     struct sq *a = (struct sq *)av;
 281     struct sq *b = (struct sq *)bv;
 282     SORT(coverage);
 283     SORT(y);
 284     SORT(x);
 285     SORT(ominosize);
 286     SORT(cy);
 287     SORT(cx);
 288     return 0;
 289 }
 290 /*
 291  * Compare function for adjusting the omino sizes after a change.
 292  * We sort first by omino size and input square, then by everything
 293  * else.
 294  */
 295 static int sqcmp_osize(void *av, void *bv)
 296 {
 297     struct sq *a = (struct sq *)av;
 298     struct sq *b = (struct sq *)bv;
 299     SORT(ominosize);
 300     SORT(cy);
 301     SORT(cx);
 302     SORT(coverage);
 303     SORT(y);
 304     SORT(x);
 305     return 0;
 306 }
 307 static void addsq(tree234 *t, int w, int h, int cx, int cy,
 308                   int x, int y, unsigned char *matrix)
 309 {
 310     int wh = w * h;
 311     struct sq *sq;
 312     int i;
 313
 314     if (x < 0 || x >= w || y < 0 || y >= h)
 315         return;
 316     if (abs(x-cx) > 1 || abs(y-cy) > 1)
 317         return;
 318     if (matrix[(cy*w+cx) * wh + y*w+x])
 319         return;
 320
 321     sq = snew(struct sq);
 322     sq->cx = cx;
 323     sq->cy = cy;
 324     sq->x = x;
 325     sq->y = y;
 326     sq->coverage = sq->ominosize = 0;
 327     for (i = 0; i < wh; i++) {
 328         if (matrix[i * wh + y*w+x])
 329             sq->coverage++;
 330         if (matrix[(cy*w+cx) * wh + i])
 331             sq->ominosize++;
 332     }
 333
 334     if (add234(t, sq) != sq)
 335         sfree(sq);                     /* already there */
 336 }
 337 static void addneighbours(tree234 *t, int w, int h, int cx, int cy,
 338                           int x, int y, unsigned char *matrix)
 339 {
 340     addsq(t, w, h, cx, cy, x-1, y, matrix);
 341     addsq(t, w, h, cx, cy, x+1, y, matrix);
 342     addsq(t, w, h, cx, cy, x, y-1, matrix);
 343     addsq(t, w, h, cx, cy, x, y+1, matrix);
 344 }
 345
 346 static char *new_game_desc(const game_params *params, random_state *rs,
 347                            char **aux, int interactive)
 348 {
 349     int w = params->w, h = params->h, wh = w * h;
 350     int i, j;
 351     unsigned char *matrix, *grid;
 352     char *mbmp, *gbmp, *ret;
 353
 354     matrix = snewn(wh * wh, unsigned char);
 355     grid = snewn(wh, unsigned char);
 356
 357     /*
 358      * First set up the matrix.
 359      */
 360     switch (params->matrix_type) {
 361       case CROSSES:
 362         for (i = 0; i < wh; i++) {
 363             int ix = i % w, iy = i / w;
 364             for (j = 0; j < wh; j++) {
 365                 int jx = j % w, jy = j / w;
 366                 if (abs(jx - ix) + abs(jy - iy) <= 1)
 367                     matrix[i*wh+j] = 1;
 368                 else
 369                     matrix[i*wh+j] = 0;
 370             }
 371         }
 372         break;
 373       case RANDOM:
 374         while (1) {
 375             tree234 *pick, *cov, *osize;
 376             int limit;
 377
 378             pick = newtree234(sqcmp_pick);
 379             cov = newtree234(sqcmp_cov);
 380             osize = newtree234(sqcmp_osize);
 381
 382             memset(matrix, 0, wh * wh);
 383             for (i = 0; i < wh; i++) {
 384                 matrix[i*wh+i] = 1;
 385             }
 386
 387             for (i = 0; i < wh; i++) {
 388                 int ix = i % w, iy = i / w;
 389                 addneighbours(pick, w, h, ix, iy, ix, iy, matrix);
 390                 addneighbours(cov, w, h, ix, iy, ix, iy, matrix);
 391                 addneighbours(osize, w, h, ix, iy, ix, iy, matrix);
 392             }
 393
 394             /*
 395              * Repeatedly choose a square to add to the matrix,
 396              * until we have enough. I'll arbitrarily choose our
 397              * limit to be the same as the total number of set bits
 398              * in the crosses matrix.
 399              */
 400             limit = 4*wh - 2*(w+h);    /* centre squares already present */
 401
 402             while (limit-- > 0) {
 403                 struct sq *sq, *sq2, sqlocal;
 404                 int k;
 405
 406                 /*
 407                  * Find the lowest element in the pick tree.
 408                  */
 409                 sq = index234(pick, 0);
 410
 411                 /*
 412                  * Find the highest element with the same coverage
 413                  * and omino size, by setting all other elements to
 414                  * lots.
 415                  */
 416                 sqlocal = *sq;
 417                 sqlocal.cx = sqlocal.cy = sqlocal.x = sqlocal.y = wh;
 418                 sq = findrelpos234(pick, &sqlocal, NULL, REL234_LT, &k);
 419                 assert(sq != 0);
 420
 421                 /*
 422                  * Pick at random from all elements up to k of the
 423                  * pick tree.
 424                  */
 425                 k = random_upto(rs, k+1);
 426                 sq = delpos234(pick, k);
 427                 del234(cov, sq);
 428                 del234(osize, sq);
 429
 430                 /*
 431                  * Add this square to the matrix.
 432                  */
 433                 matrix[(sq->cy * w + sq->cx) * wh + (sq->y * w + sq->x)] = 1;
 434
 435                 /*
 436                  * Correct the matrix coverage field of any sq
 437                  * which points at this output square.
 438                  */
 439                 sqlocal = *sq;
 440                 sqlocal.cx = sqlocal.cy = sqlocal.ominosize = -1;
 441                 while ((sq2 = findrel234(cov, &sqlocal, NULL,
 442                                          REL234_GT)) != NULL &&
 443                        sq2->coverage == sq->coverage &&
 444                        sq2->x == sq->x && sq2->y == sq->y) {
 445                     del234(pick, sq2);
 446                     del234(cov, sq2);
 447                     del234(osize, sq2);
 448                     sq2->coverage++;
 449                     add234(pick, sq2);
 450                     add234(cov, sq2);
 451                     add234(osize, sq2);
 452                 }
 453
 454                 /*
 455                  * Correct the omino size field of any sq which
 456                  * points at this input square.
 457                  */
 458                 sqlocal = *sq;
 459                 sqlocal.x = sqlocal.y = sqlocal.coverage = -1;
 460                 while ((sq2 = findrel234(osize, &sqlocal, NULL,
 461                                          REL234_GT)) != NULL &&
 462                        sq2->ominosize == sq->ominosize &&
 463                        sq2->cx == sq->cx && sq2->cy == sq->cy) {
 464                     del234(pick, sq2);
 465                     del234(cov, sq2);
 466                     del234(osize, sq2);
 467                     sq2->ominosize++;
 468                     add234(pick, sq2);
 469                     add234(cov, sq2);
 470                     add234(osize, sq2);
 471                 }
 472
 473                 /*
 474                  * The sq we actually picked out of the tree is
 475                  * finished with; but its neighbours now need to
 476                  * appear.
 477                  */
 478                 addneighbours(pick, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix);
 479                 addneighbours(cov, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix);
 480                 addneighbours(osize, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix);
 481                 sfree(sq);
 482             }
 483
 484             /*
 485              * Free all remaining sq structures.
 486              */
 487             {
 488                 struct sq *sq;
 489                 while ((sq = delpos234(pick, 0)) != NULL)
 490                     sfree(sq);
 491             }
 492             freetree234(pick);
 493             freetree234(cov);
 494             freetree234(osize);
 495
 496             /*
 497              * Finally, check to see if any two matrix rows are
 498              * exactly identical. If so, this is not an acceptable
 499              * matrix, and we give up and go round again.
 500              *
 501              * I haven't been immediately able to think of a
 502              * plausible means of algorithmically avoiding this
 503              * situation (by, say, making a small perturbation to
 504              * an offending matrix), so for the moment I'm just
 505              * going to deal with it by throwing the whole thing
 506              * away. I suspect this will lead to scalability
 507              * problems (since most of the things happening in
 508              * these matrices are local, the chance of _some_
 509              * neighbourhood having two identical regions will
 510              * increase with the grid area), but so far this puzzle
 511              * seems to be really hard at large sizes so I'm not
 512              * massively worried yet. Anyone needs this done
 513              * better, they're welcome to submit a patch.
 514              */
 515             for (i = 0; i < wh; i++) {
 516                 for (j = 0; j < wh; j++)
 517                     if (i != j &&
 518                         !memcmp(matrix + i * wh, matrix + j * wh, wh))
 519                         break;
 520                 if (j < wh)
 521                     break;
 522             }
 523             if (i == wh)
 524                 break;                 /* no matches found */
 525         }
 526         break;
 527     }
 528
 529     /*
 530      * Now invent a random initial set of lights.
 531      *
 532      * At first glance it looks as if it might be quite difficult
 533      * to choose equiprobably from all soluble light sets. After
 534      * all, soluble light sets are those in the image space of the
 535      * transformation matrix; so first we'd have to identify that
 536      * space and its dimension, then pick a random coordinate for
 537      * each basis vector and recombine. Lot of fiddly matrix
 538      * algebra there.
 539      *
 540      * However, vector spaces are nicely orthogonal and relieve us
 541      * of all that difficulty. For every point in the image space,
 542      * there are precisely as many points in the input space that
 543      * map to it as there are elements in the kernel of the
 544      * transformation matrix (because adding any kernel element to
 545      * the input does not change the output, and because any two
 546      * inputs mapping to the same output must differ by an element
 547      * of the kernel because that's what the kernel _is_); and
 548      * these cosets are all disjoint (obviously, since no input
 549      * point can map to more than one output point) and cover the
 550      * whole space (equally obviously, because no input point can
 551      * map to fewer than one output point!).
 552      *
 553      * So the input space contains the same number of points for
 554      * each point in the output space; thus, we can simply choose
 555      * equiprobably from elements of the _input_ space, and filter
 556      * the result through the transformation matrix in the obvious
 557      * way, and we thereby guarantee to choose equiprobably from
 558      * all the output points. Phew!
 559      */
 560     while (1) {
 561         memset(grid, 0, wh);
 562         for (i = 0; i < wh; i++) {
 563             int v = random_upto(rs, 2);
 564             if (v) {
 565                 for (j = 0; j < wh; j++)
 566                     grid[j] ^= matrix[i*wh+j];
 567             }
 568         }
 569         /*
 570          * Ensure we don't have the starting state already!
 571          */
 572         for (i = 0; i < wh; i++)
 573             if (grid[i])
 574                 break;
 575         if (i < wh)
 576             break;
 577     }
 578
 579     /*
 580      * Now encode the matrix and the starting grid as a game
 581      * description. We'll do this by concatenating two great big
 582      * hex bitmaps.
 583      */
 584     mbmp = encode_bitmap(matrix, wh*wh);
 585     gbmp = encode_bitmap(grid, wh);
 586     ret = snewn(strlen(mbmp) + strlen(gbmp) + 2, char);
 587     sprintf(ret, "%s,%s", mbmp, gbmp);
 588     sfree(mbmp);
 589     sfree(gbmp);
 590     sfree(matrix);
 591     sfree(grid);
 592     return ret;
 593 }
 594
 595 static char *validate_desc(const game_params *params, const char *desc)
 596 {
 597     int w = params->w, h = params->h, wh = w * h;
 598     int mlen = (wh*wh+3)/4, glen = (wh+3)/4;
 599
 600     if (strspn(desc, "0123456789abcdefABCDEF") != mlen)
 601         return "Matrix description is wrong length";
 602     if (desc[mlen] != ',')
 603         return "Expected comma after matrix description";
 604     if (strspn(desc+mlen+1, "0123456789abcdefABCDEF") != glen)
 605         return "Grid description is wrong length";
 606     if (desc[mlen+1+glen])
 607         return "Unexpected data after grid description";
 608
 609     return NULL;
 610 }
 611
 612 static game_state *new_game(midend *me, const game_params *params,
 613                             const char *desc)
 614 {
 615     int w = params->w, h = params->h, wh = w * h;
 616     int mlen = (wh*wh+3)/4;
 617
 618     game_state *state = snew(game_state);
 619
 620     state->w = w;
 621     state->h = h;
 622     state->completed = FALSE;
 623     state->cheated = FALSE;
 624     state->hints_active = FALSE;
 625     state->moves = 0;
 626     state->matrix = snew(struct matrix);
 627     state->matrix->refcount = 1;
 628     state->matrix->matrix = snewn(wh*wh, unsigned char);
 629     decode_bitmap(state->matrix->matrix, wh*wh, desc);
 630     state->grid = snewn(wh, unsigned char);
 631     decode_bitmap(state->grid, wh, desc + mlen + 1);
 632
 633     return state;
 634 }
 635
 636 static game_state *dup_game(const game_state *state)
 637 {
 638     game_state *ret = snew(game_state);
 639
 640     ret->w = state->w;
 641     ret->h = state->h;
 642     ret->completed = state->completed;
 643     ret->cheated = state->cheated;
 644     ret->hints_active = state->hints_active;
 645     ret->moves = state->moves;
 646     ret->matrix = state->matrix;
 647     state->matrix->refcount++;
 648     ret->grid = snewn(ret->w * ret->h, unsigned char);
 649     memcpy(ret->grid, state->grid, ret->w * ret->h);
 650
 651     return ret;
 652 }
 653
 654 static void free_game(game_state *state)
 655 {
 656     sfree(state->grid);
 657     if (--state->matrix->refcount <= 0) {
 658         sfree(state->matrix->matrix);
 659         sfree(state->matrix);
 660     }
 661     sfree(state);
 662 }
 663
 664 static void rowxor(unsigned char *row1, unsigned char *row2, int len)
 665 {
 666     int i;
 667     for (i = 0; i < len; i++)
 668         row1[i] ^= row2[i];
 669 }
 670
 671 static char *solve_game(const game_state *state, const game_state *currstate,
 672                         const char *aux, char **error)
 673 {
 674     int w = state->w, h = state->h, wh = w * h;
 675     unsigned char *equations, *solution, *shortest;
 676     int *und, nund;
 677     int rowsdone, colsdone;
 678     int i, j, k, len, bestlen;
 679     char *ret;
 680
 681     /*
 682      * Set up a list of simultaneous equations. Each one is of
 683      * length (wh+1) and has wh coefficients followed by a value.
 684      */
 685     equations = snewn((wh + 1) * wh, unsigned char);
 686     for (i = 0; i < wh; i++) {
 687         for (j = 0; j < wh; j++)
 688             equations[i * (wh+1) + j] = currstate->matrix->matrix[j*wh+i];
 689         equations[i * (wh+1) + wh] = currstate->grid[i] & 1;
 690     }
 691
 692     /*
 693      * Perform Gaussian elimination over GF(2).
 694      */
 695     rowsdone = colsdone = 0;
 696     nund = 0;
 697     und = snewn(wh, int);
 698     do {
 699         /*
 700          * Find the leftmost column which has a 1 in it somewhere
 701          * outside the first `rowsdone' rows.
 702          */
 703         j = -1;
 704         for (i = colsdone; i < wh; i++) {
 705             for (j = rowsdone; j < wh; j++)
 706                 if (equations[j * (wh+1) + i])
 707                     break;
 708             if (j < wh)
 709                 break;                 /* found one */
 710             /*
 711              * This is a column which will not have an equation
 712              * controlling it. Mark it as undetermined.
 713              */
 714             und[nund++] = i;
 715         }
 716
 717         /*
 718          * If there wasn't one, then we've finished: all remaining
 719          * equations are of the form 0 = constant. Check to see if
 720          * any of them wants 0 to be equal to 1; this is the
 721          * condition which indicates an insoluble problem
 722          * (therefore _hopefully_ one typed in by a user!).
 723          */
 724         if (i == wh) {
 725             for (j = rowsdone; j < wh; j++)
 726                 if (equations[j * (wh+1) + wh]) {
 727                     *error = "No solution exists for this position";
 728                     sfree(equations);
 729                     sfree(und);
 730                     return NULL;
 731                 }
 732             break;
 733         }
 734
 735         /*
 736          * We've found a 1. It's in column i, and the topmost 1 in
 737          * that column is in row j. Do a row-XOR to move it up to
 738          * the topmost row if it isn't already there.
 739          */
 740         assert(j != -1);
 741         if (j > rowsdone)
 742             rowxor(equations + rowsdone*(wh+1), equations + j*(wh+1), wh+1);
 743
 744         /*
 745          * Do row-XORs to eliminate that 1 from all rows below the
 746          * topmost row.
 747          */
 748         for (j = rowsdone + 1; j < wh; j++)
 749             if (equations[j*(wh+1) + i])
 750                 rowxor(equations + j*(wh+1),
 751                        equations + rowsdone*(wh+1), wh+1);
 752
 753         /*
 754          * Mark this row and column as done.
 755          */
 756         rowsdone++;
 757         colsdone = i+1;
 758
 759         /*
 760          * If we've done all the rows, terminate.
 761          */
 762     } while (rowsdone < wh);
 763
 764     /*
 765      * If we reach here, we have the ability to produce a solution.
 766      * So we go through _all_ possible solutions (each
 767      * corresponding to a set of arbitrary choices of those
 768      * components not directly determined by an equation), and pick
 769      * one requiring the smallest number of flips.
 770      */
 771     solution = snewn(wh, unsigned char);
 772     shortest = snewn(wh, unsigned char);
 773     memset(solution, 0, wh);
 774     bestlen = wh + 1;
 775     while (1) {
 776         /*
 777          * Find a solution based on the current values of the
 778          * undetermined variables.
 779          */
 780         for (j = rowsdone; j-- ;) {
 781             int v;
 782
 783             /*
 784              * Find the leftmost set bit in this equation.
 785              */
 786             for (i = 0; i < wh; i++)
 787                 if (equations[j * (wh+1) + i])
 788                     break;
 789             assert(i < wh);                    /* there must have been one! */
 790
 791             /*
 792              * Compute this variable using the rest.
 793              */
 794             v = equations[j * (wh+1) + wh];
 795             for (k = i+1; k < wh; k++)
 796                 if (equations[j * (wh+1) + k])
 797                     v ^= solution[k];
 798
 799             solution[i] = v;
 800         }
 801
 802         /*
 803          * Compare this solution to the current best one, and
 804          * replace the best one if this one is shorter.
 805          */
 806         len = 0;
 807         for (i = 0; i < wh; i++)
 808             if (solution[i])
 809                 len++;
 810         if (len < bestlen) {
 811             bestlen = len;
 812             memcpy(shortest, solution, wh);
 813         }
 814
 815         /*
 816          * Now increment the binary number given by the
 817          * undetermined variables: turn all 1s into 0s until we see
 818          * a 0, at which point we turn it into a 1.
 819          */
 820         for (i = 0; i < nund; i++) {
 821             solution[und[i]] = !solution[und[i]];
 822             if (solution[und[i]])
 823                 break;
 824         }
 825
 826         /*
 827          * If we didn't find a 0 at any point, we have wrapped
 828          * round and are back at the start, i.e. we have enumerated
 829          * all solutions.
 830          */
 831         if (i == nund)
 832             break;
 833     }
 834
 835     /*
 836      * We have a solution. Produce a move string encoding the
 837      * solution.
 838      */
 839     ret = snewn(wh + 2, char);
 840     ret[0] = 'S';
 841     for (i = 0; i < wh; i++)
 842         ret[i+1] = shortest[i] ? '1' : '0';
 843     ret[wh+1] = '\0';
 844
 845     sfree(shortest);
 846     sfree(solution);
 847     sfree(equations);
 848     sfree(und);
 849
 850     return ret;
 851 }
 852
 853 static int game_can_format_as_text_now(const game_params *params)
 854 {
 855     return TRUE;
 856 }
 857
 858 #define RIGHT 1
 859 #define DOWN gw
 860
 861 static char *game_text_format(const game_state *state)
 862 {
 863     int w = state->w, h = state->h, wh = w*h, r, c, dx, dy;
 864     int cw = 4, ch = 4, gw = w * cw + 2, gh = h * ch + 1, len = gw * gh;
 865     char *board = snewn(len + 1, char);
 866
 867     memset(board, ' ', len - 1);
 868
 869     for (r = 0; r < h; ++r) {
 870         for (c = 0; c < w; ++c) {
 871             int cell = r*ch*gw + c*cw, center = cell+(ch/2)*DOWN + cw/2*RIGHT;
 872             char flip = (state->grid[r*w + c] & 1) ? '#' : '.';
 873             for (dy = -1 + (r == 0); dy <= 1 - (r == h - 1); ++dy)
 874                 for (dx = -1 + (c == 0); dx <= 1 - (c == w - 1); ++dx)
 875                     if (state->matrix->matrix[(r*w+c)*wh + ((r+dy)*w + c+dx)])
 876                         board[center + dy*DOWN + dx*RIGHT] = flip;
 877             board[cell] = '+';
 878             for (dx = 1; dx < cw; ++dx) board[cell+dx*RIGHT] = '-';
 879             for (dy = 1; dy < ch; ++dy) board[cell+dy*DOWN] = '|';
 880         }
 881         board[r*ch*gw + gw - 2] = '+';
 882         board[r*ch*gw + gw - 1] = '\n';
 883         for (dy = 1; dy < ch; ++dy) {
 884             board[r*ch*gw + gw - 2 + dy*DOWN] = '|';
 885             board[r*ch*gw + gw - 1 + dy*DOWN] = '\n';
 886         }
 887     }
 888     memset(board + len - gw, '-', gw - 2);
 889     for (c = 0; c <= w; ++c) board[len - gw + cw*c] = '+';
 890     board[len - 1] = '\n';
 891     board[len] = '\0';
 892     return board;
 893 }
 894
 895 #undef RIGHT
 896 #undef DOWN
 897
 898 struct game_ui {
 899     int cx, cy, cdraw;
 900 };
 901
 902 static game_ui *new_ui(const game_state *state)
 903 {
 904     game_ui *ui = snew(game_ui);
 905     ui->cx = ui->cy = ui->cdraw = 0;
 906     return ui;
 907 }
 908
 909 static void free_ui(game_ui *ui)
 910 {
 911     sfree(ui);
 912 }
 913
 914 static char *encode_ui(const game_ui *ui)
 915 {
 916     return NULL;
 917 }
 918
 919 static void decode_ui(game_ui *ui, const char *encoding)
 920 {
 921 }
 922
 923 static void game_changed_state(game_ui *ui, const game_state *oldstate,
 924                                const game_state *newstate)
 925 {
 926 }
 927
 928 struct game_drawstate {
 929     int w, h, started;
 930     unsigned char *tiles;
 931     int tilesize;
 932 };
 933
 934 static char *interpret_move(const game_state *state, game_ui *ui,
 935                             const game_drawstate *ds,
 936                             int x, int y, int button)
 937 {
 938     int w = state->w, h = state->h, wh = w * h;
 939     char buf[80], *nullret = NULL;
 940
 941     if (button == LEFT_BUTTON || IS_CURSOR_SELECT(button)) {
 942         int tx, ty;
 943         if (button == LEFT_BUTTON) {
 944             tx = FROMCOORD(x), ty = FROMCOORD(y);
 945             ui->cdraw = 0;
 946         } else {
 947             tx = ui->cx; ty = ui->cy;
 948             ui->cdraw = 1;
 949         }
 950         nullret = UI_UPDATE;
 951
 952         if (tx >= 0 && tx < w && ty >= 0 && ty < h) {
 953             /*
 954              * It's just possible that a manually entered game ID
 955              * will have at least one square do nothing whatsoever.
 956              * If so, we avoid encoding a move at all.
 957              */
 958             int i = ty*w+tx, j, makemove = FALSE;
 959             for (j = 0; j < wh; j++) {
 960                 if (state->matrix->matrix[i*wh+j])
 961                     makemove = TRUE;
 962             }
 963             if (makemove) {
 964                 sprintf(buf, "M%d,%d", tx, ty);
 965                 return dupstr(buf);
 966             } else {
 967                 return NULL;
 968             }
 969         }
 970     }
 971     else if (IS_CURSOR_MOVE(button)) {
 972         int dx = 0, dy = 0;
 973         switch (button) {
 974         case CURSOR_UP:         dy = -1; break;
 975         case CURSOR_DOWN:       dy = 1; break;
 976         case CURSOR_RIGHT:      dx = 1; break;
 977         case CURSOR_LEFT:       dx = -1; break;
 978         default: assert(!"shouldn't get here");
 979         }
 980         ui->cx += dx; ui->cy += dy;
 981         ui->cx = min(max(ui->cx, 0), state->w - 1);
 982         ui->cy = min(max(ui->cy, 0), state->h - 1);
 983         ui->cdraw = 1;
 984         nullret = UI_UPDATE;
 985     }
 986
 987     return nullret;
 988 }
 989
 990 static game_state *execute_move(const game_state *from, const char *move)
 991 {
 992     int w = from->w, h = from->h, wh = w * h;
 993     game_state *ret;
 994     int x, y;
 995
 996     if (move[0] == 'S' && strlen(move) == wh+1) {
 997         int i;
 998
 999         ret = dup_game(from);
1000         ret->hints_active = TRUE;
1001         ret->cheated = TRUE;
1002         for (i = 0; i < wh; i++) {
1003             ret->grid[i] &= ~2;
1004             if (move[i+1] != '0')
1005                 ret->grid[i] |= 2;
1006         }
1007         return ret;
1008     } else if (move[0] == 'M' &&
1009                sscanf(move+1, "%d,%d", &x, &y) == 2 &&
1010         x >= 0 && x < w && y >= 0 && y < h) {
1011         int i, j, done;
1012
1013         ret = dup_game(from);
1014
1015         if (!ret->completed)
1016             ret->moves++;
1017
1018         i = y * w + x;
1019
1020         done = TRUE;
1021         for (j = 0; j < wh; j++) {
1022             ret->grid[j] ^= ret->matrix->matrix[i*wh+j];
1023             if (ret->grid[j] & 1)
1024                 done = FALSE;
1025         }
1026         ret->grid[i] ^= 2;             /* toggle hint */
1027         if (done) {
1028             ret->completed = TRUE;
1029             ret->hints_active = FALSE;
1030         }
1031
1032         return ret;
1033     } else
1034         return NULL;                   /* can't parse move string */
1035 }
1036
1037 /* ----------------------------------------------------------------------
1038  * Drawing routines.
1039  */
1040
1041 static void game_compute_size(const game_params *params, int tilesize,
1042                               int *x, int *y)
1043 {
1044     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1045     struct { int tilesize; } ads, *ds = &ads;
1046     ads.tilesize = tilesize;
1047
1048     *x = TILE_SIZE * params->w + 2 * BORDER;
1049     *y = TILE_SIZE * params->h + 2 * BORDER;
1050 }
1051
1052 static void game_set_size(drawing *dr, game_drawstate *ds,
1053                           const game_params *params, int tilesize)
1054 {
1055     ds->tilesize = tilesize;
1056 }
1057
1058 static float *game_colours(frontend *fe, int *ncolours)
1059 {
1060     float *ret = snewn(3 * NCOLOURS, float);
1061
1062     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1063
1064     ret[COL_WRONG * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 3;
1065     ret[COL_WRONG * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 3;
1066     ret[COL_WRONG * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 3;
1067
1068     ret[COL_RIGHT * 3 + 0] = 1.0F;
1069     ret[COL_RIGHT * 3 + 1] = 1.0F;
1070     ret[COL_RIGHT * 3 + 2] = 1.0F;
1071
1072     ret[COL_GRID * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 1.5F;
1073     ret[COL_GRID * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 1.5F;
1074     ret[COL_GRID * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 1.5F;
1075
1076     ret[COL_DIAG * 3 + 0] = ret[COL_GRID * 3 + 0];
1077     ret[COL_DIAG * 3 + 1] = ret[COL_GRID * 3 + 1];
1078     ret[COL_DIAG * 3 + 2] = ret[COL_GRID * 3 + 2];
1079
1080     ret[COL_HINT * 3 + 0] = 1.0F;
1081     ret[COL_HINT * 3 + 1] = 0.0F;
1082     ret[COL_HINT * 3 + 2] = 0.0F;
1083
1084     ret[COL_CURSOR * 3 + 0] = 0.8F;
1085     ret[COL_CURSOR * 3 + 1] = 0.0F;
1086     ret[COL_CURSOR * 3 + 2] = 0.0F;
1087
1088     *ncolours = NCOLOURS;
1089     return ret;
1090 }
1091
1092 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1093 {
1094     struct game_drawstate *ds = snew(struct game_drawstate);
1095     int i;
1096
1097     ds->started = FALSE;
1098     ds->w = state->w;
1099     ds->h = state->h;
1100     ds->tiles = snewn(ds->w*ds->h, unsigned char);
1101     ds->tilesize = 0;                  /* haven't decided yet */
1102     for (i = 0; i < ds->w*ds->h; i++)
1103         ds->tiles[i] = -1;
1104
1105     return ds;
1106 }
1107
1108 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1109 {
1110     sfree(ds->tiles);
1111     sfree(ds);
1112 }
1113
1114 static void draw_tile(drawing *dr, game_drawstate *ds, const game_state *state,
1115                       int x, int y, int tile, int anim, float animtime)
1116 {
1117     int w = ds->w, h = ds->h, wh = w * h;
1118     int bx = x * TILE_SIZE + BORDER, by = y * TILE_SIZE + BORDER;
1119     int i, j, dcol = (tile & 4) ? COL_CURSOR : COL_DIAG;
1120
1121     clip(dr, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1);
1122
1123     draw_rect(dr, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1,
1124               anim ? COL_BACKGROUND : tile & 1 ? COL_WRONG : COL_RIGHT);
1125     if (anim) {
1126         /*
1127          * Draw a polygon indicating that the square is diagonally
1128          * flipping over.
1129          */
1130         int coords[8], colour;
1131
1132         coords[0] = bx + TILE_SIZE;
1133         coords[1] = by;
1134         coords[2] = bx + (int)((float)TILE_SIZE * animtime);
1135         coords[3] = by + (int)((float)TILE_SIZE * animtime);
1136         coords[4] = bx;
1137         coords[5] = by + TILE_SIZE;
1138         coords[6] = bx + TILE_SIZE - (int)((float)TILE_SIZE * animtime);
1139         coords[7] = by + TILE_SIZE - (int)((float)TILE_SIZE * animtime);
1140
1141         colour = (tile & 1 ? COL_WRONG : COL_RIGHT);
1142         if (animtime < 0.5)
1143             colour = COL_WRONG + COL_RIGHT - colour;
1144
1145         draw_polygon(dr, coords, 4, colour, COL_GRID);
1146     }
1147
1148     /*
1149      * Draw a little diagram in the tile which indicates which
1150      * surrounding tiles flip when this one is clicked.
1151      */
1152     for (i = 0; i < h; i++)
1153         for (j = 0; j < w; j++)
1154             if (state->matrix->matrix[(y*w+x)*wh + i*w+j]) {
1155                 int ox = j - x, oy = i - y;
1156                 int td = TILE_SIZE / 16;
1157                 int cx = (bx + TILE_SIZE/2) + (2 * ox - 1) * td;
1158                 int cy = (by + TILE_SIZE/2) + (2 * oy - 1) * td;
1159                 if (ox == 0 && oy == 0)
1160                     draw_rect(dr, cx, cy, 2*td+1, 2*td+1, dcol);
1161                 else {
1162                     draw_line(dr, cx, cy, cx+2*td, cy, dcol);
1163                     draw_line(dr, cx, cy+2*td, cx+2*td, cy+2*td, dcol);
1164                     draw_line(dr, cx, cy, cx, cy+2*td, dcol);
1165                     draw_line(dr, cx+2*td, cy, cx+2*td, cy+2*td, dcol);
1166                 }
1167             }
1168
1169     /*
1170      * Draw a hint rectangle if required.
1171      */
1172     if (tile & 2) {
1173         int x1 = bx + TILE_SIZE / 20, x2 = bx + TILE_SIZE - TILE_SIZE / 20;
1174         int y1 = by + TILE_SIZE / 20, y2 = by + TILE_SIZE - TILE_SIZE / 20;
1175         int i = 3;
1176         while (i--) {
1177             draw_line(dr, x1, y1, x2, y1, COL_HINT);
1178             draw_line(dr, x1, y2, x2, y2, COL_HINT);
1179             draw_line(dr, x1, y1, x1, y2, COL_HINT);
1180             draw_line(dr, x2, y1, x2, y2, COL_HINT);
1181             x1++, y1++, x2--, y2--;
1182         }
1183     }
1184
1185     unclip(dr);
1186
1187     draw_update(dr, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1);
1188 }
1189
1190 static void game_redraw(drawing *dr, game_drawstate *ds,
1191                         const game_state *oldstate, const game_state *state,
1192                         int dir, const game_ui *ui,
1193                         float animtime, float flashtime)
1194 {
1195     int w = ds->w, h = ds->h, wh = w * h;
1196     int i, flashframe;
1197
1198     if (!ds->started) {
1199         draw_rect(dr, 0, 0, TILE_SIZE * w + 2 * BORDER,
1200                   TILE_SIZE * h + 2 * BORDER, COL_BACKGROUND);
1201
1202         /*
1203          * Draw the grid lines.
1204          */
1205         for (i = 0; i <= w; i++)
1206             draw_line(dr, i * TILE_SIZE + BORDER, BORDER,
1207                       i * TILE_SIZE + BORDER, h * TILE_SIZE + BORDER,
1208                       COL_GRID);
1209         for (i = 0; i <= h; i++)
1210             draw_line(dr, BORDER, i * TILE_SIZE + BORDER,
1211                       w * TILE_SIZE + BORDER, i * TILE_SIZE + BORDER,
1212                       COL_GRID);
1213
1214         draw_update(dr, 0, 0, TILE_SIZE * w + 2 * BORDER,
1215                     TILE_SIZE * h + 2 * BORDER);
1216
1217         ds->started = TRUE;
1218     }
1219
1220     if (flashtime)
1221         flashframe = (int)(flashtime / FLASH_FRAME);
1222     else
1223         flashframe = -1;
1224
1225     animtime /= ANIM_TIME;             /* scale it so it goes from 0 to 1 */
1226
1227     for (i = 0; i < wh; i++) {
1228         int x = i % w, y = i / w;
1229         int fx, fy, fd;
1230         int v = state->grid[i];
1231         int vv;
1232
1233         if (flashframe >= 0) {
1234             fx = (w+1)/2 - min(x+1, w-x);
1235             fy = (h+1)/2 - min(y+1, h-y);
1236             fd = max(fx, fy);
1237             if (fd == flashframe)
1238                 v |= 1;
1239             else if (fd == flashframe - 1)
1240                 v &= ~1;
1241         }
1242
1243         if (!state->hints_active)
1244             v &= ~2;
1245         if (ui->cdraw && ui->cx == x && ui->cy == y)
1246             v |= 4;
1247
1248         if (oldstate && ((state->grid[i] ^ oldstate->grid[i]) &~ 2))
1249             vv = 255;                  /* means `animated' */
1250         else
1251             vv = v;
1252
1253         if (ds->tiles[i] == 255 || vv == 255 || ds->tiles[i] != vv) {
1254             draw_tile(dr, ds, state, x, y, v, vv == 255, animtime);
1255             ds->tiles[i] = vv;
1256         }
1257     }
1258
1259     {
1260         char buf[256];
1261
1262         sprintf(buf, "%sMoves: %d",
1263                 (state->completed ?
1264                  (state->cheated ? "Auto-solved. " : "COMPLETED! ") :
1265                  (state->cheated ? "Auto-solver used. " : "")),
1266                 state->moves);
1267
1268         status_bar(dr, buf);
1269     }
1270 }
1271
1272 static float game_anim_length(const game_state *oldstate,
1273                               const game_state *newstate, int dir, game_ui *ui)
1274 {
1275     return ANIM_TIME;
1276 }
1277
1278 static float game_flash_length(const game_state *oldstate,
1279                                const game_state *newstate, int dir, game_ui *ui)
1280 {
1281     if (!oldstate->completed && newstate->completed)
1282         return FLASH_FRAME * (max((newstate->w+1)/2, (newstate->h+1)/2)+1);
1283
1284     return 0.0F;
1285 }
1286
1287 static int game_status(const game_state *state)
1288 {
1289     return state->completed ? +1 : 0;
1290 }
1291
1292 static int game_timing_state(const game_state *state, game_ui *ui)
1293 {
1294     return TRUE;
1295 }
1296
1297 static void game_print_size(const game_params *params, float *x, float *y)
1298 {
1299 }
1300
1301 static void game_print(drawing *dr, const game_state *state, int tilesize)
1302 {
1303 }
1304
1305 #ifdef COMBINED
1306 #define thegame flip
1307 #endif
1308
1309 const struct game thegame = {
1310     "Flip", "games.flip", "flip",
1311     default_params,
1312     game_fetch_preset, NULL,
1313     decode_params,
1314     encode_params,
1315     free_params,
1316     dup_params,
1317     TRUE, game_configure, custom_params,
1318     validate_params,
1319     new_game_desc,
1320     validate_desc,
1321     new_game,
1322     dup_game,
1323     free_game,
1324     TRUE, solve_game,
1325     TRUE, game_can_format_as_text_now, game_text_format,
1326     new_ui,
1327     free_ui,
1328     encode_ui,
1329     decode_ui,
1330     game_changed_state,
1331     interpret_move,
1332     execute_move,
1333     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1334     game_colours,
1335     game_new_drawstate,
1336     game_free_drawstate,
1337     game_redraw,
1338     game_anim_length,
1339     game_flash_length,
1340     game_status,
1341     FALSE, FALSE, game_print_size, game_print,
1342     TRUE,                              /* wants_statusbar */
1343     FALSE, game_timing_state,
1344     0,                                 /* flags */
1345 };