unfinished/group.c

   1 /*
   2  * group.c: a Latin-square puzzle, but played with groups' Cayley
   3  * tables. That is, you are given a Cayley table of a group with
   4  * most elements blank and a few clues, and you must fill it in
   5  * so as to preserve the group axioms.
   6  *
   7  * This is a perfectly playable and fully working puzzle, but I'm
   8  * leaving it for the moment in the 'unfinished' directory because
   9  * it's just too esoteric (not to mention _hard_) for me to be
  10  * comfortable presenting it to the general public as something they
  11  * might (implicitly) actually want to play.
  12  *
  13  * TODO:
  14  *
  15  *  - more solver techniques?
  16  *     * Inverses: once we know that gh = e, we can immediately
  17  *       deduce hg = e as well; then for any gx=y we can deduce
  18  *       hy=x, and for any xg=y we have yh=x.
  19  *     * Hard-mode associativity: we currently deduce based on
  20  *       definite numbers in the grid, but we could also winnow
  21  *       based on _possible_ numbers.
  22  *     * My overambitious original thoughts included wondering if we
  23  *       could infer that there must be elements of certain orders
  24  *       (e.g. a group of order divisible by 5 must contain an
  25  *       element of order 5), but I think in fact this is probably
  26  *       silly.
  27  *
  28  *  - a mode which shuffles the identity element into the mix
  29  *    instead of keeping it clearly shown for you?
  30  *     * shuffle more fully during table generation
  31  *     * start clue removal by clearing the identity row and column
  32  *       completely, or else it'll be totally obvious where it is
  33  *     * have to print the group elements outside the grid
  34  *     * new_ui should start the cursor at 0,0 not 1,1, and cursor
  35  *       should not be constrained to x,y >= 1
  36  *     * get rid of the COL_IDENTITY highlights
  37  *     * will we need more checks in check_errors?
  38  */
  39
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42 #include <string.h>
  43 #include <assert.h>
  44 #include <ctype.h>
  45 #include <math.h>
  46
  47 #include "puzzles.h"
  48 #include "latin.h"
  49
  50 /*
  51  * Difficulty levels. I do some macro ickery here to ensure that my
  52  * enum and the various forms of my name list always match up.
  53  */
  54 #define DIFFLIST(A) \
  55     A(TRIVIAL,Trivial,NULL,t) \
  56     A(NORMAL,Normal,solver_normal,n) \
  57     A(HARD,Hard,NULL,h) \
  58     A(EXTREME,Extreme,NULL,x) \
  59     A(UNREASONABLE,Unreasonable,NULL,u)
  60 #define ENUM(upper,title,func,lower) DIFF_ ## upper,
  61 #define TITLE(upper,title,func,lower) #title,
  62 #define ENCODE(upper,title,func,lower) #lower
  63 #define CONFIG(upper,title,func,lower) ":" #title
  64 enum { DIFFLIST(ENUM) DIFFCOUNT };
  65 static char const *const group_diffnames[] = { DIFFLIST(TITLE) };
  66 static char const group_diffchars[] = DIFFLIST(ENCODE);
  67 #define DIFFCONFIG DIFFLIST(CONFIG)
  68
  69 enum {
  70     COL_BACKGROUND,
  71     COL_IDENTITY,
  72     COL_GRID,
  73     COL_USER,
  74     COL_HIGHLIGHT,
  75     COL_ERROR,
  76     COL_PENCIL,
  77     NCOLOURS
  78 };
  79
  80 #define FROMCHAR(c) ((c)>='0'&&(c)<='9' ? (c)-'0' : \
  81                          (c)>='A'&&(c)<='Z' ? (c)-'A'+10 : (c)-'a'+10)
  82 #define ISCHAR(c) (((c)>='0'&&(c)<='9') || \
  83                        ((c)>='A'&&(c)<='Z') || ((c)>='a'&&(c)<='z'))
  84 #define TOCHAR(c) ((c)>=10 ? (c)-10+'a' : (c)+'0')
  85
  86 struct game_params {
  87     int w, diff;
  88 };
  89
  90 struct game_state {
  91     game_params par;
  92     digit *grid;
  93     unsigned char *immutable;
  94     int *pencil;                       /* bitmaps using bits 1<<1..1<<n */
  95     int completed, cheated;
  96 };
  97
  98 static game_params *default_params(void)
  99 {
 100     game_params *ret = snew(game_params);
 101
 102     ret->w = 6;
 103     ret->diff = DIFF_NORMAL;
 104
 105     return ret;
 106 }
 107
 108 const static struct game_params group_presets[] = {
 109     {  4, DIFF_NORMAL         },
 110     {  6, DIFF_NORMAL         },
 111 };
 112
 113 static int game_fetch_preset(int i, char **name, game_params **params)
 114 {
 115     game_params *ret;
 116     char buf[80];
 117
 118     if (i < 0 || i >= lenof(group_presets))
 119         return FALSE;
 120
 121     ret = snew(game_params);
 122     *ret = group_presets[i]; /* structure copy */
 123
 124     sprintf(buf, "%dx%d %s", ret->w, ret->w, group_diffnames[ret->diff]);
 125
 126     *name = dupstr(buf);
 127     *params = ret;
 128     return TRUE;
 129 }
 130
 131 static void free_params(game_params *params)
 132 {
 133     sfree(params);
 134 }
 135
 136 static game_params *dup_params(game_params *params)
 137 {
 138     game_params *ret = snew(game_params);
 139     *ret = *params;                    /* structure copy */
 140     return ret;
 141 }
 142
 143 static void decode_params(game_params *params, char const *string)
 144 {
 145     char const *p = string;
 146
 147     params->w = atoi(p);
 148     while (*p && isdigit((unsigned char)*p)) p++;
 149
 150     if (*p == 'd') {
 151         int i;
 152         p++;
 153         params->diff = DIFFCOUNT+1; /* ...which is invalid */
 154         if (*p) {
 155             for (i = 0; i < DIFFCOUNT; i++) {
 156                 if (*p == group_diffchars[i])
 157                     params->diff = i;
 158             }
 159             p++;
 160         }
 161     }
 162 }
 163
 164 static char *encode_params(game_params *params, int full)
 165 {
 166     char ret[80];
 167
 168     sprintf(ret, "%d", params->w);
 169     if (full)
 170         sprintf(ret + strlen(ret), "d%c", group_diffchars[params->diff]);
 171
 172     return dupstr(ret);
 173 }
 174
 175 static config_item *game_configure(game_params *params)
 176 {
 177     config_item *ret;
 178     char buf[80];
 179
 180     ret = snewn(3, config_item);
 181
 182     ret[0].name = "Grid size";
 183     ret[0].type = C_STRING;
 184     sprintf(buf, "%d", params->w);
 185     ret[0].sval = dupstr(buf);
 186     ret[0].ival = 0;
 187
 188     ret[1].name = "Difficulty";
 189     ret[1].type = C_CHOICES;
 190     ret[1].sval = DIFFCONFIG;
 191     ret[1].ival = params->diff;
 192
 193     ret[2].name = NULL;
 194     ret[2].type = C_END;
 195     ret[2].sval = NULL;
 196     ret[2].ival = 0;
 197
 198     return ret;
 199 }
 200
 201 static game_params *custom_params(config_item *cfg)
 202 {
 203     game_params *ret = snew(game_params);
 204
 205     ret->w = atoi(cfg[0].sval);
 206     ret->diff = cfg[1].ival;
 207
 208     return ret;
 209 }
 210
 211 static char *validate_params(game_params *params, int full)
 212 {
 213     if (params->w < 3 || params->w > 31)
 214         return "Grid size must be between 3 and 31";
 215     if (params->diff >= DIFFCOUNT)
 216         return "Unknown difficulty rating";
 217     return NULL;
 218 }
 219
 220 /* ----------------------------------------------------------------------
 221  * Solver.
 222  */
 223
 224 static int solver_normal(struct latin_solver *solver, void *vctx)
 225 {
 226     int w = solver->o;
 227     digit *grid = solver->grid;
 228     int i, j, k;
 229
 230     /*
 231      * Deduce using associativity: (ab)c = a(bc).
 232      *
 233      * So we pick any a,b,c we like; then if we know ab, bc, and
 234      * (ab)c we can fill in a(bc).
 235      */
 236     for (i = 1; i < w; i++)
 237         for (j = 1; j < w; j++)
 238             for (k = 1; k < w; k++) {
 239                 if (!grid[i*w+j] || !grid[j*w+k])
 240                     continue;
 241                 if (grid[(grid[i*w+j]-1)*w+k] &&
 242                     !grid[i*w+(grid[j*w+k]-1)]) {
 243                     int x = grid[j*w+k]-1, y = i;
 244                     int n = grid[(grid[i*w+j]-1)*w+k];
 245 #ifdef STANDALONE_SOLVER
 246                     if (solver_show_working) {
 247                         printf("%*sassociativity on %d,%d,%d: %d*%d = %d*%d\n",
 248                                solver_recurse_depth*4, "",
 249                                i+1, j+1, k+1,
 250                                grid[i*w+j], k+1, i+1, grid[j*w+k]);
 251                         printf("%*s  placing %d at (%d,%d)\n",
 252                                solver_recurse_depth*4, "",
 253                                n, x+1, y+1);
 254                     }
 255 #endif
 256                     if (solver->cube[(x*w+y)*w+n-1]) {
 257                         latin_solver_place(solver, x, y, n);
 258                         return 1;
 259                     } else {
 260 #ifdef STANDALONE_SOLVER
 261                         if (solver_show_working)
 262                             printf("%*s  contradiction!\n",
 263                                    solver_recurse_depth*4, "");
 264                         return -1;
 265 #endif
 266                     }
 267                 }
 268                 if (!grid[(grid[i*w+j]-1)*w+k] &&
 269                     grid[i*w+(grid[j*w+k]-1)]) {
 270                     int x = k, y = grid[i*w+j]-1;
 271                     int n = grid[i*w+(grid[j*w+k]-1)];
 272 #ifdef STANDALONE_SOLVER
 273                     if (solver_show_working) {
 274                         printf("%*sassociativity on %d,%d,%d: %d*%d = %d*%d\n",
 275                                solver_recurse_depth*4, "",
 276                                i+1, j+1, k+1,
 277                                grid[i*w+j], k+1, i+1, grid[j*w+k]);
 278                         printf("%*s  placing %d at (%d,%d)\n",
 279                                solver_recurse_depth*4, "",
 280                                n, x+1, y+1);
 281                     }
 282 #endif
 283                     if (solver->cube[(x*w+y)*w+n-1]) {
 284                         latin_solver_place(solver, x, y, n);
 285                         return 1;
 286                     } else {
 287 #ifdef STANDALONE_SOLVER
 288                         if (solver_show_working)
 289                             printf("%*s  contradiction!\n",
 290                                    solver_recurse_depth*4, "");
 291                         return -1;
 292 #endif
 293                     }
 294                 }
 295             }
 296
 297     return 0;
 298 }
 299
 300 #define SOLVER(upper,title,func,lower) func,
 301 static usersolver_t const group_solvers[] = { DIFFLIST(SOLVER) };
 302
 303 static int solver(int w, digit *grid, int maxdiff)
 304 {
 305     int ret;
 306
 307     ret = latin_solver(grid, w, maxdiff,
 308                        DIFF_TRIVIAL, DIFF_HARD, DIFF_EXTREME,
 309                        DIFF_EXTREME, DIFF_UNREASONABLE,
 310                        group_solvers, NULL, NULL, NULL);
 311
 312     return ret;
 313 }
 314
 315 /* ----------------------------------------------------------------------
 316  * Grid generation.
 317  */
 318
 319 static char *encode_grid(char *desc, digit *grid, int area)
 320 {
 321     int run, i;
 322     char *p = desc;
 323
 324     run = 0;
 325     for (i = 0; i <= area; i++) {
 326         int n = (i < area ? grid[i] : -1);
 327
 328         if (!n)
 329             run++;
 330         else {
 331             if (run) {
 332                 while (run > 0) {
 333                     int c = 'a' - 1 + run;
 334                     if (run > 26)
 335                         c = 'z';
 336                     *p++ = c;
 337                     run -= c - ('a' - 1);
 338                 }
 339             } else {
 340                 /*
 341                  * If there's a number in the very top left or
 342                  * bottom right, there's no point putting an
 343                  * unnecessary _ before or after it.
 344                  */
 345                 if (p > desc && n > 0)
 346                     *p++ = '_';
 347             }
 348             if (n > 0)
 349                 p += sprintf(p, "%d", n);
 350             run = 0;
 351         }
 352     }
 353     return p;
 354 }
 355
 356 /* ----- data generated by group.gap begins ----- */
 357
 358 struct group {
 359     unsigned long autosize;
 360     int order, ngens;
 361     const char *gens;
 362 };
 363 struct groups {
 364     int ngroups;
 365     const struct group *groups;
 366 };
 367
 368 static const struct group groupdata[] = {
 369     /* order 2 */
 370     {1L, 2, 1, "21"},
 371     /* order 3 */
 372     {2L, 3, 1, "231"},
 373     /* order 4 */
 374     {2L, 4, 1, "2341"},
 375     {6L, 4, 2, "2143" "3412"},
 376     /* order 5 */
 377     {4L, 5, 1, "23451"},
 378     /* order 6 */
 379     {6L, 6, 2, "365214" "214365"},
 380     {2L, 6, 1, "436521"},
 381     /* order 7 */
 382     {6L, 7, 1, "2345671"},
 383     /* order 8 */
 384     {4L, 8, 1, "23564781"},
 385     {8L, 8, 2, "24567183" "57284361"},
 386     {8L, 8, 2, "57284361" "21563487"},
 387     {24L, 8, 2, "24567183" "38472516"},
 388     {168L, 8, 3, "21563487" "35172846" "46718235"},
 389     /* order 9 */
 390     {6L, 9, 1, "245378691"},
 391     {48L, 9, 2, "245178396" "356781924"},
 392     /* order 10 */
 393     {20L, 10, 2, "3A52749618" "21436587A9"},
 394     {4L, 10, 1, "436587A921"},
 395     /* order 11 */
 396     {10L, 11, 1, "23456789AB1"},
 397     /* order 12 */
 398     {12L, 12, 2, "7C4BA5832916" "2356179A4BC8"},
 399     {4L, 12, 1, "589AB32C4761"},
 400     {24L, 12, 2, "256719AB34C8" "6A2B8C574391"},
 401     {12L, 12, 2, "7C4BA5832916" "2156349A78CB"},
 402     {12L, 12, 2, "649A78C2B153" "794B6C83A512"},
 403     /* order 13 */
 404     {12L, 13, 1, "23456789ABCD1"},
 405     /* order 14 */
 406     {42L, 14, 2, "5C7E92B4D6183A" "21436587A9CBED"},
 407     {6L, 14, 1, "6587A9CBED2143"},
 408     /* order 15 */
 409     {8L, 15, 1, "5783AB6DE9F2C41"},
 410     /* order 16 */
 411     {8L, 16, 1, "DBEG6F1427C3958A"},
 412     {96L, 16, 2, "9CB3FE6G54A87D12" "2467891BCDE3F5GA"},
 413     {32L, 16, 2, "D98G643FE2C1BA75" "25678AB1CDEF34G9"},
 414     {32L, 16, 2, "9613F7CD45A2EGB8" "25678AB1CDEF34G9"},
 415     {16L, 16, 2, "DF8G6B39E2C14A75" "2467895BCDEAF1G3"},
 416     {16L, 16, 2, "D98G64AFE2C5B371" "2467895BCDEAF1G3"},
 417     {32L, 16, 2, "DF8G6439E2C5BA71" "21678345CDE9ABGF"},
 418     {16L, 16, 2, "D98G6BAFE2C14375" "74G8EF5B6C2391DA"},
 419     {32L, 16, 2, "D92G64AF78C5B3E1" "3C59A7DGB1F8E642"},
 420     {192L, 16, 3,
 421      "D38G619AE2C45F7B" "25678AB1CDEF34G9" "7BC2EF546G8A91D3"},
 422     {64L, 16, 3, "D38G619AE2C45F7B" "CF76GBA92ED54381" "3D19A8G645FE2CB7"},
 423     {192L, 16, 3,
 424      "9GB3F7DC54A2E618" "25678AB1CDEF34G9" "3D59A2G6B1F78C4E"},
 425     {48L, 16, 3, "9G4AFE6C5B327D18" "6A2CD5F378GB19E4" "4795BC8EAF1DG236"},
 426     {20160L, 16, 4,
 427      "58AB1DE2F34G679C" "21678345CDE9ABGF" "3619A2CD45F78GBE"
 428      "4791BC2E3F56G8AD"},
 429     /* order 17 */
 430     {16L, 17, 1, "56789ABCDEFGH1234"},
 431     /* order 18 */
 432     {54L, 18, 2, "DB9HFGE17CI5342A86" "215634ABC789FGDEIH"},
 433     {6L, 18, 1, "53AB786FG4DECI9H21"},
 434     {12L, 18, 2, "53AB782FG1DE6I4HC9" "BEFGH36I5978CA1D24"},
 435     {432L, 18, 3,
 436      "96E1BCH34FG278I5DA" "EFH36I978BCA1DG245" "215634ABC789FGDEIH"},
 437     {48L, 18, 2, "53AB782FG1DE6I4HC9" "64BC89FG2DE1I5H3A7"},
 438     /* order 19 */
 439     {18L, 19, 1, "56789ABCDEFGHIJ1234"},
 440     /* order 20 */
 441     {40L, 20, 2, "7K4BI58F29CJ6DG3AH1E" "5129346D78AHBCEKFGIJ"},
 442     {8L, 20, 1, "589AC3DEG7HIJB2K4F61"},
 443     {20L, 20, 2, "4AJ8HE3CKI7G52B196FD" "5129346D78AHBCEKFGIJ"},
 444     {40L, 20, 2, "7K4BI58F29CJ6DG3AH1E" "5329176D4BAH8FEKCJIG"},
 445     {24L, 20, 2, "976D4BAH8FEKCJI5G321" "649A78DEBCHIFGK2J153"},
 446     /* order 21 */
 447     {42L, 21, 2, "9KCJ2FL5I4817B3AE6DHG" "5A8CDBFGEIJH1LK342679"},
 448     {12L, 21, 1, "5783AB6DE9GHCJKFL2I41"},
 449     /* order 22 */
 450     {110L, 22, 2, "5K7M92B4D6F8HAJCLE1G3I" "21436587A9CBEDGFIHKJML"},
 451     {10L, 22, 1, "6587A9CBEDGFIHKJML2143"},
 452     /* order 23 */
 453     {22L, 23, 1, "56789ABCDEFGHIJKLMN1234"},
 454     /* order 24 */
 455     {24L, 24, 2, "HO5ANGLDBCI9M26KJ1378E4F" "8IEFGJN3KLM2C49AO671BHD5"},
 456     {8L, 24, 1, "DH2KL4IN678OA5C9EFGBJ1M3"},
 457     {24L, 24, 2, "9FHI25LM6N78BC1ODEGJ34KA" "EAOFM74BJDK69GH5C3LI2N18"},
 458     {48L, 24, 2, "HL5ANMO6BCI9G7DEJ132FK48" "8JEFGNC4KLM2I91BO673H5DA"},
 459     {24L, 24, 2, "HO5ANGLDBCI9M26KJ1378E4F" "KN8EOCI9FGLDJ13HM2645A7B"},
 460     {48L, 24, 2, "HL5ANMO6BCI9G7DEJ132FK48" "21678345DEFG9ABCKLMHIJON"},
 461     {48L, 24, 3,
 462      "HOBANMLD5JI9G76KC432FE18" "AL5HIGO6BCN3M2DEJ1978K4F"
 463      "8JEFGNC4KLM2I91BO673H5DA"},
 464     {24L, 24, 3,
 465      "HLBANGO65JI9M2DEC4378K1F" "AO5HIMLDBCN3G76KJ192FE48"
 466      "KIFEOCN38MLDJ19AG7645H2B"},
 467     {16L, 24, 2, "DI7KLCN9FG6OJ4AH2ME5B381" "MBO8FH1JEKG23N45L679ACDI"},
 468     {16L, 24, 2, "DI7KLCN9FG6OJ4AH2ME5B381" "IDCN97KLJ4AHFG6O5B32ME18"},
 469     {48L, 24, 2, "9LCHI7ODJ43NFGEK5BA2M618" "7CDFGIJ4KL2MN95B6O8AH1E3"},
 470     {24L, 24, 2, "LAGODI3JE87KCN9B6M254HF1" "EIL6MCN9GODFA54H87K3J12B"},
 471     {24L, 24, 2, "D92KL1HI678O345NEFGABCMJ" "FBOM6NJ37LKE4IHA2GD1C985"},
 472     {144L, 24, 3,
 473      "HOBANMLD5JI9G76KC432FE18" "AL5HIGO6BCN3M2DEJ1978K4F"
 474      "21678345DEFG9ABCKLMHIJON"},
 475     {336L, 24, 3,
 476      "HKBANFEO5JI98MLDC43G7612" "AE5HI8KLBCN3FGO6J19M2D47"
 477      "85EFGABCKLM2HIJ1O67N34D9"},
 478     /* order 25 */
 479     {20L, 25, 1, "589CDEGHIJ6KLM2ANO4FP71B3"},
 480     {480L, 25, 2, "589CDEGHIJ3KLM26NO4AP7FB1" "245789BCDE1GHIJ3KLM6NOAPF"},
 481     /* order 26 */
 482     {156L, 26, 2,
 483      "5O7Q92B4D6F8HAJCLENGPI1K3M" "21436587A9CBEDGFIHKJMLONQP"},
 484     {12L, 26, 1, "6587A9CBEDGFIHKJMLONQP2143"},
 485     /* order 27 */
 486     {18L, 27, 1, "53BC689IJKDE4GHOP7LMANRFQ12"},
 487     {108L, 27, 2,
 488      "54BC79AIJKEFGH1OPLM2N3RQ68D" "DI2LG5O67Q4NBCREF9A8JKMH1P3"},
 489     {432L, 27, 2,
 490      "51BC234IJK6789AOPDEFGHRLMNQ" "3E89PLM1GHRB7Q64NKIJFDA5O2C"},
 491     {54L, 27, 2,
 492      "54BC79AIJKEFGH1OPLM2N3RQ68D" "DR2LNKI67QA8P5OEFH1GBCM34J9"},
 493     {11232L, 27, 3,
 494      "51BC234IJK6789AOPDEFGHRLMNQ" "3689BDE1GHIJ2LM4N5OP7QACRFK"
 495      "479ACEFGH1JKLM2N3OP5Q68RBDI"},
 496     /* order 28 */
 497     {84L, 28, 2,
 498      "7S4BQ58F29CJ6DGNAHKRELO3IP1M" "5129346D78AHBCELFGIPJKMSNOQR"},
 499     {12L, 28, 1, "589AC3DEG7HIKBLMOFPQRJ2S4N61"},
 500     {84L, 28, 2,
 501      "7S4BQ58F29CJ6DGNAHKRELO3IP1M" "5329176D4BAH8FELCJIPGNMSKRQO"},
 502     {36L, 28, 2,
 503      "976D4BAH8FELCJIPGNMSKRQ5O321" "649A78DEBCHIFGLMJKPQNOS2R153"},
 504     /* order 29 */
 505     {28L, 29, 1, "56789ABCDEFGHIJKLMNOPQRST1234"},
 506     /* order 30 */
 507     {24L, 30, 2,
 508      "LHQ7NOTDERSA9JK6UGF1PBCM34I285" "BFHIL3NO5Q78RSATDE6UG9JKCM1P24"},
 509     {40L, 30, 2,
 510      "DU4JOA89PS2GEFT56MKL7BCRQ1HI3N" "BQGHT36MNL78CRS1DEIU54JKOA9P2F"},
 511     {120L, 30, 2,
 512      "DS4JU589POABEFT2GHKL76MNQ1CR3I" "215634ABC789GHIDEFMNOJKLRSPQUT"},
 513     {8L, 30, 1, "HEMNJKCRS9PQIU5FT3OABL782G1D64"},
 514     /* order 31 */
 515     {30L, 31, 1, "56789ABCDEFGHIJKLMNOPQRSTUV1234"},
 516 };
 517
 518 static const struct groups groups[] = {
 519     {0, NULL},                  /* trivial case: 0 */
 520     {0, NULL},                  /* trivial case: 1 */
 521     {1, groupdata + 0},         /* 2 */
 522     {1, groupdata + 1},         /* 3 */
 523     {2, groupdata + 2},         /* 4 */
 524     {1, groupdata + 4},         /* 5 */
 525     {2, groupdata + 5},         /* 6 */
 526     {1, groupdata + 7},         /* 7 */
 527     {5, groupdata + 8},         /* 8 */
 528     {2, groupdata + 13},        /* 9 */
 529     {2, groupdata + 15},        /* 10 */
 530     {1, groupdata + 17},        /* 11 */
 531     {5, groupdata + 18},        /* 12 */
 532     {1, groupdata + 23},        /* 13 */
 533     {2, groupdata + 24},        /* 14 */
 534     {1, groupdata + 26},        /* 15 */
 535     {14, groupdata + 27},       /* 16 */
 536     {1, groupdata + 41},        /* 17 */
 537     {5, groupdata + 42},        /* 18 */
 538     {1, groupdata + 47},        /* 19 */
 539     {5, groupdata + 48},        /* 20 */
 540     {2, groupdata + 53},        /* 21 */
 541     {2, groupdata + 55},        /* 22 */
 542     {1, groupdata + 57},        /* 23 */
 543     {15, groupdata + 58},       /* 24 */
 544     {2, groupdata + 73},        /* 25 */
 545     {2, groupdata + 75},        /* 26 */
 546     {5, groupdata + 77},        /* 27 */
 547     {4, groupdata + 82},        /* 28 */
 548     {1, groupdata + 86},        /* 29 */
 549     {4, groupdata + 87},        /* 30 */
 550     {1, groupdata + 91},        /* 31 */
 551 };
 552
 553 /* ----- data generated by group.gap ends ----- */
 554
 555 static char *new_game_desc(game_params *params, random_state *rs,
 556                            char **aux, int interactive)
 557 {
 558     int w = params->w, a = w*w;
 559     digit *grid, *soln, *soln2;
 560     int *indices;
 561     int i, j, k, qh, qt;
 562     int diff = params->diff;
 563     const struct group *group;
 564     char *desc, *p;
 565
 566     /*
 567      * Difficulty exceptions: some combinations of size and
 568      * difficulty cannot be satisfied, because all puzzles of at
 569      * most that difficulty are actually even easier.
 570      *
 571      * Remember to re-test this whenever a change is made to the
 572      * solver logic!
 573      *
 574      * I tested it using the following shell command:
 575
 576 for d in t n h x u; do
 577   for i in {3..9}; do
 578     echo ./group --generate 1 ${i}d${d}
 579     perl -e 'alarm 30; exec @ARGV' ./group --generate 5 ${i}d${d} >/dev/null \
 580       || echo broken
 581   done
 582 done
 583
 584      * Of course, it's better to do that after taking the exceptions
 585      * _out_, so as to detect exceptions that should be removed as
 586      * well as those which should be added.
 587      */
 588     if (w <= 9 && diff == DIFF_EXTREME)
 589         diff--;
 590     if (w <= 6 && diff == DIFF_HARD)
 591         diff--;
 592     if (w <= 4 && diff > DIFF_TRIVIAL)
 593         diff = DIFF_TRIVIAL;
 594
 595     grid = snewn(a, digit);
 596     soln = snewn(a, digit);
 597     soln2 = snewn(a, digit);
 598     indices = snewn(a, int);
 599
 600     while (1) {
 601         /*
 602          * Construct a valid group table, by picking a group from
 603          * the above data table, decompressing it into a full
 604          * representation by BFS, and then randomly permuting its
 605          * non-identity elements.
 606          *
 607          * We build the canonical table in 'soln' (and use 'grid' as
 608          * our BFS queue), then transfer the table into 'grid'
 609          * having shuffled the rows.
 610          */
 611         assert(w >= 2);
 612         assert(w < lenof(groups));
 613         group = groups[w].groups + random_upto(rs, groups[w].ngroups);
 614         assert(group->order == w);
 615         memset(soln, 0, a);
 616         for (i = 0; i < w; i++)
 617             soln[i] = i+1;
 618         qh = qt = 0;
 619         grid[qt++] = 1;
 620         while (qh < qt) {
 621             digit *row, *newrow;
 622
 623             i = grid[qh++];
 624             row = soln + (i-1)*w;
 625
 626             for (j = 0; j < group->ngens; j++) {
 627                 int nri;
 628                 const char *gen = group->gens + j*w;
 629
 630                 /*
 631                  * Apply each group generator to row, constructing a
 632                  * new row.
 633                  */
 634                 nri = FROMCHAR(gen[row[0]-1]);   /* which row is it? */
 635                 newrow = soln + (nri-1)*w;
 636                 if (!newrow[0]) {   /* not done yet */
 637                     for (k = 0; k < w; k++)
 638                         newrow[k] = FROMCHAR(gen[row[k]-1]);
 639                     grid[qt++] = nri;
 640                 }
 641             }
 642         }
 643         /* That's got the canonical table. Now shuffle it. */
 644         for (i = 0; i < w; i++)
 645             grid[i] = i+1;
 646         shuffle(grid+1, w-1, sizeof(*grid), rs);
 647         for (i = 1; i < w; i++)
 648             for (j = 0; j < w; j++)
 649                 grid[(grid[i]-1)*w+(grid[j]-1)] = grid[soln[i*w+j]-1];
 650         for (i = 0; i < w; i++)
 651             grid[i] = i+1;
 652
 653         /*
 654          * Remove entries one by one while the puzzle is still
 655          * soluble at the appropriate difficulty level.
 656          */
 657         memcpy(soln, grid, a);
 658
 659         k = 0;
 660         for (i = 1; i < w; i++)
 661             for (j = 1; j < w; j++)
 662                 indices[k++] = i*w+j;
 663         shuffle(indices, k, sizeof(indices), rs);
 664
 665         for (i = 0; i < k; i++) {
 666             memcpy(soln2, grid, a);
 667             soln2[indices[i]] = 0;
 668             if (solver(w, soln2, diff) <= diff)
 669                 grid[indices[i]] = 0;
 670         }
 671
 672         /*
 673          * Make sure the puzzle isn't too easy.
 674          */
 675         if (diff > 0) {
 676             memcpy(soln2, grid, a);
 677             if (solver(w, soln2, diff-1) < diff)
 678                 continue;              /* go round and try again */
 679         }
 680
 681         /*
 682          * Done.
 683          */
 684         break;
 685     }
 686
 687     /*
 688      * Encode the puzzle description.
 689      */
 690     desc = snewn(a*20, char);
 691     p = encode_grid(desc, grid, a);
 692     *p++ = '\0';
 693     desc = sresize(desc, p - desc, char);
 694
 695     /*
 696      * Encode the solution.
 697      */
 698     *aux = snewn(a+2, char);
 699     (*aux)[0] = 'S';
 700     for (i = 0; i < a; i++)
 701         (*aux)[i+1] = TOCHAR(soln[i]);
 702     (*aux)[a+1] = '\0';
 703
 704     sfree(grid);
 705     sfree(soln);
 706     sfree(soln2);
 707     sfree(indices);
 708
 709     return desc;
 710 }
 711
 712 /* ----------------------------------------------------------------------
 713  * Gameplay.
 714  */
 715
 716 static char *validate_grid_desc(const char **pdesc, int range, int area)
 717 {
 718     const char *desc = *pdesc;
 719     int squares = 0;
 720     while (*desc && *desc != ',') {
 721         int n = *desc++;
 722         if (n >= 'a' && n <= 'z') {
 723             squares += n - 'a' + 1;
 724         } else if (n == '_') {
 725             /* do nothing */;
 726         } else if (n > '0' && n <= '9') {
 727             int val = atoi(desc-1);
 728             if (val < 1 || val > range)
 729                 return "Out-of-range number in game description";
 730             squares++;
 731             while (*desc >= '0' && *desc <= '9')
 732                 desc++;
 733         } else
 734             return "Invalid character in game description";
 735     }
 736
 737     if (squares < area)
 738         return "Not enough data to fill grid";
 739
 740     if (squares > area)
 741         return "Too much data to fit in grid";
 742     *pdesc = desc;
 743     return NULL;
 744 }
 745
 746 static char *validate_desc(game_params *params, char *desc)
 747 {
 748     int w = params->w, a = w*w;
 749     const char *p = desc;
 750
 751     return validate_grid_desc(&p, w, a);
 752 }
 753
 754 static char *spec_to_grid(char *desc, digit *grid, int area)
 755 {
 756     int i = 0;
 757     while (*desc && *desc != ',') {
 758         int n = *desc++;
 759         if (n >= 'a' && n <= 'z') {
 760             int run = n - 'a' + 1;
 761             assert(i + run <= area);
 762             while (run-- > 0)
 763                 grid[i++] = 0;
 764         } else if (n == '_') {
 765             /* do nothing */;
 766         } else if (n > '0' && n <= '9') {
 767             assert(i < area);
 768             grid[i++] = atoi(desc-1);
 769             while (*desc >= '0' && *desc <= '9')
 770                 desc++;
 771         } else {
 772             assert(!"We can't get here");
 773         }
 774     }
 775     assert(i == area);
 776     return desc;
 777 }
 778
 779 static game_state *new_game(midend *me, game_params *params, char *desc)
 780 {
 781     int w = params->w, a = w*w;
 782     game_state *state = snew(game_state);
 783     int i;
 784
 785     state->par = *params;              /* structure copy */
 786     state->grid = snewn(a, digit);
 787     state->immutable = snewn(a, unsigned char);
 788     state->pencil = snewn(a, int);
 789     for (i = 0; i < a; i++) {
 790         state->grid[i] = 0;
 791         state->immutable[i] = 0;
 792         state->pencil[i] = 0;
 793     }
 794
 795     desc = spec_to_grid(desc, state->grid, a);
 796     for (i = 0; i < a; i++)
 797         if (state->grid[i] != 0)
 798             state->immutable[i] = TRUE;
 799
 800     state->completed = state->cheated = FALSE;
 801
 802     return state;
 803 }
 804
 805 static game_state *dup_game(game_state *state)
 806 {
 807     int w = state->par.w, a = w*w;
 808     game_state *ret = snew(game_state);
 809
 810     ret->par = state->par;             /* structure copy */
 811
 812     ret->grid = snewn(a, digit);
 813     ret->immutable = snewn(a, unsigned char);
 814     ret->pencil = snewn(a, int);
 815     memcpy(ret->grid, state->grid, a*sizeof(digit));
 816     memcpy(ret->immutable, state->immutable, a*sizeof(unsigned char));
 817     memcpy(ret->pencil, state->pencil, a*sizeof(int));
 818
 819     ret->completed = state->completed;
 820     ret->cheated = state->cheated;
 821
 822     return ret;
 823 }
 824
 825 static void free_game(game_state *state)
 826 {
 827     sfree(state->grid);
 828     sfree(state->immutable);
 829     sfree(state->pencil);
 830     sfree(state);
 831 }
 832
 833 static char *solve_game(game_state *state, game_state *currstate,
 834                         char *aux, char **error)
 835 {
 836     int w = state->par.w, a = w*w;
 837     int i, ret;
 838     digit *soln;
 839     char *out;
 840
 841     if (aux)
 842         return dupstr(aux);
 843
 844     soln = snewn(a, digit);
 845     memcpy(soln, state->grid, a*sizeof(digit));
 846
 847     ret = solver(w, soln, DIFFCOUNT-1);
 848
 849     if (ret == diff_impossible) {
 850         *error = "No solution exists for this puzzle";
 851         out = NULL;
 852     } else if (ret == diff_ambiguous) {
 853         *error = "Multiple solutions exist for this puzzle";
 854         out = NULL;
 855     } else {
 856         out = snewn(a+2, char);
 857         out[0] = 'S';
 858         for (i = 0; i < a; i++)
 859             out[i+1] = TOCHAR(soln[i]);
 860         out[a+1] = '\0';
 861     }
 862
 863     sfree(soln);
 864     return out;
 865 }
 866
 867 static int game_can_format_as_text_now(game_params *params)
 868 {
 869     return TRUE;
 870 }
 871
 872 static char *game_text_format(game_state *state)
 873 {
 874     int w = state->par.w;
 875     int x, y;
 876     char *ret, *p, ch;
 877
 878     ret = snewn(2*w*w+1, char);        /* leave room for terminating NUL */
 879
 880     p = ret;
 881     for (y = 0; y < w; y++) {
 882         for (x = 0; x < w; x++) {
 883             digit d = state->grid[y*w+x];
 884
 885             if (d == 0) {
 886                 ch = '.';
 887             } else {
 888                 ch = TOCHAR(d);
 889             }
 890
 891             *p++ = ch;
 892             if (x == w-1) {
 893                 *p++ = '\n';
 894             } else {
 895                 *p++ = ' ';
 896             }
 897         }
 898     }
 899
 900     assert(p - ret == 2*w*w);
 901     *p = '\0';
 902     return ret;
 903 }
 904
 905 struct game_ui {
 906     /*
 907      * These are the coordinates of the currently highlighted
 908      * square on the grid, if hshow = 1.
 909      */
 910     int hx, hy;
 911     /*
 912      * This indicates whether the current highlight is a
 913      * pencil-mark one or a real one.
 914      */
 915     int hpencil;
 916     /*
 917      * This indicates whether or not we're showing the highlight
 918      * (used to be hx = hy = -1); important so that when we're
 919      * using the cursor keys it doesn't keep coming back at a
 920      * fixed position. When hshow = 1, pressing a valid number
 921      * or letter key or Space will enter that number or letter in the grid.
 922      */
 923     int hshow;
 924     /*
 925      * This indicates whether we're using the highlight as a cursor;
 926      * it means that it doesn't vanish on a keypress, and that it is
 927      * allowed on immutable squares.
 928      */
 929     int hcursor;
 930 };
 931
 932 static game_ui *new_ui(game_state *state)
 933 {
 934     game_ui *ui = snew(game_ui);
 935
 936     ui->hx = ui->hy = 1;
 937     ui->hpencil = ui->hshow = ui->hcursor = 0;
 938
 939     return ui;
 940 }
 941
 942 static void free_ui(game_ui *ui)
 943 {
 944     sfree(ui);
 945 }
 946
 947 static char *encode_ui(game_ui *ui)
 948 {
 949     return NULL;
 950 }
 951
 952 static void decode_ui(game_ui *ui, char *encoding)
 953 {
 954 }
 955
 956 static void game_changed_state(game_ui *ui, game_state *oldstate,
 957                                game_state *newstate)
 958 {
 959     int w = newstate->par.w;
 960     /*
 961      * We prevent pencil-mode highlighting of a filled square, unless
 962      * we're using the cursor keys. So if the user has just filled in
 963      * a square which we had a pencil-mode highlight in (by Undo, or
 964      * by Redo, or by Solve), then we cancel the highlight.
 965      */
 966     if (ui->hshow && ui->hpencil && !ui->hcursor &&
 967         newstate->grid[ui->hy * w + ui->hx] != 0) {
 968         ui->hshow = 0;
 969     }
 970 }
 971
 972 #define PREFERRED_TILESIZE 48
 973 #define TILESIZE (ds->tilesize)
 974 #define BORDER (TILESIZE / 2)
 975 #define GRIDEXTRA max((TILESIZE / 32),1)
 976 #define COORD(x) ((x)*TILESIZE + BORDER)
 977 #define FROMCOORD(x) (((x)+(TILESIZE-BORDER)) / TILESIZE - 1)
 978
 979 #define FLASH_TIME 0.4F
 980
 981 #define DF_HIGHLIGHT 0x0400
 982 #define DF_HIGHLIGHT_PENCIL 0x0200
 983 #define DF_IMMUTABLE 0x0100
 984 #define DF_DIGIT_MASK 0x001F
 985
 986 #define EF_DIGIT_SHIFT 5
 987 #define EF_DIGIT_MASK ((1 << EF_DIGIT_SHIFT) - 1)
 988 #define EF_LEFT_SHIFT 0
 989 #define EF_RIGHT_SHIFT (3*EF_DIGIT_SHIFT)
 990 #define EF_LEFT_MASK ((1UL << (3*EF_DIGIT_SHIFT)) - 1UL)
 991 #define EF_RIGHT_MASK (EF_LEFT_MASK << EF_RIGHT_SHIFT)
 992 #define EF_LATIN (1UL << (6*EF_DIGIT_SHIFT))
 993
 994 struct game_drawstate {
 995     int w, tilesize;
 996     int started;
 997     long *tiles, *pencil, *errors;
 998     long *errtmp;
 999 };
1000
1001 static int check_errors(game_state *state, long *errors)
1002 {
1003     int w = state->par.w, a = w*w;
1004     digit *grid = state->grid;
1005     int i, j, k, x, y, errs = FALSE;
1006
1007     if (errors)
1008         for (i = 0; i < a; i++)
1009             errors[i] = 0;
1010
1011     for (y = 0; y < w; y++) {
1012         unsigned long mask = 0, errmask = 0;
1013         for (x = 0; x < w; x++) {
1014             unsigned long bit = 1UL << grid[y*w+x];
1015             errmask |= (mask & bit);
1016             mask |= bit;
1017         }
1018
1019         if (mask != (1 << (w+1)) - (1 << 1)) {
1020             errs = TRUE;
1021             errmask &= ~1UL;
1022             if (errors) {
1023                 for (x = 0; x < w; x++)
1024                     if (errmask & (1UL << grid[y*w+x]))
1025                         errors[y*w+x] |= EF_LATIN;
1026             }
1027         }
1028     }
1029
1030     for (x = 0; x < w; x++) {
1031         unsigned long mask = 0, errmask = 0;
1032         for (y = 0; y < w; y++) {
1033             unsigned long bit = 1UL << grid[y*w+x];
1034             errmask |= (mask & bit);
1035             mask |= bit;
1036         }
1037
1038         if (mask != (1 << (w+1)) - (1 << 1)) {
1039             errs = TRUE;
1040             errmask &= ~1UL;
1041             if (errors) {
1042                 for (y = 0; y < w; y++)
1043                     if (errmask & (1UL << grid[y*w+x]))
1044                         errors[y*w+x] |= EF_LATIN;
1045             }
1046         }
1047     }
1048
1049     for (i = 1; i < w; i++)
1050         for (j = 1; j < w; j++)
1051             for (k = 1; k < w; k++)
1052                 if (grid[i*w+j] && grid[j*w+k] &&
1053                     grid[(grid[i*w+j]-1)*w+k] &&
1054                     grid[i*w+(grid[j*w+k]-1)] &&
1055                     grid[(grid[i*w+j]-1)*w+k] != grid[i*w+(grid[j*w+k]-1)]) {
1056                     if (errors) {
1057                         int a = i+1, b = j+1, c = k+1;
1058                         int ab = grid[i*w+j], bc = grid[j*w+k];
1059                         int left = (ab-1)*w+(c-1), right = (a-1)*w+(bc-1);
1060                         /*
1061                          * If the appropriate error slot is already
1062                          * used for one of the squares, we don't
1063                          * fill either of them.
1064                          */
1065                         if (!(errors[left] & EF_LEFT_MASK) &&
1066                             !(errors[right] & EF_RIGHT_MASK)) {
1067                             long err;
1068                             err = a;
1069                             err = (err << EF_DIGIT_SHIFT) | b;
1070                             err = (err << EF_DIGIT_SHIFT) | c;
1071                             errors[left] |= err << EF_LEFT_SHIFT;
1072                             errors[right] |= err << EF_RIGHT_SHIFT;
1073                         }
1074                     }
1075                     errs = TRUE;
1076                 }
1077
1078     return errs;
1079 }
1080
1081 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1082                             int x, int y, int button)
1083 {
1084     int w = state->par.w;
1085     int tx, ty;
1086     char buf[80];
1087
1088     button &= ~MOD_MASK;
1089
1090     tx = FROMCOORD(x);
1091     ty = FROMCOORD(y);
1092
1093     if (tx > 0 && tx < w && ty > 0 && ty < w) {
1094         if (button == LEFT_BUTTON) {
1095             if (tx == ui->hx && ty == ui->hy &&
1096                 ui->hshow && ui->hpencil == 0) {
1097                 ui->hshow = 0;
1098             } else {
1099                 ui->hx = tx;
1100                 ui->hy = ty;
1101                 ui->hshow = !state->immutable[ty*w+tx];
1102                 ui->hpencil = 0;
1103             }
1104             ui->hcursor = 0;
1105             return "";                 /* UI activity occurred */
1106         }
1107         if (button == RIGHT_BUTTON) {
1108             /*
1109              * Pencil-mode highlighting for non filled squares.
1110              */
1111             if (state->grid[ty*w+tx] == 0) {
1112                 if (tx == ui->hx && ty == ui->hy &&
1113                     ui->hshow && ui->hpencil) {
1114                     ui->hshow = 0;
1115                 } else {
1116                     ui->hpencil = 1;
1117                     ui->hx = tx;
1118                     ui->hy = ty;
1119                     ui->hshow = 1;
1120                 }
1121             } else {
1122                 ui->hshow = 0;
1123             }
1124             ui->hcursor = 0;
1125             return "";                 /* UI activity occurred */
1126         }
1127     }
1128     if (IS_CURSOR_MOVE(button)) {
1129         ui->hx--; ui->hy--;
1130         move_cursor(button, &ui->hx, &ui->hy, w-1, w-1, 0);
1131         ui->hx++; ui->hy++;
1132         ui->hshow = ui->hcursor = 1;
1133         return "";
1134     }
1135     if (ui->hshow &&
1136         (button == CURSOR_SELECT)) {
1137         ui->hpencil = 1 - ui->hpencil;
1138         ui->hcursor = 1;
1139         return "";
1140     }
1141
1142     if (ui->hshow &&
1143         ((ISCHAR(button) && FROMCHAR(button) <= w) ||
1144          button == CURSOR_SELECT2 || button == '\b')) {
1145         int n = FROMCHAR(button);
1146         if (button == CURSOR_SELECT2 || button == '\b')
1147             n = 0;
1148
1149         /*
1150          * Can't make pencil marks in a filled square. This can only
1151          * become highlighted if we're using cursor keys.
1152          */
1153         if (ui->hpencil && state->grid[ui->hy*w+ui->hx])
1154             return NULL;
1155
1156         /*
1157          * Can't do anything to an immutable square.
1158          */
1159         if (state->immutable[ui->hy*w+ui->hx])
1160             return NULL;
1161
1162         sprintf(buf, "%c%d,%d,%d",
1163                 (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n);
1164
1165         if (!ui->hcursor) ui->hshow = 0;
1166
1167         return dupstr(buf);
1168     }
1169
1170     if (button == 'M' || button == 'm')
1171         return dupstr("M");
1172
1173     return NULL;
1174 }
1175
1176 static game_state *execute_move(game_state *from, char *move)
1177 {
1178     int w = from->par.w, a = w*w;
1179     game_state *ret;
1180     int x, y, i, n;
1181
1182     if (move[0] == 'S') {
1183         ret = dup_game(from);
1184         ret->completed = ret->cheated = TRUE;
1185
1186         for (i = 0; i < a; i++) {
1187             if (!ISCHAR(move[i+1]) || FROMCHAR(move[i+1]) > w) {
1188                 free_game(ret);
1189                 return NULL;
1190             }
1191             ret->grid[i] = FROMCHAR(move[i+1]);
1192             ret->pencil[i] = 0;
1193         }
1194
1195         if (move[a+1] != '\0') {
1196             free_game(ret);
1197             return NULL;
1198         }
1199
1200         return ret;
1201     } else if ((move[0] == 'P' || move[0] == 'R') &&
1202         sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
1203         x >= 0 && x < w && y >= 0 && y < w && n >= 0 && n <= w) {
1204         if (from->immutable[y*w+x])
1205             return NULL;
1206
1207         ret = dup_game(from);
1208         if (move[0] == 'P' && n > 0) {
1209             ret->pencil[y*w+x] ^= 1 << n;
1210         } else {
1211             ret->grid[y*w+x] = n;
1212             ret->pencil[y*w+x] = 0;
1213
1214             if (!ret->completed && !check_errors(ret, NULL))
1215                 ret->completed = TRUE;
1216         }
1217         return ret;
1218     } else if (move[0] == 'M') {
1219         /*
1220          * Fill in absolutely all pencil marks everywhere. (I
1221          * wouldn't use this for actual play, but it's a handy
1222          * starting point when following through a set of
1223          * diagnostics output by the standalone solver.)
1224          */
1225         ret = dup_game(from);
1226         for (i = 0; i < a; i++) {
1227             if (!ret->grid[i])
1228                 ret->pencil[i] = (1 << (w+1)) - (1 << 1);
1229         }
1230         return ret;
1231     } else
1232         return NULL;                   /* couldn't parse move string */
1233 }
1234
1235 /* ----------------------------------------------------------------------
1236  * Drawing routines.
1237  */
1238
1239 #define SIZE(w) ((w) * TILESIZE + 2*BORDER)
1240
1241 static void game_compute_size(game_params *params, int tilesize,
1242                               int *x, int *y)
1243 {
1244     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1245     struct { int tilesize; } ads, *ds = &ads;
1246     ads.tilesize = tilesize;
1247
1248     *x = *y = SIZE(params->w);
1249 }
1250
1251 static void game_set_size(drawing *dr, game_drawstate *ds,
1252                           game_params *params, int tilesize)
1253 {
1254     ds->tilesize = tilesize;
1255 }
1256
1257 static float *game_colours(frontend *fe, int *ncolours)
1258 {
1259     float *ret = snewn(3 * NCOLOURS, float);
1260
1261     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1262
1263     ret[COL_GRID * 3 + 0] = 0.0F;
1264     ret[COL_GRID * 3 + 1] = 0.0F;
1265     ret[COL_GRID * 3 + 2] = 0.0F;
1266
1267     ret[COL_IDENTITY * 3 + 0] = 0.89F * ret[COL_BACKGROUND * 3 + 0];
1268     ret[COL_IDENTITY * 3 + 1] = 0.89F * ret[COL_BACKGROUND * 3 + 1];
1269     ret[COL_IDENTITY * 3 + 2] = 0.89F * ret[COL_BACKGROUND * 3 + 2];
1270
1271     ret[COL_USER * 3 + 0] = 0.0F;
1272     ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1273     ret[COL_USER * 3 + 2] = 0.0F;
1274
1275     ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0];
1276     ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1];
1277     ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2];
1278
1279     ret[COL_ERROR * 3 + 0] = 1.0F;
1280     ret[COL_ERROR * 3 + 1] = 0.0F;
1281     ret[COL_ERROR * 3 + 2] = 0.0F;
1282
1283     ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1284     ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1285     ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1286
1287     *ncolours = NCOLOURS;
1288     return ret;
1289 }
1290
1291 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1292 {
1293     int w = state->par.w, a = w*w;
1294     struct game_drawstate *ds = snew(struct game_drawstate);
1295     int i;
1296
1297     ds->w = w;
1298     ds->tilesize = 0;
1299     ds->started = FALSE;
1300     ds->tiles = snewn(a, long);
1301     ds->pencil = snewn(a, long);
1302     ds->errors = snewn(a, long);
1303     for (i = 0; i < a; i++)
1304         ds->tiles[i] = ds->pencil[i] = -1;
1305     ds->errtmp = snewn(a, long);
1306
1307     return ds;
1308 }
1309
1310 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1311 {
1312     sfree(ds->tiles);
1313     sfree(ds->pencil);
1314     sfree(ds->errors);
1315     sfree(ds->errtmp);
1316     sfree(ds);
1317 }
1318
1319 static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, long tile,
1320                       long pencil, long error)
1321 {
1322     int w = ds->w /* , a = w*w */;
1323     int tx, ty, tw, th;
1324     int cx, cy, cw, ch;
1325     char str[64];
1326
1327     tx = BORDER + x * TILESIZE + 1;
1328     ty = BORDER + y * TILESIZE + 1;
1329
1330     cx = tx;
1331     cy = ty;
1332     cw = tw = TILESIZE-1;
1333     ch = th = TILESIZE-1;
1334
1335     clip(dr, cx, cy, cw, ch);
1336
1337     /* background needs erasing */
1338     draw_rect(dr, cx, cy, cw, ch,
1339               (tile & DF_HIGHLIGHT) ? COL_HIGHLIGHT :
1340               (x == 0 || y == 0) ? COL_IDENTITY : COL_BACKGROUND);
1341
1342     /* pencil-mode highlight */
1343     if (tile & DF_HIGHLIGHT_PENCIL) {
1344         int coords[6];
1345         coords[0] = cx;
1346         coords[1] = cy;
1347         coords[2] = cx+cw/2;
1348         coords[3] = cy;
1349         coords[4] = cx;
1350         coords[5] = cy+ch/2;
1351         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1352     }
1353
1354     /* new number needs drawing? */
1355     if (tile & DF_DIGIT_MASK) {
1356         str[1] = '\0';
1357         str[0] = TOCHAR(tile & DF_DIGIT_MASK);
1358         draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2,
1359                   FONT_VARIABLE, TILESIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1360                   (error & EF_LATIN) ? COL_ERROR :
1361                   (tile & DF_IMMUTABLE) ? COL_GRID : COL_USER, str);
1362
1363         if (error & EF_LEFT_MASK) {
1364             int a = (error >> (EF_LEFT_SHIFT+2*EF_DIGIT_SHIFT))&EF_DIGIT_MASK;
1365             int b = (error >> (EF_LEFT_SHIFT+1*EF_DIGIT_SHIFT))&EF_DIGIT_MASK;
1366             int c = (error >> (EF_LEFT_SHIFT                 ))&EF_DIGIT_MASK;
1367             char buf[10];
1368             sprintf(buf, "(%c%c)%c", TOCHAR(a), TOCHAR(b), TOCHAR(c));
1369             draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/6,
1370                       FONT_VARIABLE, TILESIZE/6, ALIGN_VCENTRE | ALIGN_HCENTRE,
1371                       COL_ERROR, buf);
1372         }
1373         if (error & EF_RIGHT_MASK) {
1374             int a = (error >> (EF_RIGHT_SHIFT+2*EF_DIGIT_SHIFT))&EF_DIGIT_MASK;
1375             int b = (error >> (EF_RIGHT_SHIFT+1*EF_DIGIT_SHIFT))&EF_DIGIT_MASK;
1376             int c = (error >> (EF_RIGHT_SHIFT                 ))&EF_DIGIT_MASK;
1377             char buf[10];
1378             sprintf(buf, "%c(%c%c)", TOCHAR(a), TOCHAR(b), TOCHAR(c));
1379             draw_text(dr, tx + TILESIZE/2, ty + TILESIZE - TILESIZE/6,
1380                       FONT_VARIABLE, TILESIZE/6, ALIGN_VCENTRE | ALIGN_HCENTRE,
1381                       COL_ERROR, buf);
1382         }
1383     } else {
1384         int i, j, npencil;
1385         int pl, pr, pt, pb;
1386         float bestsize;
1387         int pw, ph, minph, pbest, fontsize;
1388
1389         /* Count the pencil marks required. */
1390         for (i = 1, npencil = 0; i <= w; i++)
1391             if (pencil & (1 << i))
1392                 npencil++;
1393         if (npencil) {
1394
1395             minph = 2;
1396
1397             /*
1398              * Determine the bounding rectangle within which we're going
1399              * to put the pencil marks.
1400              */
1401             /* Start with the whole square */
1402             pl = tx + GRIDEXTRA;
1403             pr = pl + TILESIZE - GRIDEXTRA;
1404             pt = ty + GRIDEXTRA;
1405             pb = pt + TILESIZE - GRIDEXTRA;
1406
1407             /*
1408              * We arrange our pencil marks in a grid layout, with
1409              * the number of rows and columns adjusted to allow the
1410              * maximum font size.
1411              *
1412              * So now we work out what the grid size ought to be.
1413              */
1414             bestsize = 0.0;
1415             pbest = 0;
1416             /* Minimum */
1417             for (pw = 3; pw < max(npencil,4); pw++) {
1418                 float fw, fh, fs;
1419
1420                 ph = (npencil + pw - 1) / pw;
1421                 ph = max(ph, minph);
1422                 fw = (pr - pl) / (float)pw;
1423                 fh = (pb - pt) / (float)ph;
1424                 fs = min(fw, fh);
1425                 if (fs > bestsize) {
1426                     bestsize = fs;
1427                     pbest = pw;
1428                 }
1429             }
1430             assert(pbest > 0);
1431             pw = pbest;
1432             ph = (npencil + pw - 1) / pw;
1433             ph = max(ph, minph);
1434
1435             /*
1436              * Now we've got our grid dimensions, work out the pixel
1437              * size of a grid element, and round it to the nearest
1438              * pixel. (We don't want rounding errors to make the
1439              * grid look uneven at low pixel sizes.)
1440              */
1441             fontsize = min((pr - pl) / pw, (pb - pt) / ph);
1442
1443             /*
1444              * Centre the resulting figure in the square.
1445              */
1446             pl = tx + (TILESIZE - fontsize * pw) / 2;
1447             pt = ty + (TILESIZE - fontsize * ph) / 2;
1448
1449             /*
1450              * Now actually draw the pencil marks.
1451              */
1452             for (i = 1, j = 0; i <= w; i++)
1453                 if (pencil & (1 << i)) {
1454                     int dx = j % pw, dy = j / pw;
1455
1456                     str[1] = '\0';
1457                     str[0] = TOCHAR(i);
1458                     draw_text(dr, pl + fontsize * (2*dx+1) / 2,
1459                               pt + fontsize * (2*dy+1) / 2,
1460                               FONT_VARIABLE, fontsize,
1461                               ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
1462                     j++;
1463                 }
1464         }
1465     }
1466
1467     unclip(dr);
1468
1469     draw_update(dr, cx, cy, cw, ch);
1470 }
1471
1472 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1473                         game_state *state, int dir, game_ui *ui,
1474                         float animtime, float flashtime)
1475 {
1476     int w = state->par.w /*, a = w*w */;
1477     int x, y;
1478
1479     if (!ds->started) {
1480         /*
1481          * The initial contents of the window are not guaranteed and
1482          * can vary with front ends. To be on the safe side, all
1483          * games should start by drawing a big background-colour
1484          * rectangle covering the whole window.
1485          */
1486         draw_rect(dr, 0, 0, SIZE(w), SIZE(w), COL_BACKGROUND);
1487
1488         /*
1489          * Big containing rectangle.
1490          */
1491         draw_rect(dr, COORD(0) - GRIDEXTRA, COORD(0) - GRIDEXTRA,
1492                   w*TILESIZE+1+GRIDEXTRA*2, w*TILESIZE+1+GRIDEXTRA*2,
1493                   COL_GRID);
1494
1495         draw_update(dr, 0, 0, SIZE(w), SIZE(w));
1496
1497         ds->started = TRUE;
1498     }
1499
1500     check_errors(state, ds->errtmp);
1501
1502     for (y = 0; y < w; y++) {
1503         for (x = 0; x < w; x++) {
1504             long tile = 0L, pencil = 0L, error;
1505
1506             if (state->grid[y*w+x])
1507                 tile = state->grid[y*w+x];
1508             else
1509                 pencil = (long)state->pencil[y*w+x];
1510
1511             if (state->immutable[y*w+x])
1512                 tile |= DF_IMMUTABLE;
1513
1514             if (ui->hshow && ui->hx == x && ui->hy == y)
1515                 tile |= (ui->hpencil ? DF_HIGHLIGHT_PENCIL : DF_HIGHLIGHT);
1516
1517             if (flashtime > 0 &&
1518                 (flashtime <= FLASH_TIME/3 ||
1519                  flashtime >= FLASH_TIME*2/3))
1520                 tile |= DF_HIGHLIGHT;  /* completion flash */
1521
1522             error = ds->errtmp[y*w+x];
1523
1524             if (ds->tiles[y*w+x] != tile ||
1525                 ds->pencil[y*w+x] != pencil ||
1526                 ds->errors[y*w+x] != error) {
1527                 ds->tiles[y*w+x] = tile;
1528                 ds->pencil[y*w+x] = pencil;
1529                 ds->errors[y*w+x] = error;
1530                 draw_tile(dr, ds, x, y, tile, pencil, error);
1531             }
1532         }
1533     }
1534 }
1535
1536 static float game_anim_length(game_state *oldstate, game_state *newstate,
1537                               int dir, game_ui *ui)
1538 {
1539     return 0.0F;
1540 }
1541
1542 static float game_flash_length(game_state *oldstate, game_state *newstate,
1543                                int dir, game_ui *ui)
1544 {
1545     if (!oldstate->completed && newstate->completed &&
1546         !oldstate->cheated && !newstate->cheated)
1547         return FLASH_TIME;
1548     return 0.0F;
1549 }
1550
1551 static int game_timing_state(game_state *state, game_ui *ui)
1552 {
1553     if (state->completed)
1554         return FALSE;
1555     return TRUE;
1556 }
1557
1558 static void game_print_size(game_params *params, float *x, float *y)
1559 {
1560     int pw, ph;
1561
1562     /*
1563      * We use 9mm squares by default, like Solo.
1564      */
1565     game_compute_size(params, 900, &pw, &ph);
1566     *x = pw / 100.0F;
1567     *y = ph / 100.0F;
1568 }
1569
1570 static void game_print(drawing *dr, game_state *state, int tilesize)
1571 {
1572     int w = state->par.w;
1573     int ink = print_mono_colour(dr, 0);
1574     int ehighlight = print_grey_colour(dr, 0.90F);
1575     int x, y;
1576
1577     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1578     game_drawstate ads, *ds = &ads;
1579     game_set_size(dr, ds, NULL, tilesize);
1580
1581     /*
1582      * Highlight the identity row and column.
1583      */
1584     for (x = 1; x < w; x++)
1585         draw_rect(dr, BORDER + x*TILESIZE, BORDER,
1586                   TILESIZE, TILESIZE, ehighlight);
1587     for (y = 0; y < w; y++)
1588         draw_rect(dr, BORDER, BORDER + y*TILESIZE,
1589                   TILESIZE, TILESIZE, ehighlight);
1590
1591     /*
1592      * Border.
1593      */
1594     print_line_width(dr, 3 * TILESIZE / 40);
1595     draw_rect_outline(dr, BORDER, BORDER, w*TILESIZE, w*TILESIZE, ink);
1596
1597     /*
1598      * Main grid.
1599      */
1600     for (x = 1; x < w; x++) {
1601         print_line_width(dr, TILESIZE / 40);
1602         draw_line(dr, BORDER+x*TILESIZE, BORDER,
1603                   BORDER+x*TILESIZE, BORDER+w*TILESIZE, ink);
1604     }
1605     for (y = 1; y < w; y++) {
1606         print_line_width(dr, TILESIZE / 40);
1607         draw_line(dr, BORDER, BORDER+y*TILESIZE,
1608                   BORDER+w*TILESIZE, BORDER+y*TILESIZE, ink);
1609     }
1610
1611     /*
1612      * Numbers.
1613      */
1614     for (y = 0; y < w; y++)
1615         for (x = 0; x < w; x++)
1616             if (state->grid[y*w+x]) {
1617                 char str[2];
1618                 str[1] = '\0';
1619                 str[0] = TOCHAR(state->grid[y*w+x]);
1620                 draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2,
1621                           BORDER + y*TILESIZE + TILESIZE/2,
1622                           FONT_VARIABLE, TILESIZE/2,
1623                           ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
1624             }
1625 }
1626
1627 #ifdef COMBINED
1628 #define thegame group
1629 #endif
1630
1631 const struct game thegame = {
1632     "Group", NULL, NULL,
1633     default_params,
1634     game_fetch_preset,
1635     decode_params,
1636     encode_params,
1637     free_params,
1638     dup_params,
1639     TRUE, game_configure, custom_params,
1640     validate_params,
1641     new_game_desc,
1642     validate_desc,
1643     new_game,
1644     dup_game,
1645     free_game,
1646     TRUE, solve_game,
1647     TRUE, game_can_format_as_text_now, game_text_format,
1648     new_ui,
1649     free_ui,
1650     encode_ui,
1651     decode_ui,
1652     game_changed_state,
1653     interpret_move,
1654     execute_move,
1655     PREFERRED_TILESIZE, game_compute_size, game_set_size,
1656     game_colours,
1657     game_new_drawstate,
1658     game_free_drawstate,
1659     game_redraw,
1660     game_anim_length,
1661     game_flash_length,
1662     TRUE, FALSE, game_print_size, game_print,
1663     FALSE,                             /* wants_statusbar */
1664     FALSE, game_timing_state,
1665     REQUIRE_RBUTTON | REQUIRE_NUMPAD,  /* flags */
1666 };
1667
1668 #ifdef STANDALONE_SOLVER
1669
1670 #include <stdarg.h>
1671
1672 int main(int argc, char **argv)
1673 {
1674     game_params *p;
1675     game_state *s;
1676     char *id = NULL, *desc, *err;
1677     digit *grid;
1678     int grade = FALSE;
1679     int ret, diff, really_show_working = FALSE;
1680
1681     while (--argc > 0) {
1682         char *p = *++argv;
1683         if (!strcmp(p, "-v")) {
1684             really_show_working = TRUE;
1685         } else if (!strcmp(p, "-g")) {
1686             grade = TRUE;
1687         } else if (*p == '-') {
1688             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
1689             return 1;
1690         } else {
1691             id = p;
1692         }
1693     }
1694
1695     if (!id) {
1696         fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
1697         return 1;
1698     }
1699
1700     desc = strchr(id, ':');
1701     if (!desc) {
1702         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
1703         return 1;
1704     }
1705     *desc++ = '\0';
1706
1707     p = default_params();
1708     decode_params(p, id);
1709     err = validate_desc(p, desc);
1710     if (err) {
1711         fprintf(stderr, "%s: %s\n", argv[0], err);
1712         return 1;
1713     }
1714     s = new_game(NULL, p, desc);
1715
1716     grid = snewn(p->w * p->w, digit);
1717
1718     /*
1719      * When solving a Normal puzzle, we don't want to bother the
1720      * user with Hard-level deductions. For this reason, we grade
1721      * the puzzle internally before doing anything else.
1722      */
1723     ret = -1;                          /* placate optimiser */
1724     solver_show_working = FALSE;
1725     for (diff = 0; diff < DIFFCOUNT; diff++) {
1726         memcpy(grid, s->grid, p->w * p->w);
1727         ret = solver(p->w, grid, diff);
1728         if (ret <= diff)
1729             break;
1730     }
1731
1732     if (diff == DIFFCOUNT) {
1733         if (grade)
1734             printf("Difficulty rating: ambiguous\n");
1735         else
1736             printf("Unable to find a unique solution\n");
1737     } else {
1738         if (grade) {
1739             if (ret == diff_impossible)
1740                 printf("Difficulty rating: impossible (no solution exists)\n");
1741             else
1742                 printf("Difficulty rating: %s\n", group_diffnames[ret]);
1743         } else {
1744             solver_show_working = really_show_working;
1745             memcpy(grid, s->grid, p->w * p->w);
1746             ret = solver(p->w, grid, diff);
1747             if (ret != diff)
1748                 printf("Puzzle is inconsistent\n");
1749             else {
1750                 memcpy(s->grid, grid, p->w * p->w);
1751                 fputs(game_text_format(s), stdout);
1752             }
1753         }
1754     }
1755
1756     return 0;
1757 }
1758
1759 #endif
1760
1761 /* vim: set shiftwidth=4 tabstop=8: */