unruly.c

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