From 48b0ef1cf22ec37927116ac83ea7c7cfc1f9083e Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Thu, 25 Jun 2020 14:44:33 -0400 Subject: puzzles: resync with upstream This brings the upstream version to 9aa7b7c (with some of my changes as well). Change-Id: I5bf8a3e0b8672d82cb1bf34afc07adbe12a3ac53 --- apps/plugins/puzzles/src/unfinished/group.c | 226 +++++++++++++++++++++++++++- apps/plugins/puzzles/src/unfinished/path.c | 97 ++++++++++++ 2 files changed, 318 insertions(+), 5 deletions(-) (limited to 'apps/plugins/puzzles/src/unfinished') diff --git a/apps/plugins/puzzles/src/unfinished/group.c b/apps/plugins/puzzles/src/unfinished/group.c index ef7ffba349..006a9e0ee6 100644 --- a/apps/plugins/puzzles/src/unfinished/group.c +++ b/apps/plugins/puzzles/src/unfinished/group.c @@ -43,7 +43,7 @@ #define DIFFLIST(A) \ A(TRIVIAL,Trivial,NULL,t) \ A(NORMAL,Normal,solver_normal,n) \ - A(HARD,Hard,NULL,h) \ + A(HARD,Hard,solver_hard,h) \ A(EXTREME,Extreme,NULL,x) \ A(UNREASONABLE,Unreasonable,NULL,u) #define ENUM(upper,title,func,lower) DIFF_ ## upper, @@ -280,6 +280,23 @@ static const char *validate_params(const game_params *params, bool full) * 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; @@ -295,9 +312,9 @@ static int solver_normal(struct latin_solver *solver, void *vctx) * 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 = 1; i < w; i++) - for (j = 1; j < w; j++) - for (k = 1; k < w; k++) { + 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] && @@ -358,12 +375,206 @@ static int solver_normal(struct latin_solver *solver, void *vctx) } } + /* + * 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; @@ -387,7 +598,7 @@ static int solver(const game_params *params, digit *grid, int maxdiff) ret = latin_solver_main(&solver, maxdiff, DIFF_TRIVIAL, DIFF_HARD, DIFF_EXTREME, DIFF_EXTREME, DIFF_UNREASONABLE, - group_solvers, NULL, NULL, NULL); + group_solvers, group_valid, NULL, NULL, NULL); latin_solver_free(&solver); @@ -2183,6 +2394,11 @@ int main(int argc, char **argv) } 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 diff --git a/apps/plugins/puzzles/src/unfinished/path.c b/apps/plugins/puzzles/src/unfinished/path.c index 829fbc6c75..fe5a47fd2a 100644 --- a/apps/plugins/puzzles/src/unfinished/path.c +++ b/apps/plugins/puzzles/src/unfinished/path.c @@ -68,6 +68,103 @@ * 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. */ -- cgit v1.2.3