diff options
Diffstat (limited to 'apps/plugins/puzzles/src/tracks.c')
-rw-r--r-- | apps/plugins/puzzles/src/tracks.c | 451 |
1 files changed, 407 insertions, 44 deletions
diff --git a/apps/plugins/puzzles/src/tracks.c b/apps/plugins/puzzles/src/tracks.c index 8f29faa0fd..924836afa9 100644 --- a/apps/plugins/puzzles/src/tracks.c +++ b/apps/plugins/puzzles/src/tracks.c | |||
@@ -12,6 +12,7 @@ | |||
12 | * #113 8x8:gCx5xAf,1,S4,2,5,4,6,2,3,4,2,5,2,S4,4,5,1 | 12 | * #113 8x8:gCx5xAf,1,S4,2,5,4,6,2,3,4,2,5,2,S4,4,5,1 |
13 | * #114 8x8:p5fAzkAb,1,6,3,3,3,S6,2,3,5,4,S3,3,5,1,5,1 | 13 | * #114 8x8:p5fAzkAb,1,6,3,3,3,S6,2,3,5,4,S3,3,5,1,5,1 |
14 | * #115 8x8:zi9d5tAb,1,3,4,5,3,S4,2,4,2,6,2,3,6,S3,3,1 | 14 | * #115 8x8:zi9d5tAb,1,3,4,5,3,S4,2,4,2,6,2,3,6,S3,3,1 |
15 | * #942 8x8:n5iCfAzAe,2,2,S5,5,3,5,4,5,4,5,2,S5,3,4,5,3 | ||
15 | */ | 16 | */ |
16 | 17 | ||
17 | #include <stdio.h> | 18 | #include <stdio.h> |
@@ -29,9 +30,11 @@ | |||
29 | * Difficulty levels. I do some macro ickery here to ensure that my | 30 | * Difficulty levels. I do some macro ickery here to ensure that my |
30 | * enum and the various forms of my name list always match up. | 31 | * enum and the various forms of my name list always match up. |
31 | */ | 32 | */ |
32 | #define DIFFLIST(A) \ | 33 | #define DIFFLIST(A) \ |
33 | A(EASY,Easy,e) \ | 34 | A(EASY,Easy,e) \ |
34 | A(TRICKY,Tricky,t) | 35 | A(TRICKY,Tricky,t) \ |
36 | A(HARD,Hard,h) \ | ||
37 | /* end of list */ | ||
35 | 38 | ||
36 | #define ENUM(upper,title,lower) DIFF_ ## upper, | 39 | #define ENUM(upper,title,lower) DIFF_ ## upper, |
37 | #define TITLE(upper,title,lower) #title, | 40 | #define TITLE(upper,title,lower) #title, |
@@ -65,10 +68,12 @@ static const struct game_params tracks_presets[] = { | |||
65 | {10, 8, DIFF_TRICKY, 1 }, | 68 | {10, 8, DIFF_TRICKY, 1 }, |
66 | {10, 10, DIFF_EASY, 1}, | 69 | {10, 10, DIFF_EASY, 1}, |
67 | {10, 10, DIFF_TRICKY, 1}, | 70 | {10, 10, DIFF_TRICKY, 1}, |
71 | {10, 10, DIFF_HARD, 1}, | ||
68 | {15, 10, DIFF_EASY, 1}, | 72 | {15, 10, DIFF_EASY, 1}, |
69 | {15, 10, DIFF_TRICKY, 1}, | 73 | {15, 10, DIFF_TRICKY, 1}, |
70 | {15, 15, DIFF_EASY, 1}, | 74 | {15, 15, DIFF_EASY, 1}, |
71 | {15, 15, DIFF_TRICKY, 1}, | 75 | {15, 15, DIFF_TRICKY, 1}, |
76 | {15, 15, DIFF_HARD, 1}, | ||
72 | }; | 77 | }; |
73 | 78 | ||
74 | static bool game_fetch_preset(int i, char **name, game_params **params) | 79 | static bool game_fetch_preset(int i, char **name, game_params **params) |
@@ -452,7 +457,7 @@ start: | |||
452 | state->numbers->col_s = px; | 457 | state->numbers->col_s = px; |
453 | } | 458 | } |
454 | 459 | ||
455 | static int tracks_solve(game_state *state, int diff); | 460 | static int tracks_solve(game_state *state, int diff, int *max_diff_out); |
456 | static void debug_state(game_state *state, const char *what); | 461 | static void debug_state(game_state *state, const char *what); |
457 | 462 | ||
458 | /* Clue-setting algorithm: | 463 | /* Clue-setting algorithm: |
@@ -533,6 +538,26 @@ static game_state *copy_and_strip(const game_state *state, game_state *ret, int | |||
533 | return ret; | 538 | return ret; |
534 | } | 539 | } |
535 | 540 | ||
541 | #ifdef STANDALONE_SOLVER | ||
542 | #include <stdarg.h> | ||
543 | static FILE *solver_diagnostics_fp = NULL; | ||
544 | static void solver_diagnostic(const char *fmt, ...) | ||
545 | { | ||
546 | va_list ap; | ||
547 | va_start(ap, fmt); | ||
548 | vfprintf(solver_diagnostics_fp, fmt, ap); | ||
549 | va_end(ap); | ||
550 | fputc('\n', solver_diagnostics_fp); | ||
551 | } | ||
552 | #define solverdebug(printf_params) do { \ | ||
553 | if (solver_diagnostics_fp) { \ | ||
554 | solver_diagnostic printf_params; \ | ||
555 | } \ | ||
556 | } while (0) | ||
557 | #else | ||
558 | #define solverdebug(printf_params) ((void)0) | ||
559 | #endif | ||
560 | |||
536 | static int solve_progress(const game_state *state) { | 561 | static int solve_progress(const game_state *state) { |
537 | int i, w = state->p.w, h = state->p.h, progress = 0; | 562 | int i, w = state->p.w, h = state->p.h, progress = 0; |
538 | 563 | ||
@@ -575,6 +600,7 @@ static int add_clues(game_state *state, random_state *rs, int diff) | |||
575 | int *positions = snewn(w*h, int), npositions = 0; | 600 | int *positions = snewn(w*h, int), npositions = 0; |
576 | int *nedges_previous_solve = snewn(w*h, int); | 601 | int *nedges_previous_solve = snewn(w*h, int); |
577 | game_state *scratch = dup_game(state); | 602 | game_state *scratch = dup_game(state); |
603 | int diff_used; | ||
578 | 604 | ||
579 | debug_state(state, "gen: Initial board"); | 605 | debug_state(state, "gen: Initial board"); |
580 | 606 | ||
@@ -591,17 +617,13 @@ static int add_clues(game_state *state, random_state *rs, int diff) | |||
591 | 617 | ||
592 | /* First, check whether the puzzle is already either too easy, or just right */ | 618 | /* First, check whether the puzzle is already either too easy, or just right */ |
593 | scratch = copy_and_strip(state, scratch, -1); | 619 | scratch = copy_and_strip(state, scratch, -1); |
594 | if (diff > 0) { | 620 | sr = tracks_solve(scratch, diff, &diff_used); |
595 | sr = tracks_solve(scratch, diff-1); | 621 | if (diff_used < diff) { |
596 | if (sr < 0) | 622 | ret = -1; /* already too easy, even without adding clues. */ |
597 | assert(!"Generator should not have created impossible puzzle"); | 623 | debug(("gen: ...already too easy, need new board.")); |
598 | if (sr > 0) { | 624 | goto done; |
599 | ret = -1; /* already too easy, even without adding clues. */ | ||
600 | debug(("gen: ...already too easy, need new board.")); | ||
601 | goto done; | ||
602 | } | ||
603 | } | 625 | } |
604 | sr = tracks_solve(scratch, diff); | 626 | |
605 | if (sr < 0) | 627 | if (sr < 0) |
606 | assert(!"Generator should not have created impossible puzzle"); | 628 | assert(!"Generator should not have created impossible puzzle"); |
607 | if (sr > 0) { | 629 | if (sr > 0) { |
@@ -629,12 +651,10 @@ static int add_clues(game_state *state, random_state *rs, int diff) | |||
629 | if (check_phantom_moves(scratch)) | 651 | if (check_phantom_moves(scratch)) |
630 | continue; /* adding a clue here would add phantom track */ | 652 | continue; /* adding a clue here would add phantom track */ |
631 | 653 | ||
632 | if (diff > 0) { | 654 | if (tracks_solve(scratch, diff, &diff_used) > 0) { |
633 | if (tracks_solve(scratch, diff-1) > 0) { | 655 | if (diff_used < diff) { |
634 | continue; /* adding a clue here makes it too easy */ | 656 | continue; /* adding a clue here makes it too easy */ |
635 | } | 657 | } |
636 | } | ||
637 | if (tracks_solve(scratch, diff) > 0) { | ||
638 | /* we're now soluble (and we weren't before): add this clue, and then | 658 | /* we're now soluble (and we weren't before): add this clue, and then |
639 | start stripping clues */ | 659 | start stripping clues */ |
640 | debug(("gen: ...adding clue at (%d,%d), now soluble", i%w, i/w)); | 660 | debug(("gen: ...adding clue at (%d,%d), now soluble", i%w, i/w)); |
@@ -676,7 +696,7 @@ strip_clues: | |||
676 | if (check_phantom_moves(scratch)) | 696 | if (check_phantom_moves(scratch)) |
677 | continue; /* removing a clue here would add phantom track */ | 697 | continue; /* removing a clue here would add phantom track */ |
678 | 698 | ||
679 | if (tracks_solve(scratch, diff) > 0) { | 699 | if (tracks_solve(scratch, diff, NULL) > 0) { |
680 | debug(("gen: ... removing clue at (%d,%d), still soluble without it", i%w, i/w)); | 700 | debug(("gen: ... removing clue at (%d,%d), still soluble without it", i%w, i/w)); |
681 | state->sflags[i] &= ~S_CLUE; /* still soluble without this clue. */ | 701 | state->sflags[i] &= ~S_CLUE; /* still soluble without this clue. */ |
682 | } | 702 | } |
@@ -686,6 +706,7 @@ strip_clues: | |||
686 | 706 | ||
687 | done: | 707 | done: |
688 | sfree(positions); | 708 | sfree(positions); |
709 | sfree(nedges_previous_solve); | ||
689 | free_game(scratch); | 710 | free_game(scratch); |
690 | return ret; | 711 | return ret; |
691 | } | 712 | } |
@@ -780,7 +801,7 @@ newpath: | |||
780 | } | 801 | } |
781 | *p++ = '\0'; | 802 | *p++ = '\0'; |
782 | 803 | ||
783 | ret = tracks_solve(state, DIFFCOUNT); | 804 | ret = tracks_solve(state, DIFFCOUNT, NULL); |
784 | assert(ret >= 0); | 805 | assert(ret >= 0); |
785 | free_game(state); | 806 | free_game(state); |
786 | 807 | ||
@@ -882,6 +903,10 @@ static game_state *new_game(midend *me, const game_params *params, const char *d | |||
882 | return state; | 903 | return state; |
883 | } | 904 | } |
884 | 905 | ||
906 | struct solver_scratch { | ||
907 | int *dsf; | ||
908 | }; | ||
909 | |||
885 | static int solve_set_sflag(game_state *state, int x, int y, | 910 | static int solve_set_sflag(game_state *state, int x, int y, |
886 | unsigned int f, const char *why) | 911 | unsigned int f, const char *why) |
887 | { | 912 | { |
@@ -889,10 +914,10 @@ static int solve_set_sflag(game_state *state, int x, int y, | |||
889 | 914 | ||
890 | if (state->sflags[i] & f) | 915 | if (state->sflags[i] & f) |
891 | return 0; | 916 | return 0; |
892 | debug(("solve: square (%d,%d) -> %s: %s", | 917 | solverdebug(("square (%d,%d) -> %s: %s", |
893 | x, y, (f == S_TRACK ? "TRACK" : "NOTRACK"), why)); | 918 | x, y, (f == S_TRACK ? "TRACK" : "NOTRACK"), why)); |
894 | if (state->sflags[i] & (f == S_TRACK ? S_NOTRACK : S_TRACK)) { | 919 | if (state->sflags[i] & (f == S_TRACK ? S_NOTRACK : S_TRACK)) { |
895 | debug(("solve: opposite flag already set there, marking IMPOSSIBLE")); | 920 | solverdebug(("opposite flag already set there, marking IMPOSSIBLE")); |
896 | state->impossible = true; | 921 | state->impossible = true; |
897 | } | 922 | } |
898 | state->sflags[i] |= f; | 923 | state->sflags[i] |= f; |
@@ -906,11 +931,11 @@ static int solve_set_eflag(game_state *state, int x, int y, int d, | |||
906 | 931 | ||
907 | if (sf & f) | 932 | if (sf & f) |
908 | return 0; | 933 | return 0; |
909 | debug(("solve: edge (%d,%d)/%c -> %s: %s", x, y, | 934 | solverdebug(("edge (%d,%d)/%c -> %s: %s", x, y, |
910 | (d == U) ? 'U' : (d == D) ? 'D' : (d == L) ? 'L' : 'R', | 935 | (d == U) ? 'U' : (d == D) ? 'D' : (d == L) ? 'L' : 'R', |
911 | (f == S_TRACK ? "TRACK" : "NOTRACK"), why)); | 936 | (f == S_TRACK ? "TRACK" : "NOTRACK"), why)); |
912 | if (sf & (f == E_TRACK ? E_NOTRACK : E_TRACK)) { | 937 | if (sf & (f == E_TRACK ? E_NOTRACK : E_TRACK)) { |
913 | debug(("solve: opposite flag already set there, marking IMPOSSIBLE")); | 938 | solverdebug(("opposite flag already set there, marking IMPOSSIBLE")); |
914 | state->impossible = true; | 939 | state->impossible = true; |
915 | } | 940 | } |
916 | S_E_SET(state, x, y, d, f); | 941 | S_E_SET(state, x, y, d, f); |
@@ -1063,7 +1088,7 @@ static int solve_check_single_sub(game_state *state, int si, int id, int n, | |||
1063 | if (ctrack != (target-1)) return 0; | 1088 | if (ctrack != (target-1)) return 0; |
1064 | if (nperp > 0 || n1edge != 1) return 0; | 1089 | if (nperp > 0 || n1edge != 1) return 0; |
1065 | 1090 | ||
1066 | debug(("check_single from (%d,%d): 1 match from (%d,%d)", | 1091 | solverdebug(("check_single from (%d,%d): 1 match from (%d,%d)", |
1067 | si%w, si/w, i1edge%w, i1edge/w)); | 1092 | si%w, si/w, i1edge%w, i1edge/w)); |
1068 | 1093 | ||
1069 | /* We have a match: anything that's more than 1 away from this square | 1094 | /* We have a match: anything that's more than 1 away from this square |
@@ -1120,12 +1145,12 @@ static int solve_check_loose_sub(game_state *state, int si, int id, int n, | |||
1120 | } | 1145 | } |
1121 | 1146 | ||
1122 | if (nloose > (target - e2count)) { | 1147 | if (nloose > (target - e2count)) { |
1123 | debug(("check %s from (%d,%d): more loose (%d) than empty (%d), IMPOSSIBLE", | 1148 | solverdebug(("check %s from (%d,%d): more loose (%d) than empty (%d), IMPOSSIBLE", |
1124 | what, si%w, si/w, nloose, target-e2count)); | 1149 | what, si%w, si/w, nloose, target-e2count)); |
1125 | state->impossible = true; | 1150 | state->impossible = true; |
1126 | } | 1151 | } |
1127 | if (nloose > 0 && nloose == (target - e2count)) { | 1152 | if (nloose > 0 && nloose == (target - e2count)) { |
1128 | debug(("check %s from (%d,%d): nloose = empty (%d), forcing loners out.", | 1153 | solverdebug(("check %s from (%d,%d): nloose = empty (%d), forcing loners out.", |
1129 | what, si%w, si/w, nloose)); | 1154 | what, si%w, si/w, nloose)); |
1130 | for (j = 0, i = si; j < n; j++, i += id) { | 1155 | for (j = 0, i = si; j < n; j++, i += id) { |
1131 | if (!(state->sflags[i] & S_MARK)) | 1156 | if (!(state->sflags[i] & S_MARK)) |
@@ -1146,7 +1171,7 @@ static int solve_check_loose_sub(game_state *state, int si, int id, int n, | |||
1146 | } | 1171 | } |
1147 | } | 1172 | } |
1148 | if (nloose == 1 && (target - e2count) == 2 && nperp == 0) { | 1173 | if (nloose == 1 && (target - e2count) == 2 && nperp == 0) { |
1149 | debug(("check %s from (%d,%d): 1 loose end, 2 empty squares, forcing parallel", | 1174 | solverdebug(("check %s from (%d,%d): 1 loose end, 2 empty squares, forcing parallel", |
1150 | what, si%w, si/w)); | 1175 | what, si%w, si/w)); |
1151 | for (j = 0, i = si; j < n; j++, i += id) { | 1176 | for (j = 0, i = si; j < n; j++, i += id) { |
1152 | if (!(state->sflags[i] & S_MARK)) | 1177 | if (!(state->sflags[i] & S_MARK)) |
@@ -1176,6 +1201,110 @@ static int solve_check_loose_ends(game_state *state) | |||
1176 | return did; | 1201 | return did; |
1177 | } | 1202 | } |
1178 | 1203 | ||
1204 | static void solve_check_neighbours_count( | ||
1205 | game_state *state, int start, int step, int n, int clueindex, | ||
1206 | bool *onefill, bool *oneempty) | ||
1207 | { | ||
1208 | int to_fill = state->numbers->numbers[clueindex]; | ||
1209 | int to_empty = n - to_fill; | ||
1210 | int i; | ||
1211 | for (i = 0; i < n; i++) { | ||
1212 | int p = start + i*step; | ||
1213 | if (state->sflags[p] & S_TRACK) | ||
1214 | to_fill--; | ||
1215 | if (state->sflags[p] & S_NOTRACK) | ||
1216 | to_empty--; | ||
1217 | } | ||
1218 | *onefill = (to_fill == 1); | ||
1219 | *oneempty = (to_empty == 1); | ||
1220 | } | ||
1221 | |||
1222 | static int solve_check_neighbours_try(game_state *state, int x, int y, | ||
1223 | int X, int Y, bool onefill, | ||
1224 | bool oneempty, unsigned dir, | ||
1225 | const char *what) | ||
1226 | { | ||
1227 | int w = state->p.w, p = y*w+x, P = Y*w+X; | ||
1228 | |||
1229 | /* | ||
1230 | * We're given a neighbouring pair of squares p,P, with 'dir' | ||
1231 | * being the direction from the former to the latter. We aim to | ||
1232 | * spot situations in which, if p is a track square, then P must | ||
1233 | * also be one (because p doesn't have enough free exits to avoid | ||
1234 | * using the one that goes towards P). | ||
1235 | * | ||
1236 | * Then, if the target number of track squares on their shared | ||
1237 | * row/column says that there's only one track square left to | ||
1238 | * place, it can't be p, because P would have to be one too, | ||
1239 | * violating the clue. So in that situation we can mark p as | ||
1240 | * unfilled. Conversely, if there's only one _non_-track square | ||
1241 | * left to place, it can't be P, so we can mark P as filled. | ||
1242 | */ | ||
1243 | |||
1244 | if ((state->sflags[p] | state->sflags[P]) & (S_TRACK | S_NOTRACK)) | ||
1245 | return 0; /* no need: we already know something about these squares */ | ||
1246 | |||
1247 | int possible_exits_except_dir = nbits[ | ||
1248 | ALLDIR & ~dir & ~S_E_DIRS(state, x, y, E_NOTRACK)]; | ||
1249 | if (possible_exits_except_dir >= 2) | ||
1250 | return 0; /* square p need not connect to P, even if it is filled */ | ||
1251 | |||
1252 | /* OK, now we know that if p is filled, P must be filled too. */ | ||
1253 | |||
1254 | int did = 0; | ||
1255 | if (onefill) { | ||
1256 | /* But at most one of them can be filled, so it can't be p. */ | ||
1257 | state->sflags[p] |= S_NOTRACK; | ||
1258 | solverdebug(("square (%d,%d) -> NOTRACK: otherwise, that and (%d,%d) " | ||
1259 | "would make too many TRACK in %s", x, y, X, Y, what)); | ||
1260 | did++; | ||
1261 | } | ||
1262 | if (oneempty) { | ||
1263 | /* Alternatively, at least one of them _must_ be filled, so P | ||
1264 | * must be. */ | ||
1265 | state->sflags[P] |= S_TRACK; | ||
1266 | solverdebug(("square (%d,%d) -> TRACK: otherwise, that and (%d,%d) " | ||
1267 | "would make too many NOTRACK in %s", X, Y, x, y, what)); | ||
1268 | did++; | ||
1269 | } | ||
1270 | return did; | ||
1271 | } | ||
1272 | |||
1273 | static int solve_check_neighbours(game_state *state, bool both_ways) | ||
1274 | { | ||
1275 | int w = state->p.w, h = state->p.h, x, y, did = 0; | ||
1276 | bool onefill, oneempty; | ||
1277 | |||
1278 | for (x = 0; x < w; x++) { | ||
1279 | solve_check_neighbours_count(state, x, w, h, x, &onefill, &oneempty); | ||
1280 | if (!both_ways) | ||
1281 | oneempty = false; /* disable the harder version of the deduction */ | ||
1282 | if (!onefill && !oneempty) | ||
1283 | continue; | ||
1284 | for (y = 0; y+1 < h; y++) { | ||
1285 | did += solve_check_neighbours_try(state, x, y, x, y+1, | ||
1286 | onefill, oneempty, D, "column"); | ||
1287 | did += solve_check_neighbours_try(state, x, y+1, x, y, | ||
1288 | onefill, oneempty, U, "column"); | ||
1289 | } | ||
1290 | } | ||
1291 | for (y = 0; y < h; y++) { | ||
1292 | solve_check_neighbours_count(state, y*w, 1, w, w+y, | ||
1293 | &onefill, &oneempty); | ||
1294 | if (!both_ways) | ||
1295 | oneempty = false; /* disable the harder version of the deduction */ | ||
1296 | if (!onefill && !oneempty) | ||
1297 | continue; | ||
1298 | for (x = 0; x+1 < w; x++) { | ||
1299 | did += solve_check_neighbours_try(state, x, y, x+1, y, | ||
1300 | onefill, oneempty, R, "row"); | ||
1301 | did += solve_check_neighbours_try(state, x+1, y, x, y, | ||
1302 | onefill, oneempty, L, "row"); | ||
1303 | } | ||
1304 | } | ||
1305 | return did; | ||
1306 | } | ||
1307 | |||
1179 | static int solve_check_loop_sub(game_state *state, int x, int y, int dir, | 1308 | static int solve_check_loop_sub(game_state *state, int x, int y, int dir, |
1180 | int *dsf, int startc, int endc) | 1309 | int *dsf, int startc, int endc) |
1181 | { | 1310 | { |
@@ -1195,7 +1324,7 @@ static int solve_check_loop_sub(game_state *state, int x, int y, int dir, | |||
1195 | return solve_set_eflag(state, x, y, dir, E_NOTRACK, "would close loop"); | 1324 | return solve_set_eflag(state, x, y, dir, E_NOTRACK, "would close loop"); |
1196 | } | 1325 | } |
1197 | if ((ic == startc && jc == endc) || (ic == endc && jc == startc)) { | 1326 | if ((ic == startc && jc == endc) || (ic == endc && jc == startc)) { |
1198 | debug(("Adding link at (%d,%d) would join start to end", x, y)); | 1327 | solverdebug(("Adding link at (%d,%d) would join start to end", x, y)); |
1199 | /* We mustn't join the start to the end if: | 1328 | /* We mustn't join the start to the end if: |
1200 | - there are other bits of track that aren't attached to either end | 1329 | - there are other bits of track that aren't attached to either end |
1201 | - the clues are not fully satisfied yet | 1330 | - the clues are not fully satisfied yet |
@@ -1287,10 +1416,145 @@ static void solve_discount_edge(game_state *state, int x, int y, int d) | |||
1287 | solve_set_eflag(state, x, y, d, E_NOTRACK, "outer edge"); | 1416 | solve_set_eflag(state, x, y, d, E_NOTRACK, "outer edge"); |
1288 | } | 1417 | } |
1289 | 1418 | ||
1290 | static int tracks_solve(game_state *state, int diff) | 1419 | static int solve_bridge_sub(game_state *state, int x, int y, int d, |
1420 | struct solver_scratch *sc) | ||
1421 | { | ||
1422 | /* | ||
1423 | * Imagine a graph on the squares of the grid, with an edge | ||
1424 | * connecting neighbouring squares only if it's not yet known | ||
1425 | * whether there's a track between them. | ||
1426 | * | ||
1427 | * This function is called if the edge between x,y and X,Y is a | ||
1428 | * bridge in that graph: that is, it's not part of any loop in the | ||
1429 | * graph, or equivalently, removing it would increase the number | ||
1430 | * of connected components in the graph. | ||
1431 | * | ||
1432 | * In that situation, we can fill in the edge by a parity | ||
1433 | * argument. Construct a closed loop of edges in the grid, all of | ||
1434 | * whose states are known except this one. The track starts and | ||
1435 | * ends outside this loop, so it must cross the boundary of the | ||
1436 | * loop an even number of times. So if we count up how many times | ||
1437 | * the track is known to cross the edges of our loop, then we can | ||
1438 | * fill in the last edge in whichever way makes that number even. | ||
1439 | * | ||
1440 | * In fact, there's not even any need to go to the effort of | ||
1441 | * constructing a _single_ closed loop. The simplest thing is to | ||
1442 | * delete the bridge edge from the graph, find a connected | ||
1443 | * component of the reduced graph whose boundary includes that | ||
1444 | * edge, and take every edge separating that component from | ||
1445 | * another. This may not lead to _exactly one_ cycle - the | ||
1446 | * component could be non-simply connected and have a hole in the | ||
1447 | * middle - but that doesn't matter, because the same parity | ||
1448 | * constraint applies just as well with more than one disjoint | ||
1449 | * loop. | ||
1450 | */ | ||
1451 | int w = state->p.w, h = state->p.h, wh = w*h; | ||
1452 | int X = x + DX(d), Y = y + DY(d); | ||
1453 | int xi, yi, di; | ||
1454 | |||
1455 | assert(d == D || d == R); | ||
1456 | |||
1457 | if (!sc->dsf) | ||
1458 | sc->dsf = snew_dsf(wh); | ||
1459 | dsf_init(sc->dsf, wh); | ||
1460 | |||
1461 | for (xi = 0; xi < w; xi++) { | ||
1462 | for (yi = 0; yi < h; yi++) { | ||
1463 | /* We expect to have been called with X,Y either to the | ||
1464 | * right of x,y or below it, not the other way round. If | ||
1465 | * that were not true, the tests in this loop to exclude | ||
1466 | * the bridge edge would have to be twice as annoying. */ | ||
1467 | |||
1468 | if (yi+1 < h && !S_E_FLAGS(state, xi, yi, D) && | ||
1469 | !(xi == x && yi == y && xi == X && yi+1 == Y)) | ||
1470 | dsf_merge(sc->dsf, yi*w+xi, (yi+1)*w+xi); | ||
1471 | |||
1472 | if (xi+1 < w && !S_E_FLAGS(state, xi, yi, R) && | ||
1473 | !(xi == x && yi == y && xi+1 == X && yi == Y)) | ||
1474 | dsf_merge(sc->dsf, yi*w+xi, yi*w+(xi+1)); | ||
1475 | } | ||
1476 | } | ||
1477 | |||
1478 | int component = dsf_canonify(sc->dsf, y*w+x); | ||
1479 | int parity = 0; | ||
1480 | for (xi = 0; xi < w; xi++) { | ||
1481 | for (yi = 0; yi < h; yi++) { | ||
1482 | if (dsf_canonify(sc->dsf, yi*w+xi) != component) | ||
1483 | continue; | ||
1484 | for (di = 1; di < 16; di *= 2) { | ||
1485 | int Xi = xi + DX(di), Yi = yi + DY(di); | ||
1486 | if ((Xi < 0 || Xi >= w || Yi < 0 || Yi >= h || | ||
1487 | dsf_canonify(sc->dsf, Yi*w+Xi) != component) && | ||
1488 | (S_E_DIRS(state, xi, yi, E_TRACK) & di)) | ||
1489 | parity ^= 1; | ||
1490 | } | ||
1491 | } | ||
1492 | } | ||
1493 | |||
1494 | solve_set_eflag(state, x, y, d, parity ? E_TRACK : E_NOTRACK, "parity"); | ||
1495 | return 1; | ||
1496 | } | ||
1497 | |||
1498 | struct solve_bridge_neighbour_ctx { | ||
1499 | game_state *state; | ||
1500 | int x, y, dirs; | ||
1501 | }; | ||
1502 | static int solve_bridge_neighbour(int vertex, void *vctx) | ||
1503 | { | ||
1504 | struct solve_bridge_neighbour_ctx *ctx = | ||
1505 | (struct solve_bridge_neighbour_ctx *)vctx; | ||
1506 | int w = ctx->state->p.w; | ||
1507 | |||
1508 | if (vertex >= 0) { | ||
1509 | ctx->x = vertex % w; | ||
1510 | ctx->y = vertex / w; | ||
1511 | ctx->dirs = ALLDIR | ||
1512 | & ~S_E_DIRS(ctx->state, ctx->x, ctx->y, E_TRACK) | ||
1513 | & ~S_E_DIRS(ctx->state, ctx->x, ctx->y, E_NOTRACK); | ||
1514 | } | ||
1515 | unsigned dir = ctx->dirs & -ctx->dirs; /* isolate lowest set bit */ | ||
1516 | if (!dir) | ||
1517 | return -1; | ||
1518 | ctx->dirs &= ~dir; | ||
1519 | int xr = ctx->x + DX(dir), yr = ctx->y + DY(dir); | ||
1520 | assert(0 <= xr && xr < w); | ||
1521 | assert(0 <= yr && yr < ctx->state->p.h); | ||
1522 | return yr * w + xr; | ||
1523 | } | ||
1524 | |||
1525 | static int solve_check_bridge_parity(game_state *state, | ||
1526 | struct solver_scratch *sc) | ||
1527 | { | ||
1528 | int w = state->p.w, h = state->p.h, wh = w*h; | ||
1529 | struct findloopstate *fls; | ||
1530 | struct solve_bridge_neighbour_ctx ctx[1]; | ||
1531 | int x, y, did = 0; | ||
1532 | |||
1533 | ctx->state = state; | ||
1534 | fls = findloop_new_state(wh); | ||
1535 | findloop_run(fls, wh, solve_bridge_neighbour, ctx); | ||
1536 | |||
1537 | for (x = 0; x < w; x++) { | ||
1538 | for (y = 0; y < h; y++) { | ||
1539 | if (y+1 < h && !findloop_is_loop_edge(fls, y*w+x, (y+1)*w+x)) | ||
1540 | did += solve_bridge_sub(state, x, y, D, sc); | ||
1541 | if (x+1 < w && !findloop_is_loop_edge(fls, y*w+x, y*w+(x+1))) | ||
1542 | did += solve_bridge_sub(state, x, y, R, sc); | ||
1543 | } | ||
1544 | } | ||
1545 | |||
1546 | findloop_free_state(fls); | ||
1547 | |||
1548 | return did; | ||
1549 | } | ||
1550 | |||
1551 | static int tracks_solve(game_state *state, int diff, int *max_diff_out) | ||
1291 | { | 1552 | { |
1292 | int x, y, w = state->p.w, h = state->p.h; | 1553 | int x, y, w = state->p.w, h = state->p.h; |
1293 | bool didsth; | 1554 | struct solver_scratch sc[1]; |
1555 | int max_diff = DIFF_EASY; | ||
1556 | |||
1557 | sc->dsf = NULL; | ||
1294 | 1558 | ||
1295 | debug(("solve...")); | 1559 | debug(("solve...")); |
1296 | state->impossible = false; | 1560 | state->impossible = false; |
@@ -1305,21 +1569,37 @@ static int tracks_solve(game_state *state, int diff) | |||
1305 | solve_discount_edge(state, w-1, y, R); | 1569 | solve_discount_edge(state, w-1, y, R); |
1306 | } | 1570 | } |
1307 | 1571 | ||
1308 | while (1) { | 1572 | while (!state->impossible) { |
1309 | didsth = false; | ||
1310 | 1573 | ||
1311 | didsth |= solve_update_flags(state); | 1574 | /* Can't use do ... while (0) because we need a 'continue' in this macro */ |
1312 | didsth |= solve_count_clues(state); | 1575 | #define TRY(curr_diff, funcall) \ |
1313 | didsth |= solve_check_loop(state); | 1576 | if (diff >= (curr_diff) && (funcall)) { \ |
1577 | if (max_diff < curr_diff) \ | ||
1578 | max_diff = curr_diff; \ | ||
1579 | continue; \ | ||
1580 | } else ((void)0) | ||
1314 | 1581 | ||
1315 | if (diff >= DIFF_TRICKY) { | 1582 | TRY(DIFF_EASY, solve_update_flags(state)); |
1316 | didsth |= solve_check_single(state); | 1583 | TRY(DIFF_EASY, solve_count_clues(state)); |
1317 | didsth |= solve_check_loose_ends(state); | 1584 | TRY(DIFF_EASY, solve_check_loop(state)); |
1318 | } | ||
1319 | 1585 | ||
1320 | if (!didsth || state->impossible) break; | 1586 | TRY(DIFF_TRICKY, solve_check_single(state)); |
1587 | TRY(DIFF_TRICKY, solve_check_loose_ends(state)); | ||
1588 | TRY(DIFF_TRICKY, solve_check_neighbours(state, false)); | ||
1589 | |||
1590 | TRY(DIFF_HARD, solve_check_neighbours(state, true)); | ||
1591 | TRY(DIFF_HARD, solve_check_bridge_parity(state, sc)); | ||
1592 | |||
1593 | #undef TRY | ||
1594 | |||
1595 | break; | ||
1321 | } | 1596 | } |
1322 | 1597 | ||
1598 | sfree(sc->dsf); | ||
1599 | |||
1600 | if (max_diff_out) | ||
1601 | *max_diff_out = max_diff; | ||
1602 | |||
1323 | return state->impossible ? -1 : check_completion(state, false) ? 1 : 0; | 1603 | return state->impossible ? -1 : check_completion(state, false) ? 1 : 0; |
1324 | } | 1604 | } |
1325 | 1605 | ||
@@ -1379,11 +1659,11 @@ static char *solve_game(const game_state *state, const game_state *currstate, | |||
1379 | char *move; | 1659 | char *move; |
1380 | 1660 | ||
1381 | solved = dup_game(currstate); | 1661 | solved = dup_game(currstate); |
1382 | ret = tracks_solve(solved, DIFFCOUNT); | 1662 | ret = tracks_solve(solved, DIFFCOUNT, NULL); |
1383 | if (ret < 1) { | 1663 | if (ret < 1) { |
1384 | free_game(solved); | 1664 | free_game(solved); |
1385 | solved = dup_game(state); | 1665 | solved = dup_game(state); |
1386 | ret = tracks_solve(solved, DIFFCOUNT); | 1666 | ret = tracks_solve(solved, DIFFCOUNT, NULL); |
1387 | } | 1667 | } |
1388 | 1668 | ||
1389 | if (ret < 1) { | 1669 | if (ret < 1) { |
@@ -2094,7 +2374,7 @@ static game_state *execute_move(const game_state *state, const char *move) | |||
2094 | goto badmove; | 2374 | goto badmove; |
2095 | move += n; | 2375 | move += n; |
2096 | } else if (c == 'H') { | 2376 | } else if (c == 'H') { |
2097 | tracks_solve(ret, DIFFCOUNT); | 2377 | tracks_solve(ret, DIFFCOUNT, NULL); |
2098 | move++; | 2378 | move++; |
2099 | } else { | 2379 | } else { |
2100 | goto badmove; | 2380 | goto badmove; |
@@ -2675,4 +2955,87 @@ const struct game thegame = { | |||
2675 | 0, /* flags */ | 2955 | 0, /* flags */ |
2676 | }; | 2956 | }; |
2677 | 2957 | ||
2958 | #ifdef STANDALONE_SOLVER | ||
2959 | |||
2960 | int main(int argc, char **argv) | ||
2961 | { | ||
2962 | game_params *p; | ||
2963 | game_state *s; | ||
2964 | char *id = NULL, *desc; | ||
2965 | int maxdiff = DIFFCOUNT, diff_used; | ||
2966 | const char *err; | ||
2967 | bool diagnostics = false, grade = false; | ||
2968 | int retd; | ||
2969 | |||
2970 | while (--argc > 0) { | ||
2971 | char *p = *++argv; | ||
2972 | if (!strcmp(p, "-v")) { | ||
2973 | diagnostics = true; | ||
2974 | } else if (!strcmp(p, "-g")) { | ||
2975 | grade = true; | ||
2976 | } else if (!strncmp(p, "-d", 2) && p[2] && !p[3]) { | ||
2977 | int i; | ||
2978 | bool bad = true; | ||
2979 | for (i = 0; i < lenof(tracks_diffchars); i++) | ||
2980 | if (tracks_diffchars[i] == p[2]) { | ||
2981 | bad = false; | ||
2982 | maxdiff = i; | ||
2983 | break; | ||
2984 | } | ||
2985 | if (bad) { | ||
2986 | fprintf(stderr, "%s: unrecognised difficulty `%c'\n", | ||
2987 | argv[0], p[2]); | ||
2988 | return 1; | ||
2989 | } | ||
2990 | } else if (*p == '-') { | ||
2991 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); | ||
2992 | return 1; | ||
2993 | } else { | ||
2994 | id = p; | ||
2995 | } | ||
2996 | } | ||
2997 | |||
2998 | if (!id) { | ||
2999 | fprintf(stderr, "usage: %s [-v | -g] <game_id>\n", argv[0]); | ||
3000 | return 1; | ||
3001 | } | ||
3002 | |||
3003 | desc = strchr(id, ':'); | ||
3004 | if (!desc) { | ||
3005 | fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); | ||
3006 | return 1; | ||
3007 | } | ||
3008 | *desc++ = '\0'; | ||
3009 | |||
3010 | p = default_params(); | ||
3011 | decode_params(p, id); | ||
3012 | err = validate_desc(p, desc); | ||
3013 | if (err) { | ||
3014 | fprintf(stderr, "%s: %s\n", argv[0], err); | ||
3015 | return 1; | ||
3016 | } | ||
3017 | s = new_game(NULL, p, desc); | ||
3018 | |||
3019 | solver_diagnostics_fp = (diagnostics ? stdout : NULL); | ||
3020 | retd = tracks_solve(s, maxdiff, &diff_used); | ||
3021 | if (retd < 0) { | ||
3022 | printf("Puzzle is inconsistent\n"); | ||
3023 | } else if (grade) { | ||
3024 | printf("Difficulty rating: %s\n", | ||
3025 | (retd == 0 ? "Ambiguous" : tracks_diffnames[diff_used])); | ||
3026 | } else { | ||
3027 | char *text = game_text_format(s); | ||
3028 | fputs(text, stdout); | ||
3029 | sfree(text); | ||
3030 | if (retd == 0) | ||
3031 | printf("Could not deduce a unique solution\n"); | ||
3032 | } | ||
3033 | free_game(s); | ||
3034 | free_params(p); | ||
3035 | |||
3036 | return 0; | ||
3037 | } | ||
3038 | |||
3039 | #endif | ||
3040 | |||
2678 | /* vim: set shiftwidth=4 tabstop=8: */ | 3041 | /* vim: set shiftwidth=4 tabstop=8: */ |