X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=tracks.c;h=43428a19e92b95cac1b551ebea0225d766bb3ee9;hb=a0a581c8b5422bf0c5ed3fde6aa25811e4eb89fc;hp=0944ca1b3596ee5ae73045ab459b05253c951aa6;hpb=362bf8d450b6de02f8175afe979e2bca36d48c67;p=sgt-puzzles.git diff --git a/tracks.c b/tracks.c index 0944ca1..43428a1 100644 --- a/tracks.c +++ b/tracks.c @@ -1072,7 +1072,7 @@ static int solve_check_single_sub(game_state *state, int si, int id, int n, x = i%w; y = i/w; if (abs(ox-x) > 1 || abs(oy-y) > 1) { - if (!state->sflags[i] & S_TRACK) + if (!(state->sflags[i] & S_TRACK)) did += solve_set_sflag(state, x, y, S_NOTRACK, what); } } @@ -1490,11 +1490,10 @@ static void debug_state(game_state *state, const char *what) { sfree(sstring); } -static void dsf_update_completion(game_state *state, int *loopclass, - int ax, int ay, char dir, - int *dsf) +static void dsf_update_completion(game_state *state, int ax, int ay, + char dir, int *dsf) { - int w = state->p.w, ai = ay*w+ax, bx, by, bi, ac, bc; + int w = state->p.w, ai = ay*w+ax, bx, by, bi; if (!(S_E_DIRS(state, ax, ay, E_TRACK) & dir)) return; bx = ax + DX(dir); @@ -1503,22 +1502,47 @@ static void dsf_update_completion(game_state *state, int *loopclass, if (!INGRID(state, bx, by)) return; bi = by*w+bx; - ac = dsf_canonify(dsf, ai); - bc = dsf_canonify(dsf, bi); + dsf_merge(dsf, ai, bi); +} - if (ac == bc) { - /* loop detected */ - *loopclass = ac; - } else { - dsf_merge(dsf, ai, bi); +struct tracks_neighbour_ctx { + game_state *state; + int i, n, neighbours[4]; +}; +static int tracks_neighbour(int vertex, void *vctx) +{ + struct tracks_neighbour_ctx *ctx = (struct tracks_neighbour_ctx *)vctx; + if (vertex >= 0) { + game_state *state = ctx->state; + int w = state->p.w, x = vertex % w, y = vertex / w; + int dirs = S_E_DIRS(state, x, y, E_TRACK); + int j; + + ctx->i = ctx->n = 0; + + for (j = 0; j < 4; j++) { + int dir = 1<neighbours[ctx->n++] = ny * w + nx; + } + } } + + if (ctx->i < ctx->n) + return ctx->neighbours[ctx->i++]; + else + return -1; } static int check_completion(game_state *state, int mark) { int w = state->p.w, h = state->p.h, x, y, i, target, ret = TRUE; - int ntrack, nnotrack; - int *dsf, loopclass, pathclass; + int ntrack, nnotrack, ntrackcomplete; + int *dsf, pathclass; + struct findloopstate *fls; + struct tracks_neighbour_ctx ctx; if (mark) { for (i = 0; i < w+h; i++) { @@ -1527,19 +1551,28 @@ static int check_completion(game_state *state, int mark) for (i = 0; i < w*h; i++) { state->sflags[i] &= ~S_ERROR; if (S_E_COUNT(state, i%w, i/w, E_TRACK) > 0) { - if (S_E_COUNT(state, i%w, i/w, E_TRACK) > 2) + if (S_E_COUNT(state, i%w, i/w, E_TRACK) > 2) { + ret = FALSE; state->sflags[i] |= S_ERROR; + } } } } - /* A cell is 'complete' if it has any edges marked as TRACK. */ + /* A cell is 'complete', for the purposes of marking the game as + * finished, if it has two edges marked as TRACK. But it only has + * to have one edge marked as TRACK, or be filled in as trackful + * without any specific edges known, to count towards checking + * row/column clue errors. */ for (x = 0; x < w; x++) { target = state->numbers->numbers[x]; - ntrack = nnotrack = 0; + ntrack = nnotrack = ntrackcomplete = 0; for (y = 0; y < h; y++) { - if (S_E_COUNT(state, x, y, E_TRACK) > 0) + if (S_E_COUNT(state, x, y, E_TRACK) > 0 || + state->sflags[y*w+x] & S_TRACK) ntrack++; + if (S_E_COUNT(state, x, y, E_TRACK) == 2) + ntrackcomplete++; if (state->sflags[y*w+x] & S_NOTRACK) nnotrack++; } @@ -1548,17 +1581,21 @@ static int check_completion(game_state *state, int mark) debug(("col %d error: target %d, track %d, notrack %d", x, target, ntrack, nnotrack)); state->num_errors[x] = 1; + ret = FALSE; } } - if (ntrack != target) + if (ntrackcomplete != target) ret = FALSE; } for (y = 0; y < h; y++) { target = state->numbers->numbers[w+y]; - ntrack = nnotrack = 0; + ntrack = nnotrack = ntrackcomplete = 0; for (x = 0; x < w; x++) { - if (S_E_COUNT(state, x, y, E_TRACK) == 2) + if (S_E_COUNT(state, x, y, E_TRACK) > 0 || + state->sflags[y*w+x] & S_TRACK) ntrack++; + if (S_E_COUNT(state, x, y, E_TRACK) == 2) + ntrackcomplete++; if (state->sflags[y*w+x] & S_NOTRACK) nnotrack++; } @@ -1567,36 +1604,44 @@ static int check_completion(game_state *state, int mark) debug(("row %d error: target %d, track %d, notrack %d", y, target, ntrack, nnotrack)); state->num_errors[w+y] = 1; + ret = FALSE; } } - if (ntrack != target) + if (ntrackcomplete != target) ret = FALSE; } dsf = snewn(w*h, int); dsf_init(dsf, w*h); - loopclass = -1; for (x = 0; x < w; x++) { for (y = 0; y < h; y++) { - dsf_update_completion(state, &loopclass, x, y, R, dsf); - dsf_update_completion(state, &loopclass, x, y, D, dsf); + dsf_update_completion(state, x, y, R, dsf); + dsf_update_completion(state, x, y, D, dsf); } } - if (loopclass != -1) { + + fls = findloop_new_state(w*h); + ctx.state = state; + if (findloop_run(fls, w*h, tracks_neighbour, &ctx)) { debug(("loop detected, not complete")); ret = FALSE; /* no loop allowed */ if (mark) { for (x = 0; x < w; x++) { for (y = 0; y < h; y++) { - /* TODO this will only highlight the first loop found */ - if (dsf_canonify(dsf, y*w + x) == loopclass) { - state->sflags[y*w+x] |= S_ERROR; - } + int u, v; + + u = y*w + x; + for (v = tracks_neighbour(u, &ctx); v >= 0; + v = tracks_neighbour(-1, &ctx)) + if (findloop_is_loop_edge(fls, u, v)) + state->sflags[y*w+x] |= S_ERROR; } } } } + findloop_free_state(fls); + if (mark) { pathclass = dsf_canonify(dsf, state->numbers->row_s*w); if (pathclass == dsf_canonify(dsf, (h-1)*w + state->numbers->col_s)) { @@ -1605,9 +1650,17 @@ static int check_completion(game_state *state, int mark) for (i = 0; i < w*h; i++) { if ((dsf_canonify(dsf, i) != pathclass) && ((state->sflags[i] & S_TRACK) || - (S_E_COUNT(state, i%w, i/w, E_TRACK) > 0))) + (S_E_COUNT(state, i%w, i/w, E_TRACK) > 0))) { + ret = FALSE; state->sflags[i] |= S_ERROR; + } } + } else { + /* If we _don't_ have such a path, then certainly the game + * can't be in a winning state. So even if we're not + * highlighting any _errors_, we certainly shouldn't + * return true. */ + ret = FALSE; } } @@ -2569,7 +2622,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize) const struct game thegame = { "Train Tracks", "games.tracks", "tracks", default_params, - game_fetch_preset, + game_fetch_preset, NULL, decode_params, encode_params, free_params,