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