diff options
Diffstat (limited to 'apps/plugins/puzzles/src/unfinished')
-rw-r--r-- | apps/plugins/puzzles/src/unfinished/group.c | 226 | ||||
-rw-r--r-- | apps/plugins/puzzles/src/unfinished/path.c | 97 |
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 @@ | |||
43 | #define DIFFLIST(A) \ | 43 | #define DIFFLIST(A) \ |
44 | A(TRIVIAL,Trivial,NULL,t) \ | 44 | A(TRIVIAL,Trivial,NULL,t) \ |
45 | A(NORMAL,Normal,solver_normal,n) \ | 45 | A(NORMAL,Normal,solver_normal,n) \ |
46 | A(HARD,Hard,NULL,h) \ | 46 | A(HARD,Hard,solver_hard,h) \ |
47 | A(EXTREME,Extreme,NULL,x) \ | 47 | A(EXTREME,Extreme,NULL,x) \ |
48 | A(UNREASONABLE,Unreasonable,NULL,u) | 48 | A(UNREASONABLE,Unreasonable,NULL,u) |
49 | #define ENUM(upper,title,func,lower) DIFF_ ## upper, | 49 | #define ENUM(upper,title,func,lower) DIFF_ ## upper, |
@@ -280,6 +280,23 @@ static const char *validate_params(const game_params *params, bool full) | |||
280 | * Solver. | 280 | * Solver. |
281 | */ | 281 | */ |
282 | 282 | ||
283 | static int find_identity(struct latin_solver *solver) | ||
284 | { | ||
285 | int w = solver->o; | ||
286 | digit *grid = solver->grid; | ||
287 | int i, j; | ||
288 | |||
289 | for (i = 0; i < w; i++) | ||
290 | for (j = 0; j < w; j++) { | ||
291 | if (grid[i*w+j] == i+1) | ||
292 | return j+1; | ||
293 | if (grid[i*w+j] == j+1) | ||
294 | return i+1; | ||
295 | } | ||
296 | |||
297 | return 0; | ||
298 | } | ||
299 | |||
283 | static int solver_normal(struct latin_solver *solver, void *vctx) | 300 | static int solver_normal(struct latin_solver *solver, void *vctx) |
284 | { | 301 | { |
285 | int w = solver->o; | 302 | int w = solver->o; |
@@ -295,9 +312,9 @@ static int solver_normal(struct latin_solver *solver, void *vctx) | |||
295 | * So we pick any a,b,c we like; then if we know ab, bc, and | 312 | * So we pick any a,b,c we like; then if we know ab, bc, and |
296 | * (ab)c we can fill in a(bc). | 313 | * (ab)c we can fill in a(bc). |
297 | */ | 314 | */ |
298 | for (i = 1; i < w; i++) | 315 | for (i = 0; i < w; i++) |
299 | for (j = 1; j < w; j++) | 316 | for (j = 0; j < w; j++) |
300 | for (k = 1; k < w; k++) { | 317 | for (k = 0; k < w; k++) { |
301 | if (!grid[i*w+j] || !grid[j*w+k]) | 318 | if (!grid[i*w+j] || !grid[j*w+k]) |
302 | continue; | 319 | continue; |
303 | if (grid[(grid[i*w+j]-1)*w+k] && | 320 | if (grid[(grid[i*w+j]-1)*w+k] && |
@@ -358,12 +375,206 @@ static int solver_normal(struct latin_solver *solver, void *vctx) | |||
358 | } | 375 | } |
359 | } | 376 | } |
360 | 377 | ||
378 | /* | ||
379 | * Fill in the row and column for the group identity, if it's not | ||
380 | * already known and if we've just found out what it is. | ||
381 | */ | ||
382 | i = find_identity(solver); | ||
383 | if (i) { | ||
384 | bool done_something = false; | ||
385 | for (j = 1; j <= w; j++) { | ||
386 | if (!grid[(i-1)*w+(j-1)] || !grid[(j-1)*w+(i-1)]) { | ||
387 | done_something = true; | ||
388 | } | ||
389 | } | ||
390 | if (done_something) { | ||
391 | #ifdef STANDALONE_SOLVER | ||
392 | if (solver_show_working) { | ||
393 | printf("%*s%s is the group identity\n", | ||
394 | solver_recurse_depth*4, "", names[i-1]); | ||
395 | } | ||
396 | #endif | ||
397 | for (j = 1; j <= w; j++) { | ||
398 | if (!grid[(j-1)*w+(i-1)]) { | ||
399 | if (!cube(i-1, j-1, j)) { | ||
400 | #ifdef STANDALONE_SOLVER | ||
401 | if (solver_show_working) { | ||
402 | printf("%*s but %s cannot go at (%d,%d) - " | ||
403 | "contradiction!\n", | ||
404 | solver_recurse_depth*4, "", | ||
405 | names[j-1], i, j); | ||
406 | } | ||
407 | #endif | ||
408 | return -1; | ||
409 | } | ||
410 | #ifdef STANDALONE_SOLVER | ||
411 | if (solver_show_working) { | ||
412 | printf("%*s placing %s at (%d,%d)\n", | ||
413 | solver_recurse_depth*4, "", | ||
414 | names[j-1], i, j); | ||
415 | } | ||
416 | #endif | ||
417 | latin_solver_place(solver, i-1, j-1, j); | ||
418 | } | ||
419 | if (!grid[(i-1)*w+(j-1)]) { | ||
420 | if (!cube(j-1, i-1, j)) { | ||
421 | #ifdef STANDALONE_SOLVER | ||
422 | if (solver_show_working) { | ||
423 | printf("%*s but %s cannot go at (%d,%d) - " | ||
424 | "contradiction!\n", | ||
425 | solver_recurse_depth*4, "", | ||
426 | names[j-1], j, i); | ||
427 | } | ||
428 | #endif | ||
429 | return -1; | ||
430 | } | ||
431 | #ifdef STANDALONE_SOLVER | ||
432 | if (solver_show_working) { | ||
433 | printf("%*s placing %s at (%d,%d)\n", | ||
434 | solver_recurse_depth*4, "", | ||
435 | names[j-1], j, i); | ||
436 | } | ||
437 | #endif | ||
438 | latin_solver_place(solver, j-1, i-1, j); | ||
439 | } | ||
440 | } | ||
441 | return 1; | ||
442 | } | ||
443 | } | ||
444 | |||
361 | return 0; | 445 | return 0; |
362 | } | 446 | } |
363 | 447 | ||
448 | static int solver_hard(struct latin_solver *solver, void *vctx) | ||
449 | { | ||
450 | bool done_something = false; | ||
451 | int w = solver->o; | ||
452 | #ifdef STANDALONE_SOLVER | ||
453 | char **names = solver->names; | ||
454 | #endif | ||
455 | int i, j; | ||
456 | |||
457 | /* | ||
458 | * In identity-hidden mode, systematically rule out possibilities | ||
459 | * for the group identity. | ||
460 | * | ||
461 | * In solver_normal, we used the fact that any filled square in | ||
462 | * the grid whose contents _does_ match one of the elements it's | ||
463 | * the product of - that is, ab=a or ab=b - tells you immediately | ||
464 | * that the other element is the identity. | ||
465 | * | ||
466 | * Here, we use the flip side of that: any filled square in the | ||
467 | * grid whose contents does _not_ match either its row or column - | ||
468 | * that is, if ab is neither a nor b - tells you immediately that | ||
469 | * _neither_ of those elements is the identity. And if that's | ||
470 | * true, then we can also immediately rule out the possibility | ||
471 | * that it acts as the identity on any element at all. | ||
472 | */ | ||
473 | for (i = 0; i < w; i++) { | ||
474 | bool i_can_be_id = true; | ||
475 | #ifdef STANDALONE_SOLVER | ||
476 | char title[80]; | ||
477 | #endif | ||
478 | |||
479 | for (j = 0; j < w; j++) { | ||
480 | if (grid(i,j) && grid(i,j) != j+1) { | ||
481 | #ifdef STANDALONE_SOLVER | ||
482 | if (solver_show_working) | ||
483 | sprintf(title, "%s cannot be the identity: " | ||
484 | "%s%s = %s =/= %s", names[i], names[i], names[j], | ||
485 | names[grid(i,j)-1], names[j]); | ||
486 | #endif | ||
487 | i_can_be_id = false; | ||
488 | break; | ||
489 | } | ||
490 | if (grid(j,i) && grid(j,i) != j+1) { | ||
491 | #ifdef STANDALONE_SOLVER | ||
492 | if (solver_show_working) | ||
493 | sprintf(title, "%s cannot be the identity: " | ||
494 | "%s%s = %s =/= %s", names[i], names[j], names[i], | ||
495 | names[grid(j,i)-1], names[j]); | ||
496 | #endif | ||
497 | i_can_be_id = false; | ||
498 | break; | ||
499 | } | ||
500 | } | ||
501 | |||
502 | if (!i_can_be_id) { | ||
503 | /* Now rule out ij=j or ji=j for all j. */ | ||
504 | for (j = 0; j < w; j++) { | ||
505 | if (cube(i, j, j+1)) { | ||
506 | #ifdef STANDALONE_SOLVER | ||
507 | if (solver_show_working) { | ||
508 | if (title[0]) { | ||
509 | printf("%*s%s\n", solver_recurse_depth*4, "", | ||
510 | title); | ||
511 | title[0] = '\0'; | ||
512 | } | ||
513 | printf("%*s ruling out %s at (%d,%d)\n", | ||
514 | solver_recurse_depth*4, "", names[j], i, j); | ||
515 | } | ||
516 | #endif | ||
517 | cube(i, j, j+1) = false; | ||
518 | } | ||
519 | if (cube(j, i, j+1)) { | ||
520 | #ifdef STANDALONE_SOLVER | ||
521 | if (solver_show_working) { | ||
522 | if (title[0]) { | ||
523 | printf("%*s%s\n", solver_recurse_depth*4, "", | ||
524 | title); | ||
525 | title[0] = '\0'; | ||
526 | } | ||
527 | printf("%*s ruling out %s at (%d,%d)\n", | ||
528 | solver_recurse_depth*4, "", names[j], j, i); | ||
529 | } | ||
530 | #endif | ||
531 | cube(j, i, j+1) = false; | ||
532 | } | ||
533 | } | ||
534 | } | ||
535 | } | ||
536 | |||
537 | return done_something; | ||
538 | } | ||
539 | |||
364 | #define SOLVER(upper,title,func,lower) func, | 540 | #define SOLVER(upper,title,func,lower) func, |
365 | static usersolver_t const group_solvers[] = { DIFFLIST(SOLVER) }; | 541 | static usersolver_t const group_solvers[] = { DIFFLIST(SOLVER) }; |
366 | 542 | ||
543 | static bool group_valid(struct latin_solver *solver, void *ctx) | ||
544 | { | ||
545 | int w = solver->o; | ||
546 | #ifdef STANDALONE_SOLVER | ||
547 | char **names = solver->names; | ||
548 | #endif | ||
549 | int i, j, k; | ||
550 | |||
551 | for (i = 0; i < w; i++) | ||
552 | for (j = 0; j < w; j++) | ||
553 | for (k = 0; k < w; k++) { | ||
554 | int ij = grid(i, j) - 1; | ||
555 | int jk = grid(j, k) - 1; | ||
556 | int ij_k = grid(ij, k) - 1; | ||
557 | int i_jk = grid(i, jk) - 1; | ||
558 | if (ij_k != i_jk) { | ||
559 | #ifdef STANDALONE_SOLVER | ||
560 | if (solver_show_working) { | ||
561 | printf("%*sfailure of associativity: " | ||
562 | "(%s%s)%s = %s%s = %s but " | ||
563 | "%s(%s%s) = %s%s = %s\n", | ||
564 | solver_recurse_depth*4, "", | ||
565 | names[i], names[j], names[k], | ||
566 | names[ij], names[k], names[ij_k], | ||
567 | names[i], names[j], names[k], | ||
568 | names[i], names[jk], names[i_jk]); | ||
569 | } | ||
570 | #endif | ||
571 | return false; | ||
572 | } | ||
573 | } | ||
574 | |||
575 | return true; | ||
576 | } | ||
577 | |||
367 | static int solver(const game_params *params, digit *grid, int maxdiff) | 578 | static int solver(const game_params *params, digit *grid, int maxdiff) |
368 | { | 579 | { |
369 | int w = params->w; | 580 | int w = params->w; |
@@ -387,7 +598,7 @@ static int solver(const game_params *params, digit *grid, int maxdiff) | |||
387 | ret = latin_solver_main(&solver, maxdiff, | 598 | ret = latin_solver_main(&solver, maxdiff, |
388 | DIFF_TRIVIAL, DIFF_HARD, DIFF_EXTREME, | 599 | DIFF_TRIVIAL, DIFF_HARD, DIFF_EXTREME, |
389 | DIFF_EXTREME, DIFF_UNREASONABLE, | 600 | DIFF_EXTREME, DIFF_UNREASONABLE, |
390 | group_solvers, NULL, NULL, NULL); | 601 | group_solvers, group_valid, NULL, NULL, NULL); |
391 | 602 | ||
392 | latin_solver_free(&solver); | 603 | latin_solver_free(&solver); |
393 | 604 | ||
@@ -2183,6 +2394,11 @@ int main(int argc, char **argv) | |||
2183 | } | 2394 | } |
2184 | 2395 | ||
2185 | if (diff == DIFFCOUNT) { | 2396 | if (diff == DIFFCOUNT) { |
2397 | if (really_show_working) { | ||
2398 | solver_show_working = true; | ||
2399 | memcpy(grid, s->grid, p->w * p->w); | ||
2400 | ret = solver(&s->par, grid, DIFFCOUNT - 1); | ||
2401 | } | ||
2186 | if (grade) | 2402 | if (grade) |
2187 | printf("Difficulty rating: ambiguous\n"); | 2403 | printf("Difficulty rating: ambiguous\n"); |
2188 | else | 2404 | 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 @@ | |||
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 |