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