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