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/path.c | 97 ++++++++++++++++++++++++++++++ 1 file changed, 97 insertions(+) (limited to 'apps/plugins/puzzles/src/unfinished/path.c') 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