unruly.c

   1 /*
   2  * unruly.c: Implementation for Binary Puzzles.
   3  * (C) 2012 Lennard Sprong
   4  * Created for Simon Tatham's Portable Puzzle Collection
   5  * See LICENCE for licence details
   6  *
   7  * Objective of the game: Fill the grid with zeros and ones, with the
   8  * following rules:
   9  * - There can't be a run of three or more equal numbers.
  10  * - Each row and column contains an equal amount of zeros and ones.
  11  *
  12  * This puzzle type is known under several names, including
  13  * Tohu-Wa-Vohu, One and Two and Binairo.
  14  *
  15  * Some variants include an extra constraint, stating that no two rows or two
  16  * columns may contain the same exact sequence of zeros and ones.
  17  * This rule is rarely used, so it has been discarded for this implementation.
  18  *
  19  * More information:
  20  * http://www.janko.at/Raetsel/Tohu-Wa-Vohu/index.htm
  21  */
  22
  23 /*
  24  * Possible future improvements:
  25  *
  26  * More solver cleverness
  27  *
  28  *  - a counting-based deduction in which you find groups of squares
  29  *    which must each contain at least one of a given colour, plus
  30  *    other squares which are already known to be that colour, and see
  31  *    if you have any squares left over when you've worked out where
  32  *    they all have to be. This is a generalisation of the current
  33  *    check_near_complete: where that only covers rows with three
  34  *    unfilled squares, this would handle more, such as
  35  *        0 . . 1 0 1 . . 0 .
  36  *    in which each of the two-square gaps must contain a 0, and there
  37  *    are three 0s placed, and that means the rightmost square can't
  38  *    be a 0.
  39  *
  40  *  - an 'Unreasonable' difficulty level, supporting recursion and
  41  *    backtracking.
  42  */
  43
  44 #include <stdio.h>
  45 #include <stdlib.h>
  46 #include <string.h>
  47 #include <assert.h>
  48 #include <ctype.h>
  49 #include <math.h>
  50
  51 #include "puzzles.h"
  52
  53 #ifdef STANDALONE_SOLVER
  54 int solver_verbose = FALSE;
  55 #endif
  56
  57 enum {
  58     COL_BACKGROUND,
  59     COL_GRID,
  60     COL_EMPTY,
  61     /*
  62      * When editing this enum, maintain the invariants
  63      *   COL_n_HIGHLIGHT = COL_n + 1
  64      *   COL_n_LOWLIGHT = COL_n + 2
  65      */
  66     COL_0,
  67     COL_0_HIGHLIGHT,
  68     COL_0_LOWLIGHT,
  69     COL_1,
  70     COL_1_HIGHLIGHT,
  71     COL_1_LOWLIGHT,
  72     COL_CURSOR,
  73     COL_ERROR,
  74     NCOLOURS
  75 };
  76
  77 struct game_params {
  78     int w2, h2;        /* full grid width and height respectively */
  79     int unique;        /* should row and column patterns be unique? */
  80     int diff;
  81 };
  82 #define DIFFLIST(A)                             \
  83     A(EASY,Easy, e)                             \
  84     A(NORMAL,Normal, n)                         \
  85
  86 #define ENUM(upper,title,lower) DIFF_ ## upper,
  87 #define TITLE(upper,title,lower) #title,
  88 #define ENCODE(upper,title,lower) #lower
  89 #define CONFIG(upper,title,lower) ":" #title
  90 enum { DIFFLIST(ENUM) DIFFCOUNT };
  91 static char const *const unruly_diffnames[] = { DIFFLIST(TITLE) };
  92
  93 static char const unruly_diffchars[] = DIFFLIST(ENCODE);
  94 #define DIFFCONFIG DIFFLIST(CONFIG)
  95
  96 const static struct game_params unruly_presets[] = {
  97     { 8,  8, FALSE, DIFF_EASY},
  98     { 8,  8, FALSE, DIFF_NORMAL},
  99     {10, 10, FALSE, DIFF_EASY},
 100     {10, 10, FALSE, DIFF_NORMAL},
 101     {14, 14, FALSE, DIFF_EASY},
 102     {14, 14, FALSE, DIFF_NORMAL}
 103 };
 104
 105 #define DEFAULT_PRESET 0
 106
 107 enum {
 108     EMPTY,
 109     N_ONE,
 110     N_ZERO,
 111     BOGUS
 112 };
 113
 114 #define FE_HOR_ROW_LEFT   0x0001
 115 #define FE_HOR_ROW_MID    0x0003
 116 #define FE_HOR_ROW_RIGHT  0x0002
 117
 118 #define FE_VER_ROW_TOP    0x0004
 119 #define FE_VER_ROW_MID    0x000C
 120 #define FE_VER_ROW_BOTTOM 0x0008
 121
 122 #define FE_COUNT          0x0010
 123
 124 #define FE_ROW_MATCH      0x0020
 125 #define FE_COL_MATCH      0x0040
 126
 127 #define FF_ONE            0x0080
 128 #define FF_ZERO           0x0100
 129 #define FF_CURSOR         0x0200
 130
 131 #define FF_FLASH1         0x0400
 132 #define FF_FLASH2         0x0800
 133 #define FF_IMMUTABLE      0x1000
 134
 135 struct game_state {
 136     int w2, h2;
 137     int unique;
 138     char *grid;
 139     unsigned char *immutable;
 140
 141     int completed, cheated;
 142 };
 143
 144 static game_params *default_params(void)
 145 {
 146     game_params *ret = snew(game_params);
 147
 148     *ret = unruly_presets[DEFAULT_PRESET];        /* structure copy */
 149
 150     return ret;
 151 }
 152
 153 static int game_fetch_preset(int i, char **name, game_params **params)
 154 {
 155     game_params *ret;
 156     char buf[80];
 157
 158     if (i < 0 || i >= lenof(unruly_presets))
 159         return FALSE;
 160
 161     ret = snew(game_params);
 162     *ret = unruly_presets[i];     /* structure copy */
 163
 164     sprintf(buf, "%dx%d %s", ret->w2, ret->h2, unruly_diffnames[ret->diff]);
 165
 166     *name = dupstr(buf);
 167     *params = ret;
 168     return TRUE;
 169 }
 170
 171 static void free_params(game_params *params)
 172 {
 173     sfree(params);
 174 }
 175
 176 static game_params *dup_params(const game_params *params)
 177 {
 178     game_params *ret = snew(game_params);
 179     *ret = *params;             /* structure copy */
 180     return ret;
 181 }
 182
 183 static void decode_params(game_params *params, char const *string)
 184 {
 185     char const *p = string;
 186
 187     params->unique = FALSE;
 188
 189     params->w2 = atoi(p);
 190     while (*p && isdigit((unsigned char)*p)) p++;
 191     if (*p == 'x') {
 192         p++;
 193         params->h2 = atoi(p);
 194         while (*p && isdigit((unsigned char)*p)) p++;
 195     } else {
 196         params->h2 = params->w2;
 197     }
 198
 199     if (*p == 'u') {
 200         p++;
 201         params->unique = TRUE;
 202     }
 203
 204     if (*p == 'd') {
 205         int i;
 206         p++;
 207         params->diff = DIFFCOUNT + 1;   /* ...which is invalid */
 208         if (*p) {
 209             for (i = 0; i < DIFFCOUNT; i++) {
 210                 if (*p == unruly_diffchars[i])
 211                     params->diff = i;
 212             }
 213             p++;
 214         }
 215     }
 216 }
 217
 218 static char *encode_params(const game_params *params, int full)
 219 {
 220     char buf[80];
 221
 222     sprintf(buf, "%dx%d", params->w2, params->h2);
 223     if (params->unique)
 224         strcat(buf, "u");
 225     if (full)
 226         sprintf(buf + strlen(buf), "d%c", unruly_diffchars[params->diff]);
 227
 228     return dupstr(buf);
 229 }
 230
 231 static config_item *game_configure(const game_params *params)
 232 {
 233     config_item *ret;
 234     char buf[80];
 235
 236     ret = snewn(5, config_item);
 237
 238     ret[0].name = "Width";
 239     ret[0].type = C_STRING;
 240     sprintf(buf, "%d", params->w2);
 241     ret[0].sval = dupstr(buf);
 242     ret[0].ival = 0;
 243
 244     ret[1].name = "Height";
 245     ret[1].type = C_STRING;
 246     sprintf(buf, "%d", params->h2);
 247     ret[1].sval = dupstr(buf);
 248     ret[1].ival = 0;
 249
 250     ret[2].name = "Unique rows and columns";
 251     ret[2].type = C_BOOLEAN;
 252     ret[2].ival = params->unique;
 253
 254     ret[3].name = "Difficulty";
 255     ret[3].type = C_CHOICES;
 256     ret[3].sval = DIFFCONFIG;
 257     ret[3].ival = params->diff;
 258
 259     ret[4].name = NULL;
 260     ret[4].type = C_END;
 261     ret[4].sval = NULL;
 262     ret[4].ival = 0;
 263
 264     return ret;
 265 }
 266
 267 static game_params *custom_params(const config_item *cfg)
 268 {
 269     game_params *ret = snew(game_params);
 270
 271     ret->w2 = atoi(cfg[0].sval);
 272     ret->h2 = atoi(cfg[1].sval);
 273     ret->unique = cfg[2].ival;
 274     ret->diff = cfg[3].ival;
 275
 276     return ret;
 277 }
 278
 279 static char *validate_params(const game_params *params, int full)
 280 {
 281     if ((params->w2 & 1) || (params->h2 & 1))
 282         return "Width and height must both be even";
 283     if (params->w2 < 6 || params->h2 < 6)
 284         return "Width and height must be at least 6";
 285     if (params->unique) {
 286         static const long A177790[] = {
 287             /*
 288              * The nth element of this array gives the number of
 289              * distinct possible Unruly rows of length 2n (that is,
 290              * containing exactly n 1s and n 0s and not containing
 291              * three consecutive elements the same) for as long as
 292              * those numbers fit in a 32-bit signed int.
 293              *
 294              * So in unique-rows mode, if the puzzle width is 2n, then
 295              * the height must be at most (this array)[n], and vice
 296              * versa.
 297              *
 298              * This is sequence A177790 in the Online Encyclopedia of
 299              * Integer Sequences: http://oeis.org/A177790
 300              */
 301             1L, 2L, 6L, 14L, 34L, 84L, 208L, 518L, 1296L, 3254L,
 302             8196L, 20700L, 52404L, 132942L, 337878L, 860142L,
 303             2192902L, 5598144L, 14308378L, 36610970L, 93770358L,
 304             240390602L, 616787116L, 1583765724L
 305         };
 306         if (params->w2 < 2*lenof(A177790) &&
 307             params->h2 > A177790[params->w2/2]) {
 308             return "Puzzle is too tall for unique-rows mode";
 309         }
 310         if (params->h2 < 2*lenof(A177790) &&
 311             params->w2 > A177790[params->h2/2]) {
 312             return "Puzzle is too long for unique-rows mode";
 313         }
 314     }
 315     if (params->diff >= DIFFCOUNT)
 316         return "Unknown difficulty rating";
 317
 318     return NULL;
 319 }
 320
 321 static char *validate_desc(const game_params *params, const char *desc)
 322 {
 323     int w2 = params->w2, h2 = params->h2;
 324     int s = w2 * h2;
 325
 326     const char *p = desc;
 327     int pos = 0;
 328
 329     while (*p) {
 330         if (*p >= 'a' && *p < 'z')
 331             pos += 1 + (*p - 'a');
 332         else if (*p >= 'A' && *p < 'Z')
 333             pos += 1 + (*p - 'A');
 334         else if (*p == 'Z' || *p == 'z')
 335             pos += 25;
 336         else
 337             return "Description contains invalid characters";
 338
 339         ++p;
 340     }
 341
 342     if (pos < s+1)
 343         return "Description too short";
 344     if (pos > s+1)
 345         return "Description too long";
 346
 347     return NULL;
 348 }
 349
 350 static game_state *blank_state(int w2, int h2, int unique)
 351 {
 352     game_state *state = snew(game_state);
 353     int s = w2 * h2;
 354
 355     state->w2 = w2;
 356     state->h2 = h2;
 357     state->unique = unique;
 358     state->grid = snewn(s, char);
 359     state->immutable = snewn(s, unsigned char);
 360
 361     memset(state->grid, EMPTY, s);
 362     memset(state->immutable, FALSE, s);
 363
 364     state->completed = state->cheated = FALSE;
 365
 366     return state;
 367 }
 368
 369 static game_state *new_game(midend *me, const game_params *params,
 370                             const char *desc)
 371 {
 372     int w2 = params->w2, h2 = params->h2;
 373     int s = w2 * h2;
 374
 375     game_state *state = blank_state(w2, h2, params->unique);
 376
 377     const char *p = desc;
 378     int pos = 0;
 379
 380     while (*p) {
 381         if (*p >= 'a' && *p < 'z') {
 382             pos += (*p - 'a');
 383             if (pos < s) {
 384                 state->grid[pos] = N_ZERO;
 385                 state->immutable[pos] = TRUE;
 386             }
 387             pos++;
 388         } else if (*p >= 'A' && *p < 'Z') {
 389             pos += (*p - 'A');
 390             if (pos < s) {
 391                 state->grid[pos] = N_ONE;
 392                 state->immutable[pos] = TRUE;
 393             }
 394             pos++;
 395         } else if (*p == 'Z' || *p == 'z') {
 396             pos += 25;
 397         } else
 398             assert(!"Description contains invalid characters");
 399
 400         ++p;
 401     }
 402     assert(pos == s+1);
 403
 404     return state;
 405 }
 406
 407 static game_state *dup_game(const game_state *state)
 408 {
 409     int w2 = state->w2, h2 = state->h2;
 410     int s = w2 * h2;
 411
 412     game_state *ret = blank_state(w2, h2, state->unique);
 413
 414     memcpy(ret->grid, state->grid, s);
 415     memcpy(ret->immutable, state->immutable, s);
 416
 417     ret->completed = state->completed;
 418     ret->cheated = state->cheated;
 419
 420     return ret;
 421 }
 422
 423 static void free_game(game_state *state)
 424 {
 425     sfree(state->grid);
 426     sfree(state->immutable);
 427
 428     sfree(state);
 429 }
 430
 431 static int game_can_format_as_text_now(const game_params *params)
 432 {
 433     return TRUE;
 434 }
 435
 436 static char *game_text_format(const game_state *state)
 437 {
 438     int w2 = state->w2, h2 = state->h2;
 439     int lr = w2*2 + 1;
 440
 441     char *ret = snewn(lr * h2 + 1, char);
 442     char *p = ret;
 443
 444     int x, y;
 445     for (y = 0; y < h2; y++) {
 446         for (x = 0; x < w2; x++) {
 447             /* Place number */
 448             char c = state->grid[y * w2 + x];
 449             *p++ = (c == N_ONE ? '1' : c == N_ZERO ? '0' : '.');
 450             *p++ = ' ';
 451         }
 452         /* End line */
 453         *p++ = '\n';
 454     }
 455     /* End with NUL */
 456     *p++ = '\0';
 457
 458     return ret;
 459 }
 460
 461 /* ****** *
 462  * Solver *
 463  * ****** */
 464
 465 struct unruly_scratch {
 466     int *ones_rows;
 467     int *ones_cols;
 468     int *zeros_rows;
 469     int *zeros_cols;
 470 };
 471
 472 static void unruly_solver_update_remaining(const game_state *state,
 473                                            struct unruly_scratch *scratch)
 474 {
 475     int w2 = state->w2, h2 = state->h2;
 476     int x, y;
 477
 478     /* Reset all scratch data */
 479     memset(scratch->ones_rows, 0, h2 * sizeof(int));
 480     memset(scratch->ones_cols, 0, w2 * sizeof(int));
 481     memset(scratch->zeros_rows, 0, h2 * sizeof(int));
 482     memset(scratch->zeros_cols, 0, w2 * sizeof(int));
 483
 484     for (x = 0; x < w2; x++)
 485         for (y = 0; y < h2; y++) {
 486             if (state->grid[y * w2 + x] == N_ONE) {
 487                 scratch->ones_rows[y]++;
 488                 scratch->ones_cols[x]++;
 489             } else if (state->grid[y * w2 + x] == N_ZERO) {
 490                 scratch->zeros_rows[y]++;
 491                 scratch->zeros_cols[x]++;
 492             }
 493         }
 494 }
 495
 496 static struct unruly_scratch *unruly_new_scratch(const game_state *state)
 497 {
 498     int w2 = state->w2, h2 = state->h2;
 499
 500     struct unruly_scratch *ret = snew(struct unruly_scratch);
 501
 502     ret->ones_rows = snewn(h2, int);
 503     ret->ones_cols = snewn(w2, int);
 504     ret->zeros_rows = snewn(h2, int);
 505     ret->zeros_cols = snewn(w2, int);
 506
 507     unruly_solver_update_remaining(state, ret);
 508
 509     return ret;
 510 }
 511
 512 static void unruly_free_scratch(struct unruly_scratch *scratch)
 513 {
 514     sfree(scratch->ones_rows);
 515     sfree(scratch->ones_cols);
 516     sfree(scratch->zeros_rows);
 517     sfree(scratch->zeros_cols);
 518
 519     sfree(scratch);
 520 }
 521
 522 static int unruly_solver_check_threes(game_state *state, int *rowcount,
 523                                       int *colcount, int horizontal,
 524                                       char check, char block)
 525 {
 526     int w2 = state->w2, h2 = state->h2;
 527
 528     int dx = horizontal ? 1 : 0, dy = 1 - dx;
 529     int sx = dx, sy = dy;
 530     int ex = w2 - dx, ey = h2 - dy;
 531
 532     int x, y;
 533     int ret = 0;
 534
 535     /* Check for any three squares which almost form three in a row */
 536     for (y = sy; y < ey; y++) {
 537         for (x = sx; x < ex; x++) {
 538             int i1 = (y-dy) * w2 + (x-dx);
 539             int i2 = y * w2 + x;
 540             int i3 = (y+dy) * w2 + (x+dx);
 541
 542             if (state->grid[i1] == check && state->grid[i2] == check
 543                 && state->grid[i3] == EMPTY) {
 544                 ret++;
 545 #ifdef STANDALONE_SOLVER
 546                 if (solver_verbose) {
 547                     printf("Solver: %i,%i and %i,%i confirm %c at %i,%i\n",
 548                            i1 % w2, i1 / w2, i2 % w2, i2 / w2,
 549                            (block == N_ONE ? '1' : '0'), i3 % w2,
 550                            i3 / w2);
 551                 }
 552 #endif
 553                 state->grid[i3] = block;
 554                 rowcount[i3 / w2]++;
 555                 colcount[i3 % w2]++;
 556             }
 557             if (state->grid[i1] == check && state->grid[i2] == EMPTY
 558                 && state->grid[i3] == check) {
 559                 ret++;
 560 #ifdef STANDALONE_SOLVER
 561                 if (solver_verbose) {
 562                     printf("Solver: %i,%i and %i,%i confirm %c at %i,%i\n",
 563                            i1 % w2, i1 / w2, i3 % w2, i3 / w2,
 564                            (block == N_ONE ? '1' : '0'), i2 % w2,
 565                            i2 / w2);
 566                 }
 567 #endif
 568                 state->grid[i2] = block;
 569                 rowcount[i2 / w2]++;
 570                 colcount[i2 % w2]++;
 571             }
 572             if (state->grid[i1] == EMPTY && state->grid[i2] == check
 573                 && state->grid[i3] == check) {
 574                 ret++;
 575 #ifdef STANDALONE_SOLVER
 576                 if (solver_verbose) {
 577                     printf("Solver: %i,%i and %i,%i confirm %c at %i,%i\n",
 578                            i2 % w2, i2 / w2, i3 % w2, i3 / w2,
 579                            (block == N_ONE ? '1' : '0'), i1 % w2,
 580                            i1 / w2);
 581                 }
 582 #endif
 583                 state->grid[i1] = block;
 584                 rowcount[i1 / w2]++;
 585                 colcount[i1 % w2]++;
 586             }
 587         }
 588     }
 589
 590     return ret;
 591 }
 592
 593 static int unruly_solver_check_all_threes(game_state *state,
 594                                           struct unruly_scratch *scratch)
 595 {
 596     int ret = 0;
 597
 598     ret +=
 599         unruly_solver_check_threes(state, scratch->zeros_rows,
 600                                    scratch->zeros_cols, TRUE, N_ONE, N_ZERO);
 601     ret +=
 602         unruly_solver_check_threes(state, scratch->ones_rows,
 603                                    scratch->ones_cols, TRUE, N_ZERO, N_ONE);
 604     ret +=
 605         unruly_solver_check_threes(state, scratch->zeros_rows,
 606                                    scratch->zeros_cols, FALSE, N_ONE,
 607                                    N_ZERO);
 608     ret +=
 609         unruly_solver_check_threes(state, scratch->ones_rows,
 610                                    scratch->ones_cols, FALSE, N_ZERO, N_ONE);
 611
 612     return ret;
 613 }
 614
 615 static int unruly_solver_check_uniques(game_state *state, int *rowcount,
 616                                        int horizontal, char check, char block,
 617                                        struct unruly_scratch *scratch)
 618 {
 619     int w2 = state->w2, h2 = state->h2;
 620
 621     int rmult = (horizontal ? w2 : 1);
 622     int cmult = (horizontal ? 1 : w2);
 623     int nr = (horizontal ? h2 : w2);
 624     int nc = (horizontal ? w2 : h2);
 625     int max = nc / 2;
 626
 627     int r, r2, c;
 628     int ret = 0;
 629
 630     /*
 631      * Find each row that has max entries of type 'check', and see if
 632      * all those entries match those in any row with max-1 entries. If
 633      * so, set the last non-matching entry of the latter row to ensure
 634      * that it's different.
 635      */
 636     for (r = 0; r < nr; r++) {
 637         if (rowcount[r] != max)
 638             continue;
 639         for (r2 = 0; r2 < nr; r2++) {
 640             int nmatch = 0, nonmatch = -1;
 641             if (rowcount[r2] != max-1)
 642                 continue;
 643             for (c = 0; c < nc; c++) {
 644                 if (state->grid[r*rmult + c*cmult] == check) {
 645                     if (state->grid[r2*rmult + c*cmult] == check)
 646                         nmatch++;
 647                     else
 648                         nonmatch = c;
 649                 }
 650             }
 651             if (nmatch == max-1) {
 652                 int i1 = r2 * rmult + nonmatch * cmult;
 653                 assert(nonmatch != -1);
 654                 if (state->grid[i1] == block)
 655                     continue;
 656                 assert(state->grid[i1] == EMPTY);
 657 #ifdef STANDALONE_SOLVER
 658                 if (solver_verbose) {
 659                     printf("Solver: matching %s %i, %i gives %c at %i,%i\n",
 660                            horizontal ? "rows" : "cols",
 661                            r, r2, (block == N_ONE ? '1' : '0'), i1 % w2,
 662                            i1 / w2);
 663                 }
 664 #endif
 665                 state->grid[i1] = block;
 666                 if (block == N_ONE) {
 667                     scratch->ones_rows[i1 / w2]++;
 668                     scratch->ones_cols[i1 % w2]++;
 669                 } else {
 670                     scratch->zeros_rows[i1 / w2]++;
 671                     scratch->zeros_cols[i1 % w2]++;
 672                 }
 673                 ret++;
 674             }
 675         }
 676     }
 677     return ret;
 678 }
 679
 680 static int unruly_solver_check_all_uniques(game_state *state,
 681                                            struct unruly_scratch *scratch)
 682 {
 683     int ret = 0;
 684
 685     ret += unruly_solver_check_uniques(state, scratch->ones_rows,
 686                                        TRUE, N_ONE, N_ZERO, scratch);
 687     ret += unruly_solver_check_uniques(state, scratch->zeros_rows,
 688                                        TRUE, N_ZERO, N_ONE, scratch);
 689     ret += unruly_solver_check_uniques(state, scratch->ones_cols,
 690                                        FALSE, N_ONE, N_ZERO, scratch);
 691     ret += unruly_solver_check_uniques(state, scratch->zeros_cols,
 692                                        FALSE, N_ZERO, N_ONE, scratch);
 693
 694     return ret;
 695 }
 696
 697 static int unruly_solver_fill_row(game_state *state, int i, int horizontal,
 698                                   int *rowcount, int *colcount, char fill)
 699 {
 700     int ret = 0;
 701     int w2 = state->w2, h2 = state->h2;
 702     int j;
 703
 704 #ifdef STANDALONE_SOLVER
 705     if (solver_verbose) {
 706         printf("Solver: Filling %s %i with %c:",
 707                (horizontal ? "Row" : "Col"), i,
 708                (fill == N_ZERO ? '0' : '1'));
 709     }
 710 #endif
 711     /* Place a number in every empty square in a row/column */
 712     for (j = 0; j < (horizontal ? w2 : h2); j++) {
 713         int p = (horizontal ? i * w2 + j : j * w2 + i);
 714
 715         if (state->grid[p] == EMPTY) {
 716 #ifdef STANDALONE_SOLVER
 717             if (solver_verbose) {
 718                 printf(" (%i,%i)", (horizontal ? j : i),
 719                        (horizontal ? i : j));
 720             }
 721 #endif
 722             ret++;
 723             state->grid[p] = fill;
 724             rowcount[(horizontal ? i : j)]++;
 725             colcount[(horizontal ? j : i)]++;
 726         }
 727     }
 728
 729 #ifdef STANDALONE_SOLVER
 730     if (solver_verbose) {
 731         printf("\n");
 732     }
 733 #endif
 734
 735     return ret;
 736 }
 737
 738 static int unruly_solver_check_complete_nums(game_state *state,
 739                                              int *complete, int horizontal,
 740                                              int *rowcount, int *colcount,
 741                                              char fill)
 742 {
 743     int w2 = state->w2, h2 = state->h2;
 744     int count = (horizontal ? h2 : w2); /* number of rows to check */
 745     int target = (horizontal ? w2 : h2) / 2; /* target number of 0s/1s */
 746     int *other = (horizontal ? rowcount : colcount);
 747
 748     int ret = 0;
 749
 750     int i;
 751     /* Check for completed rows/cols for one number, then fill in the rest */
 752     for (i = 0; i < count; i++) {
 753         if (complete[i] == target && other[i] < target) {
 754 #ifdef STANDALONE_SOLVER
 755             if (solver_verbose) {
 756                 printf("Solver: Row %i satisfied for %c\n", i,
 757                        (fill != N_ZERO ? '0' : '1'));
 758             }
 759 #endif
 760             ret += unruly_solver_fill_row(state, i, horizontal, rowcount,
 761                                           colcount, fill);
 762         }
 763     }
 764
 765     return ret;
 766 }
 767
 768 static int unruly_solver_check_all_complete_nums(game_state *state,
 769                                                  struct unruly_scratch *scratch)
 770 {
 771     int ret = 0;
 772
 773     ret +=
 774         unruly_solver_check_complete_nums(state, scratch->ones_rows, TRUE,
 775                                           scratch->zeros_rows,
 776                                           scratch->zeros_cols, N_ZERO);
 777     ret +=
 778         unruly_solver_check_complete_nums(state, scratch->ones_cols, FALSE,
 779                                           scratch->zeros_rows,
 780                                           scratch->zeros_cols, N_ZERO);
 781     ret +=
 782         unruly_solver_check_complete_nums(state, scratch->zeros_rows, TRUE,
 783                                           scratch->ones_rows,
 784                                           scratch->ones_cols, N_ONE);
 785     ret +=
 786         unruly_solver_check_complete_nums(state, scratch->zeros_cols, FALSE,
 787                                           scratch->ones_rows,
 788                                           scratch->ones_cols, N_ONE);
 789
 790     return ret;
 791 }
 792
 793 static int unruly_solver_check_near_complete(game_state *state,
 794                                              int *complete, int horizontal,
 795                                              int *rowcount, int *colcount,
 796                                              char fill)
 797 {
 798     int w2 = state->w2, h2 = state->h2;
 799     int w = w2/2, h = h2/2;
 800
 801     int dx = horizontal ? 1 : 0, dy = 1 - dx;
 802
 803     int sx = dx, sy = dy;
 804     int ex = w2 - dx, ey = h2 - dy;
 805
 806     int x, y;
 807     int ret = 0;
 808
 809     /*
 810      * This function checks for a row with one Y remaining, then looks
 811      * for positions that could cause the remaining squares in the row
 812      * to make 3 X's in a row. Example:
 813      *
 814      * Consider the following row:
 815      * 1 1 0 . . .
 816      * If the last 1 was placed in the last square, the remaining
 817      * squares would be 0:
 818      * 1 1 0 0 0 1
 819      * This violates the 3 in a row rule. We now know that the last 1
 820      * shouldn't be in the last cell.
 821      * 1 1 0 . . 0
 822      */
 823
 824     /* Check for any two blank and one filled square */
 825     for (y = sy; y < ey; y++) {
 826         /* One type must have 1 remaining, the other at least 2 */
 827         if (horizontal && (complete[y] < w - 1 || rowcount[y] > w - 2))
 828             continue;
 829
 830         for (x = sx; x < ex; x++) {
 831             int i, i1, i2, i3;
 832             if (!horizontal
 833                 && (complete[x] < h - 1 || colcount[x] > h - 2))
 834                 continue;
 835
 836             i = (horizontal ? y : x);
 837             i1 = (y-dy) * w2 + (x-dx);
 838             i2 = y * w2 + x;
 839             i3 = (y+dy) * w2 + (x+dx);
 840
 841             if (state->grid[i1] == fill && state->grid[i2] == EMPTY
 842                 && state->grid[i3] == EMPTY) {
 843                 /*
 844                  * Temporarily fill the empty spaces with something else.
 845                  * This avoids raising the counts for the row and column
 846                  */
 847                 state->grid[i2] = BOGUS;
 848                 state->grid[i3] = BOGUS;
 849
 850 #ifdef STANDALONE_SOLVER
 851                 if (solver_verbose) {
 852                     printf("Solver: Row %i nearly satisfied for %c\n", i,
 853                            (fill != N_ZERO ? '0' : '1'));
 854                 }
 855 #endif
 856                 ret +=
 857                     unruly_solver_fill_row(state, i, horizontal, rowcount,
 858                                          colcount, fill);
 859
 860                 state->grid[i2] = EMPTY;
 861                 state->grid[i3] = EMPTY;
 862             }
 863
 864             else if (state->grid[i1] == EMPTY && state->grid[i2] == fill
 865                      && state->grid[i3] == EMPTY) {
 866                 state->grid[i1] = BOGUS;
 867                 state->grid[i3] = BOGUS;
 868
 869 #ifdef STANDALONE_SOLVER
 870                 if (solver_verbose) {
 871                     printf("Solver: Row %i nearly satisfied for %c\n", i,
 872                            (fill != N_ZERO ? '0' : '1'));
 873                 }
 874 #endif
 875                 ret +=
 876                     unruly_solver_fill_row(state, i, horizontal, rowcount,
 877                                          colcount, fill);
 878
 879                 state->grid[i1] = EMPTY;
 880                 state->grid[i3] = EMPTY;
 881             }
 882
 883             else if (state->grid[i1] == EMPTY && state->grid[i2] == EMPTY
 884                      && state->grid[i3] == fill) {
 885                 state->grid[i1] = BOGUS;
 886                 state->grid[i2] = BOGUS;
 887
 888 #ifdef STANDALONE_SOLVER
 889                 if (solver_verbose) {
 890                     printf("Solver: Row %i nearly satisfied for %c\n", i,
 891                            (fill != N_ZERO ? '0' : '1'));
 892                 }
 893 #endif
 894                 ret +=
 895                     unruly_solver_fill_row(state, i, horizontal, rowcount,
 896                                          colcount, fill);
 897
 898                 state->grid[i1] = EMPTY;
 899                 state->grid[i2] = EMPTY;
 900             }
 901
 902             else if (state->grid[i1] == EMPTY && state->grid[i2] == EMPTY
 903                      && state->grid[i3] == EMPTY) {
 904                 state->grid[i1] = BOGUS;
 905                 state->grid[i2] = BOGUS;
 906                 state->grid[i3] = BOGUS;
 907
 908 #ifdef STANDALONE_SOLVER
 909                 if (solver_verbose) {
 910                     printf("Solver: Row %i nearly satisfied for %c\n", i,
 911                            (fill != N_ZERO ? '0' : '1'));
 912                 }
 913 #endif
 914                 ret +=
 915                     unruly_solver_fill_row(state, i, horizontal, rowcount,
 916                                          colcount, fill);
 917
 918                 state->grid[i1] = EMPTY;
 919                 state->grid[i2] = EMPTY;
 920                 state->grid[i3] = EMPTY;
 921             }
 922         }
 923     }
 924
 925     return ret;
 926 }
 927
 928 static int unruly_solver_check_all_near_complete(game_state *state,
 929                                                  struct unruly_scratch *scratch)
 930 {
 931     int ret = 0;
 932
 933     ret +=
 934         unruly_solver_check_near_complete(state, scratch->ones_rows, TRUE,
 935                                         scratch->zeros_rows,
 936                                         scratch->zeros_cols, N_ZERO);
 937     ret +=
 938         unruly_solver_check_near_complete(state, scratch->ones_cols, FALSE,
 939                                         scratch->zeros_rows,
 940                                         scratch->zeros_cols, N_ZERO);
 941     ret +=
 942         unruly_solver_check_near_complete(state, scratch->zeros_rows, TRUE,
 943                                         scratch->ones_rows,
 944                                         scratch->ones_cols, N_ONE);
 945     ret +=
 946         unruly_solver_check_near_complete(state, scratch->zeros_cols, FALSE,
 947                                         scratch->ones_rows,
 948                                         scratch->ones_cols, N_ONE);
 949
 950     return ret;
 951 }
 952
 953 static int unruly_validate_rows(const game_state *state, int horizontal,
 954                                 char check, int *errors)
 955 {
 956     int w2 = state->w2, h2 = state->h2;
 957
 958     int dx = horizontal ? 1 : 0, dy = 1 - dx;
 959
 960     int sx = dx, sy = dy;
 961     int ex = w2 - dx, ey = h2 - dy;
 962
 963     int x, y;
 964     int ret = 0;
 965
 966     int err1 = (horizontal ? FE_HOR_ROW_LEFT : FE_VER_ROW_TOP);
 967     int err2 = (horizontal ? FE_HOR_ROW_MID : FE_VER_ROW_MID);
 968     int err3 = (horizontal ? FE_HOR_ROW_RIGHT : FE_VER_ROW_BOTTOM);
 969
 970     /* Check for any three in a row, and mark errors accordingly (if
 971      * required) */
 972     for (y = sy; y < ey; y++) {
 973         for (x = sx; x < ex; x++) {
 974             int i1 = (y-dy) * w2 + (x-dx);
 975             int i2 = y * w2 + x;
 976             int i3 = (y+dy) * w2 + (x+dx);
 977
 978             if (state->grid[i1] == check && state->grid[i2] == check
 979                 && state->grid[i3] == check) {
 980                 ret++;
 981                 if (errors) {
 982                     errors[i1] |= err1;
 983                     errors[i2] |= err2;
 984                     errors[i3] |= err3;
 985                 }
 986             }
 987         }
 988     }
 989
 990     return ret;
 991 }
 992
 993 static int unruly_validate_unique(const game_state *state, int horizontal,
 994                                   int *errors)
 995 {
 996     int w2 = state->w2, h2 = state->h2;
 997
 998     int rmult = (horizontal ? w2 : 1);
 999     int cmult = (horizontal ? 1 : w2);
1000     int nr = (horizontal ? h2 : w2);
1001     int nc = (horizontal ? w2 : h2);
1002     int err = (horizontal ? FE_ROW_MATCH : FE_COL_MATCH);
1003
1004     int r, r2, c;
1005     int ret = 0;
1006
1007     /* Check for any two full rows matching exactly, and mark errors
1008      * accordingly (if required) */
1009     for (r = 0; r < nr; r++) {
1010         int nfull = 0;
1011         for (c = 0; c < nc; c++)
1012             if (state->grid[r*rmult + c*cmult] != EMPTY)
1013                 nfull++;
1014         if (nfull != nr)
1015             continue;
1016         for (r2 = r+1; r2 < nr; r2++) {
1017             int match = TRUE;
1018             for (c = 0; c < nc; c++)
1019                 if (state->grid[r*rmult + c*cmult] !=
1020                     state->grid[r2*rmult + c*cmult])
1021                     match = FALSE;
1022             if (match) {
1023                 if (errors) {
1024                     for (c = 0; c < nc; c++) {
1025                         errors[r*rmult + c*cmult] |= err;
1026                         errors[r2*rmult + c*cmult] |= err;
1027                     }
1028                 }
1029                 ret++;
1030             }
1031         }
1032     }
1033
1034     return ret;
1035 }
1036
1037 static int unruly_validate_all_rows(const game_state *state, int *errors)
1038 {
1039     int errcount = 0;
1040
1041     errcount += unruly_validate_rows(state, TRUE, N_ONE, errors);
1042     errcount += unruly_validate_rows(state, FALSE, N_ONE, errors);
1043     errcount += unruly_validate_rows(state, TRUE, N_ZERO, errors);
1044     errcount += unruly_validate_rows(state, FALSE, N_ZERO, errors);
1045
1046     if (state->unique) {
1047         errcount += unruly_validate_unique(state, TRUE, errors);
1048         errcount += unruly_validate_unique(state, FALSE, errors);
1049     }
1050
1051     if (errcount)
1052         return -1;
1053     return 0;
1054 }
1055
1056 static int unruly_validate_counts(const game_state *state,
1057                                   struct unruly_scratch *scratch, int *errors)
1058 {
1059     int w2 = state->w2, h2 = state->h2;
1060     int w = w2/2, h = h2/2;
1061     char below = FALSE;
1062     char above = FALSE;
1063     int i;
1064
1065     /* See if all rows/columns are satisfied. If one is exceeded,
1066      * mark it as an error (if required)
1067      */
1068
1069     char hasscratch = TRUE;
1070     if (!scratch) {
1071         scratch = unruly_new_scratch(state);
1072         hasscratch = FALSE;
1073     }
1074
1075     for (i = 0; i < w2; i++) {
1076         if (scratch->ones_cols[i] < h)
1077             below = TRUE;
1078         if (scratch->zeros_cols[i] < h)
1079             below = TRUE;
1080
1081         if (scratch->ones_cols[i] > h) {
1082             above = TRUE;
1083             if (errors)
1084                 errors[2*h2 + i] = TRUE;
1085         } else if (errors)
1086             errors[2*h2 + i] = FALSE;
1087
1088         if (scratch->zeros_cols[i] > h) {
1089             above = TRUE;
1090             if (errors)
1091                 errors[2*h2 + w2 + i] = TRUE;
1092         } else if (errors)
1093             errors[2*h2 + w2 + i] = FALSE;
1094     }
1095     for (i = 0; i < h2; i++) {
1096         if (scratch->ones_rows[i] < w)
1097             below = TRUE;
1098         if (scratch->zeros_rows[i] < w)
1099             below = TRUE;
1100
1101         if (scratch->ones_rows[i] > w) {
1102             above = TRUE;
1103             if (errors)
1104                 errors[i] = TRUE;
1105         } else if (errors)
1106             errors[i] = FALSE;
1107
1108         if (scratch->zeros_rows[i] > w) {
1109             above = TRUE;
1110             if (errors)
1111                 errors[h2 + i] = TRUE;
1112         } else if (errors)
1113             errors[h2 + i] = FALSE;
1114     }
1115
1116     if (!hasscratch)
1117         unruly_free_scratch(scratch);
1118
1119     return (above ? -1 : below ? 1 : 0);
1120 }
1121
1122 static int unruly_solve_game(game_state *state,
1123                              struct unruly_scratch *scratch, int diff)
1124 {
1125     int done, maxdiff = -1;
1126
1127     while (TRUE) {
1128         done = 0;
1129
1130         /* Check for impending 3's */
1131         done += unruly_solver_check_all_threes(state, scratch);
1132
1133         /* Keep using the simpler techniques while they produce results */
1134         if (done) {
1135             if (maxdiff < DIFF_EASY)
1136                 maxdiff = DIFF_EASY;
1137             continue;
1138         }
1139
1140         /* Check for completed rows */
1141         done += unruly_solver_check_all_complete_nums(state, scratch);
1142
1143         if (done) {
1144             if (maxdiff < DIFF_EASY)
1145                 maxdiff = DIFF_EASY;
1146             continue;
1147         }
1148
1149         /* Check for impending failures of row/column uniqueness, if
1150          * it's enabled in this game mode */
1151         if (state->unique) {
1152             done += unruly_solver_check_all_uniques(state, scratch);
1153
1154             if (done) {
1155                 if (maxdiff < DIFF_EASY)
1156                     maxdiff = DIFF_EASY;
1157                 continue;
1158             }
1159         }
1160
1161         /* Normal techniques */
1162         if (diff < DIFF_NORMAL)
1163             break;
1164
1165         /* Check for nearly completed rows */
1166         done += unruly_solver_check_all_near_complete(state, scratch);
1167
1168         if (done) {
1169             if (maxdiff < DIFF_NORMAL)
1170                 maxdiff = DIFF_NORMAL;
1171             continue;
1172         }
1173
1174         break;
1175     }
1176     return maxdiff;
1177 }
1178
1179 static char *solve_game(const game_state *state, const game_state *currstate,
1180                         const char *aux, char **error)
1181 {
1182     game_state *solved = dup_game(state);
1183     struct unruly_scratch *scratch = unruly_new_scratch(solved);
1184     char *ret = NULL;
1185     int result;
1186
1187     unruly_solve_game(solved, scratch, DIFFCOUNT);
1188
1189     result = unruly_validate_counts(solved, scratch, NULL);
1190     if (unruly_validate_all_rows(solved, NULL) == -1)
1191         result = -1;
1192
1193     if (result == 0) {
1194         int w2 = solved->w2, h2 = solved->h2;
1195         int s = w2 * h2;
1196         char *p;
1197         int i;
1198
1199         ret = snewn(s + 2, char);
1200         p = ret;
1201         *p++ = 'S';
1202
1203         for (i = 0; i < s; i++)
1204             *p++ = (solved->grid[i] == N_ONE ? '1' : '0');
1205
1206         *p++ = '\0';
1207     } else if (result == 1)
1208         *error = "No solution found.";
1209     else if (result == -1)
1210         *error = "Puzzle is invalid.";
1211
1212     free_game(solved);
1213     unruly_free_scratch(scratch);
1214     return ret;
1215 }
1216
1217 /* ********* *
1218  * Generator *
1219  * ********* */
1220
1221 static int unruly_fill_game(game_state *state, struct unruly_scratch *scratch,
1222                             random_state *rs)
1223 {
1224
1225     int w2 = state->w2, h2 = state->h2;
1226     int s = w2 * h2;
1227     int i, j;
1228     int *spaces;
1229
1230 #ifdef STANDALONE_SOLVER
1231     if (solver_verbose) {
1232         printf("Generator: Attempt to fill grid\n");
1233     }
1234 #endif
1235
1236     /* Generate random array of spaces */
1237     spaces = snewn(s, int);
1238     for (i = 0; i < s; i++)
1239         spaces[i] = i;
1240     shuffle(spaces, s, sizeof(*spaces), rs);
1241
1242     /*
1243      * Construct a valid filled grid by repeatedly picking an unfilled
1244      * space and fill it, then calling the solver to fill in any
1245      * spaces forced by the change.
1246      */
1247     for (j = 0; j < s; j++) {
1248         i = spaces[j];
1249
1250         if (state->grid[i] != EMPTY)
1251             continue;
1252
1253         if (random_upto(rs, 2)) {
1254             state->grid[i] = N_ONE;
1255             scratch->ones_rows[i / w2]++;
1256             scratch->ones_cols[i % w2]++;
1257         } else {
1258             state->grid[i] = N_ZERO;
1259             scratch->zeros_rows[i / w2]++;
1260             scratch->zeros_cols[i % w2]++;
1261         }
1262
1263         unruly_solve_game(state, scratch, DIFFCOUNT);
1264     }
1265     sfree(spaces);
1266
1267     if (unruly_validate_all_rows(state, NULL) != 0
1268         || unruly_validate_counts(state, scratch, NULL) != 0)
1269         return FALSE;
1270
1271     return TRUE;
1272 }
1273
1274 static char *new_game_desc(const game_params *params, random_state *rs,
1275                            char **aux, int interactive)
1276 {
1277 #ifdef STANDALONE_SOLVER
1278     char *debug;
1279     int temp_verbose = FALSE;
1280 #endif
1281
1282     int w2 = params->w2, h2 = params->h2;
1283     int s = w2 * h2;
1284     int *spaces;
1285     int i, j, run;
1286     char *ret, *p;
1287
1288     game_state *state;
1289     struct unruly_scratch *scratch;
1290
1291     int attempts = 0;
1292
1293     while (1) {
1294
1295         while (TRUE) {
1296             attempts++;
1297             state = blank_state(w2, h2, params->unique);
1298             scratch = unruly_new_scratch(state);
1299             if (unruly_fill_game(state, scratch, rs))
1300                 break;
1301             free_game(state);
1302             unruly_free_scratch(scratch);
1303         }
1304
1305 #ifdef STANDALONE_SOLVER
1306         if (solver_verbose) {
1307             printf("Puzzle generated in %i attempts\n", attempts);
1308             debug = game_text_format(state);
1309             fputs(debug, stdout);
1310             sfree(debug);
1311
1312             temp_verbose = solver_verbose;
1313             solver_verbose = FALSE;
1314         }
1315 #endif
1316
1317         unruly_free_scratch(scratch);
1318
1319         /* Generate random array of spaces */
1320         spaces = snewn(s, int);
1321         for (i = 0; i < s; i++)
1322             spaces[i] = i;
1323         shuffle(spaces, s, sizeof(*spaces), rs);
1324
1325         /*
1326          * Winnow the clues by starting from our filled grid, repeatedly
1327          * picking a filled space and emptying it, as long as the solver
1328          * reports that the puzzle can still be solved after doing so.
1329          */
1330         for (j = 0; j < s; j++) {
1331             char c;
1332             game_state *solver;
1333
1334             i = spaces[j];
1335
1336             c = state->grid[i];
1337             state->grid[i] = EMPTY;
1338
1339             solver = dup_game(state);
1340             scratch = unruly_new_scratch(state);
1341
1342             unruly_solve_game(solver, scratch, params->diff);
1343
1344             if (unruly_validate_counts(solver, scratch, NULL) != 0)
1345                 state->grid[i] = c;
1346
1347             free_game(solver);
1348             unruly_free_scratch(scratch);
1349         }
1350         sfree(spaces);
1351
1352 #ifdef STANDALONE_SOLVER
1353         if (temp_verbose) {
1354             solver_verbose = TRUE;
1355
1356             printf("Final puzzle:\n");
1357             debug = game_text_format(state);
1358             fputs(debug, stdout);
1359             sfree(debug);
1360         }
1361 #endif
1362
1363         /*
1364          * See if the game has accidentally come out too easy.
1365          */
1366         if (params->diff > 0) {
1367             int ok;
1368             game_state *solver;
1369
1370             solver = dup_game(state);
1371             scratch = unruly_new_scratch(state);
1372
1373             unruly_solve_game(solver, scratch, params->diff - 1);
1374
1375             ok = unruly_validate_counts(solver, scratch, NULL);
1376
1377             free_game(solver);
1378             unruly_free_scratch(scratch);
1379
1380             if (ok)
1381                 break;
1382         } else {
1383             /*
1384              * Puzzles of the easiest difficulty can't be too easy.
1385              */
1386             break;
1387         }
1388     }
1389
1390     /* Encode description */
1391     ret = snewn(s + 1, char);
1392     p = ret;
1393     run = 0;
1394     for (i = 0; i < s+1; i++) {
1395         if (i == s || state->grid[i] == N_ZERO) {
1396             while (run > 24) {
1397                 *p++ = 'z';
1398                 run -= 25;
1399             }
1400             *p++ = 'a' + run;
1401             run = 0;
1402         } else if (state->grid[i] == N_ONE) {
1403             while (run > 24) {
1404                 *p++ = 'Z';
1405                 run -= 25;
1406             }
1407             *p++ = 'A' + run;
1408             run = 0;
1409         } else {
1410             run++;
1411         }
1412     }
1413     *p = '\0';
1414
1415     free_game(state);
1416
1417     return ret;
1418 }
1419
1420 /* ************** *
1421  * User Interface *
1422  * ************** */
1423
1424 struct game_ui {
1425     int cx, cy;
1426     char cursor;
1427 };
1428
1429 static game_ui *new_ui(const game_state *state)
1430 {
1431     game_ui *ret = snew(game_ui);
1432
1433     ret->cx = ret->cy = 0;
1434     ret->cursor = FALSE;
1435
1436     return ret;
1437 }
1438
1439 static void free_ui(game_ui *ui)
1440 {
1441     sfree(ui);
1442 }
1443
1444 static char *encode_ui(const game_ui *ui)
1445 {
1446     return NULL;
1447 }
1448
1449 static void decode_ui(game_ui *ui, const char *encoding)
1450 {
1451 }
1452
1453 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1454                                const game_state *newstate)
1455 {
1456 }
1457
1458 struct game_drawstate {
1459     int tilesize;
1460     int w2, h2;
1461     int started;
1462
1463     int *gridfs;
1464     int *rowfs;
1465
1466     int *grid;
1467 };
1468
1469 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1470 {
1471     struct game_drawstate *ds = snew(struct game_drawstate);
1472
1473     int w2 = state->w2, h2 = state->h2;
1474     int s = w2 * h2;
1475     int i;
1476
1477     ds->tilesize = 0;
1478     ds->w2 = w2;
1479     ds->h2 = h2;
1480     ds->started = FALSE;
1481
1482     ds->gridfs = snewn(s, int);
1483     ds->rowfs = snewn(2 * (w2 + h2), int);
1484
1485     ds->grid = snewn(s, int);
1486     for (i = 0; i < s; i++)
1487         ds->grid[i] = -1;
1488
1489     return ds;
1490 }
1491
1492 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1493 {
1494     sfree(ds->gridfs);
1495     sfree(ds->rowfs);
1496     sfree(ds->grid);
1497     sfree(ds);
1498 }
1499
1500 #define COORD(x)     ( (x) * ds->tilesize + ds->tilesize/2 )
1501 #define FROMCOORD(x) ( ((x)-(ds->tilesize/2)) / ds->tilesize )
1502
1503 static char *interpret_move(const game_state *state, game_ui *ui,
1504                             const game_drawstate *ds,
1505                             int ox, int oy, int button)
1506 {
1507     int hx = ui->cx;
1508     int hy = ui->cy;
1509
1510     int gx = FROMCOORD(ox);
1511     int gy = FROMCOORD(oy);
1512
1513     int w2 = state->w2, h2 = state->h2;
1514
1515     button &= ~MOD_MASK;
1516
1517     /* Mouse click */
1518     if (button == LEFT_BUTTON || button == RIGHT_BUTTON ||
1519         button == MIDDLE_BUTTON) {
1520         if (ox >= (ds->tilesize / 2) && gx < w2
1521             && oy >= (ds->tilesize / 2) && gy < h2) {
1522             hx = gx;
1523             hy = gy;
1524             ui->cursor = FALSE;
1525         } else
1526             return NULL;
1527     }
1528
1529     /* Keyboard move */
1530     if (IS_CURSOR_MOVE(button)) {
1531         move_cursor(button, &ui->cx, &ui->cy, w2, h2, 0);
1532         ui->cursor = TRUE;
1533         return "";
1534     }
1535
1536     /* Place one */
1537     if ((ui->cursor && (button == CURSOR_SELECT || button == CURSOR_SELECT2
1538                         || button == '\b' || button == '0' || button == '1'
1539                         || button == '2')) ||
1540         button == LEFT_BUTTON || button == RIGHT_BUTTON ||
1541         button == MIDDLE_BUTTON) {
1542         char buf[80];
1543         char c, i;
1544
1545         if (state->immutable[hy * w2 + hx])
1546             return NULL;
1547
1548         c = '-';
1549         i = state->grid[hy * w2 + hx];
1550
1551         if (button == '0' || button == '2')
1552             c = '0';
1553         else if (button == '1')
1554             c = '1';
1555         else if (button == MIDDLE_BUTTON)
1556             c = '-';
1557
1558         /* Cycle through options */
1559         else if (button == CURSOR_SELECT2 || button == RIGHT_BUTTON)
1560             c = (i == EMPTY ? '0' : i == N_ZERO ? '1' : '-');
1561         else if (button == CURSOR_SELECT || button == LEFT_BUTTON)
1562             c = (i == EMPTY ? '1' : i == N_ONE ? '0' : '-');
1563
1564         if (state->grid[hy * w2 + hx] ==
1565             (c == '0' ? N_ZERO : c == '1' ? N_ONE : EMPTY))
1566             return NULL;               /* don't put no-ops on the undo chain */
1567
1568         sprintf(buf, "P%c,%d,%d", c, hx, hy);
1569
1570         return dupstr(buf);
1571     }
1572     return NULL;
1573 }
1574
1575 static game_state *execute_move(const game_state *state, const char *move)
1576 {
1577     int w2 = state->w2, h2 = state->h2;
1578     int s = w2 * h2;
1579     int x, y, i;
1580     char c;
1581
1582     game_state *ret;
1583
1584     if (move[0] == 'S') {
1585         const char *p;
1586
1587         ret = dup_game(state);
1588         p = move + 1;
1589
1590         for (i = 0; i < s; i++) {
1591
1592             if (!*p || !(*p == '1' || *p == '0')) {
1593                 free_game(ret);
1594                 return NULL;
1595             }
1596
1597             ret->grid[i] = (*p == '1' ? N_ONE : N_ZERO);
1598             p++;
1599         }
1600
1601         ret->completed = ret->cheated = TRUE;
1602         return ret;
1603     } else if (move[0] == 'P'
1604                && sscanf(move + 1, "%c,%d,%d", &c, &x, &y) == 3 && x >= 0
1605                && x < w2 && y >= 0 && y < h2 && (c == '-' || c == '0'
1606                                                  || c == '1')) {
1607         ret = dup_game(state);
1608         i = y * w2 + x;
1609
1610         if (state->immutable[i]) {
1611             free_game(ret);
1612             return NULL;
1613         }
1614
1615         ret->grid[i] = (c == '1' ? N_ONE : c == '0' ? N_ZERO : EMPTY);
1616
1617         if (!ret->completed && unruly_validate_counts(ret, NULL, NULL) == 0
1618             && (unruly_validate_all_rows(ret, NULL) == 0))
1619             ret->completed = TRUE;
1620
1621         return ret;
1622     }
1623
1624     return NULL;
1625 }
1626
1627 /* ----------------------------------------------------------------------
1628  * Drawing routines.
1629  */
1630
1631 static void game_compute_size(const game_params *params, int tilesize,
1632                               int *x, int *y)
1633 {
1634     *x = tilesize * (params->w2 + 1);
1635     *y = tilesize * (params->h2 + 1);
1636 }
1637
1638 static void game_set_size(drawing *dr, game_drawstate *ds,
1639                           const game_params *params, int tilesize)
1640 {
1641     ds->tilesize = tilesize;
1642 }
1643
1644 static float *game_colours(frontend *fe, int *ncolours)
1645 {
1646     float *ret = snewn(3 * NCOLOURS, float);
1647     int i;
1648
1649     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1650
1651     for (i = 0; i < 3; i++) {
1652         ret[COL_1 * 3 + i] = 0.2F;
1653         ret[COL_1_HIGHLIGHT * 3 + i] = 0.4F;
1654         ret[COL_1_LOWLIGHT * 3 + i] = 0.0F;
1655         ret[COL_0 * 3 + i] = 0.95F;
1656         ret[COL_0_HIGHLIGHT * 3 + i] = 1.0F;
1657         ret[COL_0_LOWLIGHT * 3 + i] = 0.9F;
1658         ret[COL_EMPTY * 3 + i] = 0.5F;
1659         ret[COL_GRID * 3 + i] = 0.3F;
1660     }
1661     game_mkhighlight_specific(fe, ret, COL_0, COL_0_HIGHLIGHT, COL_0_LOWLIGHT);
1662     game_mkhighlight_specific(fe, ret, COL_1, COL_1_HIGHLIGHT, COL_1_LOWLIGHT);
1663
1664     ret[COL_ERROR * 3 + 0] = 1.0F;
1665     ret[COL_ERROR * 3 + 1] = 0.0F;
1666     ret[COL_ERROR * 3 + 2] = 0.0F;
1667
1668     ret[COL_CURSOR * 3 + 0] = 0.0F;
1669     ret[COL_CURSOR * 3 + 1] = 0.7F;
1670     ret[COL_CURSOR * 3 + 2] = 0.0F;
1671
1672     *ncolours = NCOLOURS;
1673     return ret;
1674 }
1675
1676 static void unruly_draw_err_rectangle(drawing *dr, int x, int y, int w, int h,
1677                                       int tilesize)
1678 {
1679     double thick = tilesize / 10;
1680     double margin = tilesize / 20;
1681
1682     draw_rect(dr, x+margin, y+margin, w-2*margin, thick, COL_ERROR);
1683     draw_rect(dr, x+margin, y+margin, thick, h-2*margin, COL_ERROR);
1684     draw_rect(dr, x+margin, y+h-margin-thick, w-2*margin, thick, COL_ERROR);
1685     draw_rect(dr, x+w-margin-thick, y+margin, thick, h-2*margin, COL_ERROR);
1686 }
1687
1688 static void unruly_draw_tile(drawing *dr, int x, int y, int tilesize, int tile)
1689 {
1690     clip(dr, x, y, tilesize, tilesize);
1691
1692     /* Draw the grid edge first, so the tile can overwrite it */
1693     draw_rect(dr, x, y, tilesize, tilesize, COL_GRID);
1694
1695     /* Background of the tile */
1696     {
1697         int val = (tile & FF_ZERO ? 0 : tile & FF_ONE ? 2 : 1);
1698         val = (val == 0 ? COL_0 : val == 2 ? COL_1 : COL_EMPTY);
1699
1700         if ((tile & (FF_FLASH1 | FF_FLASH2)) &&
1701              (val == COL_0 || val == COL_1)) {
1702             val += (tile & FF_FLASH1 ? 1 : 2);
1703         }
1704
1705         draw_rect(dr, x, y, tilesize-1, tilesize-1, val);
1706
1707         if ((val == COL_0 || val == COL_1) && (tile & FF_IMMUTABLE)) {
1708             draw_rect(dr, x + tilesize/6, y + tilesize/6,
1709                       tilesize - 2*(tilesize/6) - 2, 1, val + 2);
1710             draw_rect(dr, x + tilesize/6, y + tilesize/6,
1711                       1, tilesize - 2*(tilesize/6) - 2, val + 2);
1712             draw_rect(dr, x + tilesize/6 + 1, y + tilesize - tilesize/6 - 2,
1713                       tilesize - 2*(tilesize/6) - 2, 1, val + 1);
1714             draw_rect(dr, x + tilesize - tilesize/6 - 2, y + tilesize/6 + 1,
1715                       1, tilesize - 2*(tilesize/6) - 2, val + 1);
1716         }
1717     }
1718
1719     /* 3-in-a-row errors */
1720     if (tile & (FE_HOR_ROW_LEFT | FE_HOR_ROW_RIGHT)) {
1721         int left = x, right = x + tilesize - 1;
1722         if ((tile & FE_HOR_ROW_LEFT))
1723             right += tilesize/2;
1724         if ((tile & FE_HOR_ROW_RIGHT))
1725             left -= tilesize/2;
1726         unruly_draw_err_rectangle(dr, left, y, right-left, tilesize-1, tilesize);
1727     }
1728     if (tile & (FE_VER_ROW_TOP | FE_VER_ROW_BOTTOM)) {
1729         int top = y, bottom = y + tilesize - 1;
1730         if ((tile & FE_VER_ROW_TOP))
1731             bottom += tilesize/2;
1732         if ((tile & FE_VER_ROW_BOTTOM))
1733             top -= tilesize/2;
1734         unruly_draw_err_rectangle(dr, x, top, tilesize-1, bottom-top, tilesize);
1735     }
1736
1737     /* Count errors */
1738     if (tile & FE_COUNT) {
1739         draw_text(dr, x + tilesize/2, y + tilesize/2, FONT_VARIABLE,
1740                   tilesize/2, ALIGN_HCENTRE | ALIGN_VCENTRE, COL_ERROR, "!");
1741     }
1742
1743     /* Row-match errors */
1744     if (tile & FE_ROW_MATCH) {
1745         draw_rect(dr, x, y+tilesize/2-tilesize/12,
1746                   tilesize, 2*(tilesize/12), COL_ERROR);
1747     }
1748     if (tile & FE_COL_MATCH) {
1749         draw_rect(dr, x+tilesize/2-tilesize/12, y,
1750                   2*(tilesize/12), tilesize, COL_ERROR);
1751     }
1752
1753     /* Cursor rectangle */
1754     if (tile & FF_CURSOR) {
1755         draw_rect(dr, x, y, tilesize/12, tilesize-1, COL_CURSOR);
1756         draw_rect(dr, x, y, tilesize-1, tilesize/12, COL_CURSOR);
1757         draw_rect(dr, x+tilesize-1-tilesize/12, y, tilesize/12, tilesize-1,
1758                   COL_CURSOR);
1759         draw_rect(dr, x, y+tilesize-1-tilesize/12, tilesize-1, tilesize/12,
1760                   COL_CURSOR);
1761     }
1762
1763     unclip(dr);
1764     draw_update(dr, x, y, tilesize, tilesize);
1765 }
1766
1767 #define TILE_SIZE (ds->tilesize)
1768 #define DEFAULT_TILE_SIZE 32
1769 #define FLASH_FRAME 0.12F
1770 #define FLASH_TIME (FLASH_FRAME * 3)
1771
1772 static void game_redraw(drawing *dr, game_drawstate *ds,
1773                         const game_state *oldstate, const game_state *state,
1774                         int dir, const game_ui *ui,
1775                         float animtime, float flashtime)
1776 {
1777     int w2 = state->w2, h2 = state->h2;
1778     int s = w2 * h2;
1779     int flash;
1780     int x, y, i;
1781
1782     if (!ds->started) {
1783         /* Main window background */
1784         draw_rect(dr, 0, 0, TILE_SIZE * (w2+1), TILE_SIZE * (h2+1),
1785                   COL_BACKGROUND);
1786         /* Outer edge of grid */
1787         draw_rect(dr, COORD(0)-TILE_SIZE/10, COORD(0)-TILE_SIZE/10,
1788                   TILE_SIZE*w2 + 2*(TILE_SIZE/10) - 1,
1789                   TILE_SIZE*h2 + 2*(TILE_SIZE/10) - 1, COL_GRID);
1790
1791         draw_update(dr, 0, 0, TILE_SIZE * (w2+1), TILE_SIZE * (h2+1));
1792         ds->started = TRUE;
1793     }
1794
1795     flash = 0;
1796     if (flashtime > 0)
1797         flash = (int)(flashtime / FLASH_FRAME) == 1 ? FF_FLASH2 : FF_FLASH1;
1798
1799     for (i = 0; i < s; i++)
1800         ds->gridfs[i] = 0;
1801     unruly_validate_all_rows(state, ds->gridfs);
1802     for (i = 0; i < 2 * (h2 + w2); i++)
1803         ds->rowfs[i] = 0;
1804     unruly_validate_counts(state, NULL, ds->rowfs);
1805
1806     for (y = 0; y < h2; y++) {
1807         for (x = 0; x < w2; x++) {
1808             int tile;
1809
1810             i = y * w2 + x;
1811
1812             tile = ds->gridfs[i];
1813
1814             if (state->grid[i] == N_ONE) {
1815                 tile |= FF_ONE;
1816                 if (ds->rowfs[y] || ds->rowfs[2*h2 + x])
1817                     tile |= FE_COUNT;
1818             } else if (state->grid[i] == N_ZERO) {
1819                 tile |= FF_ZERO;
1820                 if (ds->rowfs[h2 + y] || ds->rowfs[2*h2 + w2 + x])
1821                     tile |= FE_COUNT;
1822             }
1823
1824             tile |= flash;
1825
1826             if (state->immutable[i])
1827                 tile |= FF_IMMUTABLE;
1828
1829             if (ui->cursor && ui->cx == x && ui->cy == y)
1830                 tile |= FF_CURSOR;
1831
1832             if (ds->grid[i] != tile) {
1833                 ds->grid[i] = tile;
1834                 unruly_draw_tile(dr, COORD(x), COORD(y), TILE_SIZE, tile);
1835             }
1836         }
1837     }
1838 }
1839
1840 static float game_anim_length(const game_state *oldstate,
1841                               const game_state *newstate, int dir, game_ui *ui)
1842 {
1843     return 0.0F;
1844 }
1845
1846 static float game_flash_length(const game_state *oldstate,
1847                                const game_state *newstate, int dir, game_ui *ui)
1848 {
1849     if (!oldstate->completed && newstate->completed &&
1850         !oldstate->cheated && !newstate->cheated)
1851         return FLASH_TIME;
1852     return 0.0F;
1853 }
1854
1855 static int game_status(const game_state *state)
1856 {
1857     return state->completed ? +1 : 0;
1858 }
1859
1860 static int game_timing_state(const game_state *state, game_ui *ui)
1861 {
1862     return TRUE;
1863 }
1864
1865 static void game_print_size(const game_params *params, float *x, float *y)
1866 {
1867     int pw, ph;
1868
1869     /* Using 7mm squares */
1870     game_compute_size(params, 700, &pw, &ph);
1871     *x = pw / 100.0F;
1872     *y = ph / 100.0F;
1873 }
1874
1875 static void game_print(drawing *dr, const game_state *state, int tilesize)
1876 {
1877     int w2 = state->w2, h2 = state->h2;
1878     int x, y;
1879
1880     int ink = print_mono_colour(dr, 0);
1881
1882     for (y = 0; y < h2; y++)
1883         for (x = 0; x < w2; x++) {
1884             int tx = x * tilesize + (tilesize / 2);
1885             int ty = y * tilesize + (tilesize / 2);
1886
1887             /* Draw the border */
1888             int coords[8];
1889             coords[0] = tx;
1890             coords[1] = ty - 1;
1891             coords[2] = tx + tilesize;
1892             coords[3] = ty - 1;
1893             coords[4] = tx + tilesize;
1894             coords[5] = ty + tilesize - 1;
1895             coords[6] = tx;
1896             coords[7] = ty + tilesize - 1;
1897             draw_polygon(dr, coords, 4, -1, ink);
1898
1899             if (state->grid[y * w2 + x] == N_ONE)
1900                 draw_rect(dr, tx, ty, tilesize, tilesize, ink);
1901             else if (state->grid[y * w2 + x] == N_ZERO)
1902                 draw_circle(dr, tx + tilesize/2, ty + tilesize/2,
1903                             tilesize/12, ink, ink);
1904         }
1905 }
1906
1907 #ifdef COMBINED
1908 #define thegame unruly
1909 #endif
1910
1911 const struct game thegame = {
1912     "Unruly", "games.unruly", "unruly",
1913     default_params,
1914     game_fetch_preset,
1915     decode_params,
1916     encode_params,
1917     free_params,
1918     dup_params,
1919     TRUE, game_configure, custom_params,
1920     validate_params,
1921     new_game_desc,
1922     validate_desc,
1923     new_game,
1924     dup_game,
1925     free_game,
1926     TRUE, solve_game,
1927     TRUE, game_can_format_as_text_now, game_text_format,
1928     new_ui,
1929     free_ui,
1930     encode_ui,
1931     decode_ui,
1932     game_changed_state,
1933     interpret_move,
1934     execute_move,
1935     DEFAULT_TILE_SIZE, game_compute_size, game_set_size,
1936     game_colours,
1937     game_new_drawstate,
1938     game_free_drawstate,
1939     game_redraw,
1940     game_anim_length,
1941     game_flash_length,
1942     game_status,
1943     TRUE, FALSE, game_print_size, game_print,
1944     FALSE,                      /* wants_statusbar */
1945     FALSE, game_timing_state,
1946     0,                          /* flags */
1947 };
1948
1949 /* ***************** *
1950  * Standalone solver *
1951  * ***************** */
1952
1953 #ifdef STANDALONE_SOLVER
1954 #include <time.h>
1955 #include <stdarg.h>
1956
1957 /* Most of the standalone solver code was copied from unequal.c and singles.c */
1958
1959 const char *quis;
1960
1961 static void usage_exit(const char *msg)
1962 {
1963     if (msg)
1964         fprintf(stderr, "%s: %s\n", quis, msg);
1965     fprintf(stderr,
1966             "Usage: %s [-v] [--seed SEED] <params> | [game_id [game_id ...]]\n",
1967             quis);
1968     exit(1);
1969 }
1970
1971 int main(int argc, char *argv[])
1972 {
1973     random_state *rs;
1974     time_t seed = time(NULL);
1975
1976     game_params *params = NULL;
1977
1978     char *id = NULL, *desc = NULL, *err;
1979
1980     quis = argv[0];
1981
1982     while (--argc > 0) {
1983         char *p = *++argv;
1984         if (!strcmp(p, "--seed")) {
1985             if (argc == 0)
1986                 usage_exit("--seed needs an argument");
1987             seed = (time_t) atoi(*++argv);
1988             argc--;
1989         } else if (!strcmp(p, "-v"))
1990             solver_verbose = TRUE;
1991         else if (*p == '-')
1992             usage_exit("unrecognised option");
1993         else
1994             id = p;
1995     }
1996
1997     if (id) {
1998         desc = strchr(id, ':');
1999         if (desc)
2000             *desc++ = '\0';
2001
2002         params = default_params();
2003         decode_params(params, id);
2004         err = validate_params(params, TRUE);
2005         if (err) {
2006             fprintf(stderr, "Parameters are invalid\n");
2007             fprintf(stderr, "%s: %s", argv[0], err);
2008             exit(1);
2009         }
2010     }
2011
2012     if (!desc) {
2013         char *desc_gen, *aux;
2014         rs = random_new((void *) &seed, sizeof(time_t));
2015         if (!params)
2016             params = default_params();
2017         printf("Generating puzzle with parameters %s\n",
2018                encode_params(params, TRUE));
2019         desc_gen = new_game_desc(params, rs, &aux, FALSE);
2020
2021         if (!solver_verbose) {
2022             char *fmt = game_text_format(new_game(NULL, params, desc_gen));
2023             fputs(fmt, stdout);
2024             sfree(fmt);
2025         }
2026
2027         printf("Game ID: %s\n", desc_gen);
2028     } else {
2029         game_state *input;
2030         struct unruly_scratch *scratch;
2031         int maxdiff, errcode;
2032
2033         err = validate_desc(params, desc);
2034         if (err) {
2035             fprintf(stderr, "Description is invalid\n");
2036             fprintf(stderr, "%s", err);
2037             exit(1);
2038         }
2039
2040         input = new_game(NULL, params, desc);
2041         scratch = unruly_new_scratch(input);
2042
2043         maxdiff = unruly_solve_game(input, scratch, DIFFCOUNT);
2044
2045         errcode = unruly_validate_counts(input, scratch, NULL);
2046         if (unruly_validate_all_rows(input, NULL) == -1)
2047             errcode = -1;
2048
2049         if (errcode != -1) {
2050             char *fmt = game_text_format(input);
2051             fputs(fmt, stdout);
2052             sfree(fmt);
2053             if (maxdiff < 0)
2054                 printf("Difficulty: already solved!\n");
2055             else
2056                 printf("Difficulty: %s\n", unruly_diffnames[maxdiff]);
2057         }
2058
2059         if (errcode == 1)
2060             printf("No solution found.\n");
2061         else if (errcode == -1)
2062             printf("Puzzle is invalid.\n");
2063
2064         free_game(input);
2065         unruly_free_scratch(scratch);
2066     }
2067
2068     return 0;
2069 }
2070 #endif