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