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