X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=pearl.c;h=c6c305f3f22a477d69e177b78770ef04b590d588;hb=a0a581c8b5422bf0c5ed3fde6aa25811e4eb89fc;hp=977577f55bb1d78bf9b05ad9e33b36fc1b77498b;hpb=ea8da331e361c96a7e563b0a91dc3535e0d1d545;p=sgt-puzzles.git diff --git a/pearl.c b/pearl.c index 977577f..c6c305f 100644 --- a/pearl.c +++ b/pearl.c @@ -130,7 +130,6 @@ struct game_state { char *errors; /* size w*h: errors detected */ char *marks; /* size w*h: 'no line here' marks placed. */ int completed, used_solve; - int loop_length; /* filled in by check_completion when complete. */ }; #define DEFAULT_PRESET 3 @@ -1496,12 +1495,11 @@ static char nbits[16] = { 0, 1, 1, 2, #define ERROR_CLUE 16 -static void dsf_update_completion(game_state *state, int *loopclass, - int ax, int ay, char dir, - int *dsf, int *dsfsize) +static void dsf_update_completion(game_state *state, int ax, int ay, char dir, + int *dsf) { int w = state->shared->w /*, h = state->shared->h */; - int ac = ay*w+ax, ae, bx, by, bc, be; + int ac = ay*w+ax, bx, by, bc; if (!(state->lines[ac] & dir)) return; /* no link */ bx = ax + DX(dir); by = ay + DY(dir); @@ -1509,34 +1507,19 @@ static void dsf_update_completion(game_state *state, int *loopclass, assert(INGRID(state, bx, by)); /* should not have a link off grid */ bc = by*w+bx; -#if 0 assert(state->lines[bc] & F(dir)); /* should have reciprocal link */ -#endif - /* TODO put above assertion back in once we stop generating partially - * soluble puzzles. */ if (!(state->lines[bc] & F(dir))) return; - ae = dsf_canonify(dsf, ac); - be = dsf_canonify(dsf, bc); - - if (ae == be) { /* detected a loop! */ - if (*loopclass != -1) /* this is the second loop, doom. */ - return; - *loopclass = ae; - } else { - int size = dsfsize[ae] + dsfsize[be]; - dsf_merge(dsf, ac, bc); - ae = dsf_canonify(dsf, ac); - dsfsize[ae] = size; - } - return; + dsf_merge(dsf, ac, bc); } static void check_completion(game_state *state, int mark) { int w = state->shared->w, h = state->shared->h, x, y, i, d; - int had_error = FALSE /*, is_complete = FALSE */, loopclass; - int *dsf, *dsfsize; + int had_error = FALSE; + int *dsf, *component_state; + int nsilly, nloop, npath, largest_comp, largest_size, total_pathsize; + enum { COMP_NONE, COMP_LOOP, COMP_PATH, COMP_SILLY, COMP_EMPTY }; if (mark) { for (i = 0; i < w*h; i++) { @@ -1547,57 +1530,109 @@ static void check_completion(game_state *state, int mark) #define ERROR(x,y,e) do { had_error = TRUE; if (mark) state->errors[(y)*w+(x)] |= (e); } while(0) /* - * First of all: we should have one single closed loop, passing through all clues. + * Analyse the solution into loops, paths and stranger things. + * Basic strategy here is all the same as in Loopy - see the big + * comment in loopy.c's check_completion() - and for exactly the + * same reasons, since Loopy and Pearl have basically the same + * form of expected solution. */ - dsf = snewn(w*h, int); - dsfsize = snewn(w*h, int); - dsf_init(dsf, w*h); - for (i = 0; i < w*h; i++) dsfsize[i] = 1; - loopclass = -1; + dsf = snew_dsf(w*h); + /* Build the dsf. */ for (x = 0; x < w; x++) { for (y = 0; y < h; y++) { - dsf_update_completion(state, &loopclass, x, y, R, dsf, dsfsize); - dsf_update_completion(state, &loopclass, x, y, D, dsf, dsfsize); + dsf_update_completion(state, x, y, R, dsf); + dsf_update_completion(state, x, y, D, dsf); } } - if (loopclass != -1) { - /* We have a loop. Check all squares with lines on. */ - for (x = 0; x < w; x++) { - for (y = 0; y < h; y++) { - if (state->lines[y*w+x] == BLANK) { - if (state->shared->clues[y*w+x] != NOCLUE) { - /* the loop doesn't include this clue square! */ - ERROR(x, y, ERROR_CLUE); - } - } else { - if (dsf_canonify(dsf, y*w+x) != loopclass) { - /* these lines are not on the loop: mark them as error. */ - ERROR(x, y, state->lines[y*w+x]); - } - } - } - } + + /* Initialise a state variable for each connected component. */ + component_state = snewn(w*h, int); + for (i = 0; i < w*h; i++) { + if (dsf_canonify(dsf, i) == i) + component_state[i] = COMP_LOOP; + else + component_state[i] = COMP_NONE; } /* - * Second: check no clues are contradicted. + * Classify components, and mark errors where a square has more + * than two line segments. */ - for (x = 0; x < w; x++) { for (y = 0; y < h; y++) { int type = state->lines[y*w+x]; - /* - * Check that no square has more than two line segments. - */ - if (NBITS(type) > 2) { + int degree = NBITS(type); + int comp = dsf_canonify(dsf, y*w+x); + if (degree > 2) { ERROR(x,y,type); + component_state[comp] = COMP_SILLY; + } else if (degree == 0) { + component_state[comp] = COMP_EMPTY; + } else if (degree == 1) { + if (component_state[comp] != COMP_SILLY) + component_state[comp] = COMP_PATH; } - /* - * Check that no clues are contradicted. This code is similar to - * the code that sets up the maximal clue array for any given - * loop. - */ + } + } + + /* Count the components, and find the largest sensible one. */ + nsilly = nloop = npath = 0; + total_pathsize = 0; + largest_comp = largest_size = -1; + for (i = 0; i < w*h; i++) { + if (component_state[i] == COMP_SILLY) { + nsilly++; + } else if (component_state[i] == COMP_PATH) { + total_pathsize += dsf_size(dsf, i); + npath = 1; + } else if (component_state[i] == COMP_LOOP) { + int this_size; + + nloop++; + + if ((this_size = dsf_size(dsf, i)) > largest_size) { + largest_comp = i; + largest_size = this_size; + } + } + } + if (largest_size < total_pathsize) { + largest_comp = -1; /* means the paths */ + largest_size = total_pathsize; + } + + if (nloop > 0 && nloop + npath > 1) { + /* + * If there are at least two sensible components including at + * least one loop, highlight every sensible component that is + * not the largest one. + */ + for (i = 0; i < w*h; i++) { + int comp = dsf_canonify(dsf, i); + if ((component_state[comp] == COMP_PATH && + -1 != largest_comp) || + (component_state[comp] == COMP_LOOP && + comp != largest_comp)) + ERROR(i%w, i/w, state->lines[i]); + } + } + + /* Now we've finished with the dsf and component states. The only + * thing we'll need to remember later on is whether all edges were + * part of a single loop, for which our counter variables + * nsilly,nloop,npath are enough. */ + sfree(component_state); + sfree(dsf); + + /* + * Check that no clues are contradicted. This code is similar to + * the code that sets up the maximal clue array for any given + * loop. + */ + for (x = 0; x < w; x++) { + for (y = 0; y < h; y++) { + int type = state->lines[y*w+x]; if (state->shared->clues[y*w+x] == CORNER) { /* Supposed to be a corner: will find a contradiction if * it actually contains a straight line, or if it touches any @@ -1638,15 +1673,30 @@ static void check_completion(game_state *state, int mark) } } } - if (!had_error && loopclass != -1) { - state->completed = TRUE; - state->loop_length = dsfsize[loopclass]; - } - sfree(dsf); - sfree(dsfsize); + if (nloop == 1 && nsilly == 0 && npath == 0) { + /* + * If there's exactly one loop (so that the puzzle is at least + * potentially complete), we need to ensure it hasn't left any + * clue out completely. + */ + for (x = 0; x < w; x++) { + for (y = 0; y < h; y++) { + if (state->lines[y*w+x] == BLANK) { + if (state->shared->clues[y*w+x] != NOCLUE) { + /* the loop doesn't include this clue square! */ + ERROR(x, y, ERROR_CLUE); + } + } + } + } - return; + /* + * But if not, then we're done! + */ + if (!had_error) + state->completed = TRUE; + } } /* completion check: @@ -1737,7 +1787,7 @@ static char *game_text_format(const game_state *state) for (r = 0; r < h; ++r) { for (c = 0; c < w; ++c) { int i = r*w + c, cell = r*ch*gw + c*cw; - board[cell] = state->shared->clues[i]["+BW"]; + board[cell] = "+BW"[(unsigned char)state->shared->clues[i]]; if (c < w - 1 && (state->lines[i] & R || state->lines[i+1] & L)) memset(board + cell + 1, '-', cw - 1); if (r < h - 1 && (state->lines[i] & D || state->lines[i+w] & U)) @@ -2558,7 +2608,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize) const struct game thegame = { "Pearl", "games.pearl", "pearl", default_params, - game_fetch_preset, + game_fetch_preset, NULL, decode_params, encode_params, free_params,