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