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);
}
}
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);
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<<j;
+ if (dirs & dir) {
+ int nx = x + DX(dir), ny = y + DY(dir);
+ if (INGRID(state, nx, ny))
+ ctx->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++) {
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++;
}
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++;
}
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)) {
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;
}
}
const struct game thegame = {
"Train Tracks", "games.tracks", "tracks",
default_params,
- game_fetch_preset,
+ game_fetch_preset, NULL,
decode_params,
encode_params,
free_params,