diff options
Diffstat (limited to 'apps/plugins/puzzles/src/unfinished/path.c')
-rw-r--r-- | apps/plugins/puzzles/src/unfinished/path.c | 97 |
1 files changed, 97 insertions, 0 deletions
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 @@ | |||
69 | */ | 69 | */ |
70 | 70 | ||
71 | /* | 71 | /* |
72 | * 2020-05-11: some thoughts on a solver. | ||
73 | * | ||
74 | * Consider this example puzzle, from Wikipedia: | ||
75 | * | ||
76 | * ---4--- | ||
77 | * -3--25- | ||
78 | * ---31-- | ||
79 | * ---5--- | ||
80 | * ------- | ||
81 | * --1---- | ||
82 | * 2---4-- | ||
83 | * | ||
84 | * The kind of deduction that a human wants to make here is: which way | ||
85 | * does the path between the 4s go? In particular, does it go round | ||
86 | * the left of the W-shaped cluster of endpoints, or round the right | ||
87 | * of it? It's clear at a glance that it must go to the right, because | ||
88 | * _any_ path between the 4s that goes to the left of that cluster, no | ||
89 | * matter what detailed direction it takes, will disconnect the | ||
90 | * remaining grid squares into two components, with the two 2s not in | ||
91 | * the same component. So we immediately know that the path between | ||
92 | * the 4s _must_ go round the right-hand side of the grid. | ||
93 | * | ||
94 | * How do you model that global and topological reasoning in a | ||
95 | * computer? | ||
96 | * | ||
97 | * The most plausible idea I've seen so far is to use fundamental | ||
98 | * groups. The fundamental group of loops based at a given point in a | ||
99 | * space is a free group, under loop concatenation and up to homotopy, | ||
100 | * generated by the loops that go in each direction around each hole | ||
101 | * in the space. In this case, the 'holes' are clues, or connected | ||
102 | * groups of clues. | ||
103 | * | ||
104 | * So you might be able to enumerate all the homotopy classes of paths | ||
105 | * between (say) the two 4s as follows. Start with any old path | ||
106 | * between them (say, find the first one that breadth-first search | ||
107 | * will give you). Choose one of the 4s to regard as the base point | ||
108 | * (arbitrarily). Then breadth-first search among the space of _paths_ | ||
109 | * by the following procedure. Given a candidate path, append to it | ||
110 | * each of the possible loops that starts from the base point, | ||
111 | * circumnavigates one clue cluster, and returns to the base point. | ||
112 | * The result will typically be a path that retraces its steps and | ||
113 | * self-intersects. Now adjust it homotopically so that it doesn't. If | ||
114 | * that can't be done, then we haven't generated a fresh candidate | ||
115 | * path; if it can, then we've got a new path that is not homotopic to | ||
116 | * any path we already had, so add it to our list and queue it up to | ||
117 | * become the starting point of this search later. | ||
118 | * | ||
119 | * The idea is that this should exhaustively enumerate, up to | ||
120 | * homotopy, the different ways in which the two 4s can connect to | ||
121 | * each other within the constraint that you have to actually fit the | ||
122 | * path non-self-intersectingly into this grid. Then you can keep a | ||
123 | * list of those homotopy classes in mind, and start ruling them out | ||
124 | * by techniques like the connectivity approach described above. | ||
125 | * Hopefully you end up narrowing down to few enough homotopy classes | ||
126 | * that you can deduce something concrete about actual squares of the | ||
127 | * grid - for example, here, that if the path between 4s has to go | ||
128 | * round the right, then we know some specific squares it must go | ||
129 | * through, so we can fill those in. And then, having filled in a | ||
130 | * piece of the middle of a path, you can now regard connecting the | ||
131 | * ultimate endpoints to that mid-section as two separate subproblems, | ||
132 | * so you've reduced to a simpler instance of the same puzzle. | ||
133 | * | ||
134 | * But I don't know whether all of this actually works. I more or less | ||
135 | * believe the process for enumerating elements of the free group; but | ||
136 | * I'm not as confident that when you find a group element that won't | ||
137 | * fit in the grid, you'll never have to consider its descendants in | ||
138 | * the BFS either. And I'm assuming that 'unwind the self-intersection | ||
139 | * homotopically' is a thing that can actually be turned into a | ||
140 | * sensible algorithm. | ||
141 | * | ||
142 | * -------- | ||
143 | * | ||
144 | * Another thing that might be needed is to characterise _which_ | ||
145 | * homotopy class a given path is in. | ||
146 | * | ||
147 | * For this I think it's sufficient to choose a collection of paths | ||
148 | * along the _edges_ of the square grid, each of which connects two of | ||
149 | * the holes in the grid (including the grid exterior, which counts as | ||
150 | * a huge hole), such that they form a spanning tree between the | ||
151 | * holes. Then assign each of those paths an orientation, so that | ||
152 | * crossing it in one direction counts as 'positive' and the other | ||
153 | * 'negative'. Now analyse a candidate path from one square to another | ||
154 | * by following it and noting down which of those paths it crosses in | ||
155 | * which direction, then simplifying the result like a free group word | ||
156 | * (i.e. adjacent + and - crossings of the same path cancel out). | ||
157 | * | ||
158 | * -------- | ||
159 | * | ||
160 | * If we choose those paths to be of minimal length, then we can get | ||
161 | * an upper bound on the number of homotopy classes by observing that | ||
162 | * you can't traverse any of those barriers more times than will fit | ||
163 | * non-self-intersectingly in the grid. That might be an alternative | ||
164 | * method of bounding the search through the fundamental group to only | ||
165 | * finitely many possibilities. | ||
166 | */ | ||
167 | |||
168 | /* | ||
72 | * Standard notation for directions. | 169 | * Standard notation for directions. |
73 | */ | 170 | */ |
74 | #define L 0 | 171 | #define L 0 |