From eca00638aeab59cf03287b9f298c86a6de1b5a9a Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Sun, 18 Aug 2024 21:14:07 -0400 Subject: puzzles: add Slide and Sokoban. This enables two of the "unfinished" puzzles. Slide requires a new "sticky mouse mode" to enable dragging. The help system is disabled for these puzzles, since they lack manual chapters. Group is currently unplayable due to lack of request_keys() support, which will need to be added upstream. Separate fails to draw anything. Change-Id: I7bcff3679ac5b10b0f39c5eaa19a36b4b1fe8d53 --- apps/plugins/puzzles/src/unfinished/CMakeLists.txt | 31 + apps/plugins/puzzles/src/unfinished/README | 14 + apps/plugins/puzzles/src/unfinished/group.c | 2497 ++++++++++++++++++++ apps/plugins/puzzles/src/unfinished/group.gap | 97 + apps/plugins/puzzles/src/unfinished/numgame.c | 1294 ++++++++++ apps/plugins/puzzles/src/unfinished/path.c | 866 +++++++ apps/plugins/puzzles/src/unfinished/separate.c | 861 +++++++ apps/plugins/puzzles/src/unfinished/slide.c | 2444 +++++++++++++++++++ apps/plugins/puzzles/src/unfinished/sokoban.c | 1476 ++++++++++++ 9 files changed, 9580 insertions(+) create mode 100644 apps/plugins/puzzles/src/unfinished/CMakeLists.txt create mode 100644 apps/plugins/puzzles/src/unfinished/README create mode 100644 apps/plugins/puzzles/src/unfinished/group.c create mode 100644 apps/plugins/puzzles/src/unfinished/group.gap create mode 100644 apps/plugins/puzzles/src/unfinished/numgame.c create mode 100644 apps/plugins/puzzles/src/unfinished/path.c create mode 100644 apps/plugins/puzzles/src/unfinished/separate.c create mode 100644 apps/plugins/puzzles/src/unfinished/slide.c create mode 100644 apps/plugins/puzzles/src/unfinished/sokoban.c (limited to 'apps/plugins/puzzles/src/unfinished') diff --git a/apps/plugins/puzzles/src/unfinished/CMakeLists.txt b/apps/plugins/puzzles/src/unfinished/CMakeLists.txt new file mode 100644 index 0000000000..0c1e331f9b --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/CMakeLists.txt @@ -0,0 +1,31 @@ +puzzle(group + DISPLAYNAME "Group" + DESCRIPTION "Group theory puzzle" + OBJECTIVE "Complete the unfinished Cayley table of a group.") +solver(group ${CMAKE_SOURCE_DIR}/latin.c) + +puzzle(separate + DISPLAYNAME "Separate" + DESCRIPTION "Rectangle-dividing puzzle" + OBJECTIVE "Partition the grid into regions containing one of each letter.") + +puzzle(slide + DISPLAYNAME "Slide" + DESCRIPTION "Sliding block puzzle" + OBJECTIVE "Slide the blocks to let the key block out.") +solver(slide) + +puzzle(sokoban + DISPLAYNAME "Sokoban" + DESCRIPTION "Barrel-pushing puzzle" + OBJECTIVE "Push all the barrels into the target squares.") + +# These unfinished programs don't even have the structure of a puzzle +# game yet; they're just command-line programs containing test +# implementations of some of the needed functionality. + +cliprogram(numgame numgame.c) + +cliprogram(path path.c COMPILE_DEFINITIONS TEST_GEN) + +export_variables_to_parent_scope() diff --git a/apps/plugins/puzzles/src/unfinished/README b/apps/plugins/puzzles/src/unfinished/README new file mode 100644 index 0000000000..c96ccc935a --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/README @@ -0,0 +1,14 @@ +This subdirectory contains puzzle implementations which are +half-written, fundamentally flawed, or in other ways unready to be +shipped as part of the polished Puzzles collection. + +The CMake build system will _build_ all of the source in this +directory (to ensure it hasn't become unbuildable), but they won't be +included in all-in-one puzzle binaries or installed by 'make install' +targets. If you want to temporarily change that, you can reconfigure +your build by defining the CMake variable PUZZLES_ENABLE_UNFINISHED. +For example, + + cmake . -DPUZZLES_ENABLE_UNFINISHED="group;slide" + +will build as if both Group and Slide were fully official puzzles. diff --git a/apps/plugins/puzzles/src/unfinished/group.c b/apps/plugins/puzzles/src/unfinished/group.c new file mode 100644 index 0000000000..faffa89485 --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/group.c @@ -0,0 +1,2497 @@ +/* + * group.c: a Latin-square puzzle, but played with groups' Cayley + * tables. That is, you are given a Cayley table of a group with + * most elements blank and a few clues, and you must fill it in + * so as to preserve the group axioms. + * + * This is a perfectly playable and fully working puzzle, but I'm + * leaving it for the moment in the 'unfinished' directory because + * it's just too esoteric (not to mention _hard_) for me to be + * comfortable presenting it to the general public as something they + * might (implicitly) actually want to play. + * + * TODO: + * + * - more solver techniques? + * * Inverses: once we know that gh = e, we can immediately + * deduce hg = e as well; then for any gx=y we can deduce + * hy=x, and for any xg=y we have yh=x. + * * Hard-mode associativity: we currently deduce based on + * definite numbers in the grid, but we could also winnow + * based on _possible_ numbers. + * * My overambitious original thoughts included wondering if we + * could infer that there must be elements of certain orders + * (e.g. a group of order divisible by 5 must contain an + * element of order 5), but I think in fact this is probably + * silly. + */ + +#include +#include +#include +#include +#include +#ifdef NO_TGMATH_H +# include +#else +# include +#endif + +#include "puzzles.h" +#include "latin.h" + +/* + * Difficulty levels. I do some macro ickery here to ensure that my + * enum and the various forms of my name list always match up. + */ +#define DIFFLIST(A) \ + A(TRIVIAL,Trivial,NULL,t) \ + A(NORMAL,Normal,solver_normal,n) \ + A(HARD,Hard,solver_hard,h) \ + A(EXTREME,Extreme,NULL,x) \ + A(UNREASONABLE,Unreasonable,NULL,u) +#define ENUM(upper,title,func,lower) DIFF_ ## upper, +#define TITLE(upper,title,func,lower) #title, +#define ENCODE(upper,title,func,lower) #lower +#define CONFIG(upper,title,func,lower) ":" #title +enum { DIFFLIST(ENUM) DIFFCOUNT }; +static char const *const group_diffnames[] = { DIFFLIST(TITLE) }; +static char const group_diffchars[] = DIFFLIST(ENCODE); +#define DIFFCONFIG DIFFLIST(CONFIG) + +enum { + COL_BACKGROUND, + COL_GRID, + COL_USER, + COL_HIGHLIGHT, + COL_ERROR, + COL_PENCIL, + COL_DIAGONAL, + NCOLOURS +}; + +/* + * In identity mode, we number the elements e,a,b,c,d,f,g,h,... + * Otherwise, they're a,b,c,d,e,f,g,h,... in the obvious way. + */ +#define E_TO_FRONT(c,id) ( (id) && (c)<=5 ? (c) % 5 + 1 : (c) ) +#define E_FROM_FRONT(c,id) ( (id) && (c)<=5 ? ((c) + 3) % 5 + 1 : (c) ) + +#define FROMCHAR(c,id) E_TO_FRONT((((c)-('A'-1)) & ~0x20), id) +#define ISCHAR(c) (((c)>='A'&&(c)<='Z') || ((c)>='a'&&(c)<='z')) +#define TOCHAR(c,id) (E_FROM_FRONT(c,id) + ('a'-1)) + +struct game_params { + int w, diff; + bool id; +}; + +typedef struct group_common { + int refcount; + bool *immutable; +} group_common; + +struct game_state { + game_params par; + digit *grid; + int *pencil; /* bitmaps using bits 1<<1..1<w = 6; + ret->diff = DIFF_NORMAL; + ret->id = true; + + return ret; +} + +static const struct game_params group_presets[] = { + { 6, DIFF_NORMAL, true }, + { 6, DIFF_NORMAL, false }, + { 8, DIFF_NORMAL, true }, + { 8, DIFF_NORMAL, false }, + { 8, DIFF_HARD, true }, + { 8, DIFF_HARD, false }, + { 12, DIFF_NORMAL, true }, +}; + +static bool game_fetch_preset(int i, char **name, game_params **params) +{ + game_params *ret; + char buf[80]; + + if (i < 0 || i >= lenof(group_presets)) + return false; + + ret = snew(game_params); + *ret = group_presets[i]; /* structure copy */ + + sprintf(buf, "%dx%d %s%s", ret->w, ret->w, group_diffnames[ret->diff], + ret->id ? "" : ", identity hidden"); + + *name = dupstr(buf); + *params = ret; + return true; +} + +static void free_params(game_params *params) +{ + sfree(params); +} + +static game_params *dup_params(const game_params *params) +{ + game_params *ret = snew(game_params); + *ret = *params; /* structure copy */ + return ret; +} + +static void decode_params(game_params *params, char const *string) +{ + char const *p = string; + + params->w = atoi(p); + while (*p && isdigit((unsigned char)*p)) p++; + params->diff = DIFF_NORMAL; + params->id = true; + + while (*p) { + if (*p == 'd') { + int i; + p++; + params->diff = DIFFCOUNT+1; /* ...which is invalid */ + if (*p) { + for (i = 0; i < DIFFCOUNT; i++) { + if (*p == group_diffchars[i]) + params->diff = i; + } + p++; + } + } else if (*p == 'i') { + params->id = false; + p++; + } else { + /* unrecognised character */ + p++; + } + } +} + +static char *encode_params(const game_params *params, bool full) +{ + char ret[80]; + + sprintf(ret, "%d", params->w); + if (full) + sprintf(ret + strlen(ret), "d%c", group_diffchars[params->diff]); + if (!params->id) + sprintf(ret + strlen(ret), "i"); + + return dupstr(ret); +} + +static config_item *game_configure(const game_params *params) +{ + config_item *ret; + char buf[80]; + + ret = snewn(4, config_item); + + ret[0].name = "Grid size"; + ret[0].type = C_STRING; + sprintf(buf, "%d", params->w); + ret[0].u.string.sval = dupstr(buf); + + ret[1].name = "Difficulty"; + ret[1].type = C_CHOICES; + ret[1].u.choices.choicenames = DIFFCONFIG; + ret[1].u.choices.selected = params->diff; + + ret[2].name = "Show identity"; + ret[2].type = C_BOOLEAN; + ret[2].u.boolean.bval = params->id; + + ret[3].name = NULL; + ret[3].type = C_END; + + return ret; +} + +static game_params *custom_params(const config_item *cfg) +{ + game_params *ret = snew(game_params); + + ret->w = atoi(cfg[0].u.string.sval); + ret->diff = cfg[1].u.choices.selected; + ret->id = cfg[2].u.boolean.bval; + + return ret; +} + +static const char *validate_params(const game_params *params, bool full) +{ + if (params->w < 3 || params->w > 26) + return "Grid size must be between 3 and 26"; + if (params->diff >= DIFFCOUNT) + return "Unknown difficulty rating"; + if (!params->id && params->diff == DIFF_TRIVIAL) { + /* + * We can't have a Trivial-difficulty puzzle (i.e. latin + * square deductions only) without a clear identity, because + * identityless puzzles always have two rows and two columns + * entirely blank, and no latin-square deduction permits the + * distinguishing of two such rows. + */ + return "Trivial puzzles must have an identity"; + } + if (!params->id && params->w == 3) { + /* + * We can't have a 3x3 puzzle without an identity either, + * because 3x3 puzzles can't ever be harder than Trivial + * (there are no 3x3 latin squares which aren't also valid + * group tables, so enabling group-based deductions doesn't + * rule out any possible solutions) and - as above - Trivial + * puzzles can't not have an identity. + */ + return "3x3 puzzles must have an identity"; + } + return NULL; +} + +/* ---------------------------------------------------------------------- + * Solver. + */ + +static int find_identity(struct latin_solver *solver) +{ + int w = solver->o; + digit *grid = solver->grid; + int i, j; + + for (i = 0; i < w; i++) + for (j = 0; j < w; j++) { + if (grid[i*w+j] == i+1) + return j+1; + if (grid[i*w+j] == j+1) + return i+1; + } + + return 0; +} + +static int solver_normal(struct latin_solver *solver, void *vctx) +{ + int w = solver->o; +#ifdef STANDALONE_SOLVER + char **names = solver->names; +#endif + digit *grid = solver->grid; + int i, j, k; + + /* + * Deduce using associativity: (ab)c = a(bc). + * + * So we pick any a,b,c we like; then if we know ab, bc, and + * (ab)c we can fill in a(bc). + */ + for (i = 0; i < w; i++) + for (j = 0; j < w; j++) + for (k = 0; k < w; k++) { + if (!grid[i*w+j] || !grid[j*w+k]) + continue; + if (grid[(grid[i*w+j]-1)*w+k] && + !grid[i*w+(grid[j*w+k]-1)]) { + int x = grid[j*w+k]-1, y = i; + int n = grid[(grid[i*w+j]-1)*w+k]; +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*sassociativity on %s,%s,%s: %s*%s = %s*%s\n", + solver_recurse_depth*4, "", + names[i], names[j], names[k], + names[grid[i*w+j]-1], names[k], + names[i], names[grid[j*w+k]-1]); + printf("%*s placing %s at (%d,%d)\n", + solver_recurse_depth*4, "", + names[n-1], x+1, y+1); + } +#endif + if (solver->cube[(x*w+y)*w+n-1]) { + latin_solver_place(solver, x, y, n); + return 1; + } else { +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("%*s contradiction!\n", + solver_recurse_depth*4, ""); + return -1; +#endif + } + } + if (!grid[(grid[i*w+j]-1)*w+k] && + grid[i*w+(grid[j*w+k]-1)]) { + int x = k, y = grid[i*w+j]-1; + int n = grid[i*w+(grid[j*w+k]-1)]; +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*sassociativity on %s,%s,%s: %s*%s = %s*%s\n", + solver_recurse_depth*4, "", + names[i], names[j], names[k], + names[grid[i*w+j]-1], names[k], + names[i], names[grid[j*w+k]-1]); + printf("%*s placing %s at (%d,%d)\n", + solver_recurse_depth*4, "", + names[n-1], x+1, y+1); + } +#endif + if (solver->cube[(x*w+y)*w+n-1]) { + latin_solver_place(solver, x, y, n); + return 1; + } else { +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("%*s contradiction!\n", + solver_recurse_depth*4, ""); + return -1; +#endif + } + } + } + + /* + * Fill in the row and column for the group identity, if it's not + * already known and if we've just found out what it is. + */ + i = find_identity(solver); + if (i) { + bool done_something = false; + for (j = 1; j <= w; j++) { + if (!grid[(i-1)*w+(j-1)] || !grid[(j-1)*w+(i-1)]) { + done_something = true; + } + } + if (done_something) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*s%s is the group identity\n", + solver_recurse_depth*4, "", names[i-1]); + } +#endif + for (j = 1; j <= w; j++) { + if (!grid[(j-1)*w+(i-1)]) { + if (!cube(i-1, j-1, j)) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*s but %s cannot go at (%d,%d) - " + "contradiction!\n", + solver_recurse_depth*4, "", + names[j-1], i, j); + } +#endif + return -1; + } +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*s placing %s at (%d,%d)\n", + solver_recurse_depth*4, "", + names[j-1], i, j); + } +#endif + latin_solver_place(solver, i-1, j-1, j); + } + if (!grid[(i-1)*w+(j-1)]) { + if (!cube(j-1, i-1, j)) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*s but %s cannot go at (%d,%d) - " + "contradiction!\n", + solver_recurse_depth*4, "", + names[j-1], j, i); + } +#endif + return -1; + } +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*s placing %s at (%d,%d)\n", + solver_recurse_depth*4, "", + names[j-1], j, i); + } +#endif + latin_solver_place(solver, j-1, i-1, j); + } + } + return 1; + } + } + + return 0; +} + +static int solver_hard(struct latin_solver *solver, void *vctx) +{ + bool done_something = false; + int w = solver->o; +#ifdef STANDALONE_SOLVER + char **names = solver->names; +#endif + int i, j; + + /* + * In identity-hidden mode, systematically rule out possibilities + * for the group identity. + * + * In solver_normal, we used the fact that any filled square in + * the grid whose contents _does_ match one of the elements it's + * the product of - that is, ab=a or ab=b - tells you immediately + * that the other element is the identity. + * + * Here, we use the flip side of that: any filled square in the + * grid whose contents does _not_ match either its row or column - + * that is, if ab is neither a nor b - tells you immediately that + * _neither_ of those elements is the identity. And if that's + * true, then we can also immediately rule out the possibility + * that it acts as the identity on any element at all. + */ + for (i = 0; i < w; i++) { + bool i_can_be_id = true; +#ifdef STANDALONE_SOLVER + char title[80]; +#endif + + for (j = 0; j < w; j++) { + if (grid(i,j) && grid(i,j) != j+1) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) + sprintf(title, "%s cannot be the identity: " + "%s%s = %s =/= %s", names[i], names[i], names[j], + names[grid(i,j)-1], names[j]); +#endif + i_can_be_id = false; + break; + } + if (grid(j,i) && grid(j,i) != j+1) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) + sprintf(title, "%s cannot be the identity: " + "%s%s = %s =/= %s", names[i], names[j], names[i], + names[grid(j,i)-1], names[j]); +#endif + i_can_be_id = false; + break; + } + } + + if (!i_can_be_id) { + /* Now rule out ij=j or ji=j for all j. */ + for (j = 0; j < w; j++) { + if (cube(i, j, j+1)) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + if (title[0]) { + printf("%*s%s\n", solver_recurse_depth*4, "", + title); + title[0] = '\0'; + } + printf("%*s ruling out %s at (%d,%d)\n", + solver_recurse_depth*4, "", names[j], i, j); + } +#endif + cube(i, j, j+1) = false; + } + if (cube(j, i, j+1)) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + if (title[0]) { + printf("%*s%s\n", solver_recurse_depth*4, "", + title); + title[0] = '\0'; + } + printf("%*s ruling out %s at (%d,%d)\n", + solver_recurse_depth*4, "", names[j], j, i); + } +#endif + cube(j, i, j+1) = false; + } + } + } + } + + return done_something; +} + +#define SOLVER(upper,title,func,lower) func, +static usersolver_t const group_solvers[] = { DIFFLIST(SOLVER) }; + +static bool group_valid(struct latin_solver *solver, void *ctx) +{ + int w = solver->o; +#ifdef STANDALONE_SOLVER + char **names = solver->names; +#endif + int i, j, k; + + for (i = 0; i < w; i++) + for (j = 0; j < w; j++) + for (k = 0; k < w; k++) { + int ij = grid(i, j) - 1; + int jk = grid(j, k) - 1; + int ij_k = grid(ij, k) - 1; + int i_jk = grid(i, jk) - 1; + if (ij_k != i_jk) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*sfailure of associativity: " + "(%s%s)%s = %s%s = %s but " + "%s(%s%s) = %s%s = %s\n", + solver_recurse_depth*4, "", + names[i], names[j], names[k], + names[ij], names[k], names[ij_k], + names[i], names[j], names[k], + names[i], names[jk], names[i_jk]); + } +#endif + return false; + } + } + + return true; +} + +static int solver(const game_params *params, digit *grid, int maxdiff) +{ + int w = params->w; + int ret; + struct latin_solver solver; + +#ifdef STANDALONE_SOLVER + char *p, text[100], *names[50]; + int i; + + for (i = 0, p = text; i < w; i++) { + names[i] = p; + *p++ = TOCHAR(i+1, params->id); + *p++ = '\0'; + } + solver.names = names; +#endif + + if (latin_solver_alloc(&solver, grid, w)) + ret = latin_solver_main(&solver, maxdiff, + DIFF_TRIVIAL, DIFF_HARD, DIFF_EXTREME, + DIFF_EXTREME, DIFF_UNREASONABLE, + group_solvers, group_valid, NULL, NULL, NULL); + else + ret = diff_impossible; + + latin_solver_free(&solver); + + return ret; +} + +/* ---------------------------------------------------------------------- + * Grid generation. + */ + +static char *encode_grid(char *desc, digit *grid, int area) +{ + int run, i; + char *p = desc; + + run = 0; + for (i = 0; i <= area; i++) { + int n = (i < area ? grid[i] : -1); + + if (!n) + run++; + else { + if (run) { + while (run > 0) { + int c = 'a' - 1 + run; + if (run > 26) + c = 'z'; + *p++ = c; + run -= c - ('a' - 1); + } + } else { + /* + * If there's a number in the very top left or + * bottom right, there's no point putting an + * unnecessary _ before or after it. + */ + if (p > desc && n > 0) + *p++ = '_'; + } + if (n > 0) + p += sprintf(p, "%d", n); + run = 0; + } + } + return p; +} + +/* ----- data generated by group.gap begins ----- */ + +struct group { + unsigned long autosize; + int order, ngens; + const char *gens; +}; +struct groups { + int ngroups; + const struct group *groups; +}; + +static const struct group groupdata[] = { + /* order 2 */ + {1L, 2, 1, "BA"}, + /* order 3 */ + {2L, 3, 1, "BCA"}, + /* order 4 */ + {2L, 4, 1, "BCDA"}, + {6L, 4, 2, "BADC" "CDAB"}, + /* order 5 */ + {4L, 5, 1, "BCDEA"}, + /* order 6 */ + {6L, 6, 2, "CFEBAD" "BADCFE"}, + {2L, 6, 1, "DCFEBA"}, + /* order 7 */ + {6L, 7, 1, "BCDEFGA"}, + /* order 8 */ + {4L, 8, 1, "BCEFDGHA"}, + {8L, 8, 2, "BDEFGAHC" "EGBHDCFA"}, + {8L, 8, 2, "EGBHDCFA" "BAEFCDHG"}, + {24L, 8, 2, "BDEFGAHC" "CHDGBEAF"}, + {168L, 8, 3, "BAEFCDHG" "CEAGBHDF" "DFGAHBCE"}, + /* order 9 */ + {6L, 9, 1, "BDECGHFIA"}, + {48L, 9, 2, "BDEAGHCIF" "CEFGHAIBD"}, + /* order 10 */ + {20L, 10, 2, "CJEBGDIFAH" "BADCFEHGJI"}, + {4L, 10, 1, "DCFEHGJIBA"}, + /* order 11 */ + {10L, 11, 1, "BCDEFGHIJKA"}, + /* order 12 */ + {12L, 12, 2, "GLDKJEHCBIAF" "BCEFAGIJDKLH"}, + {4L, 12, 1, "EHIJKCBLDGFA"}, + {24L, 12, 2, "BEFGAIJKCDLH" "FJBKHLEGDCIA"}, + {12L, 12, 2, "GLDKJEHCBIAF" "BAEFCDIJGHLK"}, + {12L, 12, 2, "FDIJGHLBKAEC" "GIDKFLHCJEAB"}, + /* order 13 */ + {12L, 13, 1, "BCDEFGHIJKLMA"}, + /* order 14 */ + {42L, 14, 2, "ELGNIBKDMFAHCJ" "BADCFEHGJILKNM"}, + {6L, 14, 1, "FEHGJILKNMBADC"}, + /* order 15 */ + {8L, 15, 1, "EGHCJKFMNIOBLDA"}, + /* order 16 */ + {8L, 16, 1, "MKNPFOADBGLCIEHJ"}, + {96L, 16, 2, "ILKCONFPEDJHGMAB" "BDFGHIAKLMNCOEPJ"}, + {32L, 16, 2, "MIHPFDCONBLAKJGE" "BEFGHJKALMNOCDPI"}, + {32L, 16, 2, "IFACOGLMDEJBNPKH" "BEFGHJKALMNOCDPI"}, + {16L, 16, 2, "MOHPFKCINBLADJGE" "BDFGHIEKLMNJOAPC"}, + {16L, 16, 2, "MIHPFDJONBLEKCGA" "BDFGHIEKLMNJOAPC"}, + {32L, 16, 2, "MOHPFDCINBLEKJGA" "BAFGHCDELMNIJKPO"}, + {16L, 16, 2, "MIHPFKJONBLADCGE" "GDPHNOEKFLBCIAMJ"}, + {32L, 16, 2, "MIBPFDJOGHLEKCNA" "CLEIJGMPKAOHNFDB"}, + {192L, 16, 3, + "MCHPFAIJNBLDEOGK" "BEFGHJKALMNOCDPI" "GKLBNOEDFPHJIAMC"}, + {64L, 16, 3, "MCHPFAIJNBLDEOGK" "LOGFPKJIBNMEDCHA" "CMAIJHPFDEONBLKG"}, + {192L, 16, 3, + "IPKCOGMLEDJBNFAH" "BEFGHJKALMNOCDPI" "CMEIJBPFKAOGHLDN"}, + {48L, 16, 3, "IPDJONFLEKCBGMAH" "FJBLMEOCGHPKAIND" "DGIEKLHNJOAMPBCF"}, + {20160L, 16, 4, + "EHJKAMNBOCDPFGIL" "BAFGHCDELMNIJKPO" "CFAIJBLMDEOGHPKN" + "DGIAKLBNCOEFPHJM"}, + /* order 17 */ + {16L, 17, 1, "EFGHIJKLMNOPQABCD"}, + /* order 18 */ + {54L, 18, 2, "MKIQOPNAGLRECDBJHF" "BAEFCDJKLGHIOPMNRQ"}, + {6L, 18, 1, "ECJKGHFOPDMNLRIQBA"}, + {12L, 18, 2, "ECJKGHBOPAMNFRDQLI" "KNOPQCFREIGHLJAMBD"}, + {432L, 18, 3, + "IFNAKLQCDOPBGHREMJ" "NOQCFRIGHKLJAMPBDE" "BAEFCDJKLGHIOPMNRQ"}, + {48L, 18, 2, "ECJKGHBOPAMNFRDQLI" "FDKLHIOPBMNAREQCJG"}, + /* order 19 */ + {18L, 19, 1, "EFGHIJKLMNOPQRSABCD"}, + /* order 20 */ + {40L, 20, 2, "GTDKREHOBILSFMPCJQAN" "EABICDFMGHJQKLNTOPRS"}, + {8L, 20, 1, "EHIJLCMNPGQRSKBTDOFA"}, + {20L, 20, 2, "DJSHQNCLTRGPEBKAIFOM" "EABICDFMGHJQKLNTOPRS"}, + {40L, 20, 2, "GTDKREHOBILSFMPCJQAN" "ECBIAGFMDKJQHONTLSRP"}, + {24L, 20, 2, "IGFMDKJQHONTLSREPCBA" "FDIJGHMNKLQROPTBSAEC"}, + /* order 21 */ + {42L, 21, 2, "ITLSBOUERDHAGKCJNFMQP" "EJHLMKOPNRSQAUTCDBFGI"}, + {12L, 21, 1, "EGHCJKFMNIPQLSTOUBRDA"}, + /* order 22 */ + {110L, 22, 2, "ETGVIBKDMFOHQJSLUNAPCR" "BADCFEHGJILKNMPORQTSVU"}, + {10L, 22, 1, "FEHGJILKNMPORQTSVUBADC"}, + /* order 23 */ + {22L, 23, 1, "EFGHIJKLMNOPQRSTUVWABCD"}, + /* order 24 */ + {24L, 24, 2, "QXEJWPUMKLRIVBFTSACGHNDO" "HRNOPSWCTUVBLDIJXFGAKQME"}, + {8L, 24, 1, "MQBTUDRWFGHXJELINOPKSAVC"}, + {24L, 24, 2, "IOQRBEUVFWGHKLAXMNPSCDTJ" "NJXOVGDKSMTFIPQELCURBWAH"}, + {48L, 24, 2, "QUEJWVXFKLRIPGMNSACBOTDH" "HSNOPWLDTUVBRIAKXFGCQEMJ"}, + {24L, 24, 2, "QXEJWPUMKLRIVBFTSACGHNDO" "TWHNXLRIOPUMSACQVBFDEJGK"}, + {48L, 24, 2, "QUEJWVXFKLRIPGMNSACBOTDH" "BAFGHCDEMNOPIJKLTUVQRSXW"}, + {48L, 24, 3, + "QXKJWVUMESRIPGFTLDCBONAH" "JUEQRPXFKLWCVBMNSAIGHTDO" + "HSNOPWLDTUVBRIAKXFGCQEMJ"}, + {24L, 24, 3, + "QUKJWPXFESRIVBMNLDCGHTAO" "JXEQRVUMKLWCPGFTSAIBONDH" + "TRONXLWCHVUMSAIJPGFDEQBK"}, + {16L, 24, 2, "MRGTULWIOPFXSDJQBVNEKCHA" "VKXHOQASNTPBCWDEUFGIJLMR"}, + {16L, 24, 2, "MRGTULWIOPFXSDJQBVNEKCHA" "RMLWIGTUSDJQOPFXEKCBVNAH"}, + {48L, 24, 2, "IULQRGXMSDCWOPNTEKJBVFAH" "GLMOPRSDTUBVWIEKFXHJQANC"}, + {24L, 24, 2, "UJPXMRCSNHGTLWIKFVBEDQOA" "NRUFVLWIPXMOJEDQHGTCSABK"}, + {24L, 24, 2, "MIBTUAQRFGHXCDEWNOPJKLVS" "OKXVFWSCGUTNDRQJBPMALIHE"}, + {144L, 24, 3, + "QXKJWVUMESRIPGFTLDCBONAH" "JUEQRPXFKLWCVBMNSAIGHTDO" + "BAFGHCDEMNOPIJKLTUVQRSXW"}, + {336L, 24, 3, + "QTKJWONXESRIHVUMLDCPGFAB" "JNEQRHTUKLWCOPXFSAIVBMDG" + "HENOPJKLTUVBQRSAXFGWCDMI"}, + /* order 25 */ + {20L, 25, 1, "EHILMNPQRSFTUVBJWXDOYGAKC"}, + {480L, 25, 2, "EHILMNPQRSCTUVBFWXDJYGOKA" "BDEGHIKLMNAPQRSCTUVFWXJYO"}, + /* order 26 */ + {156L, 26, 2, + "EXGZIBKDMFOHQJSLUNWPYRATCV" "BADCFEHGJILKNMPORQTSVUXWZY"}, + {12L, 26, 1, "FEHGJILKNMPORQTSVUXWZYBADC"}, +}; + +static const struct groups groups[] = { + {0, NULL}, /* trivial case: 0 */ + {0, NULL}, /* trivial case: 1 */ + {1, groupdata + 0}, /* 2 */ + {1, groupdata + 1}, /* 3 */ + {2, groupdata + 2}, /* 4 */ + {1, groupdata + 4}, /* 5 */ + {2, groupdata + 5}, /* 6 */ + {1, groupdata + 7}, /* 7 */ + {5, groupdata + 8}, /* 8 */ + {2, groupdata + 13}, /* 9 */ + {2, groupdata + 15}, /* 10 */ + {1, groupdata + 17}, /* 11 */ + {5, groupdata + 18}, /* 12 */ + {1, groupdata + 23}, /* 13 */ + {2, groupdata + 24}, /* 14 */ + {1, groupdata + 26}, /* 15 */ + {14, groupdata + 27}, /* 16 */ + {1, groupdata + 41}, /* 17 */ + {5, groupdata + 42}, /* 18 */ + {1, groupdata + 47}, /* 19 */ + {5, groupdata + 48}, /* 20 */ + {2, groupdata + 53}, /* 21 */ + {2, groupdata + 55}, /* 22 */ + {1, groupdata + 57}, /* 23 */ + {15, groupdata + 58}, /* 24 */ + {2, groupdata + 73}, /* 25 */ + {2, groupdata + 75}, /* 26 */ +}; + +/* ----- data generated by group.gap ends ----- */ + +static char *new_game_desc(const game_params *params, random_state *rs, + char **aux, bool interactive) +{ + int w = params->w, a = w*w; + digit *grid, *soln, *soln2; + int *indices; + int i, j, k, qh, qt; + int diff = params->diff; + const struct group *group; + char *desc, *p; + + /* + * Difficulty exceptions: some combinations of size and + * difficulty cannot be satisfied, because all puzzles of at + * most that difficulty are actually even easier. + * + * Remember to re-test this whenever a change is made to the + * solver logic! + * + * I tested it using the following shell command: + +for d in t n h x u; do + for id in '' i; do + for i in {3..9}; do + echo -n "./group --generate 1 ${i}d${d}${id}: " + perl -e 'alarm 30; exec @ARGV' \ + ./group --generate 1 ${i}d${d}${id} >/dev/null && echo ok + done + done +done + + * Of course, it's better to do that after taking the exceptions + * _out_, so as to detect exceptions that should be removed as + * well as those which should be added. + */ + if (w < 5 && diff == DIFF_UNREASONABLE) + diff--; + if ((w < 5 || ((w == 6 || w == 8) && params->id)) && diff == DIFF_EXTREME) + diff--; + if ((w < 6 || (w == 6 && params->id)) && diff == DIFF_HARD) + diff--; + if ((w < 4 || (w == 4 && params->id)) && diff == DIFF_NORMAL) + diff--; + + grid = snewn(a, digit); + soln = snewn(a, digit); + soln2 = snewn(a, digit); + indices = snewn(a, int); + + while (1) { + /* + * Construct a valid group table, by picking a group from + * the above data table, decompressing it into a full + * representation by BFS, and then randomly permuting its + * non-identity elements. + * + * We build the canonical table in 'soln' (and use 'grid' as + * our BFS queue), then transfer the table into 'grid' + * having shuffled the rows. + */ + assert(w >= 2); + assert(w < lenof(groups)); + group = groups[w].groups + random_upto(rs, groups[w].ngroups); + assert(group->order == w); + memset(soln, 0, a); + for (i = 0; i < w; i++) + soln[i] = i+1; + qh = qt = 0; + grid[qt++] = 1; + while (qh < qt) { + digit *row, *newrow; + + i = grid[qh++]; + row = soln + (i-1)*w; + + for (j = 0; j < group->ngens; j++) { + int nri; + const char *gen = group->gens + j*w; + + /* + * Apply each group generator to row, constructing a + * new row. + */ + nri = gen[row[0]-1] - 'A' + 1; /* which row is it? */ + newrow = soln + (nri-1)*w; + if (!newrow[0]) { /* not done yet */ + for (k = 0; k < w; k++) + newrow[k] = gen[row[k]-1] - 'A' + 1; + grid[qt++] = nri; + } + } + } + /* That's got the canonical table. Now shuffle it. */ + for (i = 0; i < w; i++) + soln2[i] = i; + if (params->id) /* do we shuffle in the identity? */ + shuffle(soln2+1, w-1, sizeof(*soln2), rs); + else + shuffle(soln2, w, sizeof(*soln2), rs); + for (i = 0; i < w; i++) + for (j = 0; j < w; j++) + grid[(soln2[i])*w+(soln2[j])] = soln2[soln[i*w+j]-1]+1; + + /* + * Remove entries one by one while the puzzle is still + * soluble at the appropriate difficulty level. + */ + memcpy(soln, grid, a); + if (!params->id) { + /* + * Start by blanking the entire identity row and column, + * and also another row and column so that the player + * can't trivially determine which element is the + * identity. + */ + + j = 1 + random_upto(rs, w-1); /* pick a second row/col to blank */ + for (i = 0; i < w; i++) { + grid[(soln2[0])*w+i] = grid[i*w+(soln2[0])] = 0; + grid[(soln2[j])*w+i] = grid[i*w+(soln2[j])] = 0; + } + + memcpy(soln2, grid, a); + if (solver(params, soln2, diff) > diff) + continue; /* go round again if that didn't work */ + } + + k = 0; + for (i = (params->id ? 1 : 0); i < w; i++) + for (j = (params->id ? 1 : 0); j < w; j++) + if (grid[i*w+j]) + indices[k++] = i*w+j; + shuffle(indices, k, sizeof(*indices), rs); + + for (i = 0; i < k; i++) { + memcpy(soln2, grid, a); + soln2[indices[i]] = 0; + if (solver(params, soln2, diff) <= diff) + grid[indices[i]] = 0; + } + + /* + * Make sure the puzzle isn't too easy. + */ + if (diff > 0) { + memcpy(soln2, grid, a); + if (solver(params, soln2, diff-1) < diff) + continue; /* go round and try again */ + } + + /* + * Done. + */ + break; + } + + /* + * Encode the puzzle description. + */ + desc = snewn(a*20, char); + p = encode_grid(desc, grid, a); + *p++ = '\0'; + desc = sresize(desc, p - desc, char); + + /* + * Encode the solution. + */ + *aux = snewn(a+2, char); + (*aux)[0] = 'S'; + for (i = 0; i < a; i++) + (*aux)[i+1] = TOCHAR(soln[i], params->id); + (*aux)[a+1] = '\0'; + + sfree(grid); + sfree(soln); + sfree(soln2); + sfree(indices); + + return desc; +} + +/* ---------------------------------------------------------------------- + * Gameplay. + */ + +static const char *validate_grid_desc(const char **pdesc, int range, int area) +{ + const char *desc = *pdesc; + int squares = 0; + while (*desc && *desc != ',') { + int n = *desc++; + if (n >= 'a' && n <= 'z') { + squares += n - 'a' + 1; + } else if (n == '_') { + /* do nothing */; + } else if (n > '0' && n <= '9') { + int val = atoi(desc-1); + if (val < 1 || val > range) + return "Out-of-range number in game description"; + squares++; + while (*desc >= '0' && *desc <= '9') + desc++; + } else + return "Invalid character in game description"; + } + + if (squares < area) + return "Not enough data to fill grid"; + + if (squares > area) + return "Too much data to fit in grid"; + *pdesc = desc; + return NULL; +} + +static const char *validate_desc(const game_params *params, const char *desc) +{ + int w = params->w, a = w*w; + const char *p = desc; + + return validate_grid_desc(&p, w, a); +} + +static const char *spec_to_grid(const char *desc, digit *grid, int area) +{ + int i = 0; + while (*desc && *desc != ',') { + int n = *desc++; + if (n >= 'a' && n <= 'z') { + int run = n - 'a' + 1; + assert(i + run <= area); + while (run-- > 0) + grid[i++] = 0; + } else if (n == '_') { + /* do nothing */; + } else if (n > '0' && n <= '9') { + assert(i < area); + grid[i++] = atoi(desc-1); + while (*desc >= '0' && *desc <= '9') + desc++; + } else { + assert(!"We can't get here"); + } + } + assert(i == area); + return desc; +} + +static game_state *new_game(midend *me, const game_params *params, + const char *desc) +{ + int w = params->w, a = w*w; + game_state *state = snew(game_state); + int i; + + state->par = *params; /* structure copy */ + state->grid = snewn(a, digit); + state->common = snew(group_common); + state->common->refcount = 1; + state->common->immutable = snewn(a, bool); + state->pencil = snewn(a, int); + for (i = 0; i < a; i++) { + state->grid[i] = 0; + state->common->immutable[i] = false; + state->pencil[i] = 0; + } + state->sequence = snewn(w, digit); + state->dividers = snewn(w, int); + for (i = 0; i < w; i++) { + state->sequence[i] = i; + state->dividers[i] = -1; + } + + desc = spec_to_grid(desc, state->grid, a); + for (i = 0; i < a; i++) + if (state->grid[i] != 0) + state->common->immutable[i] = true; + + state->completed = false; + state->cheated = false; + + return state; +} + +static game_state *dup_game(const game_state *state) +{ + int w = state->par.w, a = w*w; + game_state *ret = snew(game_state); + + ret->par = state->par; /* structure copy */ + + ret->grid = snewn(a, digit); + ret->common = state->common; + ret->common->refcount++; + ret->pencil = snewn(a, int); + ret->sequence = snewn(w, digit); + ret->dividers = snewn(w, int); + memcpy(ret->grid, state->grid, a*sizeof(digit)); + memcpy(ret->pencil, state->pencil, a*sizeof(int)); + memcpy(ret->sequence, state->sequence, w*sizeof(digit)); + memcpy(ret->dividers, state->dividers, w*sizeof(int)); + + ret->completed = state->completed; + ret->cheated = state->cheated; + + return ret; +} + +static void free_game(game_state *state) +{ + sfree(state->grid); + if (--state->common->refcount == 0) { + sfree(state->common->immutable); + sfree(state->common); + } + sfree(state->pencil); + sfree(state->sequence); + sfree(state); +} + +static char *solve_game(const game_state *state, const game_state *currstate, + const char *aux, const char **error) +{ + int w = state->par.w, a = w*w; + int i, ret; + digit *soln; + char *out; + + if (aux) + return dupstr(aux); + + soln = snewn(a, digit); + memcpy(soln, state->grid, a*sizeof(digit)); + + ret = solver(&state->par, soln, DIFFCOUNT-1); + + if (ret == diff_impossible) { + *error = "No solution exists for this puzzle"; + out = NULL; + } else if (ret == diff_ambiguous) { + *error = "Multiple solutions exist for this puzzle"; + out = NULL; + } else { + out = snewn(a+2, char); + out[0] = 'S'; + for (i = 0; i < a; i++) + out[i+1] = TOCHAR(soln[i], state->par.id); + out[a+1] = '\0'; + } + + sfree(soln); + return out; +} + +static bool game_can_format_as_text_now(const game_params *params) +{ + return true; +} + +static char *game_text_format(const game_state *state) +{ + int w = state->par.w; + int x, y; + char *ret, *p, ch; + + ret = snewn(2*w*w+1, char); /* leave room for terminating NUL */ + + p = ret; + for (y = 0; y < w; y++) { + for (x = 0; x < w; x++) { + digit d = state->grid[y*w+x]; + + if (d == 0) { + ch = '.'; + } else { + ch = TOCHAR(d, state->par.id); + } + + *p++ = ch; + if (x == w-1) { + *p++ = '\n'; + } else { + *p++ = ' '; + } + } + } + + assert(p - ret == 2*w*w); + *p = '\0'; + return ret; +} + +struct game_ui { + /* + * These are the coordinates of the primary highlighted square on + * the grid, if hshow = 1. + */ + int hx, hy; + /* + * These are the coordinates hx,hy _before_ they go through + * state->sequence. + */ + int ohx, ohy; + /* + * These variables give the length and displacement of a diagonal + * sequence of highlighted squares starting at ohx,ohy (still if + * hshow = 1). To find the squares' real coordinates, for 0<=isequence. + */ + int odx, ody, odn; + /* + * This indicates whether the current highlight is a + * pencil-mark one or a real one. + */ + bool hpencil; + /* + * This indicates whether or not we're showing the highlight + * (used to be hx = hy = -1); important so that when we're + * using the cursor keys it doesn't keep coming back at a + * fixed position. When hshow = 1, pressing a valid number + * or letter key or Space will enter that number or letter in the grid. + */ + bool hshow; + /* + * This indicates whether we're using the highlight as a cursor; + * it means that it doesn't vanish on a keypress, and that it is + * allowed on immutable squares. + */ + bool hcursor; + /* + * This indicates whether we're dragging a table header to + * reposition an entire row or column. + */ + int drag; /* 0=none 1=row 2=col */ + int dragnum; /* element being dragged */ + int dragpos; /* its current position */ + int edgepos; + + /* + * User preference option: if the user right-clicks in a square + * and presses a letter key to add/remove a pencil mark, do we + * hide the mouse highlight again afterwards? + * + * Historically our answer was yes. The Android port prefers no. + * There are advantages both ways, depending how much you dislike + * the highlight cluttering your view. So it's a preference. + */ + bool pencil_keep_highlight; +}; + +static game_ui *new_ui(const game_state *state) +{ + game_ui *ui = snew(game_ui); + + ui->hx = ui->hy = 0; + ui->hpencil = false; + ui->hshow = false; + ui->hcursor = false; + ui->drag = 0; + + ui->pencil_keep_highlight = false; + + return ui; +} + +static void free_ui(game_ui *ui) +{ + sfree(ui); +} + +static config_item *get_prefs(game_ui *ui) +{ + config_item *ret; + + ret = snewn(2, config_item); + + ret[0].name = "Keep mouse highlight after changing a pencil mark"; + ret[0].kw = "pencil-keep-highlight"; + ret[0].type = C_BOOLEAN; + ret[0].u.boolean.bval = ui->pencil_keep_highlight; + + ret[1].name = NULL; + ret[1].type = C_END; + + return ret; +} + +static void set_prefs(game_ui *ui, const config_item *cfg) +{ + ui->pencil_keep_highlight = cfg[0].u.boolean.bval; +} + +static void game_changed_state(game_ui *ui, const game_state *oldstate, + const game_state *newstate) +{ + int w = newstate->par.w; + /* + * We prevent pencil-mode highlighting of a filled square, unless + * we're using the cursor keys. So if the user has just filled in + * a square which we had a pencil-mode highlight in (by Undo, or + * by Redo, or by Solve), then we cancel the highlight. + */ + if (ui->hshow && ui->hpencil && !ui->hcursor && + newstate->grid[ui->hy * w + ui->hx] != 0) { + ui->hshow = false; + } + if (ui->hshow && ui->odn > 1) { + /* + * Reordering of rows or columns within the range of a + * multifill selection cancels the multifill and deselects + * everything. + */ + int i; + for (i = 0; i < ui->odn; i++) { + if (oldstate->sequence[ui->ohx + i*ui->odx] != + newstate->sequence[ui->ohx + i*ui->odx]) { + ui->hshow = false; + break; + } + if (oldstate->sequence[ui->ohy + i*ui->ody] != + newstate->sequence[ui->ohy + i*ui->ody]) { + ui->hshow = false; + break; + } + } + } else if (ui->hshow && + (newstate->sequence[ui->ohx] != ui->hx || + newstate->sequence[ui->ohy] != ui->hy)) { + /* + * Otherwise, reordering of the row or column containing the + * selection causes the selection to move with it. + */ + int i; + for (i = 0; i < w; i++) { + if (newstate->sequence[i] == ui->hx) + ui->ohx = i; + if (newstate->sequence[i] == ui->hy) + ui->ohy = i; + } + } +} + +static const char *current_key_label(const game_ui *ui, + const game_state *state, int button) +{ + if (ui->hshow && button == CURSOR_SELECT) + return ui->hpencil ? "Ink" : "Pencil"; + if (ui->hshow && button == CURSOR_SELECT2) { + int w = state->par.w; + int i; + for (i = 0; i < ui->odn; i++) { + int x = state->sequence[ui->ohx + i*ui->odx]; + int y = state->sequence[ui->ohy + i*ui->ody]; + int index = y*w+x; + if (ui->hpencil && state->grid[index]) return ""; + if (state->common->immutable[index]) return ""; + } + return "Clear"; + } + return ""; +} + +#define PREFERRED_TILESIZE 48 +#define TILESIZE (ds->tilesize) +#define BORDER (TILESIZE / 2) +#define LEGEND (TILESIZE) +#define GRIDEXTRA max((TILESIZE / 32),1) +#define COORD(x) ((x)*TILESIZE + BORDER + LEGEND) +#define FROMCOORD(x) (((x)+(TILESIZE-BORDER-LEGEND)) / TILESIZE - 1) + +#define FLASH_TIME 0.4F + +#define DF_DIVIDER_TOP 0x1000 +#define DF_DIVIDER_BOT 0x2000 +#define DF_DIVIDER_LEFT 0x4000 +#define DF_DIVIDER_RIGHT 0x8000 +#define DF_HIGHLIGHT 0x0400 +#define DF_HIGHLIGHT_PENCIL 0x0200 +#define DF_IMMUTABLE 0x0100 +#define DF_LEGEND 0x0080 +#define DF_DIGIT_MASK 0x001F + +#define EF_DIGIT_SHIFT 5 +#define EF_DIGIT_MASK ((1 << EF_DIGIT_SHIFT) - 1) +#define EF_LEFT_SHIFT 0 +#define EF_RIGHT_SHIFT (3*EF_DIGIT_SHIFT) +#define EF_LEFT_MASK ((1UL << (3*EF_DIGIT_SHIFT)) - 1UL) +#define EF_RIGHT_MASK (EF_LEFT_MASK << EF_RIGHT_SHIFT) +#define EF_LATIN (1UL << (6*EF_DIGIT_SHIFT)) + +struct game_drawstate { + game_params par; + int w, tilesize; + bool started; + long *tiles, *legend, *pencil, *errors; + long *errtmp; + digit *sequence; +}; + +static bool check_errors(const game_state *state, long *errors) +{ + int w = state->par.w, a = w*w; + digit *grid = state->grid; + int i, j, k, x, y; + bool errs = false; + + /* + * To verify that we have a valid group table, it suffices to + * test latin-square-hood and associativity only. All the other + * group axioms follow from those two. + * + * Proof: + * + * Associativity is given; closure is obvious from latin- + * square-hood. We need to show that an identity exists and that + * every element has an inverse. + * + * Identity: take any element a. There will be some element e + * such that ea=a (in a latin square, every element occurs in + * every row and column, so a must occur somewhere in the a + * column, say on row e). For any other element b, there must + * exist x such that ax=b (same argument from latin-square-hood + * again), and then associativity gives us eb = e(ax) = (ea)x = + * ax = b. Hence eb=b for all b, i.e. e is a left-identity. A + * similar argument tells us that there must be some f which is + * a right-identity, and then we show they are the same element + * by observing that ef must simultaneously equal e and equal f. + * + * Inverses: given any a, by the latin-square argument again, + * there must exist p and q such that pa=e and aq=e (i.e. left- + * and right-inverses). We can show these are equal by + * associativity: p = pe = p(aq) = (pa)q = eq = q. [] + */ + + if (errors) + for (i = 0; i < a; i++) + errors[i] = 0; + + for (y = 0; y < w; y++) { + unsigned long mask = 0, errmask = 0; + for (x = 0; x < w; x++) { + unsigned long bit = 1UL << grid[y*w+x]; + errmask |= (mask & bit); + mask |= bit; + } + + if (mask != (1 << (w+1)) - (1 << 1)) { + errs = true; + errmask &= ~1UL; + if (errors) { + for (x = 0; x < w; x++) + if (errmask & (1UL << grid[y*w+x])) + errors[y*w+x] |= EF_LATIN; + } + } + } + + for (x = 0; x < w; x++) { + unsigned long mask = 0, errmask = 0; + for (y = 0; y < w; y++) { + unsigned long bit = 1UL << grid[y*w+x]; + errmask |= (mask & bit); + mask |= bit; + } + + if (mask != (1 << (w+1)) - (1 << 1)) { + errs = true; + errmask &= ~1UL; + if (errors) { + for (y = 0; y < w; y++) + if (errmask & (1UL << grid[y*w+x])) + errors[y*w+x] |= EF_LATIN; + } + } + } + + for (i = 1; i < w; i++) + for (j = 1; j < w; j++) + for (k = 1; k < w; k++) + if (grid[i*w+j] && grid[j*w+k] && + grid[(grid[i*w+j]-1)*w+k] && + grid[i*w+(grid[j*w+k]-1)] && + grid[(grid[i*w+j]-1)*w+k] != grid[i*w+(grid[j*w+k]-1)]) { + if (errors) { + int a = i+1, b = j+1, c = k+1; + int ab = grid[i*w+j], bc = grid[j*w+k]; + int left = (ab-1)*w+(c-1), right = (a-1)*w+(bc-1); + /* + * If the appropriate error slot is already + * used for one of the squares, we don't + * fill either of them. + */ + if (!(errors[left] & EF_LEFT_MASK) && + !(errors[right] & EF_RIGHT_MASK)) { + long err; + err = a; + err = (err << EF_DIGIT_SHIFT) | b; + err = (err << EF_DIGIT_SHIFT) | c; + errors[left] |= err << EF_LEFT_SHIFT; + errors[right] |= err << EF_RIGHT_SHIFT; + } + } + errs = true; + } + + return errs; +} + +static int find_in_sequence(digit *seq, int len, digit n) +{ + int i; + + for (i = 0; i < len; i++) + if (seq[i] == n) + return i; + + assert(!"Should never get here"); + return -1; +} + +static char *interpret_move(const game_state *state, game_ui *ui, + const game_drawstate *ds, + int x, int y, int button) +{ + int w = state->par.w; + int tx, ty; + char buf[80]; + + button = STRIP_BUTTON_MODIFIERS(button); + + tx = FROMCOORD(x); + ty = FROMCOORD(y); + + if (ui->drag) { + if (IS_MOUSE_DRAG(button)) { + int tcoord = ((ui->drag &~ 4) == 1 ? ty : tx); + ui->drag |= 4; /* some movement has happened */ + if (tcoord >= 0 && tcoord < w) { + ui->dragpos = tcoord; + return MOVE_UI_UPDATE; + } + } else if (IS_MOUSE_RELEASE(button)) { + if (ui->drag & 4) { + ui->drag = 0; /* end drag */ + if (state->sequence[ui->dragpos] == ui->dragnum) + return MOVE_UI_UPDATE; /* drag was a no-op overall */ + sprintf(buf, "D%d,%d", ui->dragnum, ui->dragpos); + return dupstr(buf); + } else { + ui->drag = 0; /* end 'drag' */ + if (ui->edgepos > 0 && ui->edgepos < w) { + sprintf(buf, "V%d,%d", + state->sequence[ui->edgepos-1], + state->sequence[ui->edgepos]); + return dupstr(buf); + } else + return MOVE_UI_UPDATE; /* no-op */ + } + } + } else if (IS_MOUSE_DOWN(button)) { + if (tx >= 0 && tx < w && ty >= 0 && ty < w) { + int otx = tx, oty = ty; + tx = state->sequence[tx]; + ty = state->sequence[ty]; + if (button == LEFT_BUTTON) { + if (tx == ui->hx && ty == ui->hy && + ui->hshow && !ui->hpencil) { + ui->hshow = false; + } else { + ui->hx = tx; + ui->hy = ty; + ui->ohx = otx; + ui->ohy = oty; + ui->odx = ui->ody = 0; + ui->odn = 1; + ui->hshow = !state->common->immutable[ty*w+tx]; + ui->hpencil = false; + } + ui->hcursor = false; + return MOVE_UI_UPDATE; + } + if (button == RIGHT_BUTTON) { + /* + * Pencil-mode highlighting for non filled squares. + */ + if (state->grid[ty*w+tx] == 0) { + if (tx == ui->hx && ty == ui->hy && + ui->hshow && ui->hpencil) { + ui->hshow = false; + } else { + ui->hpencil = true; + ui->hx = tx; + ui->hy = ty; + ui->ohx = otx; + ui->ohy = oty; + ui->odx = ui->ody = 0; + ui->odn = 1; + ui->hshow = true; + } + } else { + ui->hshow = false; + } + ui->hcursor = false; + return MOVE_UI_UPDATE; + } + } else if (tx >= 0 && tx < w && ty == -1) { + ui->drag = 2; + ui->dragnum = state->sequence[tx]; + ui->dragpos = tx; + ui->edgepos = FROMCOORD(x + TILESIZE/2); + return MOVE_UI_UPDATE; + } else if (ty >= 0 && ty < w && tx == -1) { + ui->drag = 1; + ui->dragnum = state->sequence[ty]; + ui->dragpos = ty; + ui->edgepos = FROMCOORD(y + TILESIZE/2); + return MOVE_UI_UPDATE; + } + } else if (IS_MOUSE_DRAG(button)) { + if (!ui->hpencil && + tx >= 0 && tx < w && ty >= 0 && ty < w && + abs(tx - ui->ohx) == abs(ty - ui->ohy)) { + ui->odn = abs(tx - ui->ohx) + 1; + ui->odx = (tx < ui->ohx ? -1 : +1); + ui->ody = (ty < ui->ohy ? -1 : +1); + } else { + ui->odx = ui->ody = 0; + ui->odn = 1; + } + return MOVE_UI_UPDATE; + } + + if (IS_CURSOR_MOVE(button)) { + int cx = find_in_sequence(state->sequence, w, ui->hx); + int cy = find_in_sequence(state->sequence, w, ui->hy); + move_cursor(button, &cx, &cy, w, w, false, NULL); + ui->hx = state->sequence[cx]; + ui->hy = state->sequence[cy]; + ui->hshow = true; + ui->hcursor = true; + ui->ohx = cx; + ui->ohy = cy; + ui->odx = ui->ody = 0; + ui->odn = 1; + return MOVE_UI_UPDATE; + } + if (ui->hshow && + (button == CURSOR_SELECT)) { + ui->hpencil = !ui->hpencil; + ui->hcursor = true; + return MOVE_UI_UPDATE; + } + + if (ui->hshow && + ((ISCHAR(button) && FROMCHAR(button, state->par.id) <= w) || + button == CURSOR_SELECT2 || button == '\b')) { + int n = FROMCHAR(button, state->par.id); + int i, buflen; + char *movebuf; + + if (button == CURSOR_SELECT2 || button == '\b') + n = 0; + + for (i = 0; i < ui->odn; i++) { + int x = state->sequence[ui->ohx + i*ui->odx]; + int y = state->sequence[ui->ohy + i*ui->ody]; + int index = y*w+x; + + /* + * Can't make pencil marks in a filled square. This can only + * become highlighted if we're using cursor keys. + */ + if (ui->hpencil && state->grid[index]) + return NULL; + + /* + * Can't do anything to an immutable square. Exception: + * trying to set it to what it already was is OK (so that + * multifilling can set a whole diagonal to a without + * having to detour round the one immutable square in the + * middle that already said a). + */ + if (!ui->hpencil && state->grid[index] == n) + /* OK even if it is immutable */; + else if (state->common->immutable[index]) + return NULL; + } + + movebuf = snewn(80 * ui->odn, char); + buflen = sprintf(movebuf, "%c%d,%d,%d", + (char)(ui->hpencil && n > 0 ? 'P' : 'R'), + ui->hx, ui->hy, n); + for (i = 1; i < ui->odn; i++) { + assert(buflen < i*80); + buflen += sprintf(movebuf + buflen, "+%d,%d", + state->sequence[ui->ohx + i*ui->odx], + state->sequence[ui->ohy + i*ui->ody]); + } + movebuf = sresize(movebuf, buflen+1, char); + + /* + * Hide the highlight after a keypress, if it was mouse- + * generated. Also, don't hide it if this move has changed + * pencil marks and the user preference says not to hide the + * highlight in that situation. + */ + if (!ui->hcursor && !(ui->hpencil && ui->pencil_keep_highlight)) + ui->hshow = false; + + return movebuf; + } + + if (button == 'M' || button == 'm') + return dupstr("M"); + + return NULL; +} + +static game_state *execute_move(const game_state *from, const char *move) +{ + int w = from->par.w, a = w*w; + game_state *ret; + int x, y, i, j, n, pos; + + if (move[0] == 'S') { + ret = dup_game(from); + ret->completed = ret->cheated = true; + + for (i = 0; i < a; i++) { + if (!ISCHAR(move[i+1]) || FROMCHAR(move[i+1], from->par.id) > w) { + free_game(ret); + return NULL; + } + ret->grid[i] = FROMCHAR(move[i+1], from->par.id); + ret->pencil[i] = 0; + } + + if (move[a+1] != '\0') { + free_game(ret); + return NULL; + } + + return ret; + } else if ((move[0] == 'P' || move[0] == 'R') && + sscanf(move+1, "%d,%d,%d%n", &x, &y, &n, &pos) == 3 && + n >= 0 && n <= w) { + const char *mp = move + 1 + pos; + bool pencil = (move[0] == 'P'); + ret = dup_game(from); + + while (1) { + if (x < 0 || x >= w || y < 0 || y >= w) { + free_game(ret); + return NULL; + } + if (from->common->immutable[y*w+x] && + !(!pencil && from->grid[y*w+x] == n)) + return NULL; + + if (move[0] == 'P' && n > 0) { + ret->pencil[y*w+x] ^= 1 << n; + } else { + ret->grid[y*w+x] = n; + ret->pencil[y*w+x] = 0; + } + + if (!*mp) + break; + + if (*mp != '+') + return NULL; + if (sscanf(mp, "+%d,%d%n", &x, &y, &pos) < 2) + return NULL; + mp += pos; + } + + if (!ret->completed && !check_errors(ret, NULL)) + ret->completed = true; + + return ret; + } else if (move[0] == 'M') { + /* + * Fill in absolutely all pencil marks everywhere. (I + * wouldn't use this for actual play, but it's a handy + * starting point when following through a set of + * diagnostics output by the standalone solver.) + */ + ret = dup_game(from); + for (i = 0; i < a; i++) { + if (!ret->grid[i]) + ret->pencil[i] = (1 << (w+1)) - (1 << 1); + } + return ret; + } else if (move[0] == 'D' && + sscanf(move+1, "%d,%d", &x, &y) == 2) { + /* + * Reorder the rows and columns so that digit x is in position + * y. + */ + ret = dup_game(from); + for (i = j = 0; i < w; i++) { + if (i == y) { + ret->sequence[i] = x; + } else { + if (from->sequence[j] == x) + j++; + ret->sequence[i] = from->sequence[j++]; + } + } + /* + * Eliminate any obsoleted dividers. + */ + for (x = 0; x < w; x++) { + int i = ret->sequence[x]; + int j = (x+1 < w ? ret->sequence[x+1] : -1); + if (ret->dividers[i] != j) + ret->dividers[i] = -1; + } + return ret; + } else if (move[0] == 'V' && + sscanf(move+1, "%d,%d", &i, &j) == 2) { + ret = dup_game(from); + if (ret->dividers[i] == j) + ret->dividers[i] = -1; + else + ret->dividers[i] = j; + return ret; + } else + return NULL; /* couldn't parse move string */ +} + +/* ---------------------------------------------------------------------- + * Drawing routines. + */ + +#define SIZE(w) ((w) * TILESIZE + 2*BORDER + LEGEND) + +static void game_compute_size(const game_params *params, int tilesize, + const game_ui *ui, int *x, int *y) +{ + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + struct { int tilesize; } ads, *ds = &ads; + ads.tilesize = tilesize; + + *x = *y = SIZE(params->w); +} + +static void game_set_size(drawing *dr, game_drawstate *ds, + const game_params *params, int tilesize) +{ + ds->tilesize = tilesize; +} + +static float *game_colours(frontend *fe, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + + frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); + + ret[COL_GRID * 3 + 0] = 0.0F; + ret[COL_GRID * 3 + 1] = 0.0F; + ret[COL_GRID * 3 + 2] = 0.0F; + + ret[COL_USER * 3 + 0] = 0.0F; + ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1]; + ret[COL_USER * 3 + 2] = 0.0F; + + ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0]; + ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1]; + ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2]; + + ret[COL_ERROR * 3 + 0] = 1.0F; + ret[COL_ERROR * 3 + 1] = 0.0F; + ret[COL_ERROR * 3 + 2] = 0.0F; + + ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0]; + ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1]; + ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2]; + + ret[COL_DIAGONAL * 3 + 0] = 0.95F * ret[COL_BACKGROUND * 3 + 0]; + ret[COL_DIAGONAL * 3 + 1] = 0.95F * ret[COL_BACKGROUND * 3 + 1]; + ret[COL_DIAGONAL * 3 + 2] = 0.95F * ret[COL_BACKGROUND * 3 + 2]; + + *ncolours = NCOLOURS; + return ret; +} + +static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) +{ + int w = state->par.w, a = w*w; + struct game_drawstate *ds = snew(struct game_drawstate); + int i; + + ds->w = w; + ds->par = state->par; /* structure copy */ + ds->tilesize = 0; + ds->started = false; + ds->tiles = snewn(a, long); + ds->legend = snewn(w, long); + ds->pencil = snewn(a, long); + ds->errors = snewn(a, long); + ds->sequence = snewn(a, digit); + for (i = 0; i < a; i++) + ds->tiles[i] = ds->pencil[i] = -1; + for (i = 0; i < w; i++) + ds->legend[i] = -1; + ds->errtmp = snewn(a, long); + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds->tiles); + sfree(ds->pencil); + sfree(ds->errors); + sfree(ds->errtmp); + sfree(ds->sequence); + sfree(ds); +} + +static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, long tile, + long pencil, long error) +{ + int w = ds->w /* , a = w*w */; + int tx, ty, tw, th; + int cx, cy, cw, ch; + char str[64]; + + tx = BORDER + LEGEND + x * TILESIZE + 1; + ty = BORDER + LEGEND + y * TILESIZE + 1; + + cx = tx; + cy = ty; + cw = tw = TILESIZE-1; + ch = th = TILESIZE-1; + + if (tile & DF_LEGEND) { + cx += TILESIZE/10; + cy += TILESIZE/10; + cw -= TILESIZE/5; + ch -= TILESIZE/5; + tile |= DF_IMMUTABLE; + } + + clip(dr, cx, cy, cw, ch); + + /* background needs erasing */ + draw_rect(dr, cx, cy, cw, ch, + (tile & DF_HIGHLIGHT) ? COL_HIGHLIGHT : + (x == y) ? COL_DIAGONAL : COL_BACKGROUND); + + /* dividers */ + if (tile & DF_DIVIDER_TOP) + draw_rect(dr, cx, cy, cw, 1, COL_GRID); + if (tile & DF_DIVIDER_BOT) + draw_rect(dr, cx, cy+ch-1, cw, 1, COL_GRID); + if (tile & DF_DIVIDER_LEFT) + draw_rect(dr, cx, cy, 1, ch, COL_GRID); + if (tile & DF_DIVIDER_RIGHT) + draw_rect(dr, cx+cw-1, cy, 1, ch, COL_GRID); + + /* pencil-mode highlight */ + if (tile & DF_HIGHLIGHT_PENCIL) { + int coords[6]; + coords[0] = cx; + coords[1] = cy; + coords[2] = cx+cw/2; + coords[3] = cy; + coords[4] = cx; + coords[5] = cy+ch/2; + draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT); + } + + /* new number needs drawing? */ + if (tile & DF_DIGIT_MASK) { + str[1] = '\0'; + str[0] = TOCHAR(tile & DF_DIGIT_MASK, ds->par.id); + draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2, + FONT_VARIABLE, TILESIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE, + (error & EF_LATIN) ? COL_ERROR : + (tile & DF_IMMUTABLE) ? COL_GRID : COL_USER, str); + + if (error & EF_LEFT_MASK) { + int a = (error >> (EF_LEFT_SHIFT+2*EF_DIGIT_SHIFT))&EF_DIGIT_MASK; + int b = (error >> (EF_LEFT_SHIFT+1*EF_DIGIT_SHIFT))&EF_DIGIT_MASK; + int c = (error >> (EF_LEFT_SHIFT ))&EF_DIGIT_MASK; + char buf[10]; + sprintf(buf, "(%c%c)%c", TOCHAR(a, ds->par.id), + TOCHAR(b, ds->par.id), TOCHAR(c, ds->par.id)); + draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/6, + FONT_VARIABLE, TILESIZE/6, ALIGN_VCENTRE | ALIGN_HCENTRE, + COL_ERROR, buf); + } + if (error & EF_RIGHT_MASK) { + int a = (error >> (EF_RIGHT_SHIFT+2*EF_DIGIT_SHIFT))&EF_DIGIT_MASK; + int b = (error >> (EF_RIGHT_SHIFT+1*EF_DIGIT_SHIFT))&EF_DIGIT_MASK; + int c = (error >> (EF_RIGHT_SHIFT ))&EF_DIGIT_MASK; + char buf[10]; + sprintf(buf, "%c(%c%c)", TOCHAR(a, ds->par.id), + TOCHAR(b, ds->par.id), TOCHAR(c, ds->par.id)); + draw_text(dr, tx + TILESIZE/2, ty + TILESIZE - TILESIZE/6, + FONT_VARIABLE, TILESIZE/6, ALIGN_VCENTRE | ALIGN_HCENTRE, + COL_ERROR, buf); + } + } else { + int i, j, npencil; + int pl, pr, pt, pb; + float bestsize; + int pw, ph, minph, pbest, fontsize; + + /* Count the pencil marks required. */ + for (i = 1, npencil = 0; i <= w; i++) + if (pencil & (1 << i)) + npencil++; + if (npencil) { + + minph = 2; + + /* + * Determine the bounding rectangle within which we're going + * to put the pencil marks. + */ + /* Start with the whole square */ + pl = tx + GRIDEXTRA; + pr = pl + TILESIZE - GRIDEXTRA; + pt = ty + GRIDEXTRA; + pb = pt + TILESIZE - GRIDEXTRA; + + /* + * We arrange our pencil marks in a grid layout, with + * the number of rows and columns adjusted to allow the + * maximum font size. + * + * So now we work out what the grid size ought to be. + */ + bestsize = 0.0; + pbest = 0; + /* Minimum */ + for (pw = 3; pw < max(npencil,4); pw++) { + float fw, fh, fs; + + ph = (npencil + pw - 1) / pw; + ph = max(ph, minph); + fw = (pr - pl) / (float)pw; + fh = (pb - pt) / (float)ph; + fs = min(fw, fh); + if (fs > bestsize) { + bestsize = fs; + pbest = pw; + } + } + assert(pbest > 0); + pw = pbest; + ph = (npencil + pw - 1) / pw; + ph = max(ph, minph); + + /* + * Now we've got our grid dimensions, work out the pixel + * size of a grid element, and round it to the nearest + * pixel. (We don't want rounding errors to make the + * grid look uneven at low pixel sizes.) + */ + fontsize = min((pr - pl) / pw, (pb - pt) / ph); + + /* + * Centre the resulting figure in the square. + */ + pl = tx + (TILESIZE - fontsize * pw) / 2; + pt = ty + (TILESIZE - fontsize * ph) / 2; + + /* + * Now actually draw the pencil marks. + */ + for (i = 1, j = 0; i <= w; i++) + if (pencil & (1 << i)) { + int dx = j % pw, dy = j / pw; + + str[1] = '\0'; + str[0] = TOCHAR(i, ds->par.id); + draw_text(dr, pl + fontsize * (2*dx+1) / 2, + pt + fontsize * (2*dy+1) / 2, + FONT_VARIABLE, fontsize, + ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str); + j++; + } + } + } + + unclip(dr); + + draw_update(dr, cx, cy, cw, ch); +} + +static void game_redraw(drawing *dr, game_drawstate *ds, + const game_state *oldstate, const game_state *state, + int dir, const game_ui *ui, + float animtime, float flashtime) +{ + int w = state->par.w /*, a = w*w */; + int x, y, i, j; + + if (!ds->started) { + /* + * Big containing rectangle. + */ + draw_rect(dr, COORD(0) - GRIDEXTRA, COORD(0) - GRIDEXTRA, + w*TILESIZE+1+GRIDEXTRA*2, w*TILESIZE+1+GRIDEXTRA*2, + COL_GRID); + + draw_update(dr, 0, 0, SIZE(w), SIZE(w)); + + ds->started = true; + } + + check_errors(state, ds->errtmp); + + /* + * Construct a modified version of state->sequence which takes + * into account an unfinished drag operation. + */ + if (ui->drag) { + x = ui->dragnum; + y = ui->dragpos; + } else { + x = y = -1; + } + for (i = j = 0; i < w; i++) { + if (i == y) { + ds->sequence[i] = x; + } else { + if (state->sequence[j] == x) + j++; + ds->sequence[i] = state->sequence[j++]; + } + } + + /* + * Draw the table legend. + */ + for (x = 0; x < w; x++) { + int sx = ds->sequence[x]; + long tile = (sx+1) | DF_LEGEND; + if (ds->legend[x] != tile) { + ds->legend[x] = tile; + draw_tile(dr, ds, -1, x, tile, 0, 0); + draw_tile(dr, ds, x, -1, tile, 0, 0); + } + } + + for (y = 0; y < w; y++) { + int sy = ds->sequence[y]; + for (x = 0; x < w; x++) { + long tile = 0L, pencil = 0L, error; + int sx = ds->sequence[x]; + + if (state->grid[sy*w+sx]) + tile = state->grid[sy*w+sx]; + else + pencil = (long)state->pencil[sy*w+sx]; + + if (state->common->immutable[sy*w+sx]) + tile |= DF_IMMUTABLE; + + if ((ui->drag == 5 && ui->dragnum == sy) || + (ui->drag == 6 && ui->dragnum == sx)) { + tile |= DF_HIGHLIGHT; + } else if (ui->hshow) { + int i = abs(x - ui->ohx); + bool highlight = false; + if (ui->odn > 1) { + /* + * When a diagonal multifill selection is shown, + * we show it in its original grid position + * regardless of in-progress row/col drags. Moving + * every square about would be horrible. + */ + if (i >= 0 && i < ui->odn && + x == ui->ohx + i*ui->odx && + y == ui->ohy + i*ui->ody) + highlight = true; + } else { + /* + * For a single square, we move its highlight + * around with the drag. + */ + highlight = (ui->hx == sx && ui->hy == sy); + } + if (highlight) + tile |= (ui->hpencil ? DF_HIGHLIGHT_PENCIL : DF_HIGHLIGHT); + } + + if (flashtime > 0 && + (flashtime <= FLASH_TIME/3 || + flashtime >= FLASH_TIME*2/3)) + tile |= DF_HIGHLIGHT; /* completion flash */ + + if (y <= 0 || state->dividers[ds->sequence[y-1]] == sy) + tile |= DF_DIVIDER_TOP; + if (y+1 >= w || state->dividers[sy] == ds->sequence[y+1]) + tile |= DF_DIVIDER_BOT; + if (x <= 0 || state->dividers[ds->sequence[x-1]] == sx) + tile |= DF_DIVIDER_LEFT; + if (x+1 >= w || state->dividers[sx] == ds->sequence[x+1]) + tile |= DF_DIVIDER_RIGHT; + + error = ds->errtmp[sy*w+sx]; + + if (ds->tiles[y*w+x] != tile || + ds->pencil[y*w+x] != pencil || + ds->errors[y*w+x] != error) { + ds->tiles[y*w+x] = tile; + ds->pencil[y*w+x] = pencil; + ds->errors[y*w+x] = error; + draw_tile(dr, ds, x, y, tile, pencil, error); + } + } + } +} + +static float game_anim_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + return 0.0F; +} + +static float game_flash_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + if (!oldstate->completed && newstate->completed && + !oldstate->cheated && !newstate->cheated) + return FLASH_TIME; + return 0.0F; +} + +static void game_get_cursor_location(const game_ui *ui, + const game_drawstate *ds, + const game_state *state, + const game_params *params, + int *x, int *y, int *w, int *h) +{ +} + +static int game_status(const game_state *state) +{ + return state->completed ? +1 : 0; +} + +static bool game_timing_state(const game_state *state, game_ui *ui) +{ + if (state->completed) + return false; + return true; +} + +static void game_print_size(const game_params *params, const game_ui *ui, + float *x, float *y) +{ + int pw, ph; + + /* + * We use 9mm squares by default, like Solo. + */ + game_compute_size(params, 900, ui, &pw, &ph); + *x = pw / 100.0F; + *y = ph / 100.0F; +} + +static void game_print(drawing *dr, const game_state *state, const game_ui *ui, + int tilesize) +{ + int w = state->par.w; + int ink = print_mono_colour(dr, 0); + int x, y; + + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + game_drawstate ads, *ds = &ads; + game_set_size(dr, ds, NULL, tilesize); + + /* + * Border. + */ + print_line_width(dr, 3 * TILESIZE / 40); + draw_rect_outline(dr, BORDER + LEGEND, BORDER + LEGEND, + w*TILESIZE, w*TILESIZE, ink); + + /* + * Legend on table. + */ + for (x = 0; x < w; x++) { + char str[2]; + str[1] = '\0'; + str[0] = TOCHAR(x+1, state->par.id); + draw_text(dr, BORDER+LEGEND + x*TILESIZE + TILESIZE/2, + BORDER + TILESIZE/2, + FONT_VARIABLE, TILESIZE/2, + ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str); + draw_text(dr, BORDER + TILESIZE/2, + BORDER+LEGEND + x*TILESIZE + TILESIZE/2, + FONT_VARIABLE, TILESIZE/2, + ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str); + } + + /* + * Main grid. + */ + for (x = 1; x < w; x++) { + print_line_width(dr, TILESIZE / 40); + draw_line(dr, BORDER+LEGEND+x*TILESIZE, BORDER+LEGEND, + BORDER+LEGEND+x*TILESIZE, BORDER+LEGEND+w*TILESIZE, ink); + } + for (y = 1; y < w; y++) { + print_line_width(dr, TILESIZE / 40); + draw_line(dr, BORDER+LEGEND, BORDER+LEGEND+y*TILESIZE, + BORDER+LEGEND+w*TILESIZE, BORDER+LEGEND+y*TILESIZE, ink); + } + + /* + * Numbers. + */ + for (y = 0; y < w; y++) + for (x = 0; x < w; x++) + if (state->grid[y*w+x]) { + char str[2]; + str[1] = '\0'; + str[0] = TOCHAR(state->grid[y*w+x], state->par.id); + draw_text(dr, BORDER+LEGEND + x*TILESIZE + TILESIZE/2, + BORDER+LEGEND + y*TILESIZE + TILESIZE/2, + FONT_VARIABLE, TILESIZE/2, + ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str); + } +} + +#ifdef COMBINED +#define thegame group +#endif + +const struct game thegame = { + "Group", NULL, NULL, + default_params, + game_fetch_preset, NULL, + decode_params, + encode_params, + free_params, + dup_params, + true, game_configure, custom_params, + validate_params, + new_game_desc, + validate_desc, + new_game, + dup_game, + free_game, + true, solve_game, + true, game_can_format_as_text_now, game_text_format, + get_prefs, set_prefs, + new_ui, + free_ui, + NULL, /* encode_ui */ + NULL, /* decode_ui */ + NULL, /* game_request_keys */ + game_changed_state, + current_key_label, + interpret_move, + execute_move, + PREFERRED_TILESIZE, game_compute_size, game_set_size, + game_colours, + game_new_drawstate, + game_free_drawstate, + game_redraw, + game_anim_length, + game_flash_length, + game_get_cursor_location, + game_status, + true, false, game_print_size, game_print, + false, /* wants_statusbar */ + false, game_timing_state, + REQUIRE_RBUTTON | REQUIRE_NUMPAD, /* flags */ +}; + +#ifdef STANDALONE_SOLVER + +#include + +int main(int argc, char **argv) +{ + game_params *p; + game_state *s; + char *id = NULL, *desc; + const char *err; + digit *grid; + bool grade = false; + int ret, diff; + bool really_show_working = false; + + while (--argc > 0) { + char *p = *++argv; + if (!strcmp(p, "-v")) { + really_show_working = true; + } else if (!strcmp(p, "-g")) { + grade = true; + } else if (*p == '-') { + fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); + return 1; + } else { + id = p; + } + } + + if (!id) { + fprintf(stderr, "usage: %s [-g | -v] \n", argv[0]); + return 1; + } + + desc = strchr(id, ':'); + if (!desc) { + fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); + return 1; + } + *desc++ = '\0'; + + p = default_params(); + decode_params(p, id); + err = validate_desc(p, desc); + if (err) { + fprintf(stderr, "%s: %s\n", argv[0], err); + return 1; + } + s = new_game(NULL, p, desc); + + grid = snewn(p->w * p->w, digit); + + /* + * When solving a Normal puzzle, we don't want to bother the + * user with Hard-level deductions. For this reason, we grade + * the puzzle internally before doing anything else. + */ + ret = -1; /* placate optimiser */ + solver_show_working = 0; + for (diff = 0; diff < DIFFCOUNT; diff++) { + memcpy(grid, s->grid, p->w * p->w); + ret = solver(&s->par, grid, diff); + if (ret <= diff) + break; + } + + if (diff == DIFFCOUNT) { + if (really_show_working) { + solver_show_working = true; + memcpy(grid, s->grid, p->w * p->w); + ret = solver(&s->par, grid, DIFFCOUNT - 1); + } + if (grade) + printf("Difficulty rating: ambiguous\n"); + else + printf("Unable to find a unique solution\n"); + } else { + if (grade) { + if (ret == diff_impossible) + printf("Difficulty rating: impossible (no solution exists)\n"); + else + printf("Difficulty rating: %s\n", group_diffnames[ret]); + } else { + solver_show_working = really_show_working; + memcpy(grid, s->grid, p->w * p->w); + ret = solver(&s->par, grid, diff); + if (ret != diff) + printf("Puzzle is inconsistent\n"); + else { + memcpy(s->grid, grid, p->w * p->w); + fputs(game_text_format(s), stdout); + } + } + } + + return 0; +} + +#endif + +/* vim: set shiftwidth=4 tabstop=8: */ diff --git a/apps/plugins/puzzles/src/unfinished/group.gap b/apps/plugins/puzzles/src/unfinished/group.gap new file mode 100644 index 0000000000..280adf4664 --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/group.gap @@ -0,0 +1,97 @@ +# run this file with +# gap -b -q < /dev/null group.gap | perl -pe 's/\\\n//s' | indent -kr + +Print("/* ----- data generated by group.gap begins ----- */\n\n"); +Print("struct group {\n unsigned long autosize;\n"); +Print(" int order, ngens;\n const char *gens;\n};\n"); +Print("struct groups {\n int ngroups;\n"); +Print(" const struct group *groups;\n};\n\n"); +Print("static const struct group groupdata[] = {\n"); +offsets := [0]; +offset := 0; +for n in [2..26] do + Print(" /* order ", n, " */\n"); + for G in AllSmallGroups(n) do + + # Construct a representation of the group G as a subgroup + # of a permutation group, and find its generators in that + # group. + + # GAP has the 'IsomorphismPermGroup' function, but I don't want + # to use it because it doesn't guarantee that the permutation + # representation of the group forms a Cayley table. For example, + # C_4 could be represented as a subgroup of S_4 in many ways, + # and not all of them work: the group generated by (12) and (34) + # is clearly isomorphic to C_4 but its four elements do not form + # a Cayley table. The group generated by (12)(34) and (13)(24) + # is OK, though. + # + # Hence I construct the permutation representation _as_ the + # Cayley table, and then pick generators of that. This + # guarantees that when we rebuild the full group by BFS in + # group.c, we will end up with the right thing. + + ge := Elements(G); + gi := []; + for g in ge do + gr := []; + for h in ge do + k := g*h; + for i in [1..n] do + if k = ge[i] then + Add(gr, i); + fi; + od; + od; + Add(gi, PermList(gr)); + od; + + # GAP has the 'GeneratorsOfGroup' function, but we don't want to + # use it because it's bad at picking generators - it thinks the + # generators of C_4 are [ (1,2)(3,4), (1,3,2,4) ] and that those + # of C_6 are [ (1,2,3)(4,5,6), (1,4)(2,5)(3,6) ] ! + + gl := ShallowCopy(Elements(gi)); + Sort(gl, function(v,w) return Order(v) > Order(w); end); + + gens := []; + for x in gl do + if gens = [] or not (x in gp) then + Add(gens, x); + gp := GroupWithGenerators(gens); + fi; + od; + + # Construct the C representation of the group generators. + s := []; + for x in gens do + if Size(s) > 0 then + Add(s, '"'); + Add(s, ' '); + Add(s, '"'); + fi; + sep := "\\0"; + for i in ListPerm(x) do + chars := "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + Add(s, chars[i]); + od; + od; + s := JoinStringsWithSeparator([" {", String(Size(AutomorphismGroup(G))), + "L, ", String(Size(G)), + ", ", String(Size(gens)), + ", \"", s, "\"},\n"],""); + Print(s); + offset := offset + 1; + od; + Add(offsets, offset); +od; +Print("};\n\nstatic const struct groups groups[] = {\n"); +Print(" {0, NULL}, /* trivial case: 0 */\n"); +Print(" {0, NULL}, /* trivial case: 1 */\n"); +n := 2; +for i in [1..Size(offsets)-1] do + Print(" {", offsets[i+1] - offsets[i], ", groupdata+", + offsets[i], "}, /* ", i+1, " */\n"); +od; +Print("};\n\n/* ----- data generated by group.gap ends ----- */\n"); +quit; diff --git a/apps/plugins/puzzles/src/unfinished/numgame.c b/apps/plugins/puzzles/src/unfinished/numgame.c new file mode 100644 index 0000000000..cf919922e7 --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/numgame.c @@ -0,0 +1,1294 @@ +/* + * This program implements a breadth-first search which + * exhaustively solves the Countdown numbers game, and related + * games with slightly different rule sets such as `Flippo'. + * + * Currently it is simply a standalone command-line utility to + * which you provide a set of numbers and it tells you everything + * it can make together with how many different ways it can be + * made. I would like ultimately to turn it into the generator for + * a Puzzles puzzle, but I haven't even started on writing a + * Puzzles user interface yet. + */ + +/* + * TODO: + * + * - start thinking about difficulty ratings + * + anything involving associative operations will be flagged + * as many-paths because of the associative options (e.g. + * 2*3*4 can be (2*3)*4 or 2*(3*4), or indeed (2*4)*3). This + * is probably a _good_ thing, since those are unusually + * easy. + * + tree-structured calculations ((a*b)/(c+d)) have multiple + * paths because the independent branches of the tree can be + * evaluated in either order, whereas straight-line + * calculations with no branches will be considered easier. + * Can we do anything about this? It's certainly not clear to + * me that tree-structure calculations are _easier_, although + * I'm also not convinced they're harder. + * + I think for a realistic difficulty assessment we must also + * consider the `obviousness' of the arithmetic operations in + * some heuristic sense, and also (in Countdown) how many + * numbers ended up being used. + * - actually try some generations + * - at this point we're probably ready to start on the Puzzles + * integration. + */ + +#include +#include +#include +#include +#ifdef NO_TGMATH_H +# include +#else +# include +#endif + +#include "puzzles.h" +#include "tree234.h" + +/* + * To search for numbers we can make, we employ a breadth-first + * search across the space of sets of input numbers. That is, for + * example, we start with the set (3,6,25,50,75,100); we apply + * moves which involve combining two numbers (e.g. adding the 50 + * and the 75 takes us to the set (3,6,25,100,125); and then we see + * if we ever end up with a set containing (say) 952. + * + * If the rules are changed so that all the numbers must be used, + * this is easy to adjust to: we simply see if we end up with a set + * containing _only_ (say) 952. + * + * Obviously, we can vary the rules about permitted arithmetic + * operations simply by altering the set of valid moves in the bfs. + * However, there's one common rule in this sort of puzzle which + * takes a little more thought, and that's _concatenation_. For + * example, if you are given (say) four 4s and required to make 10, + * you are permitted to combine two of the 4s into a 44 to begin + * with, making (44-4)/4 = 10. However, you are generally not + * allowed to concatenate two numbers that _weren't_ both in the + * original input set (you couldn't multiply two 4s to get 16 and + * then concatenate a 4 on to it to make 164), so concatenation is + * not an operation which is valid in all situations. + * + * We could enforce this restriction by storing a flag alongside + * each number indicating whether or not it's an original number; + * the rules being that concatenation of two numbers is only valid + * if they both have the original flag, and that its output _also_ + * has the original flag (so that you can concatenate three 4s into + * a 444), but that applying any other arithmetic operation clears + * the original flag on the output. However, we can get marginally + * simpler than that by observing that since concatenation has to + * happen to a number before any other operation, we can simply + * place all the concatenations at the start of the search. In + * other words, we have a global flag on an entire number _set_ + * which indicates whether we are still permitted to perform + * concatenations; if so, we can concatenate any of the numbers in + * that set. Performing any other operation clears the flag. + */ + +#define SETFLAG_CONCAT 1 /* we can do concatenation */ + +struct sets; + +struct ancestor { + struct set *prev; /* index of ancestor set in set list */ + unsigned char pa, pb, po, pr; /* operation that got here from prev */ +}; + +struct set { + int *numbers; /* rationals stored as n,d pairs */ + short nnumbers; /* # of rationals, so half # of ints */ + short flags; /* SETFLAG_CONCAT only, at present */ + int npaths; /* number of ways to reach this set */ + struct ancestor a; /* primary ancestor */ + struct ancestor *as; /* further ancestors, if we care */ + int nas, assize; +}; + +struct output { + int number; + struct set *set; + int index; /* which number in the set is it? */ + int npaths; /* number of ways to reach this */ +}; + +#define SETLISTLEN 1024 +#define NUMBERLISTLEN 32768 +#define OUTPUTLISTLEN 1024 +struct operation; +struct sets { + struct set **setlists; + int nsets, nsetlists, setlistsize; + tree234 *settree; + int **numberlists; + int nnumbers, nnumberlists, numberlistsize; + struct output **outputlists; + int noutputs, noutputlists, outputlistsize; + tree234 *outputtree; + const struct operation *const *ops; +}; + +#define OPFLAG_NEEDS_CONCAT 1 +#define OPFLAG_KEEPS_CONCAT 2 +#define OPFLAG_UNARY 4 +#define OPFLAG_UNARYPREFIX 8 +#define OPFLAG_FN 16 + +struct operation { + /* + * Most operations should be shown in the output working, but + * concatenation should not; we just take the result of the + * concatenation and assume that it's obvious how it was + * derived. + */ + int display; + + /* + * Text display of the operator, in expressions and for + * debugging respectively. + */ + const char *text, *dbgtext; + + /* + * Flags dictating when the operator can be applied. + */ + int flags; + + /* + * Priority of the operator (for avoiding unnecessary + * parentheses when formatting it into a string). + */ + int priority; + + /* + * Associativity of the operator. Bit 0 means we need parens + * when the left operand of one of these operators is another + * instance of it, e.g. (2^3)^4. Bit 1 means we need parens + * when the right operand is another instance of the same + * operator, e.g. 2-(3-4). Thus: + * + * - this field is 0 for a fully associative operator, since + * we never need parens. + * - it's 1 for a right-associative operator. + * - it's 2 for a left-associative operator. + * - it's 3 for a _non_-associative operator (which always + * uses parens just to be sure). + */ + int assoc; + + /* + * Whether the operator is commutative. Saves time in the + * search if we don't have to try it both ways round. + */ + int commutes; + + /* + * Function which implements the operator. Returns true on + * success, false on failure. Takes two rationals and writes + * out a third. + */ + int (*perform)(int *a, int *b, int *output); +}; + +struct rules { + const struct operation *const *ops; + int use_all; +}; + +#define MUL(r, a, b) do { \ + (r) = (a) * (b); \ + if ((b) && (a) && (r) / (b) != (a)) return false; \ +} while (0) + +#define ADD(r, a, b) do { \ + (r) = (a) + (b); \ + if ((a) > 0 && (b) > 0 && (r) < 0) return false; \ + if ((a) < 0 && (b) < 0 && (r) > 0) return false; \ +} while (0) + +#define OUT(output, n, d) do { \ + int g = gcd((n),(d)); \ + if (g < 0) g = -g; \ + if ((d) < 0) g = -g; \ + if (g == -1 && (n) < -INT_MAX) return false; \ + if (g == -1 && (d) < -INT_MAX) return false; \ + (output)[0] = (n)/g; \ + (output)[1] = (d)/g; \ + assert((output)[1] > 0); \ +} while (0) + +static int gcd(int x, int y) +{ + while (x != 0 && y != 0) { + int t = x; + x = y; + y = t % y; + } + + return abs(x + y); /* i.e. whichever one isn't zero */ +} + +static int perform_add(int *a, int *b, int *output) +{ + int at, bt, tn, bn; + /* + * a0/a1 + b0/b1 = (a0*b1 + b0*a1) / (a1*b1) + */ + MUL(at, a[0], b[1]); + MUL(bt, b[0], a[1]); + ADD(tn, at, bt); + MUL(bn, a[1], b[1]); + OUT(output, tn, bn); + return true; +} + +static int perform_sub(int *a, int *b, int *output) +{ + int at, bt, tn, bn; + /* + * a0/a1 - b0/b1 = (a0*b1 - b0*a1) / (a1*b1) + */ + MUL(at, a[0], b[1]); + MUL(bt, b[0], a[1]); + ADD(tn, at, -bt); + MUL(bn, a[1], b[1]); + OUT(output, tn, bn); + return true; +} + +static int perform_mul(int *a, int *b, int *output) +{ + int tn, bn; + /* + * a0/a1 * b0/b1 = (a0*b0) / (a1*b1) + */ + MUL(tn, a[0], b[0]); + MUL(bn, a[1], b[1]); + OUT(output, tn, bn); + return true; +} + +static int perform_div(int *a, int *b, int *output) +{ + int tn, bn; + + /* + * Division by zero is outlawed. + */ + if (b[0] == 0) + return false; + + /* + * a0/a1 / b0/b1 = (a0*b1) / (a1*b0) + */ + MUL(tn, a[0], b[1]); + MUL(bn, a[1], b[0]); + OUT(output, tn, bn); + return true; +} + +static int perform_exact_div(int *a, int *b, int *output) +{ + int tn, bn; + + /* + * Division by zero is outlawed. + */ + if (b[0] == 0) + return false; + + /* + * a0/a1 / b0/b1 = (a0*b1) / (a1*b0) + */ + MUL(tn, a[0], b[1]); + MUL(bn, a[1], b[0]); + OUT(output, tn, bn); + + /* + * Exact division means we require the result to be an integer. + */ + return (output[1] == 1); +} + +static int max_p10(int n, int *p10_r) +{ + /* + * Find the smallest power of ten strictly greater than n. + * + * Special case: we must return at least 10, even if n is + * zero. (This is because this function is used for finding + * the power of ten by which to multiply a number being + * concatenated to the front of n, and concatenating 1 to 0 + * should yield 10 and not 1.) + */ + int p10 = 10; + while (p10 <= (INT_MAX/10) && p10 <= n) + p10 *= 10; + if (p10 > INT_MAX/10) + return false; /* integer overflow */ + *p10_r = p10; + return true; +} + +static int perform_concat(int *a, int *b, int *output) +{ + int t1, t2, p10; + + /* + * We can't concatenate anything which isn't a non-negative + * integer. + */ + if (a[1] != 1 || b[1] != 1 || a[0] < 0 || b[0] < 0) + return false; + + /* + * For concatenation, we can safely assume leading zeroes + * aren't an issue. It isn't clear whether they `should' be + * allowed, but it turns out not to matter: concatenating a + * leading zero on to a number in order to harmlessly get rid + * of the zero is never necessary because unwanted zeroes can + * be disposed of by adding them to something instead. So we + * disallow them always. + * + * The only other possibility is that you might want to + * concatenate a leading zero on to something and then + * concatenate another non-zero digit on to _that_ (to make, + * for example, 106); but that's also unnecessary, because you + * can make 106 just as easily by concatenating the 0 on to the + * _end_ of the 1 first. + */ + if (a[0] == 0) + return false; + + if (!max_p10(b[0], &p10)) return false; + + MUL(t1, p10, a[0]); + ADD(t2, t1, b[0]); + OUT(output, t2, 1); + return true; +} + +#define IPOW(ret, x, y) do { \ + int ipow_limit = (y); \ + if ((x) == 1 || (x) == 0) ipow_limit = 1; \ + else if ((x) == -1) ipow_limit &= 1; \ + (ret) = 1; \ + while (ipow_limit-- > 0) { \ + int tmp; \ + MUL(tmp, ret, x); \ + ret = tmp; \ + } \ +} while (0) + +static int perform_exp(int *a, int *b, int *output) +{ + int an, ad, xn, xd; + + /* + * Exponentiation is permitted if the result is rational. This + * means that: + * + * - first we see whether we can take the (denominator-of-b)th + * root of a and get a rational; if not, we give up. + * + * - then we do take that root of a + * + * - then we multiply by itself (numerator-of-b) times. + */ + if (b[1] > 1) { + an = (int)(0.5 + pow(a[0], 1.0/b[1])); + ad = (int)(0.5 + pow(a[1], 1.0/b[1])); + IPOW(xn, an, b[1]); + IPOW(xd, ad, b[1]); + if (xn != a[0] || xd != a[1]) + return false; + } else { + an = a[0]; + ad = a[1]; + } + if (b[0] >= 0) { + IPOW(xn, an, b[0]); + IPOW(xd, ad, b[0]); + } else { + IPOW(xd, an, -b[0]); + IPOW(xn, ad, -b[0]); + } + if (xd == 0) + return false; + + OUT(output, xn, xd); + return true; +} + +static int perform_factorial(int *a, int *b, int *output) +{ + int ret, t, i; + + /* + * Factorials of non-negative integers are permitted. + */ + if (a[1] != 1 || a[0] < 0) + return false; + + /* + * However, a special case: we don't take a factorial of + * anything which would thereby remain the same. + */ + if (a[0] == 1 || a[0] == 2) + return false; + + ret = 1; + for (i = 1; i <= a[0]; i++) { + MUL(t, ret, i); + ret = t; + } + + OUT(output, ret, 1); + return true; +} + +static int perform_decimal(int *a, int *b, int *output) +{ + int p10; + + /* + * Add a decimal digit to the front of a number; + * fail if it's not an integer. + * So, 1 --> 0.1, 15 --> 0.15, + * or, rather, 1 --> 1/10, 15 --> 15/100, + * x --> x / (smallest power of 10 > than x) + * + */ + if (a[1] != 1) return false; + + if (!max_p10(a[0], &p10)) return false; + + OUT(output, a[0], p10); + return true; +} + +static int perform_recur(int *a, int *b, int *output) +{ + int p10, tn, bn; + + /* + * This converts a number like .4 to .44444..., or .45 to .45454... + * The input number must be -1 < a < 1. + * + * Calculate the smallest power of 10 that divides the denominator exactly, + * returning if no such power of 10 exists. Then multiply the numerator + * up accordingly, and the new denominator becomes that power of 10 - 1. + */ + if (abs(a[0]) >= abs(a[1])) return false; /* -1 < a < 1 */ + + p10 = 10; + while (p10 <= (INT_MAX/10)) { + if ((a[1] <= p10) && (p10 % a[1]) == 0) goto found; + p10 *= 10; + } + return false; +found: + tn = a[0] * (p10 / a[1]); + bn = p10 - 1; + + OUT(output, tn, bn); + return true; +} + +static int perform_root(int *a, int *b, int *output) +{ + /* + * A root B is: 1 iff a == 0 + * B ^ (1/A) otherwise + */ + int ainv[2], res; + + if (a[0] == 0) { + OUT(output, 1, 1); + return true; + } + + OUT(ainv, a[1], a[0]); + res = perform_exp(b, ainv, output); + return res; +} + +static int perform_perc(int *a, int *b, int *output) +{ + if (a[0] == 0) return false; /* 0% = 0, uninteresting. */ + if (a[1] > (INT_MAX/100)) return false; + + OUT(output, a[0], a[1]*100); + return true; +} + +static int perform_gamma(int *a, int *b, int *output) +{ + int asub1[2]; + + /* + * gamma(a) = (a-1)! + * + * special case not caught by perform_fact: gamma(1) is 1 so + * don't bother. + */ + if (a[0] == 1 && a[1] == 1) return false; + + OUT(asub1, a[0]-a[1], a[1]); + return perform_factorial(asub1, b, output); +} + +static int perform_sqrt(int *a, int *b, int *output) +{ + int half[2] = { 1, 2 }; + + /* + * sqrt(0) == 0, sqrt(1) == 1: don't perform unary noops. + */ + if (a[0] == 0 || (a[0] == 1 && a[1] == 1)) return false; + + return perform_exp(a, half, output); +} + +static const struct operation op_add = { + true, "+", "+", 0, 10, 0, true, perform_add +}; +static const struct operation op_sub = { + true, "-", "-", 0, 10, 2, false, perform_sub +}; +static const struct operation op_mul = { + true, "*", "*", 0, 20, 0, true, perform_mul +}; +static const struct operation op_div = { + true, "/", "/", 0, 20, 2, false, perform_div +}; +static const struct operation op_xdiv = { + true, "/", "/", 0, 20, 2, false, perform_exact_div +}; +static const struct operation op_concat = { + false, "", "concat", OPFLAG_NEEDS_CONCAT | OPFLAG_KEEPS_CONCAT, + 1000, 0, false, perform_concat +}; +static const struct operation op_exp = { + true, "^", "^", 0, 30, 1, false, perform_exp +}; +static const struct operation op_factorial = { + true, "!", "!", OPFLAG_UNARY, 40, 0, false, perform_factorial +}; +static const struct operation op_decimal = { + true, ".", ".", OPFLAG_UNARY | OPFLAG_UNARYPREFIX | OPFLAG_NEEDS_CONCAT | OPFLAG_KEEPS_CONCAT, 50, 0, false, perform_decimal +}; +static const struct operation op_recur = { + true, "...", "recur", OPFLAG_UNARY | OPFLAG_NEEDS_CONCAT, 45, 2, false, perform_recur +}; +static const struct operation op_root = { + true, "v~", "root", 0, 30, 1, false, perform_root +}; +static const struct operation op_perc = { + true, "%", "%", OPFLAG_UNARY | OPFLAG_NEEDS_CONCAT, 45, 1, false, perform_perc +}; +static const struct operation op_gamma = { + true, "gamma", "gamma", OPFLAG_UNARY | OPFLAG_UNARYPREFIX | OPFLAG_FN, 1, 3, false, perform_gamma +}; +static const struct operation op_sqrt = { + true, "v~", "sqrt", OPFLAG_UNARY | OPFLAG_UNARYPREFIX, 30, 1, false, perform_sqrt +}; + +/* + * In Countdown, divisions resulting in fractions are disallowed. + * http://www.askoxford.com/wordgames/countdown/rules/ + */ +static const struct operation *const ops_countdown[] = { + &op_add, &op_mul, &op_sub, &op_xdiv, NULL +}; +static const struct rules rules_countdown = { + ops_countdown, false +}; + +/* + * A slightly different rule set which handles the reasonably well + * known puzzle of making 24 using two 3s and two 8s. For this we + * need rational rather than integer division. + */ +static const struct operation *const ops_3388[] = { + &op_add, &op_mul, &op_sub, &op_div, NULL +}; +static const struct rules rules_3388 = { + ops_3388, true +}; + +/* + * A still more permissive rule set usable for the four-4s problem + * and similar things. Permits concatenation. + */ +static const struct operation *const ops_four4s[] = { + &op_add, &op_mul, &op_sub, &op_div, &op_concat, NULL +}; +static const struct rules rules_four4s = { + ops_four4s, true +}; + +/* + * The most permissive ruleset I can think of. Permits + * exponentiation, and also silly unary operators like factorials. + */ +static const struct operation *const ops_anythinggoes[] = { + &op_add, &op_mul, &op_sub, &op_div, &op_concat, &op_exp, &op_factorial, + &op_decimal, &op_recur, &op_root, &op_perc, &op_gamma, &op_sqrt, NULL +}; +static const struct rules rules_anythinggoes = { + ops_anythinggoes, true +}; + +#define ratcmp(a,op,b) ( (long long)(a)[0] * (b)[1] op \ + (long long)(b)[0] * (a)[1] ) + +static int addtoset(struct set *set, int newnumber[2]) +{ + int i, j; + + /* Find where we want to insert the new number */ + for (i = 0; i < set->nnumbers && + ratcmp(set->numbers+2*i, <, newnumber); i++); + + /* Move everything else up */ + for (j = set->nnumbers; j > i; j--) { + set->numbers[2*j] = set->numbers[2*j-2]; + set->numbers[2*j+1] = set->numbers[2*j-1]; + } + + /* Insert the new number */ + set->numbers[2*i] = newnumber[0]; + set->numbers[2*i+1] = newnumber[1]; + + set->nnumbers++; + + return i; +} + +#define ensure(array, size, newlen, type) do { \ + if ((newlen) > (size)) { \ + (size) = (newlen) + 512; \ + (array) = sresize((array), (size), type); \ + } \ +} while (0) + +static int setcmp(void *av, void *bv) +{ + struct set *a = (struct set *)av; + struct set *b = (struct set *)bv; + int i; + + if (a->nnumbers < b->nnumbers) + return -1; + else if (a->nnumbers > b->nnumbers) + return +1; + + if (a->flags < b->flags) + return -1; + else if (a->flags > b->flags) + return +1; + + for (i = 0; i < a->nnumbers; i++) { + if (ratcmp(a->numbers+2*i, <, b->numbers+2*i)) + return -1; + else if (ratcmp(a->numbers+2*i, >, b->numbers+2*i)) + return +1; + } + + return 0; +} + +static int outputcmp(void *av, void *bv) +{ + struct output *a = (struct output *)av; + struct output *b = (struct output *)bv; + + if (a->number < b->number) + return -1; + else if (a->number > b->number) + return +1; + + return 0; +} + +static int outputfindcmp(void *av, void *bv) +{ + int *a = (int *)av; + struct output *b = (struct output *)bv; + + if (*a < b->number) + return -1; + else if (*a > b->number) + return +1; + + return 0; +} + +static void addset(struct sets *s, struct set *set, int multiple, + struct set *prev, int pa, int po, int pb, int pr) +{ + struct set *s2; + int npaths = (prev ? prev->npaths : 1); + + assert(set == s->setlists[s->nsets / SETLISTLEN] + s->nsets % SETLISTLEN); + s2 = add234(s->settree, set); + if (s2 == set) { + /* + * New set added to the tree. + */ + set->a.prev = prev; + set->a.pa = pa; + set->a.po = po; + set->a.pb = pb; + set->a.pr = pr; + set->npaths = npaths; + s->nsets++; + s->nnumbers += 2 * set->nnumbers; + set->as = NULL; + set->nas = set->assize = 0; + } else { + /* + * Rediscovered an existing set. Update its npaths. + */ + s2->npaths += npaths; + /* + * And optionally enter it as an additional ancestor. + */ + if (multiple) { + if (s2->nas >= s2->assize) { + s2->assize = s2->nas * 3 / 2 + 4; + s2->as = sresize(s2->as, s2->assize, struct ancestor); + } + s2->as[s2->nas].prev = prev; + s2->as[s2->nas].pa = pa; + s2->as[s2->nas].po = po; + s2->as[s2->nas].pb = pb; + s2->as[s2->nas].pr = pr; + s2->nas++; + } + } +} + +static struct set *newset(struct sets *s, int nnumbers, int flags) +{ + struct set *sn; + + ensure(s->setlists, s->setlistsize, s->nsets/SETLISTLEN+1, struct set *); + while (s->nsetlists <= s->nsets / SETLISTLEN) + s->setlists[s->nsetlists++] = snewn(SETLISTLEN, struct set); + sn = s->setlists[s->nsets / SETLISTLEN] + s->nsets % SETLISTLEN; + + if (s->nnumbers + nnumbers * 2 > s->nnumberlists * NUMBERLISTLEN) + s->nnumbers = s->nnumberlists * NUMBERLISTLEN; + ensure(s->numberlists, s->numberlistsize, + s->nnumbers/NUMBERLISTLEN+1, int *); + while (s->nnumberlists <= s->nnumbers / NUMBERLISTLEN) + s->numberlists[s->nnumberlists++] = snewn(NUMBERLISTLEN, int); + sn->numbers = s->numberlists[s->nnumbers / NUMBERLISTLEN] + + s->nnumbers % NUMBERLISTLEN; + + /* + * Start the set off empty. + */ + sn->nnumbers = 0; + + sn->flags = flags; + + return sn; +} + +static int addoutput(struct sets *s, struct set *ss, int index, int *n) +{ + struct output *o, *o2; + + /* + * Target numbers are always integers. + */ + if (ss->numbers[2*index+1] != 1) + return false; + + ensure(s->outputlists, s->outputlistsize, s->noutputs/OUTPUTLISTLEN+1, + struct output *); + while (s->noutputlists <= s->noutputs / OUTPUTLISTLEN) + s->outputlists[s->noutputlists++] = snewn(OUTPUTLISTLEN, + struct output); + o = s->outputlists[s->noutputs / OUTPUTLISTLEN] + + s->noutputs % OUTPUTLISTLEN; + + o->number = ss->numbers[2*index]; + o->set = ss; + o->index = index; + o->npaths = ss->npaths; + o2 = add234(s->outputtree, o); + if (o2 != o) { + o2->npaths += o->npaths; + } else { + s->noutputs++; + } + *n = o->number; + return true; +} + +static struct sets *do_search(int ninputs, int *inputs, + const struct rules *rules, int *target, + int debug, int multiple) +{ + struct sets *s; + struct set *sn; + int qpos, i; + const struct operation *const *ops = rules->ops; + + s = snew(struct sets); + s->setlists = NULL; + s->nsets = s->nsetlists = s->setlistsize = 0; + s->numberlists = NULL; + s->nnumbers = s->nnumberlists = s->numberlistsize = 0; + s->outputlists = NULL; + s->noutputs = s->noutputlists = s->outputlistsize = 0; + s->settree = newtree234(setcmp); + s->outputtree = newtree234(outputcmp); + s->ops = ops; + + /* + * Start with the input set. + */ + sn = newset(s, ninputs, SETFLAG_CONCAT); + for (i = 0; i < ninputs; i++) { + int newnumber[2]; + newnumber[0] = inputs[i]; + newnumber[1] = 1; + addtoset(sn, newnumber); + } + addset(s, sn, multiple, NULL, 0, 0, 0, 0); + + /* + * Now perform the breadth-first search: keep looping over sets + * until we run out of steam. + */ + qpos = 0; + while (qpos < s->nsets) { + struct set *ss = s->setlists[qpos / SETLISTLEN] + qpos % SETLISTLEN; + struct set *sn; + int i, j, k, m; + + if (debug) { + int i; + printf("processing set:"); + for (i = 0; i < ss->nnumbers; i++) { + printf(" %d", ss->numbers[2*i]); + if (ss->numbers[2*i+1] != 1) + printf("/%d", ss->numbers[2*i+1]); + } + printf("\n"); + } + + /* + * Record all the valid output numbers in this state. We + * can always do this if there's only one number in the + * state; otherwise, we can only do it if we aren't + * required to use all the numbers in coming to our answer. + */ + if (ss->nnumbers == 1 || !rules->use_all) { + for (i = 0; i < ss->nnumbers; i++) { + int n; + + if (addoutput(s, ss, i, &n) && target && n == *target) + return s; + } + } + + /* + * Try every possible operation from this state. + */ + for (k = 0; ops[k] && ops[k]->perform; k++) { + if ((ops[k]->flags & OPFLAG_NEEDS_CONCAT) && + !(ss->flags & SETFLAG_CONCAT)) + continue; /* can't use this operation here */ + for (i = 0; i < ss->nnumbers; i++) { + int jlimit = (ops[k]->flags & OPFLAG_UNARY ? 1 : ss->nnumbers); + for (j = 0; j < jlimit; j++) { + int n[2], newnn = ss->nnumbers; + int pa, po, pb, pr; + + if (!(ops[k]->flags & OPFLAG_UNARY)) { + if (i == j) + continue; /* can't combine a number with itself */ + if (i > j && ops[k]->commutes) + continue; /* no need to do this both ways round */ + newnn--; + } + if (!ops[k]->perform(ss->numbers+2*i, ss->numbers+2*j, n)) + continue; /* operation failed */ + + sn = newset(s, newnn, ss->flags); + + if (!(ops[k]->flags & OPFLAG_KEEPS_CONCAT)) + sn->flags &= ~SETFLAG_CONCAT; + + for (m = 0; m < ss->nnumbers; m++) { + if (m == i || (!(ops[k]->flags & OPFLAG_UNARY) && + m == j)) + continue; + sn->numbers[2*sn->nnumbers] = ss->numbers[2*m]; + sn->numbers[2*sn->nnumbers + 1] = ss->numbers[2*m + 1]; + sn->nnumbers++; + } + pa = i; + if (ops[k]->flags & OPFLAG_UNARY) + pb = sn->nnumbers+10; + else + pb = j; + po = k; + pr = addtoset(sn, n); + addset(s, sn, multiple, ss, pa, po, pb, pr); + if (debug) { + int i; + if (ops[k]->flags & OPFLAG_UNARYPREFIX) + printf(" %s %d ->", ops[po]->dbgtext, pa); + else if (ops[k]->flags & OPFLAG_UNARY) + printf(" %d %s ->", pa, ops[po]->dbgtext); + else + printf(" %d %s %d ->", pa, ops[po]->dbgtext, pb); + for (i = 0; i < sn->nnumbers; i++) { + printf(" %d", sn->numbers[2*i]); + if (sn->numbers[2*i+1] != 1) + printf("/%d", sn->numbers[2*i+1]); + } + printf("\n"); + } + } + } + } + + qpos++; + } + + return s; +} + +static void free_sets(struct sets *s) +{ + int i; + + freetree234(s->settree); + freetree234(s->outputtree); + for (i = 0; i < s->nsetlists; i++) + sfree(s->setlists[i]); + sfree(s->setlists); + for (i = 0; i < s->nnumberlists; i++) + sfree(s->numberlists[i]); + sfree(s->numberlists); + for (i = 0; i < s->noutputlists; i++) + sfree(s->outputlists[i]); + sfree(s->outputlists); + sfree(s); +} + +/* + * Print a text formula for producing a given output. + */ +static void print_recurse(struct sets *s, struct set *ss, int pathindex, + int index, int priority, int assoc, int child); +static void print_recurse_inner(struct sets *s, struct set *ss, + struct ancestor *a, int pathindex, int index, + int priority, int assoc, int child) +{ + if (a->prev && index != a->pr) { + int pi; + + /* + * This number was passed straight down from this set's + * predecessor. Find its index in the previous set and + * recurse to there. + */ + pi = index; + assert(pi != a->pr); + if (pi > a->pr) + pi--; + if (pi >= min(a->pa, a->pb)) { + pi++; + if (pi >= max(a->pa, a->pb)) + pi++; + } + print_recurse(s, a->prev, pathindex, pi, priority, assoc, child); + } else if (a->prev && index == a->pr && + s->ops[a->po]->display) { + /* + * This number was created by a displayed operator in the + * transition from this set to its predecessor. Hence we + * write an open paren, then recurse into the first + * operand, then write the operator, then the second + * operand, and finally close the paren. + */ + const char *op; + int parens, thispri, thisassoc; + + /* + * Determine whether we need parentheses. + */ + thispri = s->ops[a->po]->priority; + thisassoc = s->ops[a->po]->assoc; + parens = (thispri < priority || + (thispri == priority && (assoc & child))); + + if (parens) + putchar('('); + + if (s->ops[a->po]->flags & OPFLAG_UNARYPREFIX) + for (op = s->ops[a->po]->text; *op; op++) + putchar(*op); + + if (s->ops[a->po]->flags & OPFLAG_FN) + putchar('('); + + print_recurse(s, a->prev, pathindex, a->pa, thispri, thisassoc, 1); + + if (s->ops[a->po]->flags & OPFLAG_FN) + putchar(')'); + + if (!(s->ops[a->po]->flags & OPFLAG_UNARYPREFIX)) + for (op = s->ops[a->po]->text; *op; op++) + putchar(*op); + + if (!(s->ops[a->po]->flags & OPFLAG_UNARY)) + print_recurse(s, a->prev, pathindex, a->pb, thispri, thisassoc, 2); + + if (parens) + putchar(')'); + } else { + /* + * This number is either an original, or something formed + * by a non-displayed operator (concatenation). Either way, + * we display it as is. + */ + printf("%d", ss->numbers[2*index]); + if (ss->numbers[2*index+1] != 1) + printf("/%d", ss->numbers[2*index+1]); + } +} +static void print_recurse(struct sets *s, struct set *ss, int pathindex, + int index, int priority, int assoc, int child) +{ + if (!ss->a.prev || pathindex < ss->a.prev->npaths) { + print_recurse_inner(s, ss, &ss->a, pathindex, + index, priority, assoc, child); + } else { + int i; + pathindex -= ss->a.prev->npaths; + for (i = 0; i < ss->nas; i++) { + if (pathindex < ss->as[i].prev->npaths) { + print_recurse_inner(s, ss, &ss->as[i], pathindex, + index, priority, assoc, child); + break; + } + pathindex -= ss->as[i].prev->npaths; + } + } +} +static void print(int pathindex, struct sets *s, struct output *o) +{ + print_recurse(s, o->set, pathindex, o->index, 0, 0, 0); +} + +/* + * gcc -g -O0 -o numgame numgame.c -I.. ../{malloc,tree234,nullfe}.c -lm + */ +int main(int argc, char **argv) +{ + int doing_opts = true; + const struct rules *rules = NULL; + char *pname = argv[0]; + int got_target = false, target = 0; + int numbers[10], nnumbers = 0; + int verbose = false; + int pathcounts = false; + int multiple = false; + int debug_bfs = false; + int got_range = false, rangemin = 0, rangemax = 0; + + struct output *o; + struct sets *s; + int i, start, limit; + + while (--argc) { + char *p = *++argv; + int c; + + if (doing_opts && *p == '-') { + p++; + + if (!strcmp(p, "-")) { + doing_opts = false; + continue; + } else if (*p == '-') { + p++; + if (!strcmp(p, "debug-bfs")) { + debug_bfs = true; + } else { + fprintf(stderr, "%s: option '--%s' not recognised\n", + pname, p); + } + } else while (p && *p) switch (c = *p++) { + case 'C': + rules = &rules_countdown; + break; + case 'B': + rules = &rules_3388; + break; + case 'D': + rules = &rules_four4s; + break; + case 'A': + rules = &rules_anythinggoes; + break; + case 'v': + verbose = true; + break; + case 'p': + pathcounts = true; + break; + case 'm': + multiple = true; + break; + case 't': + case 'r': + { + char *v; + if (*p) { + v = p; + p = NULL; + } else if (--argc) { + v = *++argv; + } else { + fprintf(stderr, "%s: option '-%c' expects an" + " argument\n", pname, c); + return 1; + } + switch (c) { + case 't': + got_target = true; + target = atoi(v); + break; + case 'r': + { + char *sep = strchr(v, '-'); + got_range = true; + if (sep) { + rangemin = atoi(v); + rangemax = atoi(sep+1); + } else { + rangemin = 0; + rangemax = atoi(v); + } + } + break; + } + } + break; + default: + fprintf(stderr, "%s: option '-%c' not" + " recognised\n", pname, c); + return 1; + } + } else { + if (nnumbers >= lenof(numbers)) { + fprintf(stderr, "%s: internal limit of %d numbers exceeded\n", + pname, (int)lenof(numbers)); + return 1; + } else { + numbers[nnumbers++] = atoi(p); + } + } + } + + if (!rules) { + fprintf(stderr, "%s: no rule set specified; use -C,-B,-D,-A\n", pname); + return 1; + } + + if (!nnumbers) { + fprintf(stderr, "%s: no input numbers specified\n", pname); + return 1; + } + + if (got_range) { + if (got_target) { + fprintf(stderr, "%s: only one of -t and -r may be specified\n", pname); + return 1; + } + if (rangemin >= rangemax) { + fprintf(stderr, "%s: range not sensible (%d - %d)\n", pname, rangemin, rangemax); + return 1; + } + } + + s = do_search(nnumbers, numbers, rules, (got_target ? &target : NULL), + debug_bfs, multiple); + + if (got_target) { + o = findrelpos234(s->outputtree, &target, outputfindcmp, + REL234_LE, &start); + if (!o) + start = -1; + o = findrelpos234(s->outputtree, &target, outputfindcmp, + REL234_GE, &limit); + if (!o) + limit = -1; + assert(start != -1 || limit != -1); + if (start == -1) + start = limit; + else if (limit == -1) + limit = start; + limit++; + } else if (got_range) { + if (!findrelpos234(s->outputtree, &rangemin, outputfindcmp, + REL234_GE, &start) || + !findrelpos234(s->outputtree, &rangemax, outputfindcmp, + REL234_LE, &limit)) { + printf("No solutions available in specified range %d-%d\n", rangemin, rangemax); + return 1; + } + limit++; + } else { + start = 0; + limit = count234(s->outputtree); + } + + for (i = start; i < limit; i++) { + char buf[256]; + + o = index234(s->outputtree, i); + + sprintf(buf, "%d", o->number); + + if (pathcounts) + sprintf(buf + strlen(buf), " [%d]", o->npaths); + + if (got_target || verbose) { + int j, npaths; + + if (multiple) + npaths = o->npaths; + else + npaths = 1; + + for (j = 0; j < npaths; j++) { + printf("%s = ", buf); + print(j, s, o); + putchar('\n'); + } + } else { + printf("%s\n", buf); + } + } + + free_sets(s); + + return 0; +} + +/* vim: set shiftwidth=4 tabstop=8: */ diff --git a/apps/plugins/puzzles/src/unfinished/path.c b/apps/plugins/puzzles/src/unfinished/path.c new file mode 100644 index 0000000000..2515ed0b71 --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/path.c @@ -0,0 +1,866 @@ +/* + * Experimental grid generator for Nikoli's `Number Link' puzzle. + */ + +#include +#include +#include +#include +#include "puzzles.h" + +/* + * 2005-07-08: This is currently a Path grid generator which will + * construct valid grids at a plausible speed. However, the grids + * are not of suitable quality to be used directly as puzzles. + * + * The basic strategy is to start with an empty grid, and + * repeatedly either (a) add a new path to it, or (b) extend one + * end of a path by one square in some direction and push other + * paths into new shapes in the process. The effect of this is that + * we are able to construct a set of paths which between them fill + * the entire grid. + * + * Quality issues: if we set the main loop to do (a) where possible + * and (b) only where necessary, we end up with a grid containing a + * few too many small paths, which therefore doesn't make for an + * interesting puzzle. If we reverse the priority so that we do (b) + * where possible and (a) only where necessary, we end up with some + * staggeringly interwoven grids with very very few separate paths, + * but the result of this is that there's invariably a solution + * other than the intended one which leaves many grid squares + * unfilled. There's also a separate problem which is that many + * grids have really boring and obvious paths in them, such as the + * entire bottom row of the grid being taken up by a single path. + * + * It's not impossible that a few tweaks might eliminate or reduce + * the incidence of boring paths, and might also find a happy + * medium between too many and too few. There remains the question + * of unique solutions, however. I fear there is no alternative but + * to write - somehow! - a solver. + * + * While I'm here, some notes on UI strategy for the parts of the + * puzzle implementation that _aren't_ the generator: + * + * - data model is to track connections between adjacent squares, + * so that you aren't limited to extending a path out from each + * number but can also mark sections of path which you know + * _will_ come in handy later. + * + * - user interface is to click in one square and drag to an + * adjacent one, thus creating a link between them. We can + * probably tolerate rapid mouse motion causing a drag directly + * to a square which is a rook move away, but any other rapid + * motion is ambiguous and probably the best option is to wait + * until the mouse returns to a square we know how to reach. + * + * - a drag causing the current path to backtrack has the effect + * of removing bits of it. + * + * - the UI should enforce at all times the constraint that at + * most two links can come into any square. + * + * - my Cunning Plan for actually implementing this: the game_ui + * contains a grid-sized array, which is copied from the current + * game_state on starting a drag. While a drag is active, the + * contents of the game_ui is adjusted with every mouse motion, + * and is displayed _in place_ of the game_state itself. On + * termination of a drag, the game_ui array is copied back into + * the new game_state (or rather, a string move is encoded which + * has precisely the set of link changes to cause that effect). + */ + +/* + * 2020-05-11: some thoughts on a solver. + * + * Consider this example puzzle, from Wikipedia: + * + * ---4--- + * -3--25- + * ---31-- + * ---5--- + * ------- + * --1---- + * 2---4-- + * + * The kind of deduction that a human wants to make here is: which way + * does the path between the 4s go? In particular, does it go round + * the left of the W-shaped cluster of endpoints, or round the right + * of it? It's clear at a glance that it must go to the right, because + * _any_ path between the 4s that goes to the left of that cluster, no + * matter what detailed direction it takes, will disconnect the + * remaining grid squares into two components, with the two 2s not in + * the same component. So we immediately know that the path between + * the 4s _must_ go round the right-hand side of the grid. + * + * How do you model that global and topological reasoning in a + * computer? + * + * The most plausible idea I've seen so far is to use fundamental + * groups. The fundamental group of loops based at a given point in a + * space is a free group, under loop concatenation and up to homotopy, + * generated by the loops that go in each direction around each hole + * in the space. In this case, the 'holes' are clues, or connected + * groups of clues. + * + * So you might be able to enumerate all the homotopy classes of paths + * between (say) the two 4s as follows. Start with any old path + * between them (say, find the first one that breadth-first search + * will give you). Choose one of the 4s to regard as the base point + * (arbitrarily). Then breadth-first search among the space of _paths_ + * by the following procedure. Given a candidate path, append to it + * each of the possible loops that starts from the base point, + * circumnavigates one clue cluster, and returns to the base point. + * The result will typically be a path that retraces its steps and + * self-intersects. Now adjust it homotopically so that it doesn't. If + * that can't be done, then we haven't generated a fresh candidate + * path; if it can, then we've got a new path that is not homotopic to + * any path we already had, so add it to our list and queue it up to + * become the starting point of this search later. + * + * The idea is that this should exhaustively enumerate, up to + * homotopy, the different ways in which the two 4s can connect to + * each other within the constraint that you have to actually fit the + * path non-self-intersectingly into this grid. Then you can keep a + * list of those homotopy classes in mind, and start ruling them out + * by techniques like the connectivity approach described above. + * Hopefully you end up narrowing down to few enough homotopy classes + * that you can deduce something concrete about actual squares of the + * grid - for example, here, that if the path between 4s has to go + * round the right, then we know some specific squares it must go + * through, so we can fill those in. And then, having filled in a + * piece of the middle of a path, you can now regard connecting the + * ultimate endpoints to that mid-section as two separate subproblems, + * so you've reduced to a simpler instance of the same puzzle. + * + * But I don't know whether all of this actually works. I more or less + * believe the process for enumerating elements of the free group; but + * I'm not as confident that when you find a group element that won't + * fit in the grid, you'll never have to consider its descendants in + * the BFS either. And I'm assuming that 'unwind the self-intersection + * homotopically' is a thing that can actually be turned into a + * sensible algorithm. + * + * -------- + * + * Another thing that might be needed is to characterise _which_ + * homotopy class a given path is in. + * + * For this I think it's sufficient to choose a collection of paths + * along the _edges_ of the square grid, each of which connects two of + * the holes in the grid (including the grid exterior, which counts as + * a huge hole), such that they form a spanning tree between the + * holes. Then assign each of those paths an orientation, so that + * crossing it in one direction counts as 'positive' and the other + * 'negative'. Now analyse a candidate path from one square to another + * by following it and noting down which of those paths it crosses in + * which direction, then simplifying the result like a free group word + * (i.e. adjacent + and - crossings of the same path cancel out). + * + * -------- + * + * If we choose those paths to be of minimal length, then we can get + * an upper bound on the number of homotopy classes by observing that + * you can't traverse any of those barriers more times than will fit + * non-self-intersectingly in the grid. That might be an alternative + * method of bounding the search through the fundamental group to only + * finitely many possibilities. + */ + +/* + * Standard notation for directions. + */ +#define L 0 +#define U 1 +#define R 2 +#define D 3 +#define DX(dir) ( (dir)==L ? -1 : (dir)==R ? +1 : 0) +#define DY(dir) ( (dir)==U ? -1 : (dir)==D ? +1 : 0) + +/* + * Perform a breadth-first search over a grid of squares with the + * colour of square (X,Y) given by grid[Y*w+X]. The search begins + * at (x,y), and finds all squares which are the same colour as + * (x,y) and reachable from it by orthogonal moves. On return: + * - dist[Y*w+X] gives the distance of (X,Y) from (x,y), or -1 if + * unreachable or a different colour + * - the returned value is the number of reachable squares, + * including (x,y) itself + * - list[0] up to list[returned value - 1] list those squares, in + * increasing order of distance from (x,y) (and in arbitrary + * order within that). + */ +static int bfs(int w, int h, int *grid, int x, int y, int *dist, int *list) +{ + int i, j, c, listsize, listdone; + + /* + * Start by clearing the output arrays. + */ + for (i = 0; i < w*h; i++) + dist[i] = list[i] = -1; + + /* + * Set up the initial list. + */ + listsize = 1; + listdone = 0; + list[0] = y*w+x; + dist[y*w+x] = 0; + c = grid[y*w+x]; + + /* + * Repeatedly process a square and add any extra squares to the + * end of list. + */ + while (listdone < listsize) { + i = list[listdone++]; + y = i / w; + x = i % w; + for (j = 0; j < 4; j++) { + int xx, yy, ii; + + xx = x + DX(j); + yy = y + DY(j); + ii = yy*w+xx; + + if (xx >= 0 && xx < w && yy >= 0 && yy < h && + grid[ii] == c && dist[ii] == -1) { + dist[ii] = dist[i] + 1; + assert(listsize < w*h); + list[listsize++] = ii; + } + } + } + + return listsize; +} + +struct genctx { + int w, h; + int *grid, *sparegrid, *sparegrid2, *sparegrid3; + int *dist, *list; + + int npaths, pathsize; + int *pathends, *sparepathends; /* 2*npaths entries */ + int *pathspare; /* npaths entries */ + int *extends; /* 8*npaths entries */ +}; + +static struct genctx *new_genctx(int w, int h) +{ + struct genctx *ctx = snew(struct genctx); + ctx->w = w; + ctx->h = h; + ctx->grid = snewn(w * h, int); + ctx->sparegrid = snewn(w * h, int); + ctx->sparegrid2 = snewn(w * h, int); + ctx->sparegrid3 = snewn(w * h, int); + ctx->dist = snewn(w * h, int); + ctx->list = snewn(w * h, int); + ctx->npaths = ctx->pathsize = 0; + ctx->pathends = ctx->sparepathends = ctx->pathspare = ctx->extends = NULL; + return ctx; +} + +static void free_genctx(struct genctx *ctx) +{ + sfree(ctx->grid); + sfree(ctx->sparegrid); + sfree(ctx->sparegrid2); + sfree(ctx->sparegrid3); + sfree(ctx->dist); + sfree(ctx->list); + sfree(ctx->pathends); + sfree(ctx->sparepathends); + sfree(ctx->pathspare); + sfree(ctx->extends); +} + +static int newpath(struct genctx *ctx) +{ + int n; + + n = ctx->npaths++; + if (ctx->npaths > ctx->pathsize) { + ctx->pathsize += 16; + ctx->pathends = sresize(ctx->pathends, ctx->pathsize*2, int); + ctx->sparepathends = sresize(ctx->sparepathends, ctx->pathsize*2, int); + ctx->pathspare = sresize(ctx->pathspare, ctx->pathsize, int); + ctx->extends = sresize(ctx->extends, ctx->pathsize*8, int); + } + return n; +} + +static int is_endpoint(struct genctx *ctx, int x, int y) +{ + int w = ctx->w, h = ctx->h, c; + + assert(x >= 0 && x < w && y >= 0 && y < h); + + c = ctx->grid[y*w+x]; + if (c < 0) + return false; /* empty square is not an endpoint! */ + assert(c >= 0 && c < ctx->npaths); + if (ctx->pathends[c*2] == y*w+x || ctx->pathends[c*2+1] == y*w+x) + return true; + return false; +} + +/* + * Tries to extend a path by one square in the given direction, + * pushing other paths around if necessary. Returns true on success + * or false on failure. + */ +static int extend_path(struct genctx *ctx, int path, int end, int direction) +{ + int w = ctx->w, h = ctx->h; + int x, y, xe, ye, cut; + int i, j, jp, n, first, last; + + assert(path >= 0 && path < ctx->npaths); + assert(end == 0 || end == 1); + + /* + * Find the endpoint of the path and the point we plan to + * extend it into. + */ + y = ctx->pathends[path * 2 + end] / w; + x = ctx->pathends[path * 2 + end] % w; + assert(x >= 0 && x < w && y >= 0 && y < h); + + xe = x + DX(direction); + ye = y + DY(direction); + if (xe < 0 || xe >= w || ye < 0 || ye >= h) + return false; /* could not extend in this direction */ + + /* + * We don't extend paths _directly_ into endpoints of other + * paths, although we don't mind too much if a knock-on effect + * of an extension is to push part of another path into a third + * path's endpoint. + */ + if (is_endpoint(ctx, xe, ye)) + return false; + + /* + * We can't extend a path back the way it came. + */ + if (ctx->grid[ye*w+xe] == path) + return false; + + /* + * Paths may not double back on themselves. Check if the new + * point is adjacent to any point of this path other than (x,y). + */ + for (j = 0; j < 4; j++) { + int xf, yf; + + xf = xe + DX(j); + yf = ye + DY(j); + + if (xf >= 0 && xf < w && yf >= 0 && yf < h && + (xf != x || yf != y) && ctx->grid[yf*w+xf] == path) + return false; + } + + /* + * Now we're convinced it's valid to _attempt_ the extension. + * It may still fail if we run out of space to push other paths + * into. + * + * So now we can set up our temporary data structures. We will + * need: + * + * - a spare copy of the grid on which to gradually move paths + * around (sparegrid) + * + * - a second spare copy with which to remember how paths + * looked just before being cut (sparegrid2). FIXME: is + * sparegrid2 necessary? right now it's never different from + * grid itself + * + * - a third spare copy with which to do the internal + * calculations involved in reconstituting a cut path + * (sparegrid3) + * + * - something to track which paths currently need + * reconstituting after being cut, and which have already + * been cut (pathspare) + * + * - a spare copy of pathends to store the altered states in + * (sparepathends) + */ + memcpy(ctx->sparegrid, ctx->grid, w*h*sizeof(int)); + memcpy(ctx->sparegrid2, ctx->grid, w*h*sizeof(int)); + memcpy(ctx->sparepathends, ctx->pathends, ctx->npaths*2*sizeof(int)); + for (i = 0; i < ctx->npaths; i++) + ctx->pathspare[i] = 0; /* 0=untouched, 1=broken, 2=fixed */ + + /* + * Working in sparegrid, actually extend the path. If it cuts + * another, begin a loop in which we restore any cut path by + * moving it out of the way. + */ + cut = ctx->sparegrid[ye*w+xe]; + ctx->sparegrid[ye*w+xe] = path; + ctx->sparepathends[path*2+end] = ye*w+xe; + ctx->pathspare[path] = 2; /* this one is sacrosanct */ + if (cut >= 0) { + assert(cut >= 0 && cut < ctx->npaths); + ctx->pathspare[cut] = 1; /* broken */ + + while (1) { + for (i = 0; i < ctx->npaths; i++) + if (ctx->pathspare[i] == 1) + break; + if (i == ctx->npaths) + break; /* we're done */ + + /* + * Path i needs restoring. So walk along its original + * track (as given in sparegrid2) and see where it's + * been cut. Where it has, surround the cut points in + * the same colour, without overwriting already-fixed + * paths. + */ + memcpy(ctx->sparegrid3, ctx->sparegrid, w*h*sizeof(int)); + n = bfs(w, h, ctx->sparegrid2, + ctx->pathends[i*2] % w, ctx->pathends[i*2] / w, + ctx->dist, ctx->list); + first = last = -1; +if (ctx->sparegrid3[ctx->pathends[i*2]] != i || + ctx->sparegrid3[ctx->pathends[i*2+1]] != i) return false;/* FIXME */ + for (j = 0; j < n; j++) { + jp = ctx->list[j]; + assert(ctx->dist[jp] == j); + assert(ctx->sparegrid2[jp] == i); + + /* + * Wipe out the original path in sparegrid. + */ + if (ctx->sparegrid[jp] == i) + ctx->sparegrid[jp] = -1; + + /* + * Be prepared to shorten the path at either end if + * the endpoints have been stomped on. + */ + if (ctx->sparegrid3[jp] == i) { + if (first < 0) + first = jp; + last = jp; + } + + if (ctx->sparegrid3[jp] != i) { + int jx = jp % w, jy = jp / w; + int dx, dy; + for (dy = -1; dy <= +1; dy++) + for (dx = -1; dx <= +1; dx++) { + int newp, newv; + if (!dy && !dx) + continue; /* central square */ + if (jx+dx < 0 || jx+dx >= w || + jy+dy < 0 || jy+dy >= h) + continue; /* out of range */ + newp = (jy+dy)*w+(jx+dx); + newv = ctx->sparegrid3[newp]; + if (newv >= 0 && (newv == i || + ctx->pathspare[newv] == 2)) + continue; /* can't use this square */ + ctx->sparegrid3[newp] = i; + } + } + } + + if (first < 0 || last < 0) + return false; /* path is completely wiped out! */ + + /* + * Now we've covered sparegrid3 in possible squares for + * the new layout of path i. Find the actual layout + * we're going to use by bfs: we want the shortest path + * from one endpoint to the other. + */ + n = bfs(w, h, ctx->sparegrid3, first % w, first / w, + ctx->dist, ctx->list); + if (ctx->dist[last] < 2) { + /* + * Either there is no way to get between the path's + * endpoints, or the remaining endpoints simply + * aren't far enough apart to make the path viable + * any more. This means the entire push operation + * has failed. + */ + return false; + } + + /* + * Write the new path into sparegrid. Also save the new + * endpoint locations, in case they've changed. + */ + jp = last; + j = ctx->dist[jp]; + while (1) { + int d; + + if (ctx->sparegrid[jp] >= 0) { + if (ctx->pathspare[ctx->sparegrid[jp]] == 2) + return false; /* somehow we've hit a fixed path */ + ctx->pathspare[ctx->sparegrid[jp]] = 1; /* broken */ + } + ctx->sparegrid[jp] = i; + + if (j == 0) + break; + + /* + * Now look at the neighbours of jp to find one + * which has dist[] one less. + */ + for (d = 0; d < 4; d++) { + int jx = (jp % w) + DX(d), jy = (jp / w) + DY(d); + if (jx >= 0 && jx < w && jy >= 0 && jy < w && + ctx->dist[jy*w+jx] == j-1) { + jp = jy*w+jx; + j--; + break; + } + } + assert(d < 4); + } + + ctx->sparepathends[i*2] = first; + ctx->sparepathends[i*2+1] = last; +/* printf("new ends of path %d: %d,%d\n", i, first, last); */ + ctx->pathspare[i] = 2; /* fixed */ + } + } + + /* + * If we got here, the extension was successful! + */ + memcpy(ctx->grid, ctx->sparegrid, w*h*sizeof(int)); + memcpy(ctx->pathends, ctx->sparepathends, ctx->npaths*2*sizeof(int)); + return true; +} + +/* + * Tries to add a new path to the grid. + */ +static int add_path(struct genctx *ctx, random_state *rs) +{ + int w = ctx->w, h = ctx->h; + int i, ii, n; + + /* + * Our strategy is: + * - randomly choose an empty square in the grid + * - do a BFS from that point to find a long path starting + * from it + * - if we run out of viable empty squares, return failure. + */ + + /* + * Use `sparegrid' to collect a list of empty squares. + */ + n = 0; + for (i = 0; i < w*h; i++) + if (ctx->grid[i] == -1) + ctx->sparegrid[n++] = i; + + /* + * Shuffle the grid. + */ + for (i = n; i-- > 1 ;) { + int k = random_upto(rs, i+1); + if (k != i) { + int t = ctx->sparegrid[i]; + ctx->sparegrid[i] = ctx->sparegrid[k]; + ctx->sparegrid[k] = t; + } + } + + /* + * Loop over it trying to add paths. This looks like a + * horrifying N^4 algorithm (that is, (w*h)^2), but I predict + * that in fact the worst case will very rarely arise because + * when there's lots of grid space an attempt will succeed very + * quickly. + */ + for (ii = 0; ii < n; ii++) { + int i = ctx->sparegrid[ii]; + int y = i / w, x = i % w, nsq; + int r, c, j; + + /* + * BFS from here to find long paths. + */ + nsq = bfs(w, h, ctx->grid, x, y, ctx->dist, ctx->list); + + /* + * If there aren't any long enough, give up immediately. + */ + assert(nsq > 0); /* must be the start square at least! */ + if (ctx->dist[ctx->list[nsq-1]] < 3) + continue; + + /* + * Find the first viable endpoint in ctx->list (i.e. the + * first point with distance at least three). I could + * binary-search for this, but that would be O(log N) + * whereas in fact I can get a constant time bound by just + * searching up from the start - after all, there can be at + * most 13 points at _less_ than distance 3 from the + * starting one! + */ + for (j = 0; j < nsq; j++) + if (ctx->dist[ctx->list[j]] >= 3) + break; + assert(j < nsq); /* we tested above that there was one */ + + /* + * Now we know that any element of `list' between j and nsq + * would be valid in principle. However, we want a few long + * paths rather than many small ones, so select only those + * elements which are either the maximum length or one + * below it. + */ + while (ctx->dist[ctx->list[j]] + 1 < ctx->dist[ctx->list[nsq-1]]) + j++; + r = j + random_upto(rs, nsq - j); + j = ctx->list[r]; + + /* + * And that's our endpoint. Mark the new path on the grid. + */ + c = newpath(ctx); + ctx->pathends[c*2] = i; + ctx->pathends[c*2+1] = j; + ctx->grid[j] = c; + while (j != i) { + int d, np, index, pts[4]; + np = 0; + for (d = 0; d < 4; d++) { + int xn = (j % w) + DX(d), yn = (j / w) + DY(d); + if (xn >= 0 && xn < w && yn >= 0 && yn < w && + ctx->dist[yn*w+xn] == ctx->dist[j] - 1) + pts[np++] = yn*w+xn; + } + if (np > 1) + index = random_upto(rs, np); + else + index = 0; + j = pts[index]; + ctx->grid[j] = c; + } + + return true; + } + + return false; +} + +/* + * The main grid generation loop. + */ +static void gridgen_mainloop(struct genctx *ctx, random_state *rs) +{ + int w = ctx->w, h = ctx->h; + int i, n; + + /* + * The generation algorithm doesn't always converge. Loop round + * until it does. + */ + while (1) { + for (i = 0; i < w*h; i++) + ctx->grid[i] = -1; + ctx->npaths = 0; + + while (1) { + /* + * See if the grid is full. + */ + for (i = 0; i < w*h; i++) + if (ctx->grid[i] < 0) + break; + if (i == w*h) + return; + +#ifdef GENERATION_DIAGNOSTICS + { + int x, y; + for (y = 0; y < h; y++) { + printf("|"); + for (x = 0; x < w; x++) { + if (ctx->grid[y*w+x] >= 0) + printf("%2d", ctx->grid[y*w+x]); + else + printf(" ."); + } + printf(" |\n"); + } + } +#endif + /* + * Try adding a path. + */ + if (add_path(ctx, rs)) { +#ifdef GENERATION_DIAGNOSTICS + printf("added path\n"); +#endif + continue; + } + + /* + * Try extending a path. First list all the possible + * extensions. + */ + for (i = 0; i < ctx->npaths * 8; i++) + ctx->extends[i] = i; + n = i; + + /* + * Then shuffle the list. + */ + for (i = n; i-- > 1 ;) { + int k = random_upto(rs, i+1); + if (k != i) { + int t = ctx->extends[i]; + ctx->extends[i] = ctx->extends[k]; + ctx->extends[k] = t; + } + } + + /* + * Now try each one in turn until one works. + */ + for (i = 0; i < n; i++) { + int p, d, e; + p = ctx->extends[i]; + d = p % 4; + p /= 4; + e = p % 2; + p /= 2; + +#ifdef GENERATION_DIAGNOSTICS + printf("trying to extend path %d end %d (%d,%d) in dir %d\n", p, e, + ctx->pathends[p*2+e] % w, + ctx->pathends[p*2+e] / w, d); +#endif + if (extend_path(ctx, p, e, d)) { +#ifdef GENERATION_DIAGNOSTICS + printf("extended path %d end %d (%d,%d) in dir %d\n", p, e, + ctx->pathends[p*2+e] % w, + ctx->pathends[p*2+e] / w, d); +#endif + break; + } + } + + if (i < n) + continue; + + break; + } + } +} + +/* + * Wrapper function which deals with the boring bits such as + * removing the solution from the generated grid, shuffling the + * numeric labels and creating/disposing of the context structure. + */ +static int *gridgen(int w, int h, random_state *rs) +{ + struct genctx *ctx; + int *ret; + int i; + + ctx = new_genctx(w, h); + + gridgen_mainloop(ctx, rs); + + /* + * There is likely to be an ordering bias in the numbers + * (longer paths on lower numbers due to there having been more + * grid space when laying them down). So we must shuffle the + * numbers. We use ctx->pathspare for this. + * + * This is also as good a time as any to shift to numbering + * from 1, for display to the user. + */ + for (i = 0; i < ctx->npaths; i++) + ctx->pathspare[i] = i+1; + for (i = ctx->npaths; i-- > 1 ;) { + int k = random_upto(rs, i+1); + if (k != i) { + int t = ctx->pathspare[i]; + ctx->pathspare[i] = ctx->pathspare[k]; + ctx->pathspare[k] = t; + } + } + + /* FIXME: remove this at some point! */ + { + int y, x; + for (y = 0; y < h; y++) { + printf("|"); + for (x = 0; x < w; x++) { + assert(ctx->grid[y*w+x] >= 0); + printf("%2d", ctx->pathspare[ctx->grid[y*w+x]]); + } + printf(" |\n"); + } + printf("\n"); + } + + /* + * Clear the grid, and write in just the endpoints. + */ + for (i = 0; i < w*h; i++) + ctx->grid[i] = 0; + for (i = 0; i < ctx->npaths; i++) { + ctx->grid[ctx->pathends[i*2]] = + ctx->grid[ctx->pathends[i*2+1]] = ctx->pathspare[i]; + } + + ret = ctx->grid; + ctx->grid = NULL; + + free_genctx(ctx); + + return ret; +} + +#ifdef TEST_GEN + +#define TEST_GENERAL + +int main(void) +{ + int w = 10, h = 8; + random_state *rs = random_new("12345", 5); + int x, y, i, *grid; + + for (i = 0; i < 10; i++) { + grid = gridgen(w, h, rs); + + for (y = 0; y < h; y++) { + printf("|"); + for (x = 0; x < w; x++) { + if (grid[y*w+x] > 0) + printf("%2d", grid[y*w+x]); + else + printf(" ."); + } + printf(" |\n"); + } + printf("\n"); + + sfree(grid); + } + + return 0; +} +#endif diff --git a/apps/plugins/puzzles/src/unfinished/separate.c b/apps/plugins/puzzles/src/unfinished/separate.c new file mode 100644 index 0000000000..6ca07252ad --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/separate.c @@ -0,0 +1,861 @@ +/* + * separate.c: Implementation of `Block Puzzle', a Japanese-only + * Nikoli puzzle seen at + * http://www.nikoli.co.jp/ja/puzzles/block_puzzle/ + * + * It's difficult to be absolutely sure of the rules since online + * Japanese translators are so bad, but looking at the sample + * puzzle it seems fairly clear that the rules of this one are + * very simple. You have an mxn grid in which every square + * contains a letter, there are k distinct letters with k dividing + * mn, and every letter occurs the same number of times; your aim + * is to find a partition of the grid into disjoint k-ominoes such + * that each k-omino contains exactly one of each letter. + * + * (It may be that Nikoli always have m,n,k equal to one another. + * However, I don't see that that's critical to the puzzle; k|mn + * is the only really important constraint, and even that could + * probably be dispensed with if some squares were marked as + * unused.) + */ + +/* + * Current status: only the solver/generator is yet written, and + * although working in principle it's _very_ slow. It generates + * 5x5n5 or 6x6n4 readily enough, 6x6n6 with a bit of effort, and + * 7x7n7 only with a serious strain. I haven't dared try it higher + * than that yet. + * + * One idea to speed it up is to implement more of the solver. + * Ideas I've so far had include: + * + * - Generalise the deduction currently expressed as `an + * undersized chain with only one direction to extend must take + * it'. More generally, the deduction should say `if all the + * possible k-ominoes containing a given chain also contain + * square x, then mark square x as part of that k-omino'. + * + For example, consider this case: + * + * a ? b This represents the top left of a board; the letters + * ? ? ? a,b,c do not represent the letters used in the puzzle, + * c ? ? but indicate that those three squares are known to be + * of different ominoes. Now if k >= 4, we can immediately + * deduce that the square midway between b and c belongs to the + * same omino as a, because there is no way we can make a 4-or- + * more-omino containing a which does not also contain that square. + * (Most easily seen by imagining cutting that square out of the + * grid; then, clearly, the omino containing a has only two + * squares to expand into, and needs at least three.) + * + * The key difficulty with this mode of reasoning is + * identifying such squares. I can't immediately think of a + * simple algorithm for finding them on a wholesale basis. + * + * - Bfs out from a chain looking for the letters it lacks. For + * example, in this situation (top three rows of a 7x7n7 grid): + * + * +-----------+-+ + * |E-A-F-B-C D|D| + * +------- || + * |E-C-G-D G|G E| + * +-+--- | + * |E|E G A B F A| + * + * In this situation we can be sure that the top left chain + * E-A-F-B-C does extend rightwards to the D, because there is + * no other D within reach of that chain. Note also that the + * bfs can skip squares which are known to belong to other + * ominoes than this one. + * + * (This deduction, I fear, should only be used in an + * emergency, because it relies on _all_ squares within range + * of the bfs having particular values and so using it during + * incremental generation rather nails down a lot of the grid.) + * + * It's conceivable that another thing we could do would be to + * increase the flexibility in the grid generator: instead of + * nailing down the _value_ of any square depended on, merely nail + * down its equivalence to other squares. Unfortunately this turns + * the letter-selection phase of generation into a general graph + * colouring problem (we must draw a graph with equivalence + * classes of squares as the vertices, and an edge between any two + * vertices representing equivalence classes which contain squares + * that share an omino, and then k-colour the result) and hence + * requires recursion, which bodes ill for something we're doing + * that many times per generation. + * + * I suppose a simple thing I could try would be tuning the retry + * count, just in case it's set too high or too low for efficient + * generation. + */ + +#include +#include +#include +#include +#include +#ifdef NO_TGMATH_H +# include +#else +# include +#endif + +#include "puzzles.h" + +enum { + COL_BACKGROUND, + NCOLOURS +}; + +struct game_params { + int w, h, k; +}; + +struct game_state { + int FIXME; +}; + +static game_params *default_params(void) +{ + game_params *ret = snew(game_params); + + ret->w = ret->h = ret->k = 5; /* FIXME: a bit bigger? */ + + return ret; +} + +static bool game_fetch_preset(int i, char **name, game_params **params) +{ + return false; +} + +static void free_params(game_params *params) +{ + sfree(params); +} + +static game_params *dup_params(const game_params *params) +{ + game_params *ret = snew(game_params); + *ret = *params; /* structure copy */ + return ret; +} + +static void decode_params(game_params *params, char const *string) +{ + params->w = params->h = params->k = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + if (*string == 'x') { + string++; + params->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + } + if (*string == 'n') { + string++; + params->k = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + } +} + +static char *encode_params(const game_params *params, bool full) +{ + char buf[256]; + sprintf(buf, "%dx%dn%d", params->w, params->h, params->k); + return dupstr(buf); +} + +static config_item *game_configure(const game_params *params) +{ + return NULL; +} + +static game_params *custom_params(const config_item *cfg) +{ + return NULL; +} + +static const char *validate_params(const game_params *params, bool full) +{ + return NULL; +} + +/* ---------------------------------------------------------------------- + * Solver and generator. + */ + +struct solver_scratch { + int w, h, k; + + /* + * Tracks connectedness between squares. + */ + DSF *dsf; + + /* + * size[dsf_canonify(dsf, yx)] tracks the size of the + * connected component containing yx. + */ + int *size; + + /* + * contents[dsf_canonify(dsf, yx)*k+i] tracks whether or not + * the connected component containing yx includes letter i. If + * the value is -1, it doesn't; otherwise its value is the + * index in the main grid of the square which contributes that + * letter to the component. + */ + int *contents; + + /* + * disconnect[dsf_canonify(dsf, yx1)*w*h + dsf_canonify(dsf, yx2)] + * tracks whether or not the connected components containing + * yx1 and yx2 are known to be distinct. + */ + bool *disconnect; + + /* + * Temporary space used only inside particular solver loops. + */ + int *tmp; +}; + +static struct solver_scratch *solver_scratch_new(int w, int h, int k) +{ + int wh = w*h; + struct solver_scratch *sc = snew(struct solver_scratch); + + sc->w = w; + sc->h = h; + sc->k = k; + + sc->dsf = dsf_new(wh); + sc->size = snewn(wh, int); + sc->contents = snewn(wh * k, int); + sc->disconnect = snewn(wh*wh, bool); + sc->tmp = snewn(wh, int); + + return sc; +} + +static void solver_scratch_free(struct solver_scratch *sc) +{ + dsf_free(sc->dsf); + sfree(sc->size); + sfree(sc->contents); + sfree(sc->disconnect); + sfree(sc->tmp); + sfree(sc); +} + +static void solver_connect(struct solver_scratch *sc, int yx1, int yx2) +{ + int w = sc->w, h = sc->h, k = sc->k; + int wh = w*h; + int i, yxnew; + + yx1 = dsf_canonify(sc->dsf, yx1); + yx2 = dsf_canonify(sc->dsf, yx2); + assert(yx1 != yx2); + + /* + * To connect two components together into a bigger one, we + * start by merging them in the dsf itself. + */ + dsf_merge(sc->dsf, yx1, yx2); + yxnew = dsf_canonify(sc->dsf, yx2); + + /* + * The size of the new component is the sum of the sizes of the + * old ones. + */ + sc->size[yxnew] = sc->size[yx1] + sc->size[yx2]; + + /* + * The contents bitmap of the new component is the union of the + * contents of the old ones. + * + * Given two numbers at most one of which is not -1, we can + * find the other one by adding the two and adding 1; this + * will yield -1 if both were -1 to begin with, otherwise the + * other. + * + * (A neater approach would be to take their bitwise AND, but + * this is unfortunately not well-defined standard C when done + * to signed integers.) + */ + for (i = 0; i < k; i++) { + assert(sc->contents[yx1*k+i] < 0 || sc->contents[yx2*k+i] < 0); + sc->contents[yxnew*k+i] = (sc->contents[yx1*k+i] + + sc->contents[yx2*k+i] + 1); + } + + /* + * We must combine the rows _and_ the columns in the disconnect + * matrix. + */ + for (i = 0; i < wh; i++) + sc->disconnect[yxnew*wh+i] = (sc->disconnect[yx1*wh+i] || + sc->disconnect[yx2*wh+i]); + for (i = 0; i < wh; i++) + sc->disconnect[i*wh+yxnew] = (sc->disconnect[i*wh+yx1] || + sc->disconnect[i*wh+yx2]); +} + +static void solver_disconnect(struct solver_scratch *sc, int yx1, int yx2) +{ + int w = sc->w, h = sc->h; + int wh = w*h; + + yx1 = dsf_canonify(sc->dsf, yx1); + yx2 = dsf_canonify(sc->dsf, yx2); + assert(yx1 != yx2); + assert(!sc->disconnect[yx1*wh+yx2]); + assert(!sc->disconnect[yx2*wh+yx1]); + + /* + * Mark the components as disconnected from each other in the + * disconnect matrix. + */ + sc->disconnect[yx1*wh+yx2] = true; + sc->disconnect[yx2*wh+yx1] = true; +} + +static void solver_init(struct solver_scratch *sc) +{ + int w = sc->w, h = sc->h; + int wh = w*h; + int i; + + /* + * Set up most of the scratch space. We don't set up the + * contents array, however, because this will change if we + * adjust the letter arrangement and re-run the solver. + */ + dsf_reinit(sc->dsf); + for (i = 0; i < wh; i++) sc->size[i] = 1; + memset(sc->disconnect, 0, wh*wh * sizeof(bool)); +} + +static int solver_attempt(struct solver_scratch *sc, const unsigned char *grid, + bool *gen_lock) +{ + int w = sc->w, h = sc->h, k = sc->k; + int wh = w*h; + int i, x, y; + bool done_something_overall = false; + + /* + * Set up the contents array from the grid. + */ + for (i = 0; i < wh*k; i++) + sc->contents[i] = -1; + for (i = 0; i < wh; i++) + sc->contents[dsf_canonify(sc->dsf, i)*k+grid[i]] = i; + + while (1) { + bool done_something = false; + + /* + * Go over the grid looking for reasons to add to the + * disconnect matrix. We're after pairs of squares which: + * + * - are adjacent in the grid + * - belong to distinct dsf components + * - their components are not already marked as + * disconnected + * - their components share a letter in common. + */ + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + int dir; + for (dir = 0; dir < 2; dir++) { + int x2 = x + dir, y2 = y + 1 - dir; + int yx = y*w+x, yx2 = y2*w+x2; + + if (x2 >= w || y2 >= h) + continue; /* one square is outside the grid */ + + yx = dsf_canonify(sc->dsf, yx); + yx2 = dsf_canonify(sc->dsf, yx2); + if (yx == yx2) + continue; /* same dsf component */ + + if (sc->disconnect[yx*wh+yx2]) + continue; /* already known disconnected */ + + for (i = 0; i < k; i++) + if (sc->contents[yx*k+i] >= 0 && + sc->contents[yx2*k+i] >= 0) + break; + if (i == k) + continue; /* no letter in common */ + + /* + * We've found one. Mark yx and yx2 as + * disconnected from each other. + */ +#ifdef SOLVER_DIAGNOSTICS + printf("Disconnecting %d and %d (%c)\n", yx, yx2, 'A'+i); +#endif + solver_disconnect(sc, yx, yx2); + done_something = done_something_overall = true; + + /* + * We have just made a deduction which hinges + * on two particular grid squares being the + * same. If we are feeding back to a generator + * loop, we must therefore mark those squares + * as fixed in the generator, so that future + * rearrangement of the grid will not break + * the information on which we have already + * based deductions. + */ + if (gen_lock) { + gen_lock[sc->contents[yx*k+i]] = true; + gen_lock[sc->contents[yx2*k+i]] = true; + } + } + } + } + + /* + * Now go over the grid looking for dsf components which + * are below maximum size and only have one way to extend, + * and extending them. + */ + for (i = 0; i < wh; i++) + sc->tmp[i] = -1; + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + int yx = dsf_canonify(sc->dsf, y*w+x); + int dir; + + if (sc->size[yx] == k) + continue; + + for (dir = 0; dir < 4; dir++) { + int x2 = x + (dir==0 ? -1 : dir==2 ? 1 : 0); + int y2 = y + (dir==1 ? -1 : dir==3 ? 1 : 0); + int yx2, yx2c; + + if (y2 < 0 || y2 >= h || x2 < 0 || x2 >= w) + continue; + yx2 = y2*w+x2; + yx2c = dsf_canonify(sc->dsf, yx2); + + if (yx2c != yx && !sc->disconnect[yx2c*wh+yx]) { + /* + * Component yx can be extended into square + * yx2. + */ + if (sc->tmp[yx] == -1) + sc->tmp[yx] = yx2; + else if (sc->tmp[yx] != yx2) + sc->tmp[yx] = -2; /* multiple choices found */ + } + } + } + } + for (i = 0; i < wh; i++) { + if (sc->tmp[i] >= 0) { + /* + * Make sure we haven't connected the two already + * during this loop (which could happen if for + * _both_ components this was the only way to + * extend them). + */ + if (dsf_canonify(sc->dsf, i) == + dsf_canonify(sc->dsf, sc->tmp[i])) + continue; + +#ifdef SOLVER_DIAGNOSTICS + printf("Connecting %d and %d\n", i, sc->tmp[i]); +#endif + solver_connect(sc, i, sc->tmp[i]); + done_something = done_something_overall = true; + break; + } + } + + if (!done_something) + break; + } + + /* + * Return 0 if we haven't made any progress; 1 if we've done + * something but not solved it completely; 2 if we've solved + * it completely. + */ + for (i = 0; i < wh; i++) + if (sc->size[dsf_canonify(sc->dsf, i)] != k) + break; + if (i == wh) + return 2; + if (done_something_overall) + return 1; + return 0; +} + +static unsigned char *generate(int w, int h, int k, random_state *rs) +{ + int wh = w*h; + int n = wh/k; + struct solver_scratch *sc; + unsigned char *grid; + unsigned char *shuffled; + int i, j, m, retries; + int *permutation; + bool *gen_lock; + + sc = solver_scratch_new(w, h, k); + grid = snewn(wh, unsigned char); + shuffled = snewn(k, unsigned char); + permutation = snewn(wh, int); + gen_lock = snewn(wh, bool); + + do { + DSF *dsf = divvy_rectangle(w, h, k, rs); + + /* + * Go through the dsf and find the indices of all the + * squares involved in each omino, in a manner conducive + * to per-omino indexing. We set permutation[i*k+j] to be + * the index of the jth square (ordered arbitrarily) in + * omino i. + */ + for (i = j = 0; i < wh; i++) + if (dsf_canonify(dsf, i) == i) { + sc->tmp[i] = j; + /* + * During this loop and the following one, we use + * the last element of each row of permutation[] + * as a counter of the number of indices so far + * placed in it. When we place the final index of + * an omino, that counter is overwritten, but that + * doesn't matter because we'll never use it + * again. Of course this depends critically on + * divvy_rectangle() having returned correct + * results, or else chaos would ensue. + */ + permutation[j*k+k-1] = 0; + j++; + } + for (i = 0; i < wh; i++) { + j = sc->tmp[dsf_canonify(dsf, i)]; + m = permutation[j*k+k-1]++; + permutation[j*k+m] = i; + } + + /* + * Track which squares' letters we have already depended + * on for deductions. This is gradually updated by + * solver_attempt(). + */ + memset(gen_lock, 0, wh * sizeof(bool)); + + /* + * Now repeatedly fill the grid with letters, and attempt + * to solve it. If the solver makes progress but does not + * fail completely, then gen_lock will have been updated + * and we try again. On a complete failure, though, we + * have no option but to give up and abandon this set of + * ominoes. + */ + solver_init(sc); + retries = k*k; + while (1) { + /* + * Fill the grid with letters. We can safely use + * sc->tmp to hold the set of letters required at each + * stage, since it's at least size k and is currently + * unused. + */ + for (i = 0; i < n; i++) { + /* + * First, determine the set of letters already + * placed in this omino by gen_lock. + */ + for (j = 0; j < k; j++) + sc->tmp[j] = j; + for (j = 0; j < k; j++) { + int index = permutation[i*k+j]; + int letter = grid[index]; + if (gen_lock[index]) + sc->tmp[letter] = -1; + } + /* + * Now collect together all the remaining letters + * and randomly shuffle them. + */ + for (j = m = 0; j < k; j++) + if (sc->tmp[j] >= 0) + sc->tmp[m++] = sc->tmp[j]; + shuffle(sc->tmp, m, sizeof(*sc->tmp), rs); + /* + * Finally, write the shuffled letters into the + * grid. + */ + for (j = 0; j < k; j++) { + int index = permutation[i*k+j]; + if (!gen_lock[index]) + grid[index] = sc->tmp[--m]; + } + assert(m == 0); + } + + /* + * Now we have a candidate grid. Attempt to progress + * the solution. + */ + m = solver_attempt(sc, grid, gen_lock); + if (m == 2 || /* success */ + (m == 0 && retries-- <= 0)) /* failure */ + break; + if (m == 1) + retries = k*k; /* reset this counter, and continue */ + } + + dsf_free(dsf); + } while (m == 0); + + sfree(gen_lock); + sfree(permutation); + sfree(shuffled); + solver_scratch_free(sc); + + return grid; +} + +/* ---------------------------------------------------------------------- + * End of solver/generator code. + */ + +static char *new_game_desc(const game_params *params, random_state *rs, + char **aux, bool interactive) +{ + int w = params->w, h = params->h, wh = w*h, k = params->k; + unsigned char *grid; + char *desc; + int i; + + grid = generate(w, h, k, rs); + + desc = snewn(wh+1, char); + for (i = 0; i < wh; i++) + desc[i] = 'A' + grid[i]; + desc[wh] = '\0'; + + sfree(grid); + + return desc; +} + +static const char *validate_desc(const game_params *params, const char *desc) +{ + return NULL; +} + +static game_state *new_game(midend *me, const game_params *params, + const char *desc) +{ + game_state *state = snew(game_state); + + state->FIXME = 0; + + return state; +} + +static game_state *dup_game(const game_state *state) +{ + game_state *ret = snew(game_state); + + ret->FIXME = state->FIXME; + + return ret; +} + +static void free_game(game_state *state) +{ + sfree(state); +} + +static char *solve_game(const game_state *state, const game_state *currstate, + const char *aux, const char **error) +{ + return NULL; +} + +static bool game_can_format_as_text_now(const game_params *params) +{ + return true; +} + +static char *game_text_format(const game_state *state) +{ + return NULL; +} + +static game_ui *new_ui(const game_state *state) +{ + return NULL; +} + +static void free_ui(game_ui *ui) +{ +} + +static void game_changed_state(game_ui *ui, const game_state *oldstate, + const game_state *newstate) +{ +} + +struct game_drawstate { + int tilesize; + int FIXME; +}; + +static char *interpret_move(const game_state *state, game_ui *ui, + const game_drawstate *ds, + int x, int y, int button) +{ + return NULL; +} + +static game_state *execute_move(const game_state *state, const char *move) +{ + return NULL; +} + +/* ---------------------------------------------------------------------- + * Drawing routines. + */ + +static void game_compute_size(const game_params *params, int tilesize, + const game_ui *ui, int *x, int *y) +{ + *x = *y = 10 * tilesize; /* FIXME */ +} + +static void game_set_size(drawing *dr, game_drawstate *ds, + const game_params *params, int tilesize) +{ + ds->tilesize = tilesize; +} + +static float *game_colours(frontend *fe, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + + frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); + + *ncolours = NCOLOURS; + return ret; +} + +static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) +{ + struct game_drawstate *ds = snew(struct game_drawstate); + + ds->tilesize = 0; + ds->FIXME = 0; + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds); +} + +static void game_redraw(drawing *dr, game_drawstate *ds, + const game_state *oldstate, const game_state *state, + int dir, const game_ui *ui, + float animtime, float flashtime) +{ +} + +static float game_anim_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + return 0.0F; +} + +static float game_flash_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + return 0.0F; +} + +static void game_get_cursor_location(const game_ui *ui, + const game_drawstate *ds, + const game_state *state, + const game_params *params, + int *x, int *y, int *w, int *h) +{ +} + +static int game_status(const game_state *state) +{ + return 0; +} + +static bool game_timing_state(const game_state *state, game_ui *ui) +{ + return true; +} + +static void game_print_size(const game_params *params, const game_ui *ui, + float *x, float *y) +{ +} + +static void game_print(drawing *dr, const game_state *state, const game_ui *ui, + int tilesize) +{ +} + +#ifdef COMBINED +#define thegame separate +#endif + +const struct game thegame = { + "Separate", NULL, NULL, + default_params, + game_fetch_preset, NULL, + decode_params, + encode_params, + free_params, + dup_params, + false, game_configure, custom_params, + validate_params, + new_game_desc, + validate_desc, + new_game, + dup_game, + free_game, + false, solve_game, + false, game_can_format_as_text_now, game_text_format, + NULL, NULL, /* get_prefs, set_prefs */ + new_ui, + free_ui, + NULL, /* encode_ui */ + NULL, /* decode_ui */ + NULL, /* game_request_keys */ + game_changed_state, + NULL, /* current_key_label */ + interpret_move, + execute_move, + 20 /* FIXME */, game_compute_size, game_set_size, + game_colours, + game_new_drawstate, + game_free_drawstate, + game_redraw, + game_anim_length, + game_flash_length, + game_get_cursor_location, + game_status, + false, false, game_print_size, game_print, + false, /* wants_statusbar */ + false, game_timing_state, + 0, /* flags */ +}; diff --git a/apps/plugins/puzzles/src/unfinished/slide.c b/apps/plugins/puzzles/src/unfinished/slide.c new file mode 100644 index 0000000000..4c4d98943e --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/slide.c @@ -0,0 +1,2444 @@ +/* + * slide.c: Implementation of the block-sliding puzzle `Klotski'. + */ + +/* + * TODO: + * + * - Improve the generator. + * * actually, we seem to be mostly sensible already now. I + * want more choice over the type of main block and location + * of the exit/target, and I think I probably ought to give + * up on compactness and just bite the bullet and have the + * target area right outside the main wall, but mostly I + * think it's OK. + * * the move limit tends to make the game _slower_ to + * generate, which is odd. Perhaps investigate why. + * + * - Improve the graphics. + * * All the colours are a bit wishy-washy. _Some_ dark + * colours would surely not be excessive? Probably darken + * the tiles, the walls and the main block, and leave the + * target marker pale. + * * The cattle grid effect is still disgusting. Think of + * something completely different. + * * The highlight for next-piece-to-move in the solver is + * excessive, and the shadow blends in too well with the + * piece lowlights. Adjust both. + */ + +#include +#include +#include +#include +#include +#ifdef NO_TGMATH_H +# include +#else +# include +#endif + +#include "puzzles.h" +#include "tree234.h" + +/* + * The implementation of this game revolves around the insight + * which makes an exhaustive-search solver feasible: although + * there are many blocks which can be rearranged in many ways, any + * two blocks of the same shape are _indistinguishable_ and hence + * the number of _distinct_ board layouts is generally much + * smaller. So we adopt a representation for board layouts which + * is inherently canonical, i.e. there are no two distinct + * representations which encode indistinguishable layouts. + * + * The way we do this is to encode each square of the board, in + * the normal left-to-right top-to-bottom order, as being one of + * the following things: + * - the first square (in the given order) of a block (`anchor') + * - special case of the above: the anchor for the _main_ block + * (i.e. the one which the aim of the game is to get to the + * target position) + * - a subsequent square of a block whose previous square was N + * squares ago + * - an impassable wall + * + * (We also separately store data about which board positions are + * forcefields only passable by the main block. We can't encode + * that in the main board data, because then the main block would + * destroy forcefields as it went over them.) + * + * Hence, for example, a 2x2 square block would be encoded as + * ANCHOR, followed by DIST(1), and w-2 squares later on there + * would be DIST(w-1) followed by DIST(1). So if you start at the + * last of those squares, the DIST numbers give you a linked list + * pointing back through all the other squares in the same block. + * + * So the solver simply does a bfs over all reachable positions, + * encoding them in this format and storing them in a tree234 to + * ensure it doesn't ever revisit an already-analysed position. + */ + +enum { + /* + * The colours are arranged here so that every base colour is + * directly followed by its highlight colour and then its + * lowlight colour. Do not break this, or draw_tile() will get + * confused. + */ + COL_BACKGROUND, + COL_HIGHLIGHT, + COL_LOWLIGHT, + COL_DRAGGING, + COL_DRAGGING_HIGHLIGHT, + COL_DRAGGING_LOWLIGHT, + COL_MAIN, + COL_MAIN_HIGHLIGHT, + COL_MAIN_LOWLIGHT, + COL_MAIN_DRAGGING, + COL_MAIN_DRAGGING_HIGHLIGHT, + COL_MAIN_DRAGGING_LOWLIGHT, + COL_TARGET, + COL_TARGET_HIGHLIGHT, + COL_TARGET_LOWLIGHT, + NCOLOURS +}; + +/* + * Board layout is a simple array of bytes. Each byte holds: + */ +#define ANCHOR 255 /* top-left-most square of some piece */ +#define MAINANCHOR 254 /* anchor of _main_ piece */ +#define EMPTY 253 /* empty square */ +#define WALL 252 /* immovable wall */ +#define MAXDIST 251 +/* all other values indicate distance back to previous square of same block */ +#define ISDIST(x) ( (unsigned char)((x)-1) <= MAXDIST-1 ) +#define DIST(x) (x) +#define ISANCHOR(x) ( (x)==ANCHOR || (x)==MAINANCHOR ) +#define ISBLOCK(x) ( ISANCHOR(x) || ISDIST(x) ) + +/* + * MAXDIST is the largest DIST value we can encode. This must + * therefore also be the maximum puzzle width in theory (although + * solver running time will dictate a much smaller limit in + * practice). + */ +#define MAXWID MAXDIST + +struct game_params { + int w, h; + int maxmoves; +}; + +struct game_immutable_state { + int refcount; + bool *forcefield; +}; + +struct game_solution { + int nmoves; + int *moves; /* just like from solve_board() */ + int refcount; +}; + +struct game_state { + int w, h; + unsigned char *board; + int tx, ty; /* target coords for MAINANCHOR */ + int minmoves; /* for display only */ + int lastmoved, lastmoved_pos; /* for move counting */ + int movecount; + int completed; + bool cheated; + struct game_immutable_state *imm; + struct game_solution *soln; + int soln_index; +}; + +static game_params *default_params(void) +{ + game_params *ret = snew(game_params); + + ret->w = 7; + ret->h = 6; + ret->maxmoves = 40; + + return ret; +} + +static const struct game_params slide_presets[] = { + {7, 6, 25}, + {7, 6, -1}, + {8, 6, -1}, +}; + +static bool game_fetch_preset(int i, char **name, game_params **params) +{ + game_params *ret; + char str[80]; + + if (i < 0 || i >= lenof(slide_presets)) + return false; + + ret = snew(game_params); + *ret = slide_presets[i]; + + sprintf(str, "%dx%d", ret->w, ret->h); + if (ret->maxmoves >= 0) + sprintf(str + strlen(str), ", max %d moves", ret->maxmoves); + else + sprintf(str + strlen(str), ", no move limit"); + + *name = dupstr(str); + *params = ret; + return true; +} + +static void free_params(game_params *params) +{ + sfree(params); +} + +static game_params *dup_params(const game_params *params) +{ + game_params *ret = snew(game_params); + *ret = *params; /* structure copy */ + return ret; +} + +static void decode_params(game_params *params, char const *string) +{ + params->w = params->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + if (*string == 'x') { + string++; + params->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + } + if (*string == 'm') { + string++; + params->maxmoves = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + } else if (*string == 'u') { + string++; + params->maxmoves = -1; + } +} + +static char *encode_params(const game_params *params, bool full) +{ + char data[256]; + + sprintf(data, "%dx%d", params->w, params->h); + if (params->maxmoves >= 0) + sprintf(data + strlen(data), "m%d", params->maxmoves); + else + sprintf(data + strlen(data), "u"); + + return dupstr(data); +} + +static config_item *game_configure(const game_params *params) +{ + config_item *ret; + char buf[80]; + + ret = snewn(4, config_item); + + ret[0].name = "Width"; + ret[0].type = C_STRING; + sprintf(buf, "%d", params->w); + ret[0].u.string.sval = dupstr(buf); + + ret[1].name = "Height"; + ret[1].type = C_STRING; + sprintf(buf, "%d", params->h); + ret[1].u.string.sval = dupstr(buf); + + ret[2].name = "Solution length limit"; + ret[2].type = C_STRING; + sprintf(buf, "%d", params->maxmoves); + ret[2].u.string.sval = dupstr(buf); + + ret[3].name = NULL; + ret[3].type = C_END; + + return ret; +} + +static game_params *custom_params(const config_item *cfg) +{ + game_params *ret = snew(game_params); + + ret->w = atoi(cfg[0].u.string.sval); + ret->h = atoi(cfg[1].u.string.sval); + ret->maxmoves = atoi(cfg[2].u.string.sval); + + return ret; +} + +static const char *validate_params(const game_params *params, bool full) +{ + if (params->w > MAXWID) + return "Width must be at most " STR(MAXWID); + + if (params->w < 5) + return "Width must be at least 5"; + if (params->h < 4) + return "Height must be at least 4"; + + return NULL; +} + +static char *board_text_format(int w, int h, unsigned char *data, + bool *forcefield) +{ + int wh = w*h; + DSF *dsf = dsf_new(wh); + int i, x, y; + int retpos, retlen = (w*2+2)*(h*2+1)+1; + char *ret = snewn(retlen, char); + + for (i = 0; i < wh; i++) + if (ISDIST(data[i])) + dsf_merge(dsf, i - data[i], i); + retpos = 0; + for (y = 0; y < 2*h+1; y++) { + for (x = 0; x < 2*w+1; x++) { + int v; + int i = (y/2)*w+(x/2); + +#define dtype(i) (ISBLOCK(data[i]) ? \ + dsf_canonify(dsf, i) : data[i]) +#define dchar(t) ((t)==EMPTY ? ' ' : (t)==WALL ? '#' : \ + data[t] == MAINANCHOR ? '*' : '%') + + if (y % 2 && x % 2) { + int j = dtype(i); + v = dchar(j); + } else if (y % 2 && !(x % 2)) { + int j1 = (x > 0 ? dtype(i-1) : -1); + int j2 = (x < 2*w ? dtype(i) : -1); + if (j1 != j2) + v = '|'; + else + v = dchar(j1); + } else if (!(y % 2) && (x % 2)) { + int j1 = (y > 0 ? dtype(i-w) : -1); + int j2 = (y < 2*h ? dtype(i) : -1); + if (j1 != j2) + v = '-'; + else + v = dchar(j1); + } else { + int j1 = (x > 0 && y > 0 ? dtype(i-w-1) : -1); + int j2 = (x > 0 && y < 2*h ? dtype(i-1) : -1); + int j3 = (x < 2*w && y > 0 ? dtype(i-w) : -1); + int j4 = (x < 2*w && y < 2*h ? dtype(i) : -1); + if (j1 == j2 && j2 == j3 && j3 == j4) + v = dchar(j1); + else if (j1 == j2 && j3 == j4) + v = '|'; + else if (j1 == j3 && j2 == j4) + v = '-'; + else + v = '+'; + } + + assert(retpos < retlen); + ret[retpos++] = v; + } + assert(retpos < retlen); + ret[retpos++] = '\n'; + } + assert(retpos < retlen); + ret[retpos++] = '\0'; + assert(retpos == retlen); + + return ret; +} + +/* ---------------------------------------------------------------------- + * Solver. + */ + +/* + * During solver execution, the set of visited board positions is + * stored as a tree234 of the following structures. `w', `h' and + * `data' are obvious in meaning; `dist' represents the minimum + * distance to reach this position from the starting point. + * + * `prev' links each board to the board position from which it was + * most efficiently derived. + */ +struct board { + int w, h; + int dist; + struct board *prev; + unsigned char *data; +}; + +static int boardcmp(void *av, void *bv) +{ + struct board *a = (struct board *)av; + struct board *b = (struct board *)bv; + return memcmp(a->data, b->data, a->w * a->h); +} + +static struct board *newboard(int w, int h, unsigned char *data) +{ + struct board *b = malloc(sizeof(struct board) + w*h); + b->data = (unsigned char *)b + sizeof(struct board); + memcpy(b->data, data, w*h); + b->w = w; + b->h = h; + b->dist = -1; + b->prev = NULL; + return b; +} + +/* + * The actual solver. Given a board, attempt to find the minimum + * length of move sequence which moves MAINANCHOR to (tx,ty), or + * -1 if no solution exists. Returns that minimum length. + * + * Also, if `moveout' is provided, writes out the moves in the + * form of a sequence of pairs of integers indicating the source + * and destination points of the anchor of the moved piece in each + * move. Exactly twice as many integers are written as the number + * returned from solve_board(), and `moveout' receives an int * + * which is a pointer to a dynamically allocated array. + */ +static int solve_board(int w, int h, unsigned char *board, + bool *forcefield, int tx, int ty, + int movelimit, int **moveout) +{ + int wh = w*h; + struct board *b, *b2, *b3; + int *next, *which; + bool *anchors, *movereached; + int *movequeue, mqhead, mqtail; + tree234 *sorted, *queue; + int i, j, dir; + int qlen, lastdist; + int ret; + +#ifdef SOLVER_DIAGNOSTICS + { + char *t = board_text_format(w, h, board); + for (i = 0; i < h; i++) { + for (j = 0; j < w; j++) { + int c = board[i*w+j]; + if (ISDIST(c)) + printf("D%-3d", c); + else if (c == MAINANCHOR) + printf("M "); + else if (c == ANCHOR) + printf("A "); + else if (c == WALL) + printf("W "); + else if (c == EMPTY) + printf("E "); + } + printf("\n"); + } + + printf("Starting solver for:\n%s\n", t); + sfree(t); + } +#endif + + sorted = newtree234(boardcmp); + queue = newtree234(NULL); + + b = newboard(w, h, board); + b->dist = 0; + add234(sorted, b); + addpos234(queue, b, 0); + qlen = 1; + + next = snewn(wh, int); + anchors = snewn(wh, bool); + which = snewn(wh, int); + movereached = snewn(wh, bool); + movequeue = snewn(wh, int); + lastdist = -1; + + while ((b = delpos234(queue, 0)) != NULL) { + qlen--; + if (movelimit >= 0 && b->dist >= movelimit) { + /* + * The problem is not soluble in under `movelimit' + * moves, so we can quit right now. + */ + b2 = NULL; + goto done; + } + if (b->dist != lastdist) { +#ifdef SOLVER_DIAGNOSTICS + printf("dist %d (%d)\n", b->dist, count234(sorted)); +#endif + lastdist = b->dist; + } + /* + * Find all the anchors and form a linked list of the + * squares within each block. + */ + for (i = 0; i < wh; i++) { + next[i] = -1; + anchors[i] = false; + which[i] = -1; + if (ISANCHOR(b->data[i])) { + anchors[i] = true; + which[i] = i; + } else if (ISDIST(b->data[i])) { + j = i - b->data[i]; + next[j] = i; + which[i] = which[j]; + } + } + + /* + * For each anchor, do an array-based BFS to find all the + * places we can slide it to. + */ + for (i = 0; i < wh; i++) { + if (!anchors[i]) + continue; + + mqhead = mqtail = 0; + for (j = 0; j < wh; j++) + movereached[j] = false; + movequeue[mqtail++] = i; + while (mqhead < mqtail) { + int pos = movequeue[mqhead++]; + + /* + * Try to move in each direction from here. + */ + for (dir = 0; dir < 4; dir++) { + int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0); + int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0); + int offset = dy*w + dx; + int newpos = pos + offset; + int d = newpos - i; + + /* + * For each square involved in this block, + * check to see if the square d spaces away + * from it is either empty or part of the same + * block. + */ + for (j = i; j >= 0; j = next[j]) { + int jy = (pos+j-i) / w + dy, jx = (pos+j-i) % w + dx; + if (jy >= 0 && jy < h && jx >= 0 && jx < w && + ((b->data[j+d] == EMPTY || which[j+d] == i) && + (b->data[i] == MAINANCHOR || !forcefield[j+d]))) + /* ok */; + else + break; + } + if (j >= 0) + continue; /* this direction wasn't feasible */ + + /* + * If we've already tried moving this piece + * here, leave it. + */ + if (movereached[newpos]) + continue; + movereached[newpos] = true; + movequeue[mqtail++] = newpos; + + /* + * We have a viable move. Make it. + */ + b2 = newboard(w, h, b->data); + for (j = i; j >= 0; j = next[j]) + b2->data[j] = EMPTY; + for (j = i; j >= 0; j = next[j]) + b2->data[j+d] = b->data[j]; + + b3 = add234(sorted, b2); + if (b3 != b2) { + sfree(b2); /* we already got one */ + } else { + b2->dist = b->dist + 1; + b2->prev = b; + addpos234(queue, b2, qlen++); + if (b2->data[ty*w+tx] == MAINANCHOR) + goto done; /* search completed! */ + } + } + } + } + } + b2 = NULL; + + done: + + if (b2) { + ret = b2->dist; + if (moveout) { + /* + * Now b2 represents the solved position. Backtrack to + * output the solution. + */ + *moveout = snewn(ret * 2, int); + j = ret * 2; + + while (b2->prev) { + int from = -1, to = -1; + + b = b2->prev; + + /* + * Scan b and b2 to find out which piece has + * moved. + */ + for (i = 0; i < wh; i++) { + if (ISANCHOR(b->data[i]) && !ISANCHOR(b2->data[i])) { + assert(from == -1); + from = i; + } else if (!ISANCHOR(b->data[i]) && ISANCHOR(b2->data[i])){ + assert(to == -1); + to = i; + } + } + + assert(from >= 0 && to >= 0); + assert(j >= 2); + (*moveout)[--j] = to; + (*moveout)[--j] = from; + + b2 = b; + } + assert(j == 0); + } + } else { + ret = -1; /* no solution */ + if (moveout) + *moveout = NULL; + } + + freetree234(queue); + + while ((b = delpos234(sorted, 0)) != NULL) + sfree(b); + freetree234(sorted); + + sfree(next); + sfree(anchors); + sfree(movereached); + sfree(movequeue); + sfree(which); + + return ret; +} + +/* ---------------------------------------------------------------------- + * Random board generation. + */ + +static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves, + random_state *rs, unsigned char **rboard, + bool **rforcefield, int movelimit) +{ + int wh = w*h; + unsigned char *board, *board2; + bool *forcefield; + bool *tried_merge; + DSF *dsf; + int *list, nlist, pos; + int tx, ty; + int i, j; + int moves = 0; /* placate optimiser */ + + /* + * Set up a board and fill it with singletons, except for a + * border of walls. + */ + board = snewn(wh, unsigned char); + forcefield = snewn(wh, bool); + board2 = snewn(wh, unsigned char); + memset(board, ANCHOR, wh); + memset(forcefield, 0, wh * sizeof(bool)); + for (i = 0; i < w; i++) + board[i] = board[i+w*(h-1)] = WALL; + for (i = 0; i < h; i++) + board[i*w] = board[i*w+(w-1)] = WALL; + + tried_merge = snewn(wh * wh, bool); + memset(tried_merge, 0, wh*wh * sizeof(bool)); + dsf = dsf_new(wh); + + /* + * Invent a main piece at one extreme. (FIXME: vary the + * extreme, and the piece.) + */ + board[w+1] = MAINANCHOR; + board[w+2] = DIST(1); + board[w*2+1] = DIST(w-1); + board[w*2+2] = DIST(1); + + /* + * Invent a target position. (FIXME: vary this too.) + */ + tx = w-2; + ty = h-3; + forcefield[ty*w+tx+1] = true; + forcefield[(ty+1)*w+tx+1] = true; + board[ty*w+tx+1] = board[(ty+1)*w+tx+1] = EMPTY; + + /* + * Gradually remove singletons until the game becomes soluble. + */ + for (j = w; j-- > 0 ;) + for (i = h; i-- > 0 ;) + if (board[i*w+j] == ANCHOR) { + /* + * See if the board is already soluble. + */ + if ((moves = solve_board(w, h, board, forcefield, + tx, ty, movelimit, NULL)) >= 0) + goto soluble; + + /* + * Otherwise, remove this piece. + */ + board[i*w+j] = EMPTY; + } + assert(!"We shouldn't get here"); + soluble: + + /* + * Make a list of all the inter-block edges on the board. + */ + list = snewn(wh*2, int); + nlist = 0; + for (i = 0; i+1 < w; i++) + for (j = 0; j < h; j++) + list[nlist++] = (j*w+i) * 2 + 0; /* edge to the right of j*w+i */ + for (j = 0; j+1 < h; j++) + for (i = 0; i < w; i++) + list[nlist++] = (j*w+i) * 2 + 1; /* edge below j*w+i */ + + /* + * Now go through that list in random order, trying to merge + * the blocks on each side of each edge. + */ + shuffle(list, nlist, sizeof(*list), rs); + while (nlist > 0) { + int x1, y1, p1, c1; + int x2, y2, p2, c2; + + pos = list[--nlist]; + y1 = y2 = pos / (w*2); + x1 = x2 = (pos / 2) % w; + if (pos % 2) + y2++; + else + x2++; + p1 = y1*w+x1; + p2 = y2*w+x2; + + /* + * Immediately abandon the attempt if we've already tried + * to merge the same pair of blocks along a different + * edge. + */ + c1 = dsf_canonify(dsf, p1); + c2 = dsf_canonify(dsf, p2); + if (tried_merge[c1 * wh + c2]) + continue; + + /* + * In order to be mergeable, these two squares must each + * either be, or belong to, a non-main anchor, and their + * anchors must also be distinct. + */ + if (!ISBLOCK(board[p1]) || !ISBLOCK(board[p2])) + continue; + while (ISDIST(board[p1])) + p1 -= board[p1]; + while (ISDIST(board[p2])) + p2 -= board[p2]; + if (board[p1] == MAINANCHOR || board[p2] == MAINANCHOR || p1 == p2) + continue; + + /* + * We can merge these blocks. Try it, and see if the + * puzzle remains soluble. + */ + memcpy(board2, board, wh); + j = -1; + while (p1 < wh || p2 < wh) { + /* + * p1 and p2 are the squares at the head of each block + * list. Pick the smaller one and put it on the output + * block list. + */ + i = min(p1, p2); + if (j < 0) { + board[i] = ANCHOR; + } else { + assert(i - j <= MAXDIST); + board[i] = DIST(i - j); + } + j = i; + + /* + * Now advance whichever list that came from. + */ + if (i == p1) { + do { + p1++; + } while (p1 < wh && board[p1] != DIST(p1-i)); + } else { + do { + p2++; + } while (p2 < wh && board[p2] != DIST(p2-i)); + } + } + j = solve_board(w, h, board, forcefield, tx, ty, movelimit, NULL); + if (j < 0) { + /* + * Didn't work. Revert the merge. + */ + memcpy(board, board2, wh); + tried_merge[c1 * wh + c2] = true; + tried_merge[c2 * wh + c1] = true; + } else { + int c; + + moves = j; + + dsf_merge(dsf, c1, c2); + c = dsf_canonify(dsf, c1); + for (i = 0; i < wh; i++) + tried_merge[c*wh+i] = (tried_merge[c1*wh+i] || + tried_merge[c2*wh+i]); + for (i = 0; i < wh; i++) + tried_merge[i*wh+c] = (tried_merge[i*wh+c1] || + tried_merge[i*wh+c2]); + } + } + + dsf_free(dsf); + sfree(list); + sfree(tried_merge); + sfree(board2); + + *rtx = tx; + *rty = ty; + *rboard = board; + *rforcefield = forcefield; + *minmoves = moves; +} + +/* ---------------------------------------------------------------------- + * End of solver/generator code. + */ + +static char *new_game_desc(const game_params *params, random_state *rs, + char **aux, bool interactive) +{ + int w = params->w, h = params->h, wh = w*h; + int tx, ty, minmoves; + unsigned char *board; + bool *forcefield; + char *ret, *p; + int i; + + generate_board(params->w, params->h, &tx, &ty, &minmoves, rs, + &board, &forcefield, params->maxmoves); +#ifdef GENERATOR_DIAGNOSTICS + { + char *t = board_text_format(params->w, params->h, board); + printf("%s\n", t); + sfree(t); + } +#endif + + /* + * Encode as a game ID. + */ + ret = snewn(wh * 6 + 40, char); + p = ret; + i = 0; + while (i < wh) { + if (ISDIST(board[i])) { + p += sprintf(p, "d%d", board[i]); + i++; + } else { + int count = 1; + int b = board[i]; + bool f = forcefield[i]; + int c = (b == ANCHOR ? 'a' : + b == MAINANCHOR ? 'm' : + b == EMPTY ? 'e' : + /* b == WALL ? */ 'w'); + if (f) *p++ = 'f'; + *p++ = c; + i++; + while (i < wh && board[i] == b && forcefield[i] == f) + i++, count++; + if (count > 1) + p += sprintf(p, "%d", count); + } + } + p += sprintf(p, ",%d,%d,%d", tx, ty, minmoves); + ret = sresize(ret, p+1 - ret, char); + + sfree(board); + sfree(forcefield); + + return ret; +} + +static const char *validate_desc(const game_params *params, const char *desc) +{ + int w = params->w, h = params->h, wh = w*h; + bool *active; + int *link; + int mains = 0; + int i, tx, ty, minmoves; + const char *ret; + + active = snewn(wh, bool); + link = snewn(wh, int); + i = 0; + + while (*desc && *desc != ',') { + if (i >= wh) { + ret = "Too much data in game description"; + goto done; + } + link[i] = -1; + active[i] = false; + if (*desc == 'f' || *desc == 'F') { + desc++; + if (!*desc) { + ret = "Expected another character after 'f' in game " + "description"; + goto done; + } + } + + if (*desc == 'd' || *desc == 'D') { + int dist; + + desc++; + if (!isdigit((unsigned char)*desc)) { + ret = "Expected a number after 'd' in game description"; + goto done; + } + dist = atoi(desc); + while (*desc && isdigit((unsigned char)*desc)) desc++; + + if (dist <= 0 || dist > i) { + ret = "Out-of-range number after 'd' in game description"; + goto done; + } + + if (!active[i - dist]) { + ret = "Invalid back-reference in game description"; + goto done; + } + + link[i] = i - dist; + + active[i] = true; + active[link[i]] = false; + i++; + } else { + int c = *desc++; + int count = 1; + + if (!strchr("aAmMeEwW", c)) { + ret = "Invalid character in game description"; + goto done; + } + if (isdigit((unsigned char)*desc)) { + count = atoi(desc); + while (*desc && isdigit((unsigned char)*desc)) desc++; + } + if (i + count > wh) { + ret = "Too much data in game description"; + goto done; + } + while (count-- > 0) { + active[i] = (strchr("aAmM", c) != NULL); + link[i] = -1; + if (strchr("mM", c) != NULL) { + mains++; + } + i++; + } + } + } + if (mains != 1) { + ret = (mains == 0 ? "No main piece specified in game description" : + "More than one main piece specified in game description"); + goto done; + } + if (i < wh) { + ret = "Not enough data in game description"; + goto done; + } + + /* + * Now read the target coordinates. + */ + i = sscanf(desc, ",%d,%d,%d", &tx, &ty, &minmoves); + if (i < 2) { + ret = "No target coordinates specified"; + goto done; + /* + * (but minmoves is optional) + */ + } + + ret = NULL; + + done: + sfree(active); + sfree(link); + return ret; +} + +static game_state *new_game(midend *me, const game_params *params, + const char *desc) +{ + int w = params->w, h = params->h, wh = w*h; + game_state *state; + int i; + + state = snew(game_state); + state->w = w; + state->h = h; + state->board = snewn(wh, unsigned char); + state->lastmoved = state->lastmoved_pos = -1; + state->movecount = 0; + state->imm = snew(struct game_immutable_state); + state->imm->refcount = 1; + state->imm->forcefield = snewn(wh, bool); + + i = 0; + + while (*desc && *desc != ',') { + bool f = false; + + assert(i < wh); + + if (*desc == 'f') { + f = true; + desc++; + assert(*desc); + } + + if (*desc == 'd' || *desc == 'D') { + int dist; + + desc++; + dist = atoi(desc); + while (*desc && isdigit((unsigned char)*desc)) desc++; + + state->board[i] = DIST(dist); + state->imm->forcefield[i] = f; + + i++; + } else { + int c = *desc++; + int count = 1; + + if (isdigit((unsigned char)*desc)) { + count = atoi(desc); + while (*desc && isdigit((unsigned char)*desc)) desc++; + } + assert(i + count <= wh); + + c = (c == 'a' || c == 'A' ? ANCHOR : + c == 'm' || c == 'M' ? MAINANCHOR : + c == 'e' || c == 'E' ? EMPTY : + /* c == 'w' || c == 'W' ? */ WALL); + + while (count-- > 0) { + state->board[i] = c; + state->imm->forcefield[i] = f; + i++; + } + } + } + + /* + * Now read the target coordinates. + */ + state->tx = state->ty = 0; + state->minmoves = -1; + i = sscanf(desc, ",%d,%d,%d", &state->tx, &state->ty, &state->minmoves); + + if (state->board[state->ty*w+state->tx] == MAINANCHOR) + state->completed = 0; /* already complete! */ + else + state->completed = -1; + + state->cheated = false; + state->soln = NULL; + state->soln_index = -1; + + return state; +} + +static game_state *dup_game(const game_state *state) +{ + int w = state->w, h = state->h, wh = w*h; + game_state *ret = snew(game_state); + + ret->w = state->w; + ret->h = state->h; + ret->board = snewn(wh, unsigned char); + memcpy(ret->board, state->board, wh); + ret->tx = state->tx; + ret->ty = state->ty; + ret->minmoves = state->minmoves; + ret->lastmoved = state->lastmoved; + ret->lastmoved_pos = state->lastmoved_pos; + ret->movecount = state->movecount; + ret->completed = state->completed; + ret->cheated = state->cheated; + ret->imm = state->imm; + ret->imm->refcount++; + ret->soln = state->soln; + ret->soln_index = state->soln_index; + if (ret->soln) + ret->soln->refcount++; + + return ret; +} + +static void free_game(game_state *state) +{ + if (--state->imm->refcount <= 0) { + sfree(state->imm->forcefield); + sfree(state->imm); + } + if (state->soln && --state->soln->refcount <= 0) { + sfree(state->soln->moves); + sfree(state->soln); + } + sfree(state->board); + sfree(state); +} + +static char *solve_game(const game_state *state, const game_state *currstate, + const char *aux, const char **error) +{ + int *moves; + int nmoves; + int i; + char *ret, *p, sep; + + /* + * Run the solver and attempt to find the shortest solution + * from the current position. + */ + nmoves = solve_board(state->w, state->h, state->board, + state->imm->forcefield, state->tx, state->ty, + -1, &moves); + + if (nmoves < 0) { + *error = "Unable to find a solution to this puzzle"; + return NULL; + } + if (nmoves == 0) { + *error = "Puzzle is already solved"; + return NULL; + } + + /* + * Encode the resulting solution as a move string. + */ + ret = snewn(nmoves * 40, char); + p = ret; + sep = 'S'; + + for (i = 0; i < nmoves; i++) { + p += sprintf(p, "%c%d-%d", sep, moves[i*2], moves[i*2+1]); + sep = ','; + } + + sfree(moves); + assert(p - ret < nmoves * 40); + ret = sresize(ret, p+1 - ret, char); + + return ret; +} + +static bool game_can_format_as_text_now(const game_params *params) +{ + return true; +} + +static char *game_text_format(const game_state *state) +{ + return board_text_format(state->w, state->h, state->board, + state->imm->forcefield); +} + +struct game_ui { + bool dragging; + int drag_anchor; + int drag_offset_x, drag_offset_y; + int drag_currpos; + bool *reachable; + int *bfs_queue; /* used as scratch in interpret_move */ +}; + +static game_ui *new_ui(const game_state *state) +{ + int w = state->w, h = state->h, wh = w*h; + game_ui *ui = snew(game_ui); + + ui->dragging = false; + ui->drag_anchor = ui->drag_currpos = -1; + ui->drag_offset_x = ui->drag_offset_y = -1; + ui->reachable = snewn(wh, bool); + memset(ui->reachable, 0, wh * sizeof(bool)); + ui->bfs_queue = snewn(wh, int); + + return ui; +} + +static void free_ui(game_ui *ui) +{ + sfree(ui->bfs_queue); + sfree(ui->reachable); + sfree(ui); +} + +static void game_changed_state(game_ui *ui, const game_state *oldstate, + const game_state *newstate) +{ +} + +#define PREFERRED_TILESIZE 32 +#define TILESIZE (ds->tilesize) +#define BORDER (TILESIZE/2) +#define COORD(x) ( (x) * TILESIZE + BORDER ) +#define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 ) +#define BORDER_WIDTH (1 + TILESIZE/20) +#define HIGHLIGHT_WIDTH (1 + TILESIZE/16) + +#define FLASH_INTERVAL 0.10F +#define FLASH_TIME 3*FLASH_INTERVAL + +struct game_drawstate { + int tilesize; + int w, h; + unsigned long *grid; /* what's currently displayed */ +}; + +static char *interpret_move(const game_state *state, game_ui *ui, + const game_drawstate *ds, + int x, int y, int button) +{ + int w = state->w, h = state->h, wh = w*h; + int tx, ty, i, j; + int qhead, qtail; + + if (button == LEFT_BUTTON) { + tx = FROMCOORD(x); + ty = FROMCOORD(y); + + if (tx < 0 || tx >= w || ty < 0 || ty >= h || + !ISBLOCK(state->board[ty*w+tx])) + return NULL; /* this click has no effect */ + + /* + * User has clicked on a block. Find the block's anchor + * and register that we've started dragging it. + */ + i = ty*w+tx; + while (ISDIST(state->board[i])) + i -= state->board[i]; + assert(i >= 0 && i < wh); + + ui->dragging = true; + ui->drag_anchor = i; + ui->drag_offset_x = tx - (i % w); + ui->drag_offset_y = ty - (i / w); + ui->drag_currpos = i; + + /* + * Now we immediately bfs out from the current location of + * the anchor, to find all the places to which this block + * can be dragged. + */ + memset(ui->reachable, 0, wh * sizeof(bool)); + qhead = qtail = 0; + ui->reachable[i] = true; + ui->bfs_queue[qtail++] = i; + for (j = i; j < wh; j++) + if (state->board[j] == DIST(j - i)) + i = j; + while (qhead < qtail) { + int pos = ui->bfs_queue[qhead++]; + int x = pos % w, y = pos / w; + int dir; + + for (dir = 0; dir < 4; dir++) { + int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0); + int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0); + int newpos; + + if (x + dx < 0 || x + dx >= w || + y + dy < 0 || y + dy >= h) + continue; + + newpos = pos + dy*w + dx; + if (ui->reachable[newpos]) + continue; /* already done this one */ + + /* + * Now search the grid to see if the block we're + * dragging could fit into this space. + */ + for (j = i; j >= 0; j = (ISDIST(state->board[j]) ? + j - state->board[j] : -1)) { + int jx = (j+pos-ui->drag_anchor) % w; + int jy = (j+pos-ui->drag_anchor) / w; + int j2; + + if (jx + dx < 0 || jx + dx >= w || + jy + dy < 0 || jy + dy >= h) + break; /* this position isn't valid at all */ + + j2 = (j+pos-ui->drag_anchor) + dy*w + dx; + + if (state->board[j2] == EMPTY && + (!state->imm->forcefield[j2] || + state->board[ui->drag_anchor] == MAINANCHOR)) + continue; + while (ISDIST(state->board[j2])) + j2 -= state->board[j2]; + assert(j2 >= 0 && j2 < wh); + if (j2 == ui->drag_anchor) + continue; + else + break; + } + + if (j < 0) { + /* + * If we got to the end of that loop without + * disqualifying this position, mark it as + * reachable for this drag. + */ + ui->reachable[newpos] = true; + ui->bfs_queue[qtail++] = newpos; + } + } + } + + /* + * And that's it. Update the display to reflect the start + * of a drag. + */ + return MOVE_UI_UPDATE; + } else if (button == LEFT_DRAG && ui->dragging) { + int dist, distlimit, dx, dy, s, px, py; + + tx = FROMCOORD(x); + ty = FROMCOORD(y); + + tx -= ui->drag_offset_x; + ty -= ui->drag_offset_y; + + /* + * Now search outwards from (tx,ty), in order of Manhattan + * distance, until we find a reachable square. + */ + distlimit = w+tx; + distlimit = max(distlimit, h+ty); + distlimit = max(distlimit, tx); + distlimit = max(distlimit, ty); + for (dist = 0; dist <= distlimit; dist++) { + for (dx = -dist; dx <= dist; dx++) + for (s = -1; s <= +1; s += 2) { + dy = s * (dist - abs(dx)); + px = tx + dx; + py = ty + dy; + if (px >= 0 && px < w && py >= 0 && py < h && + ui->reachable[py*w+px]) { + ui->drag_currpos = py*w+px; + return MOVE_UI_UPDATE; + } + } + } + return NULL; /* give up - this drag has no effect */ + } else if (button == LEFT_RELEASE && ui->dragging) { + char data[256], *str; + + /* + * Terminate the drag, and if the piece has actually moved + * then return a move string quoting the old and new + * locations of the piece's anchor. + */ + if (ui->drag_anchor != ui->drag_currpos) { + sprintf(data, "M%d-%d", ui->drag_anchor, ui->drag_currpos); + str = dupstr(data); + } else + str = MOVE_UI_UPDATE; + + ui->dragging = false; + ui->drag_anchor = ui->drag_currpos = -1; + ui->drag_offset_x = ui->drag_offset_y = -1; + memset(ui->reachable, 0, wh * sizeof(bool)); + + return str; + } else if (button == ' ' && state->soln) { + /* + * Make the next move in the stored solution. + */ + char data[256]; + int a1, a2; + + a1 = state->soln->moves[state->soln_index*2]; + a2 = state->soln->moves[state->soln_index*2+1]; + if (a1 == state->lastmoved_pos) + a1 = state->lastmoved; + + sprintf(data, "M%d-%d", a1, a2); + return dupstr(data); + } + + return NULL; +} + +static bool move_piece(int w, int h, const unsigned char *src, + unsigned char *dst, bool *ff, int from, int to) +{ + int wh = w*h; + int i, j; + + if (!ISANCHOR(dst[from])) + return false; + + /* + * Scan to the far end of the piece's linked list. + */ + for (i = j = from; j < wh; j++) + if (src[j] == DIST(j - i)) + i = j; + + /* + * Remove the piece from its old location in the new + * game state. + */ + for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1)) + dst[j] = EMPTY; + + /* + * And put it back in at the new location. + */ + for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1)) { + int jn = j + to - from; + if (jn < 0 || jn >= wh) + return false; + if (dst[jn] == EMPTY && (!ff[jn] || src[from] == MAINANCHOR)) { + dst[jn] = src[j]; + } else { + return false; + } + } + + return true; +} + +static game_state *execute_move(const game_state *state, const char *move) +{ + int w = state->w, h = state->h /* , wh = w*h */; + char c; + int a1, a2, n, movesize; + game_state *ret = dup_game(state); + + while (*move) { + c = *move; + if (c == 'S') { + /* + * This is a solve move, so we just set up a stored + * solution path. + */ + if (ret->soln && --ret->soln->refcount <= 0) { + sfree(ret->soln->moves); + sfree(ret->soln); + } + ret->soln = snew(struct game_solution); + ret->soln->nmoves = 0; + ret->soln->moves = NULL; + ret->soln->refcount = 1; + ret->soln_index = 0; + ret->cheated = true; + + movesize = 0; + move++; + while (1) { + if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2) { + free_game(ret); + return NULL; + } + + /* + * Special case: if the first move in the solution + * involves the piece for which we already have a + * partial stored move, adjust the source point to + * the original starting point of that piece. + */ + if (ret->soln->nmoves == 0 && a1 == ret->lastmoved) + a1 = ret->lastmoved_pos; + + if (ret->soln->nmoves >= movesize) { + movesize = (ret->soln->nmoves + 48) * 4 / 3; + ret->soln->moves = sresize(ret->soln->moves, + 2*movesize, int); + } + + ret->soln->moves[2*ret->soln->nmoves] = a1; + ret->soln->moves[2*ret->soln->nmoves+1] = a2; + ret->soln->nmoves++; + move += n; + if (*move != ',') + break; + move++; /* eat comma */ + } + } else if (c == 'M') { + move++; + if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2 || + !move_piece(w, h, state->board, ret->board, + state->imm->forcefield, a1, a2)) { + free_game(ret); + return NULL; + } + if (a1 == ret->lastmoved) { + /* + * If the player has moved the same piece as they + * moved last time, don't increment the move + * count. In fact, if they've put the piece back + * where it started from, _decrement_ the move + * count. + */ + if (a2 == ret->lastmoved_pos) { + ret->movecount--; /* reverted last move */ + ret->lastmoved = ret->lastmoved_pos = -1; + } else { + ret->lastmoved = a2; + /* don't change lastmoved_pos */ + } + } else { + ret->lastmoved = a2; + ret->lastmoved_pos = a1; + ret->movecount++; + } + + /* + * If we have a stored solution path, see if we've + * strayed from it or successfully made the next move + * along it. + */ + if (ret->soln && ret->lastmoved_pos >= 0) { + if (ret->lastmoved_pos != + ret->soln->moves[ret->soln_index*2]) { + /* strayed from the path */ + ret->soln->refcount--; + assert(ret->soln->refcount > 0); + /* `state' at least still exists */ + ret->soln = NULL; + ret->soln_index = -1; + } else if (ret->lastmoved == + ret->soln->moves[ret->soln_index*2+1]) { + /* advanced along the path */ + ret->soln_index++; + if (ret->soln_index >= ret->soln->nmoves) { + /* finished the path! */ + ret->soln->refcount--; + assert(ret->soln->refcount > 0); + /* `state' at least still exists */ + ret->soln = NULL; + ret->soln_index = -1; + } + } + } + + if (ret->board[a2] == MAINANCHOR && + a2 == ret->ty * w + ret->tx && ret->completed < 0) + ret->completed = ret->movecount; + move += n; + } else { + free_game(ret); + return NULL; + } + if (*move == ';') + move++; + else if (*move) { + free_game(ret); + return NULL; + } + } + + return ret; +} + +/* ---------------------------------------------------------------------- + * Drawing routines. + */ + +static void game_compute_size(const game_params *params, int tilesize, + const game_ui *ui, int *x, int *y) +{ + /* fool the macros */ + struct dummy { int tilesize; } dummy, *ds = &dummy; + dummy.tilesize = tilesize; + + *x = params->w * TILESIZE + 2*BORDER; + *y = params->h * TILESIZE + 2*BORDER; +} + +static void game_set_size(drawing *dr, game_drawstate *ds, + const game_params *params, int tilesize) +{ + ds->tilesize = tilesize; +} + +static void raise_colour(float *target, float *src, float *limit) +{ + int i; + for (i = 0; i < 3; i++) + target[i] = (2*src[i] + limit[i]) / 3; +} + +static float *game_colours(frontend *fe, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + + game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT); + + /* + * When dragging a tile, we light it up a bit. + */ + raise_colour(ret+3*COL_DRAGGING, + ret+3*COL_BACKGROUND, ret+3*COL_HIGHLIGHT); + raise_colour(ret+3*COL_DRAGGING_HIGHLIGHT, + ret+3*COL_HIGHLIGHT, ret+3*COL_HIGHLIGHT); + raise_colour(ret+3*COL_DRAGGING_LOWLIGHT, + ret+3*COL_LOWLIGHT, ret+3*COL_HIGHLIGHT); + + /* + * The main tile is tinted blue. + */ + ret[COL_MAIN * 3 + 0] = ret[COL_BACKGROUND * 3 + 0]; + ret[COL_MAIN * 3 + 1] = ret[COL_BACKGROUND * 3 + 1]; + ret[COL_MAIN * 3 + 2] = ret[COL_HIGHLIGHT * 3 + 2]; + game_mkhighlight_specific(fe, ret, COL_MAIN, + COL_MAIN_HIGHLIGHT, COL_MAIN_LOWLIGHT); + + /* + * And we light that up a bit too when dragging. + */ + raise_colour(ret+3*COL_MAIN_DRAGGING, + ret+3*COL_MAIN, ret+3*COL_MAIN_HIGHLIGHT); + raise_colour(ret+3*COL_MAIN_DRAGGING_HIGHLIGHT, + ret+3*COL_MAIN_HIGHLIGHT, ret+3*COL_MAIN_HIGHLIGHT); + raise_colour(ret+3*COL_MAIN_DRAGGING_LOWLIGHT, + ret+3*COL_MAIN_LOWLIGHT, ret+3*COL_MAIN_HIGHLIGHT); + + /* + * The target area on the floor is tinted green. + */ + ret[COL_TARGET * 3 + 0] = ret[COL_BACKGROUND * 3 + 0]; + ret[COL_TARGET * 3 + 1] = ret[COL_HIGHLIGHT * 3 + 1]; + ret[COL_TARGET * 3 + 2] = ret[COL_BACKGROUND * 3 + 2]; + game_mkhighlight_specific(fe, ret, COL_TARGET, + COL_TARGET_HIGHLIGHT, COL_TARGET_LOWLIGHT); + + *ncolours = NCOLOURS; + return ret; +} + +static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) +{ + int w = state->w, h = state->h, wh = w*h; + struct game_drawstate *ds = snew(struct game_drawstate); + int i; + + ds->tilesize = 0; + ds->w = w; + ds->h = h; + ds->grid = snewn(wh, unsigned long); + for (i = 0; i < wh; i++) + ds->grid[i] = ~(unsigned long)0; + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds->grid); + sfree(ds); +} + +#define BG_NORMAL 0x00000001UL +#define BG_TARGET 0x00000002UL +#define BG_FORCEFIELD 0x00000004UL +#define FLASH_LOW 0x00000008UL +#define FLASH_HIGH 0x00000010UL +#define FG_WALL 0x00000020UL +#define FG_MAIN 0x00000040UL +#define FG_NORMAL 0x00000080UL +#define FG_DRAGGING 0x00000100UL +#define FG_SHADOW 0x00000200UL +#define FG_SOLVEPIECE 0x00000400UL +#define FG_MAINPIECESH 11 +#define FG_SHADOWSH 19 + +#define PIECE_LBORDER 0x00000001UL +#define PIECE_TBORDER 0x00000002UL +#define PIECE_RBORDER 0x00000004UL +#define PIECE_BBORDER 0x00000008UL +#define PIECE_TLCORNER 0x00000010UL +#define PIECE_TRCORNER 0x00000020UL +#define PIECE_BLCORNER 0x00000040UL +#define PIECE_BRCORNER 0x00000080UL +#define PIECE_MASK 0x000000FFUL + +/* + * Utility function. + */ +#define TYPE_MASK 0xF000 +#define COL_MASK 0x0FFF +#define TYPE_RECT 0x0000 +#define TYPE_TLCIRC 0x4000 +#define TYPE_TRCIRC 0x5000 +#define TYPE_BLCIRC 0x6000 +#define TYPE_BRCIRC 0x7000 +static void maybe_rect(drawing *dr, int x, int y, int w, int h, + int coltype, int col2) +{ + int colour = coltype & COL_MASK, type = coltype & TYPE_MASK; + + if (colour > NCOLOURS) + return; + if (type == TYPE_RECT) { + draw_rect(dr, x, y, w, h, colour); + } else { + int cx, cy, r; + + clip(dr, x, y, w, h); + + cx = x; + cy = y; + r = w-1; + if (type & 0x1000) + cx += r; + if (type & 0x2000) + cy += r; + + if (col2 == -1 || col2 == coltype) { + assert(w == h); + draw_circle(dr, cx, cy, r, colour, colour); + } else { + /* + * We aim to draw a quadrant of a circle in two + * different colours. We do this using Bresenham's + * algorithm directly, because the Puzzles drawing API + * doesn't have a draw-sector primitive. + */ + int bx, by, bd, bd2; + int xm = (type & 0x1000 ? -1 : +1); + int ym = (type & 0x2000 ? -1 : +1); + + by = r; + bx = 0; + bd = 0; + while (by >= bx) { + /* + * Plot the point. + */ + { + int x1 = cx+xm*bx, y1 = cy+ym*bx; + int x2, y2; + + x2 = cx+xm*by; y2 = y1; + draw_rect(dr, min(x1,x2), min(y1,y2), + abs(x1-x2)+1, abs(y1-y2)+1, colour); + x2 = x1; y2 = cy+ym*by; + draw_rect(dr, min(x1,x2), min(y1,y2), + abs(x1-x2)+1, abs(y1-y2)+1, col2); + } + + bd += 2*bx + 1; + bd2 = bd - (2*by - 1); + if (abs(bd2) < abs(bd)) { + bd = bd2; + by--; + } + bx++; + } + } + + unclip(dr); + } +} + +static void draw_wallpart(drawing *dr, game_drawstate *ds, + int tx, int ty, unsigned long val, + int cl, int cc, int ch) +{ + int coords[6]; + + draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc); + if (val & PIECE_LBORDER) + draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, TILESIZE, + ch); + if (val & PIECE_RBORDER) + draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty, + HIGHLIGHT_WIDTH, TILESIZE, cl); + if (val & PIECE_TBORDER) + draw_rect(dr, tx, ty, TILESIZE, HIGHLIGHT_WIDTH, ch); + if (val & PIECE_BBORDER) + draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH, + TILESIZE, HIGHLIGHT_WIDTH, cl); + if (!((PIECE_BBORDER | PIECE_LBORDER) &~ val)) { + draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH, + HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl); + clip(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH, + HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH); + coords[0] = tx - 1; + coords[1] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1; + coords[2] = tx + HIGHLIGHT_WIDTH; + coords[3] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1; + coords[4] = tx - 1; + coords[5] = ty + TILESIZE; + draw_polygon(dr, coords, 3, ch, ch); + unclip(dr); + } else if (val & PIECE_BLCORNER) { + draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH, + HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch); + clip(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH, + HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH); + coords[0] = tx - 1; + coords[1] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1; + coords[2] = tx + HIGHLIGHT_WIDTH; + coords[3] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1; + coords[4] = tx - 1; + coords[5] = ty + TILESIZE; + draw_polygon(dr, coords, 3, cl, cl); + unclip(dr); + } + if (!((PIECE_TBORDER | PIECE_RBORDER) &~ val)) { + draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty, + HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl); + clip(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty, + HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH); + coords[0] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1; + coords[1] = ty - 1; + coords[2] = tx + TILESIZE; + coords[3] = ty - 1; + coords[4] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1; + coords[5] = ty + HIGHLIGHT_WIDTH; + draw_polygon(dr, coords, 3, ch, ch); + unclip(dr); + } else if (val & PIECE_TRCORNER) { + draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty, + HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch); + clip(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty, + HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH); + coords[0] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1; + coords[1] = ty - 1; + coords[2] = tx + TILESIZE; + coords[3] = ty - 1; + coords[4] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1; + coords[5] = ty + HIGHLIGHT_WIDTH; + draw_polygon(dr, coords, 3, cl, cl); + unclip(dr); + } + if (val & PIECE_TLCORNER) + draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch); + if (val & PIECE_BRCORNER) + draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, + ty+TILESIZE-HIGHLIGHT_WIDTH, + HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl); +} + +static void draw_piecepart(drawing *dr, game_drawstate *ds, + int tx, int ty, unsigned long val, + int cl, int cc, int ch) +{ + int x[6], y[6]; + + /* + * Drawing the blocks is hellishly fiddly. The blocks don't + * stretch to the full size of the tile; there's a border + * around them of size BORDER_WIDTH. Then they have bevelled + * borders of size HIGHLIGHT_WIDTH, and also rounded corners. + * + * I tried for some time to find a clean and clever way to + * figure out what needed drawing from the corner and border + * flags, but in the end the cleanest way I could find was the + * following. We divide the grid square into 25 parts by + * ruling four horizontal and four vertical lines across it; + * those lines are at BORDER_WIDTH and BORDER_WIDTH + + * HIGHLIGHT_WIDTH from the top, from the bottom, from the + * left and from the right. Then we carefully consider each of + * the resulting 25 sections of square, and decide separately + * what needs to go in it based on the flags. In complicated + * cases there can be up to five possibilities affecting any + * given section (no corner or border flags, just the corner + * flag, one border flag, the other border flag, both border + * flags). So there's a lot of very fiddly logic here and all + * I could really think to do was give it my best shot and + * then test it and correct all the typos. Not fun to write, + * and I'm sure it isn't fun to read either, but it seems to + * work. + */ + + x[0] = tx; + x[1] = x[0] + BORDER_WIDTH; + x[2] = x[1] + HIGHLIGHT_WIDTH; + x[5] = tx + TILESIZE; + x[4] = x[5] - BORDER_WIDTH; + x[3] = x[4] - HIGHLIGHT_WIDTH; + + y[0] = ty; + y[1] = y[0] + BORDER_WIDTH; + y[2] = y[1] + HIGHLIGHT_WIDTH; + y[5] = ty + TILESIZE; + y[4] = y[5] - BORDER_WIDTH; + y[3] = y[4] - HIGHLIGHT_WIDTH; + +#define RECT(p,q) x[p], y[q], x[(p)+1]-x[p], y[(q)+1]-y[q] + + maybe_rect(dr, RECT(0,0), + (val & (PIECE_TLCORNER | PIECE_TBORDER | + PIECE_LBORDER)) ? -1 : cc, -1); + maybe_rect(dr, RECT(1,0), + (val & PIECE_TLCORNER) ? ch : (val & PIECE_TBORDER) ? -1 : + (val & PIECE_LBORDER) ? ch : cc, -1); + maybe_rect(dr, RECT(2,0), + (val & PIECE_TBORDER) ? -1 : cc, -1); + maybe_rect(dr, RECT(3,0), + (val & PIECE_TRCORNER) ? cl : (val & PIECE_TBORDER) ? -1 : + (val & PIECE_RBORDER) ? cl : cc, -1); + maybe_rect(dr, RECT(4,0), + (val & (PIECE_TRCORNER | PIECE_TBORDER | + PIECE_RBORDER)) ? -1 : cc, -1); + maybe_rect(dr, RECT(0,1), + (val & PIECE_TLCORNER) ? ch : (val & PIECE_LBORDER) ? -1 : + (val & PIECE_TBORDER) ? ch : cc, -1); + maybe_rect(dr, RECT(1,1), + (val & PIECE_TLCORNER) ? cc : -1, -1); + maybe_rect(dr, RECT(1,1), + (val & PIECE_TLCORNER) ? ch | TYPE_TLCIRC : + !((PIECE_TBORDER | PIECE_LBORDER) &~ val) ? ch | TYPE_BRCIRC : + (val & (PIECE_TBORDER | PIECE_LBORDER)) ? ch : cc, -1); + maybe_rect(dr, RECT(2,1), + (val & PIECE_TBORDER) ? ch : cc, -1); + maybe_rect(dr, RECT(3,1), + (val & PIECE_TRCORNER) ? cc : -1, -1); + maybe_rect(dr, RECT(3,1), + (val & (PIECE_TBORDER | PIECE_RBORDER)) == PIECE_TBORDER ? ch : + (val & (PIECE_TBORDER | PIECE_RBORDER)) == PIECE_RBORDER ? cl : + !((PIECE_TBORDER|PIECE_RBORDER) &~ val) ? cl | TYPE_BLCIRC : + (val & PIECE_TRCORNER) ? cl | TYPE_TRCIRC : + cc, ch); + maybe_rect(dr, RECT(4,1), + (val & PIECE_TRCORNER) ? ch : (val & PIECE_RBORDER) ? -1 : + (val & PIECE_TBORDER) ? ch : cc, -1); + maybe_rect(dr, RECT(0,2), + (val & PIECE_LBORDER) ? -1 : cc, -1); + maybe_rect(dr, RECT(1,2), + (val & PIECE_LBORDER) ? ch : cc, -1); + maybe_rect(dr, RECT(2,2), + cc, -1); + maybe_rect(dr, RECT(3,2), + (val & PIECE_RBORDER) ? cl : cc, -1); + maybe_rect(dr, RECT(4,2), + (val & PIECE_RBORDER) ? -1 : cc, -1); + maybe_rect(dr, RECT(0,3), + (val & PIECE_BLCORNER) ? cl : (val & PIECE_LBORDER) ? -1 : + (val & PIECE_BBORDER) ? cl : cc, -1); + maybe_rect(dr, RECT(1,3), + (val & PIECE_BLCORNER) ? cc : -1, -1); + maybe_rect(dr, RECT(1,3), + (val & (PIECE_BBORDER | PIECE_LBORDER)) == PIECE_BBORDER ? cl : + (val & (PIECE_BBORDER | PIECE_LBORDER)) == PIECE_LBORDER ? ch : + !((PIECE_BBORDER|PIECE_LBORDER) &~ val) ? ch | TYPE_TRCIRC : + (val & PIECE_BLCORNER) ? ch | TYPE_BLCIRC : + cc, cl); + maybe_rect(dr, RECT(2,3), + (val & PIECE_BBORDER) ? cl : cc, -1); + maybe_rect(dr, RECT(3,3), + (val & PIECE_BRCORNER) ? cc : -1, -1); + maybe_rect(dr, RECT(3,3), + (val & PIECE_BRCORNER) ? cl | TYPE_BRCIRC : + !((PIECE_BBORDER | PIECE_RBORDER) &~ val) ? cl | TYPE_TLCIRC : + (val & (PIECE_BBORDER | PIECE_RBORDER)) ? cl : cc, -1); + maybe_rect(dr, RECT(4,3), + (val & PIECE_BRCORNER) ? cl : (val & PIECE_RBORDER) ? -1 : + (val & PIECE_BBORDER) ? cl : cc, -1); + maybe_rect(dr, RECT(0,4), + (val & (PIECE_BLCORNER | PIECE_BBORDER | + PIECE_LBORDER)) ? -1 : cc, -1); + maybe_rect(dr, RECT(1,4), + (val & PIECE_BLCORNER) ? ch : (val & PIECE_BBORDER) ? -1 : + (val & PIECE_LBORDER) ? ch : cc, -1); + maybe_rect(dr, RECT(2,4), + (val & PIECE_BBORDER) ? -1 : cc, -1); + maybe_rect(dr, RECT(3,4), + (val & PIECE_BRCORNER) ? cl : (val & PIECE_BBORDER) ? -1 : + (val & PIECE_RBORDER) ? cl : cc, -1); + maybe_rect(dr, RECT(4,4), + (val & (PIECE_BRCORNER | PIECE_BBORDER | + PIECE_RBORDER)) ? -1 : cc, -1); + +#undef RECT +} + +static void draw_tile(drawing *dr, game_drawstate *ds, + int x, int y, unsigned long val) +{ + int tx = COORD(x), ty = COORD(y); + int cc, ch, cl; + + /* + * Draw the tile background. + */ + if (val & BG_TARGET) + cc = COL_TARGET; + else + cc = COL_BACKGROUND; + ch = cc+1; + cl = cc+2; + if (val & FLASH_LOW) + cc = cl; + else if (val & FLASH_HIGH) + cc = ch; + + draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc); + if (val & BG_FORCEFIELD) { + /* + * Cattle-grid effect to indicate that nothing but the + * main block can slide over this square. + */ + int n = 3 * (TILESIZE / (3*HIGHLIGHT_WIDTH)); + int i; + + for (i = 1; i < n; i += 3) { + draw_rect(dr, tx,ty+(TILESIZE*i/n), TILESIZE,HIGHLIGHT_WIDTH, cl); + draw_rect(dr, tx+(TILESIZE*i/n),ty, HIGHLIGHT_WIDTH,TILESIZE, cl); + } + } + + /* + * Draw the tile midground: a shadow of a block, for + * displaying partial solutions. + */ + if (val & FG_SHADOW) { + draw_piecepart(dr, ds, tx, ty, (val >> FG_SHADOWSH) & PIECE_MASK, + cl, cl, cl); + } + + /* + * Draw the tile foreground, i.e. some section of a block or + * wall. + */ + if (val & FG_WALL) { + cc = COL_BACKGROUND; + ch = cc+1; + cl = cc+2; + if (val & FLASH_LOW) + cc = cl; + else if (val & FLASH_HIGH) + cc = ch; + + draw_wallpart(dr, ds, tx, ty, (val >> FG_MAINPIECESH) & PIECE_MASK, + cl, cc, ch); + } else if (val & (FG_MAIN | FG_NORMAL)) { + if (val & FG_DRAGGING) + cc = (val & FG_MAIN ? COL_MAIN_DRAGGING : COL_DRAGGING); + else + cc = (val & FG_MAIN ? COL_MAIN : COL_BACKGROUND); + ch = cc+1; + cl = cc+2; + + if (val & FLASH_LOW) + cc = cl; + else if (val & (FLASH_HIGH | FG_SOLVEPIECE)) + cc = ch; + + draw_piecepart(dr, ds, tx, ty, (val >> FG_MAINPIECESH) & PIECE_MASK, + cl, cc, ch); + } + + draw_update(dr, tx, ty, TILESIZE, TILESIZE); +} + +static unsigned long find_piecepart(int w, int h, DSF *dsf, int x, int y) +{ + int i = y*w+x; + int canon = dsf_canonify(dsf, i); + unsigned long val = 0; + + if (x == 0 || canon != dsf_canonify(dsf, i-1)) + val |= PIECE_LBORDER; + if (y== 0 || canon != dsf_canonify(dsf, i-w)) + val |= PIECE_TBORDER; + if (x == w-1 || canon != dsf_canonify(dsf, i+1)) + val |= PIECE_RBORDER; + if (y == h-1 || canon != dsf_canonify(dsf, i+w)) + val |= PIECE_BBORDER; + if (!(val & (PIECE_TBORDER | PIECE_LBORDER)) && + canon != dsf_canonify(dsf, i-1-w)) + val |= PIECE_TLCORNER; + if (!(val & (PIECE_TBORDER | PIECE_RBORDER)) && + canon != dsf_canonify(dsf, i+1-w)) + val |= PIECE_TRCORNER; + if (!(val & (PIECE_BBORDER | PIECE_LBORDER)) && + canon != dsf_canonify(dsf, i-1+w)) + val |= PIECE_BLCORNER; + if (!(val & (PIECE_BBORDER | PIECE_RBORDER)) && + canon != dsf_canonify(dsf, i+1+w)) + val |= PIECE_BRCORNER; + return val; +} + +static void game_redraw(drawing *dr, game_drawstate *ds, + const game_state *oldstate, const game_state *state, + int dir, const game_ui *ui, + float animtime, float flashtime) +{ + int w = state->w, h = state->h, wh = w*h; + unsigned char *board; + DSF *dsf; + int x, y, mainanchor, mainpos, dragpos, solvepos, solvesrc, solvedst; + + /* + * Construct the board we'll be displaying (which may be + * different from the one in state if ui describes a drag in + * progress). + */ + board = snewn(wh, unsigned char); + memcpy(board, state->board, wh); + if (ui->dragging) { + bool mpret = move_piece(w, h, state->board, board, + state->imm->forcefield, + ui->drag_anchor, ui->drag_currpos); + assert(mpret); + } + + if (state->soln) { + solvesrc = state->soln->moves[state->soln_index*2]; + solvedst = state->soln->moves[state->soln_index*2+1]; + if (solvesrc == state->lastmoved_pos) + solvesrc = state->lastmoved; + if (solvesrc == ui->drag_anchor) + solvesrc = ui->drag_currpos; + } else + solvesrc = solvedst = -1; + + /* + * Build a dsf out of that board, so we can conveniently tell + * which edges are connected and which aren't. + */ + dsf = dsf_new(wh); + mainanchor = -1; + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + int i = y*w+x; + + if (ISDIST(board[i])) + dsf_merge(dsf, i, i - board[i]); + if (board[i] == MAINANCHOR) + mainanchor = i; + if (board[i] == WALL) { + if (x > 0 && board[i-1] == WALL) + dsf_merge(dsf, i, i-1); + if (y > 0 && board[i-w] == WALL) + dsf_merge(dsf, i, i-w); + } + } + assert(mainanchor >= 0); + mainpos = dsf_canonify(dsf, mainanchor); + dragpos = ui->drag_currpos > 0 ? dsf_canonify(dsf, ui->drag_currpos) : -1; + solvepos = solvesrc >= 0 ? dsf_canonify(dsf, solvesrc) : -1; + + /* + * Now we can construct the data about what we want to draw. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + int i = y*w+x; + int j; + unsigned long val; + int canon; + + /* + * See if this square is part of the target area. + */ + j = i + mainanchor - (state->ty * w + state->tx); + while (j >= 0 && j < wh && ISDIST(board[j])) + j -= board[j]; + if (j == mainanchor) + val = BG_TARGET; + else + val = BG_NORMAL; + + if (state->imm->forcefield[i]) + val |= BG_FORCEFIELD; + + if (flashtime > 0) { + int flashtype = (int)(flashtime / FLASH_INTERVAL) & 1; + val |= (flashtype ? FLASH_LOW : FLASH_HIGH); + } + + if (board[i] != EMPTY) { + canon = dsf_canonify(dsf, i); + + if (board[i] == WALL) + val |= FG_WALL; + else if (canon == mainpos) + val |= FG_MAIN; + else + val |= FG_NORMAL; + if (canon == dragpos) + val |= FG_DRAGGING; + if (canon == solvepos) + val |= FG_SOLVEPIECE; + + /* + * Now look around to see if other squares + * belonging to the same block are adjacent to us. + */ + val |= find_piecepart(w, h, dsf, x, y) << FG_MAINPIECESH; + } + + /* + * If we're in the middle of showing a solution, + * display a shadow piece for the target of the + * current move. + */ + if (solvepos >= 0) { + int si = i - solvedst + solvesrc; + if (si >= 0 && si < wh && dsf_canonify(dsf, si) == solvepos) { + val |= find_piecepart(w, h, dsf, + si % w, si / w) << FG_SHADOWSH; + val |= FG_SHADOW; + } + } + + if (val != ds->grid[i]) { + draw_tile(dr, ds, x, y, val); + ds->grid[i] = val; + } + } + + /* + * Update the status bar. + */ + { + char statusbuf[256]; + + sprintf(statusbuf, "%sMoves: %d", + (state->completed >= 0 ? + (state->cheated ? "Auto-solved. " : "COMPLETED! ") : + (state->cheated ? "Auto-solver used. " : "")), + (state->completed >= 0 ? state->completed : state->movecount)); + if (state->minmoves >= 0) + sprintf(statusbuf+strlen(statusbuf), " (min %d)", + state->minmoves); + + status_bar(dr, statusbuf); + } + + dsf_free(dsf); + sfree(board); +} + +static float game_anim_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + return 0.0F; +} + +static float game_flash_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + if (oldstate->completed < 0 && newstate->completed >= 0) + return FLASH_TIME; + + return 0.0F; +} + +static void game_get_cursor_location(const game_ui *ui, + const game_drawstate *ds, + const game_state *state, + const game_params *params, + int *x, int *y, int *w, int *h) +{ +} + +static int game_status(const game_state *state) +{ + return state->completed ? +1 : 0; +} + +static bool game_timing_state(const game_state *state, game_ui *ui) +{ + return true; +} + +static void game_print_size(const game_params *params, const game_ui *ui, + float *x, float *y) +{ +} + +static void game_print(drawing *dr, const game_state *state, const game_ui *ui, + int tilesize) +{ +} + +#ifdef COMBINED +#define thegame slide +#endif + +const struct game thegame = { + "Slide", NULL, NULL, + default_params, + game_fetch_preset, NULL, + decode_params, + encode_params, + free_params, + dup_params, + true, game_configure, custom_params, + validate_params, + new_game_desc, + validate_desc, + new_game, + dup_game, + free_game, + true, solve_game, + true, game_can_format_as_text_now, game_text_format, + NULL, NULL, /* get_prefs, set_prefs */ + new_ui, + free_ui, + NULL, /* encode_ui */ + NULL, /* decode_ui */ + NULL, /* game_request_keys */ + game_changed_state, + NULL, /* current_key_label */ + interpret_move, + execute_move, + PREFERRED_TILESIZE, game_compute_size, game_set_size, + game_colours, + game_new_drawstate, + game_free_drawstate, + game_redraw, + game_anim_length, + game_flash_length, + game_get_cursor_location, + game_status, + false, false, game_print_size, game_print, + true, /* wants_statusbar */ + false, game_timing_state, + 0, /* flags */ +}; + +#ifdef STANDALONE_SOLVER + +#include + +int main(int argc, char **argv) +{ + game_params *p; + game_state *s; + char *id = NULL, *desc; + const char *err; + bool count = false; + int ret; + int *moves; + + while (--argc > 0) { + char *p = *++argv; + /* + if (!strcmp(p, "-v")) { + verbose = true; + } else + */ + if (!strcmp(p, "-c")) { + count = true; + } else if (*p == '-') { + fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); + return 1; + } else { + id = p; + } + } + + if (!id) { + fprintf(stderr, "usage: %s [-c | -v] \n", argv[0]); + return 1; + } + + desc = strchr(id, ':'); + if (!desc) { + fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); + return 1; + } + *desc++ = '\0'; + + p = default_params(); + decode_params(p, id); + err = validate_desc(p, desc); + if (err) { + fprintf(stderr, "%s: %s\n", argv[0], err); + return 1; + } + s = new_game(NULL, p, desc); + + ret = solve_board(s->w, s->h, s->board, s->imm->forcefield, + s->tx, s->ty, -1, &moves); + if (ret < 0) { + printf("No solution found\n"); + } else { + int index = 0; + if (count) { + printf("%d moves required\n", ret); + return 0; + } + while (1) { + bool moveret; + char *text = board_text_format(s->w, s->h, s->board, + s->imm->forcefield); + game_state *s2; + + printf("position %d:\n%s", index, text); + + if (index >= ret) + break; + + s2 = dup_game(s); + moveret = move_piece(s->w, s->h, s->board, + s2->board, s->imm->forcefield, + moves[index*2], moves[index*2+1]); + assert(moveret); + + free_game(s); + s = s2; + index++; + } + } + + return 0; +} + +#endif diff --git a/apps/plugins/puzzles/src/unfinished/sokoban.c b/apps/plugins/puzzles/src/unfinished/sokoban.c new file mode 100644 index 0000000000..1f3c688af1 --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/sokoban.c @@ -0,0 +1,1476 @@ +/* + * sokoban.c: An implementation of the well-known Sokoban barrel- + * pushing game. Random generation is too simplistic to be + * credible, but the rest of the gameplay works well enough to use + * it with hand-written level descriptions. + */ + +/* + * TODO: + * + * - I think it would be better to ditch the `prev' array, and + * instead make the `dist' array strictly monotonic (by having + * each distance be something like I*A+S, where A is the grid + * area, I the number of INITIAL squares trampled on, and S the + * number of harmless spaces moved through). This would permit + * the path-tracing when a pull is actually made to choose + * randomly from all the possible shortest routes, which would + * be superior in terms of eliminating directional bias. + * + So when tracing the path back to the current px,py, we + * look at all four adjacent squares, find the minimum + * distance, check that it's _strictly smaller_ than that of + * the current square, and restrict our choice to precisely + * those squares with that minimum distance. + * + The other place `prev' is currently used is in the check + * for consistency of a pull. We would have to replace the + * check for whether prev[ny*w+nx]==oy*w+ox with a check that + * made sure there was at least one adjacent square with a + * smaller distance which _wasn't_ oy*w+ox. Then when we did + * the path-tracing we'd also have to take this special case + * into account. + * + * - More discriminating choice of pull. (Snigger.) + * + favour putting targets in clumps + * + try to shoot for a reasonably consistent number of barrels + * (adjust willingness to generate a new barrel depending on + * how many are already present) + * + adjust willingness to break new ground depending on how + * much is already broken + * + * - generation time parameters: + * + enable NetHack mode (and find a better place for the hole) + * + decide how many of the remaining Is should be walls + * + * - at the end of generation, randomly position the starting + * player coordinates, probably by (somehow) reusing the same + * bfs currently inside the loop. + * + * - possible backtracking? + * + * - IWBNI we could spot completely unreachable bits of level at + * the outside, and not bother drawing grid lines for them. The + * NH levels currently look a bit weird with grid lines on the + * outside of the boundary. + */ + +#include +#include +#include +#include +#include +#ifdef NO_TGMATH_H +# include +#else +# include +#endif + +#include "puzzles.h" + +/* + * Various subsets of these constants are used during game + * generation, game play, game IDs and the game_drawstate. + */ +#define INITIAL 'i' /* used only in game generation */ +#define SPACE 's' +#define WALL 'w' +#define PIT 'p' +#define DEEP_PIT 'd' +#define TARGET 't' +#define BARREL 'b' +#define BARRELTARGET 'f' /* target is 'f'illed */ +#define PLAYER 'u' /* yo'u'; used in game IDs */ +#define PLAYERTARGET 'v' /* bad letter: v is to u as t is to s */ +#define INVALID '!' /* used in drawstate to force redraw */ +/* + * We also support the use of any capital letter as a barrel, which + * will be displayed with that letter as a label. (This facilitates + * people distributing annotated game IDs for particular Sokoban + * levels, so they can accompany them with verbal instructions + * about pushing particular barrels in particular ways.) Therefore, + * to find out whether something is a barrel, we need a test + * function which does a bit more than just comparing to BARREL. + * + * When resting on target squares, capital-letter barrels are + * replaced with their control-character value (A -> ^A). + */ +#define IS_PLAYER(c) ( (c)==PLAYER || (c)==PLAYERTARGET ) +#define IS_BARREL(c) ( (c)==BARREL || (c)==BARRELTARGET || \ + ((c)>='A' && (c)<='Z') || ((c)>=1 && (c)<=26) ) +#define IS_ON_TARGET(c) ( (c)==TARGET || (c)==BARRELTARGET || \ + (c)==PLAYERTARGET || ((c)>=1 && (c)<=26) ) +#define TARGETISE(b) ( (b)==BARREL ? BARRELTARGET : (b)-('A'-1) ) +#define DETARGETISE(b) ( (b)==BARRELTARGET ? BARREL : (b)+('A'-1) ) +#define BARREL_LABEL(b) ( (b)>='A'&&(b)<='Z' ? (b) : \ + (b)>=1 && (b)<=26 ? (b)+('A'-1) : 0 ) + +#define DX(d) (d == 0 ? -1 : d == 2 ? +1 : 0) +#define DY(d) (d == 1 ? -1 : d == 3 ? +1 : 0) + +#define FLASH_LENGTH 0.3F + +enum { + COL_BACKGROUND, + COL_TARGET, + COL_PIT, + COL_DEEP_PIT, + COL_BARREL, + COL_PLAYER, + COL_TEXT, + COL_GRID, + COL_OUTLINE, + COL_HIGHLIGHT, + COL_LOWLIGHT, + COL_WALL, + NCOLOURS +}; + +struct game_params { + int w, h; + /* + * FIXME: a parameter involving degree of filling in? + */ +}; + +struct game_state { + game_params p; + unsigned char *grid; + int px, py; + bool completed; +}; + +static game_params *default_params(void) +{ + game_params *ret = snew(game_params); + + ret->w = 12; + ret->h = 10; + + return ret; +} + +static void free_params(game_params *params) +{ + sfree(params); +} + +static game_params *dup_params(const game_params *params) +{ + game_params *ret = snew(game_params); + *ret = *params; /* structure copy */ + return ret; +} + +static const struct game_params sokoban_presets[] = { + { 12, 10 }, + { 16, 12 }, + { 20, 16 }, +}; + +static bool game_fetch_preset(int i, char **name, game_params **params) +{ + game_params p, *ret; + char *retname; + char namebuf[80]; + + if (i < 0 || i >= lenof(sokoban_presets)) + return false; + + p = sokoban_presets[i]; + ret = dup_params(&p); + sprintf(namebuf, "%dx%d", ret->w, ret->h); + retname = dupstr(namebuf); + + *params = ret; + *name = retname; + return true; +} + +static void decode_params(game_params *params, char const *string) +{ + params->w = params->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + if (*string == 'x') { + string++; + params->h = atoi(string); + } +} + +static char *encode_params(const game_params *params, bool full) +{ + char data[256]; + + sprintf(data, "%dx%d", params->w, params->h); + + return dupstr(data); +} + +static config_item *game_configure(const game_params *params) +{ + config_item *ret; + char buf[80]; + + ret = snewn(3, config_item); + + ret[0].name = "Width"; + ret[0].type = C_STRING; + sprintf(buf, "%d", params->w); + ret[0].u.string.sval = dupstr(buf); + + ret[1].name = "Height"; + ret[1].type = C_STRING; + sprintf(buf, "%d", params->h); + ret[1].u.string.sval = dupstr(buf); + + ret[2].name = NULL; + ret[2].type = C_END; + + return ret; +} + +static game_params *custom_params(const config_item *cfg) +{ + game_params *ret = snew(game_params); + + ret->w = atoi(cfg[0].u.string.sval); + ret->h = atoi(cfg[1].u.string.sval); + + return ret; +} + +static const char *validate_params(const game_params *params, bool full) +{ + if (params->w < 4 || params->h < 4) + return "Width and height must both be at least 4"; + + return NULL; +} + +/* ---------------------------------------------------------------------- + * Game generation mechanism. + * + * To generate a Sokoban level, we begin with a completely blank + * grid and make valid inverse moves. Grid squares can be in a + * number of states. The states are: + * + * - INITIAL: this square has not as yet been touched by any + * inverse move, which essentially means we haven't decided what + * it is yet. + * + * - SPACE: this square is a space. + * + * - TARGET: this square is a space which is also the target for a + * barrel. + * + * - BARREL: this square contains a barrel. + * + * - BARRELTARGET: this square contains a barrel _on_ a target. + * + * - WALL: this square is a wall. + * + * - PLAYER: this square contains the player. + * + * - PLAYERTARGET: this square contains the player on a target. + * + * We begin with every square of the in state INITIAL, apart from a + * solid ring of WALLs around the edge. We randomly position the + * PLAYER somewhere. Thereafter our valid moves are: + * + * - to move the PLAYER in one direction _pulling_ a barrel after + * us. For this to work, we must have SPACE or INITIAL in the + * direction we're moving, and BARREL or BARRELTARGET in the + * direction we're moving away from. We leave SPACE or TARGET + * respectively in the vacated square. + * + * - to create a new barrel by transforming an INITIAL square into + * BARRELTARGET. + * + * - to move the PLAYER freely through SPACE and TARGET squares, + * leaving SPACE or TARGET where it started. + * + * - to move the player through INITIAL squares, carving a tunnel + * of SPACEs as it goes. + * + * We try to avoid destroying INITIAL squares wherever possible (if + * there's a path to where we want to be using only SPACE, then we + * should always use that). At the end of generation, every square + * still in state INITIAL is one which was not required at any + * point during generation, which means we can randomly choose + * whether to make it SPACE or WALL. + * + * It's unclear as yet what the right strategy for wall placement + * should be. Too few WALLs will yield many alternative solutions + * to the puzzle, whereas too many might rule out so many + * possibilities that the intended solution becomes obvious. + */ + +static void sokoban_generate(int w, int h, unsigned char *grid, int moves, + bool nethack, random_state *rs) +{ + struct pull { + int ox, oy, nx, ny, score; + }; + + struct pull *pulls; + int *dist, *prev, *heap; + int x, y, px, py, i, j, d, heapsize, npulls; + + pulls = snewn(w * h * 4, struct pull); + dist = snewn(w * h, int); + prev = snewn(w * h, int); + heap = snewn(w * h, int); + + /* + * Configure the initial grid. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) + grid[y*w+x] = (x == 0 || y == 0 || x == w-1 || y == h-1 ? + WALL : INITIAL); + if (nethack) + grid[1] = DEEP_PIT; + + /* + * Place the player. + */ + i = random_upto(rs, (w-2) * (h-2)); + x = 1 + i % (w-2); + y = 1 + i / (w-2); + grid[y*w+x] = SPACE; + px = x; + py = y; + + /* + * Now loop around making random inverse Sokoban moves. In this + * loop we aim to make one actual barrel-pull per iteration, + * plus as many free moves as are necessary to get into + * position for that pull. + */ + while (moves-- >= 0) { + /* + * First enumerate all the viable barrel-pulls we can + * possibly make, counting two pulls of the same barrel in + * different directions as different. We also include pulls + * we can perform by creating a new barrel. Each pull is + * marked with the amount of violence it would have to do + * to the grid. + */ + npulls = 0; + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) + for (d = 0; d < 4; d++) { + int dx = DX(d); + int dy = DY(d); + int nx = x + dx, ny = y + dy; + int npx = nx + dx, npy = ny + dy; + int score = 0; + + /* + * The candidate move is to put the player at + * (nx,ny), and move him to (npx,npy), pulling + * a barrel at (x,y) to (nx,ny). So first we + * must check that all those squares are within + * the boundaries of the grid. For this it is + * sufficient to check npx,npy. + */ + if (npx < 0 || npx >= w || npy < 0 || npy >= h) + continue; + + /* + * (x,y) must either be a barrel, or a square + * which we can convert into a barrel. + */ + switch (grid[y*w+x]) { + case BARREL: case BARRELTARGET: + break; + case INITIAL: + if (nethack) + continue; + score += 10 /* new_barrel_score */; + break; + case DEEP_PIT: + if (!nethack) + continue; + break; + default: + continue; + } + + /* + * (nx,ny) must either be a space, or a square + * which we can convert into a space. + */ + switch (grid[ny*w+nx]) { + case SPACE: case TARGET: + break; + case INITIAL: + score += 3 /* new_space_score */; + break; + default: + continue; + } + + /* + * (npx,npy) must also either be a space, or a + * square which we can convert into a space. + */ + switch (grid[npy*w+npx]) { + case SPACE: case TARGET: + break; + case INITIAL: + score += 3 /* new_space_score */; + break; + default: + continue; + } + + /* + * That's sufficient to tag this as a possible + * pull right now. We still don't know if we + * can reach the required player position, but + * that's a job for the subsequent BFS phase to + * tell us. + */ + pulls[npulls].ox = x; + pulls[npulls].oy = y; + pulls[npulls].nx = nx; + pulls[npulls].ny = ny; + pulls[npulls].score = score; +#ifdef GENERATION_DIAGNOSTICS + printf("found potential pull: (%d,%d)-(%d,%d) cost %d\n", + pulls[npulls].ox, pulls[npulls].oy, + pulls[npulls].nx, pulls[npulls].ny, + pulls[npulls].score); +#endif + npulls++; + } +#ifdef GENERATION_DIAGNOSTICS + printf("found %d potential pulls\n", npulls); +#endif + + /* + * If there are no pulls available at all, we give up. + * + * (FIXME: or perhaps backtrack?) + */ + if (npulls == 0) + break; + + /* + * Now we do a BFS from our current position, to find all + * the squares we can get the player into. + * + * This BFS is unusually tricky. We want to give a positive + * distance only to squares which we have to carve through + * INITIALs to get to, which means we can't just stick + * every square we reach on the end of our to-do list. + * Instead, we must maintain our list as a proper priority + * queue. + */ + for (i = 0; i < w*h; i++) + dist[i] = prev[i] = -1; + + heap[0] = py*w+px; + heapsize = 1; + dist[py*w+px] = 0; + +#define PARENT(n) ( ((n)-1)/2 ) +#define LCHILD(n) ( 2*(n)+1 ) +#define RCHILD(n) ( 2*(n)+2 ) +#define SWAP(i,j) do { int swaptmp = (i); (i) = (j); (j) = swaptmp; } while (0) + + while (heapsize > 0) { + /* + * Pull the smallest element off the heap: it's at + * position 0. Move the arbitrary element from the very + * end of the heap into position 0. + */ + y = heap[0] / w; + x = heap[0] % w; + + heapsize--; + heap[0] = heap[heapsize]; + + /* + * Now repeatedly move that arbitrary element down the + * heap by swapping it with the more suitable of its + * children. + */ + i = 0; + while (1) { + int lc, rc; + + lc = LCHILD(i); + rc = RCHILD(i); + + if (lc >= heapsize) + break; /* we've hit bottom */ + + if (rc >= heapsize) { + /* + * Special case: there is only one child to + * check. + */ + if (dist[heap[i]] > dist[heap[lc]]) + SWAP(heap[i], heap[lc]); + + /* _Now_ we've hit bottom. */ + break; + } else { + /* + * The common case: there are two children and + * we must check them both. + */ + if (dist[heap[i]] > dist[heap[lc]] || + dist[heap[i]] > dist[heap[rc]]) { + /* + * Pick the more appropriate child to swap with + * (i.e. the one which would want to be the + * parent if one were above the other - as one + * is about to be). + */ + if (dist[heap[lc]] > dist[heap[rc]]) { + SWAP(heap[i], heap[rc]); + i = rc; + } else { + SWAP(heap[i], heap[lc]); + i = lc; + } + } else { + /* This element is in the right place; we're done. */ + break; + } + } + } + + /* + * OK, that's given us (x,y) for this phase of the + * search. Now try all directions from here. + */ + + for (d = 0; d < 4; d++) { + int dx = DX(d); + int dy = DY(d); + int nx = x + dx, ny = y + dy; + if (nx < 0 || nx >= w || ny < 0 || ny >= h) + continue; + if (grid[ny*w+nx] != SPACE && grid[ny*w+nx] != TARGET && + grid[ny*w+nx] != INITIAL) + continue; + if (dist[ny*w+nx] == -1) { + dist[ny*w+nx] = dist[y*w+x] + (grid[ny*w+nx] == INITIAL); + prev[ny*w+nx] = y*w+x; + + /* + * Now insert ny*w+nx at the end of the heap, + * and move it down to its appropriate resting + * place. + */ + i = heapsize; + heap[heapsize++] = ny*w+nx; + + /* + * Swap element n with its parent repeatedly to + * preserve the heap property. + */ + + while (i > 0) { + int p = PARENT(i); + + if (dist[heap[p]] > dist[heap[i]]) { + SWAP(heap[p], heap[i]); + i = p; + } else + break; + } + } + } + } + +#undef PARENT +#undef LCHILD +#undef RCHILD +#undef SWAP + +#ifdef GENERATION_DIAGNOSTICS + printf("distance map:\n"); + for (i = 0; i < h; i++) { + for (j = 0; j < w; j++) { + int d = dist[i*w+j]; + int c; + if (d < 0) + c = '#'; + else if (d >= 36) + c = '!'; + else if (d >= 10) + c = 'A' - 10 + d; + else + c = '0' + d; + putchar(c); + } + putchar('\n'); + } +#endif + + /* + * Now we can go back through the `pulls' array, adjusting + * the score for each pull depending on how hard it is to + * reach its starting point, and also throwing out any + * whose starting points are genuinely unreachable even + * with the possibility of carving through INITIAL squares. + */ + for (i = j = 0; i < npulls; i++) { +#ifdef GENERATION_DIAGNOSTICS + printf("potential pull (%d,%d)-(%d,%d)", + pulls[i].ox, pulls[i].oy, + pulls[i].nx, pulls[i].ny); +#endif + x = pulls[i].nx; + y = pulls[i].ny; + if (dist[y*w+x] < 0) { +#ifdef GENERATION_DIAGNOSTICS + printf(" unreachable\n"); +#endif + continue; /* this pull isn't feasible at all */ + } else { + /* + * Another nasty special case we have to check is + * whether the initial barrel location (ox,oy) is + * on the path used to reach the square. This can + * occur if that square is in state INITIAL: the + * pull is initially considered valid on the basis + * that the INITIAL can become BARRELTARGET, and + * it's also considered reachable on the basis that + * INITIAL can be turned into SPACE, but it can't + * be both at once. + * + * Fortunately, if (ox,oy) is on the path at all, + * it must be only one space from the end, so this + * is easy to spot and rule out. + */ + if (prev[y*w+x] == pulls[i].oy*w+pulls[i].ox) { +#ifdef GENERATION_DIAGNOSTICS + printf(" goes through itself\n"); +#endif + continue; /* this pull isn't feasible at all */ + } + pulls[j] = pulls[i]; /* structure copy */ + pulls[j].score += dist[y*w+x] * 3 /* new_space_score */; +#ifdef GENERATION_DIAGNOSTICS + printf(" reachable at distance %d (cost now %d)\n", + dist[y*w+x], pulls[j].score); +#endif + j++; + } + } + npulls = j; + + /* + * Again, if there are no pulls available at all, we give + * up. + * + * (FIXME: or perhaps backtrack?) + */ + if (npulls == 0) + break; + + /* + * Now choose which pull to make. On the one hand we should + * prefer pulls which do less damage to the INITIAL squares + * (thus, ones for which we can already get into position + * via existing SPACEs, and for which the barrel already + * exists and doesn't have to be invented); on the other, + * we want to avoid _always_ preferring such pulls, on the + * grounds that that will lead to levels without very much + * stuff in. + * + * When creating new barrels, we prefer creations which are + * next to existing TARGET squares. + * + * FIXME: for the moment I'll make this very simple indeed. + */ + i = random_upto(rs, npulls); + + /* + * Actually make the pull, including carving a path to get + * to the site if necessary. + */ + x = pulls[i].nx; + y = pulls[i].ny; + while (prev[y*w+x] >= 0) { + int p; + + if (grid[y*w+x] == INITIAL) + grid[y*w+x] = SPACE; + + p = prev[y*w+x]; + y = p / w; + x = p % w; + } + px = 2*pulls[i].nx - pulls[i].ox; + py = 2*pulls[i].ny - pulls[i].oy; + if (grid[py*w+px] == INITIAL) + grid[py*w+px] = SPACE; + if (grid[pulls[i].ny*w+pulls[i].nx] == TARGET) + grid[pulls[i].ny*w+pulls[i].nx] = BARRELTARGET; + else + grid[pulls[i].ny*w+pulls[i].nx] = BARREL; + if (grid[pulls[i].oy*w+pulls[i].ox] == BARREL) + grid[pulls[i].oy*w+pulls[i].ox] = SPACE; + else if (grid[pulls[i].oy*w+pulls[i].ox] != DEEP_PIT) + grid[pulls[i].oy*w+pulls[i].ox] = TARGET; + } + + sfree(heap); + sfree(prev); + sfree(dist); + sfree(pulls); + + if (grid[py*w+px] == TARGET) + grid[py*w+px] = PLAYERTARGET; + else + grid[py*w+px] = PLAYER; +} + +static char *new_game_desc(const game_params *params, random_state *rs, + char **aux, bool interactive) +{ + int w = params->w, h = params->h; + char *desc; + int desclen, descpos, descsize, prev, count; + unsigned char *grid; + int i, j; + + /* + * FIXME: perhaps some more interesting means of choosing how + * many moves to try? + */ + grid = snewn(w*h, unsigned char); + sokoban_generate(w, h, grid, w*h, false, rs); + + desclen = descpos = descsize = 0; + desc = NULL; + prev = -1; + count = 0; + for (i = 0; i < w*h; i++) { + if (descsize < desclen + 40) { + descsize = desclen + 100; + desc = sresize(desc, descsize, char); + desc[desclen] = '\0'; + } + switch (grid[i]) { + case INITIAL: + j = 'w'; /* FIXME: make some of these 's'? */ + break; + case SPACE: + j = 's'; + break; + case WALL: + j = 'w'; + break; + case TARGET: + j = 't'; + break; + case BARREL: + j = 'b'; + break; + case BARRELTARGET: + j = 'f'; + break; + case DEEP_PIT: + j = 'd'; + break; + case PLAYER: + j = 'u'; + break; + case PLAYERTARGET: + j = 'v'; + break; + default: + j = '?'; + break; + } + assert(j != '?'); + if (j != prev) { + desc[desclen++] = j; + descpos = desclen; + prev = j; + count = 1; + } else { + count++; + desclen = descpos + sprintf(desc+descpos, "%d", count); + } + } + + sfree(grid); + + return desc; +} + +static const char *validate_desc(const game_params *params, const char *desc) +{ + int w = params->w, h = params->h; + int area = 0; + int nplayers = 0; + + while (*desc) { + int c = *desc++; + int n = 1; + if (*desc && isdigit((unsigned char)*desc)) { + n = atoi(desc); + while (*desc && isdigit((unsigned char)*desc)) desc++; + } + + area += n; + + if (c == PLAYER || c == PLAYERTARGET) + nplayers += n; + else if (c == INITIAL || c == SPACE || c == WALL || c == TARGET || + c == PIT || c == DEEP_PIT || IS_BARREL(c)) + /* ok */; + else + return "Invalid character in game description"; + } + + if (area > w*h) + return "Too much data in game description"; + if (area < w*h) + return "Too little data in game description"; + if (nplayers < 1) + return "No starting player position specified"; + if (nplayers > 1) + return "More than one starting player position specified"; + + return NULL; +} + +static game_state *new_game(midend *me, const game_params *params, + const char *desc) +{ + int w = params->w, h = params->h; + game_state *state = snew(game_state); + int i; + + state->p = *params; /* structure copy */ + state->grid = snewn(w*h, unsigned char); + state->px = state->py = -1; + state->completed = false; + + i = 0; + + while (*desc) { + int c = *desc++; + int n = 1; + if (*desc && isdigit((unsigned char)*desc)) { + n = atoi(desc); + while (*desc && isdigit((unsigned char)*desc)) desc++; + } + + if (c == PLAYER || c == PLAYERTARGET) { + state->py = i / w; + state->px = i % w; + c = IS_ON_TARGET(c) ? TARGET : SPACE; + } + + while (n-- > 0) + state->grid[i++] = c; + } + + assert(i == w*h); + assert(state->px != -1 && state->py != -1); + + return state; +} + +static game_state *dup_game(const game_state *state) +{ + int w = state->p.w, h = state->p.h; + game_state *ret = snew(game_state); + + ret->p = state->p; /* structure copy */ + ret->grid = snewn(w*h, unsigned char); + memcpy(ret->grid, state->grid, w*h); + ret->px = state->px; + ret->py = state->py; + ret->completed = state->completed; + + return ret; +} + +static void free_game(game_state *state) +{ + sfree(state->grid); + sfree(state); +} + +static char *solve_game(const game_state *state, const game_state *currstate, + const char *aux, const char **error) +{ + return NULL; +} + +static bool game_can_format_as_text_now(const game_params *params) +{ + return true; +} + +static char *game_text_format(const game_state *state) +{ + return NULL; +} + +static game_ui *new_ui(const game_state *state) +{ + return NULL; +} + +static void free_ui(game_ui *ui) +{ +} + +static void game_changed_state(game_ui *ui, const game_state *oldstate, + const game_state *newstate) +{ +} + +struct game_drawstate { + game_params p; + int tilesize; + bool started; + unsigned short *grid; +}; + +#define PREFERRED_TILESIZE 32 +#define TILESIZE (ds->tilesize) +#define BORDER (TILESIZE) +#define HIGHLIGHT_WIDTH (TILESIZE / 10) +#define COORD(x) ( (x) * TILESIZE + BORDER ) +#define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 ) + +/* + * I'm going to need to do most of the move-type analysis in both + * interpret_move and execute_move, so I'll abstract it out into a + * subfunction. move_type() returns -1 for an illegal move, 0 for a + * movement, and 1 for a push. + */ +static int move_type(const game_state *state, int dx, int dy) +{ + int w = state->p.w, h = state->p.h; + int px = state->px, py = state->py; + int nx, ny, nbx, nby; + + assert(dx >= -1 && dx <= +1); + assert(dy >= -1 && dy <= +1); + assert(dx || dy); + + nx = px + dx; + ny = py + dy; + + /* + * Disallow any move that goes off the grid. + */ + if (nx < 0 || nx >= w || ny < 0 || ny >= h) + return -1; + + /* + * Examine the target square of the move to see whether it's a + * space, a barrel, or a wall. + */ + + if (state->grid[ny*w+nx] == WALL || + state->grid[ny*w+nx] == PIT || + state->grid[ny*w+nx] == DEEP_PIT) + return -1; /* this one's easy; just disallow it */ + + if (IS_BARREL(state->grid[ny*w+nx])) { + /* + * This is a push move. For a start, that means it must not + * be diagonal. + */ + if (dy && dx) + return -1; + + /* + * Now find the location of the third square involved in + * the push, and stop if it's off the edge. + */ + nbx = nx + dx; + nby = ny + dy; + if (nbx < 0 || nbx >= w || nby < 0 || nby >= h) + return -1; + + /* + * That third square must be able to accept a barrel. + */ + if (state->grid[nby*w+nbx] == SPACE || + state->grid[nby*w+nbx] == TARGET || + state->grid[nby*w+nbx] == PIT || + state->grid[nby*w+nbx] == DEEP_PIT) { + /* + * The push is valid. + */ + return 1; + } else { + return -1; + } + } else { + /* + * This is just an ordinary move. We've already checked the + * target square, so the only thing left to check is that a + * diagonal move has a space on one side to have notionally + * gone through. + */ + if (dx && dy && + state->grid[(py+dy)*w+px] != SPACE && + state->grid[(py+dy)*w+px] != TARGET && + state->grid[py*w+(px+dx)] != SPACE && + state->grid[py*w+(px+dx)] != TARGET) + return -1; + + /* + * Otherwise, the move is valid. + */ + return 0; + } +} + +static char *interpret_move(const game_state *state, game_ui *ui, + const game_drawstate *ds, + int x, int y, int button) +{ + int dx=0, dy=0; + char *move; + + /* + * Diagonal movement is supported as it is in NetHack: it's + * for movement only (never pushing), and one of the two + * squares adjacent to both the source and destination + * squares must be free to move through. In other words, it + * is only a shorthand for two orthogonal moves and cannot + * change the nature of the actual puzzle game. + */ + if (button == CURSOR_UP || button == (MOD_NUM_KEYPAD | '8')) + dx = 0, dy = -1; + else if (button == CURSOR_DOWN || button == (MOD_NUM_KEYPAD | '2')) + dx = 0, dy = +1; + else if (button == CURSOR_LEFT || button == (MOD_NUM_KEYPAD | '4')) + dx = -1, dy = 0; + else if (button == CURSOR_RIGHT || button == (MOD_NUM_KEYPAD | '6')) + dx = +1, dy = 0; + else if (button == (MOD_NUM_KEYPAD | '7')) + dx = -1, dy = -1; + else if (button == (MOD_NUM_KEYPAD | '9')) + dx = +1, dy = -1; + else if (button == (MOD_NUM_KEYPAD | '1')) + dx = -1, dy = +1; + else if (button == (MOD_NUM_KEYPAD | '3')) + dx = +1, dy = +1; + else if (button == LEFT_BUTTON) + { + if(x < COORD(state->px)) + dx = -1; + else if (x > COORD(state->px + 1)) + dx = 1; + if(y < COORD(state->py)) + dy = -1; + else if (y > COORD(state->py + 1)) + dy = 1; + } + else + return NULL; + + if((dx == 0) && (dy == 0)) + return(NULL); + + if (move_type(state, dx, dy) < 0) + return NULL; + + move = snewn(2, char); + move[1] = '\0'; + move[0] = '5' - 3*dy + dx; + return move; +} + +static game_state *execute_move(const game_state *state, const char *move) +{ + int w = state->p.w, h = state->p.h; + int px = state->px, py = state->py; + int dx, dy, nx, ny, nbx, nby, type, m, i; + bool freebarrels, freetargets; + game_state *ret; + + if (*move < '1' || *move == '5' || *move > '9' || move[1]) + return NULL; /* invalid move string */ + + m = *move - '0'; + dx = (m + 2) % 3 - 1; + dy = 2 - (m + 2) / 3; + type = move_type(state, dx, dy); + if (type < 0) + return NULL; + + ret = dup_game(state); + + nx = px + dx; + ny = py + dy; + nbx = nx + dx; + nby = ny + dy; + + if (type) { + int b; + + /* + * Push. + */ + b = ret->grid[ny*w+nx]; + if (IS_ON_TARGET(b)) { + ret->grid[ny*w+nx] = TARGET; + b = DETARGETISE(b); + } else + ret->grid[ny*w+nx] = SPACE; + + if (ret->grid[nby*w+nbx] == PIT) + ret->grid[nby*w+nbx] = SPACE; + else if (ret->grid[nby*w+nbx] == DEEP_PIT) + /* do nothing - the pit eats the barrel and remains there */; + else if (ret->grid[nby*w+nbx] == TARGET) + ret->grid[nby*w+nbx] = TARGETISE(b); + else + ret->grid[nby*w+nbx] = b; + } + + ret->px = nx; + ret->py = ny; + + /* + * Check for completion. This is surprisingly complicated, + * given the presence of pits and deep pits, and also the fact + * that some Sokoban levels with pits have fewer pits than + * barrels (due to providing spares, e.g. NetHack's). I think + * the completion condition in fact must be that the game + * cannot become any _more_ complete. That is, _either_ there + * are no remaining barrels not on targets, _or_ there is a + * good reason why any such barrels cannot be placed. The only + * available good reason is that there are no remaining pits, + * no free target squares, and no deep pits at all. + */ + if (!ret->completed) { + freebarrels = false; + freetargets = false; + for (i = 0; i < w*h; i++) { + int v = ret->grid[i]; + + if (IS_BARREL(v) && !IS_ON_TARGET(v)) + freebarrels = true; + if (v == DEEP_PIT || v == PIT || + (!IS_BARREL(v) && IS_ON_TARGET(v))) + freetargets = true; + } + + if (!freebarrels || !freetargets) + ret->completed = true; + } + + return ret; +} + +/* ---------------------------------------------------------------------- + * Drawing routines. + */ + +static void game_compute_size(const game_params *params, int tilesize, + const game_ui *ui, int *x, int *y) +{ + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + struct { int tilesize; } ads, *ds = &ads; + ads.tilesize = tilesize; + + *x = 2 * BORDER + 1 + params->w * TILESIZE; + *y = 2 * BORDER + 1 + params->h * TILESIZE; +} + +static void game_set_size(drawing *dr, game_drawstate *ds, + const game_params *params, int tilesize) +{ + ds->tilesize = tilesize; +} + +static float *game_colours(frontend *fe, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + int i; + + game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT); + + ret[COL_OUTLINE * 3 + 0] = 0.0F; + ret[COL_OUTLINE * 3 + 1] = 0.0F; + ret[COL_OUTLINE * 3 + 2] = 0.0F; + + ret[COL_PLAYER * 3 + 0] = 0.0F; + ret[COL_PLAYER * 3 + 1] = 1.0F; + ret[COL_PLAYER * 3 + 2] = 0.0F; + + ret[COL_BARREL * 3 + 0] = 0.6F; + ret[COL_BARREL * 3 + 1] = 0.3F; + ret[COL_BARREL * 3 + 2] = 0.0F; + + ret[COL_TARGET * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0]; + ret[COL_TARGET * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1]; + ret[COL_TARGET * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2]; + + ret[COL_PIT * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0] / 2; + ret[COL_PIT * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1] / 2; + ret[COL_PIT * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2] / 2; + + ret[COL_DEEP_PIT * 3 + 0] = 0.0F; + ret[COL_DEEP_PIT * 3 + 1] = 0.0F; + ret[COL_DEEP_PIT * 3 + 2] = 0.0F; + + ret[COL_TEXT * 3 + 0] = 1.0F; + ret[COL_TEXT * 3 + 1] = 1.0F; + ret[COL_TEXT * 3 + 2] = 1.0F; + + ret[COL_GRID * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0]; + ret[COL_GRID * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1]; + ret[COL_GRID * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2]; + + ret[COL_OUTLINE * 3 + 0] = 0.0F; + ret[COL_OUTLINE * 3 + 1] = 0.0F; + ret[COL_OUTLINE * 3 + 2] = 0.0F; + + for (i = 0; i < 3; i++) { + ret[COL_WALL * 3 + i] = (3 * ret[COL_BACKGROUND * 3 + i] + + 1 * ret[COL_HIGHLIGHT * 3 + i]) / 4; + } + + *ncolours = NCOLOURS; + return ret; +} + +static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) +{ + int w = state->p.w, h = state->p.h; + struct game_drawstate *ds = snew(struct game_drawstate); + int i; + + ds->tilesize = 0; + ds->p = state->p; /* structure copy */ + ds->grid = snewn(w*h, unsigned short); + for (i = 0; i < w*h; i++) + ds->grid[i] = INVALID; + ds->started = false; + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds->grid); + sfree(ds); +} + +static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v) +{ + int tx = COORD(x), ty = COORD(y); + int bg = (v & 0x100 ? COL_HIGHLIGHT : COL_BACKGROUND); + + v &= 0xFF; + + clip(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1); + draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1, bg); + + if (v == WALL) { + int coords[6]; + + coords[0] = tx + TILESIZE; + coords[1] = ty + TILESIZE; + coords[2] = tx + TILESIZE; + coords[3] = ty + 1; + coords[4] = tx + 1; + coords[5] = ty + TILESIZE; + draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT); + + coords[0] = tx + 1; + coords[1] = ty + 1; + draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT); + + draw_rect(dr, tx + 1 + HIGHLIGHT_WIDTH, ty + 1 + HIGHLIGHT_WIDTH, + TILESIZE - 2*HIGHLIGHT_WIDTH, + TILESIZE - 2*HIGHLIGHT_WIDTH, COL_WALL); + } else if (v == PIT) { + draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, + TILESIZE*3/7, COL_PIT, COL_OUTLINE); + } else if (v == DEEP_PIT) { + draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, + TILESIZE*3/7, COL_DEEP_PIT, COL_OUTLINE); + } else { + if (IS_ON_TARGET(v)) { + draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, + TILESIZE*3/7, COL_TARGET, COL_OUTLINE); + } + if (IS_PLAYER(v)) { + draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, + TILESIZE/3, COL_PLAYER, COL_OUTLINE); + } else if (IS_BARREL(v)) { + char str[2]; + + draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, + TILESIZE/3, COL_BARREL, COL_OUTLINE); + str[1] = '\0'; + str[0] = BARREL_LABEL(v); + if (str[0]) { + draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2, + FONT_VARIABLE, TILESIZE/2, + ALIGN_VCENTRE | ALIGN_HCENTRE, COL_TEXT, str); + } + } + } + + unclip(dr); + draw_update(dr, tx, ty, TILESIZE, TILESIZE); +} + +static void game_redraw(drawing *dr, game_drawstate *ds, + const game_state *oldstate, const game_state *state, + int dir, const game_ui *ui, + float animtime, float flashtime) +{ + int w = state->p.w, h = state->p.h /*, wh = w*h */; + int x, y; + int flashtype; + + if (flashtime && + !((int)(flashtime * 3 / FLASH_LENGTH) % 2)) + flashtype = 0x100; + else + flashtype = 0; + + /* + * Initialise a fresh drawstate. + */ + if (!ds->started) { + /* + * Draw the grid lines. + */ + for (y = 0; y <= h; y++) + draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), + COL_LOWLIGHT); + for (x = 0; x <= w; x++) + draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), + COL_LOWLIGHT); + + ds->started = true; + } + + /* + * Draw the grid contents. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + int v = state->grid[y*w+x]; + if (y == state->py && x == state->px) { + if (v == TARGET) + v = PLAYERTARGET; + else { + assert(v == SPACE); + v = PLAYER; + } + } + + v |= flashtype; + + if (ds->grid[y*w+x] != v) { + draw_tile(dr, ds, x, y, v); + ds->grid[y*w+x] = v; + } + } + +} + +static float game_anim_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + return 0.0F; +} + +static float game_flash_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) +{ + if (!oldstate->completed && newstate->completed) + return FLASH_LENGTH; + else + return 0.0F; +} + +static void game_get_cursor_location(const game_ui *ui, + const game_drawstate *ds, + const game_state *state, + const game_params *params, + int *x, int *y, int *w, int *h) +{ +} + +static int game_status(const game_state *state) +{ + return state->completed ? +1 : 0; +} + +static bool game_timing_state(const game_state *state, game_ui *ui) +{ + return true; +} + +static void game_print_size(const game_params *params, const game_ui *ui, + float *x, float *y) +{ +} + +static void game_print(drawing *dr, const game_state *state, const game_ui *ui, + int tilesize) +{ +} + +#ifdef COMBINED +#define thegame sokoban +#endif + +const struct game thegame = { + "Sokoban", NULL, NULL, + default_params, + game_fetch_preset, NULL, + decode_params, + encode_params, + free_params, + dup_params, + true, game_configure, custom_params, + validate_params, + new_game_desc, + validate_desc, + new_game, + dup_game, + free_game, + false, solve_game, + false, game_can_format_as_text_now, game_text_format, + NULL, NULL, /* get_prefs, set_prefs */ + new_ui, + free_ui, + NULL, /* encode_ui */ + NULL, /* decode_ui */ + NULL, /* game_request_keys */ + game_changed_state, + NULL, /* current_key_label */ + interpret_move, + execute_move, + PREFERRED_TILESIZE, game_compute_size, game_set_size, + game_colours, + game_new_drawstate, + game_free_drawstate, + game_redraw, + game_anim_length, + game_flash_length, + game_get_cursor_location, + game_status, + false, false, game_print_size, game_print, + false, /* wants_statusbar */ + false, game_timing_state, + 0, /* flags */ +}; -- cgit v1.2.3