puzzles: resync with upstream

This brings the upstream version to 9aa7b7c (with some of my changes as
well).

Change-Id: I5bf8a3e0b8672d82cb1bf34afc07adbe12a3ac53

2 files changed, 318 insertions, 5 deletions

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
@@ -69,6 +69,103 @@
  */
 
 /*
+ * 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