-static solver_state *solve_game_rec(const solver_state *sstate_start, int diff)
-{
- int i, j, w, h;
- int current_yes, current_no, desired;
- solver_state *sstate, *sstate_saved, *sstate_tmp;
- int t;
- solver_state *sstate_rec_solved;
- int recursive_soln_count;
- char *square_solved;
- char *dot_solved;
- int solver_progress;
-
- h = sstate_start->state->h;
- w = sstate_start->state->w;
-
- dot_solved = snewn(DOT_COUNT(sstate_start->state), char);
- square_solved = snewn(SQUARE_COUNT(sstate_start->state), char);
- memset(dot_solved, FALSE, DOT_COUNT(sstate_start->state));
- memset(square_solved, FALSE, SQUARE_COUNT(sstate_start->state));
-
-#if 0
- printf("solve_game_rec: recursion_remaining = %d\n",
- sstate_start->recursion_remaining);
-#endif
-
- sstate = dup_solver_state((solver_state *)sstate_start);
-
-#define FOUND_MISTAKE \
- do { \
- sstate->solver_status = SOLVER_MISTAKE; \
- sfree(dot_solved); sfree(square_solved); \
- free_solver_state(sstate_saved); \
- return sstate; \
- } while (0)
-
- sstate_saved = NULL;
-
-nonrecursive_solver:
-
- while (1) {
- solver_progress = FALSE;
-
- /* First we do the 'easy' work, that might cause concrete results */
-
- /* Per-square deductions */
- for (j = 0; j < h; ++j) {
- for (i = 0; i < w; ++i) {
- /* Begin rules that look at the clue (if there is one) */
- if (square_solved[i + j*w])
- continue;
-
- desired = CLUE_AT(sstate->state, i, j);
- if (desired == ' ')
- continue;
-
- desired = desired - '0';
- current_yes = square_order(sstate->state, i, j, LINE_YES);
- current_no = square_order(sstate->state, i, j, LINE_NO);
-
- if (current_yes + current_no == 4) {
- square_solved[i + j*w] = TRUE;
- continue;
- }
-
- if (desired < current_yes)
- FOUND_MISTAKE;
- if (desired == current_yes) {
- square_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO);
- square_solved[i + j*w] = TRUE;
- solver_progress = TRUE;
- continue;
- }
-
- if (4 - desired < current_no)
- FOUND_MISTAKE;
- if (4 - desired == current_no) {
- square_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_YES);
- square_solved[i + j*w] = TRUE;
- solver_progress = TRUE;
- }
- }
- }
-
- /* Per-dot deductions */
- for (j = 0; j < h + 1; ++j) {
- for (i = 0; i < w + 1; ++i) {
- if (dot_solved[i + j*(w+1)])
- continue;
-
- switch (dot_order(sstate->state, i, j, LINE_YES)) {
- case 0:
- switch (dot_order(sstate->state, i, j, LINE_NO)) {
- case 3:
- dot_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO);
- solver_progress = TRUE;
- /* fall through */
- case 4:
- dot_solved[i + j*(w+1)] = TRUE;
- break;
- }
- break;
- case 1:
- switch (dot_order(sstate->state, i, j, LINE_NO)) {
-#define H1(dline, dir1_dot, dir2_dot, dot_howmany) \
- if (dir1_dot(sstate->state, i, j) == LINE_UNKNOWN) { \
- if (dir2_dot(sstate->state, i, j) == LINE_UNKNOWN){ \
- solver_progress |= \
- SET_BIT(sstate->dot_howmany[i + (w + 1) * j], \
- dline); \
- } \
- }
- case 1:
- if (diff > DIFF_EASY) {
-#define HANDLE_DLINE(dline, dir1_dot, dir2_dot) \
- H1(dline, dir1_dot, dir2_dot, dot_atleastone)
- /* 1 yes, 1 no, so exactly one of unknowns is
- * yes */
- DOT_DLINES;
-#undef HANDLE_DLINE
- }
- /* fall through */
- case 0:
- if (diff > DIFF_EASY) {
-#define HANDLE_DLINE(dline, dir1_dot, dir2_dot) \
- H1(dline, dir1_dot, dir2_dot, dot_atmostone)
- /* 1 yes, fewer than 2 no, so at most one of
- * unknowns is yes */
- DOT_DLINES;
-#undef HANDLE_DLINE
- }
-#undef H1
- break;
- case 2: /* 1 yes, 2 no */
- dot_setall(sstate->state, i, j,
- LINE_UNKNOWN, LINE_YES);
- dot_solved[i + j*(w+1)] = TRUE;
- solver_progress = TRUE;
- break;
- case 3: /* 1 yes, 3 no */
- FOUND_MISTAKE;
- break;
- }
- break;
- case 2:
- if (dot_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO)) {
- solver_progress = TRUE;
- }
- dot_solved[i + j*(w+1)] = TRUE;
- break;
- case 3:
- case 4:
- FOUND_MISTAKE;
- break;
- }
- if (diff > DIFF_EASY) {
-#define HANDLE_DLINE(dline, dir1_dot, dir2_dot) \
- if (BIT_SET(sstate->dot_atleastone[i + (w + 1) * j], dline)) { \
- solver_progress |= \
- SET_BIT(sstate->dot_atmostone[i + (w + 1) * j], \
- OPP_DLINE(dline)); \
- }
- /* If at least one of a dline in a dot is YES, at most one
- * of the opposite dline to that dot must be YES. */
- DOT_DLINES;
- }
-#undef HANDLE_DLINE
-
-#define H1(dline, dir1_sq, dir2_sq, dot_howmany, line_query, line_set) \
- if (BIT_SET(sstate->dot_howmany[i + (w+1) * j], dline)) { \
- t = dir1_sq(sstate->state, i, j); \
- if (t == line_query) { \
- if (dir2_sq(sstate->state, i, j) != line_set) { \
- LV_##dir2_sq(sstate->state, i, j) = line_set; \
- solver_progress = TRUE; \
- } \
- } else { \
- t = dir2_sq(sstate->state, i, j); \
- if (t == line_query) { \
- if (dir1_sq(sstate->state, i, j) != line_set) { \
- LV_##dir1_sq(sstate->state, i, j) = line_set; \
- solver_progress = TRUE; \
- } \
- } \
- } \
- }
- if (diff > DIFF_EASY) {
-#define HANDLE_DLINE(dline, dir1_sq, dir2_sq) \
- H1(dline, dir1_sq, dir2_sq, dot_atmostone, LINE_YES, LINE_NO)
- /* If at most one of the DLINE is on, and one is definitely
- * on, set the other to definitely off */
- DOT_DLINES;
-#undef HANDLE_DLINE
- }
-
- if (diff > DIFF_EASY) {
-#define HANDLE_DLINE(dline, dir1_sq, dir2_sq) \
- H1(dline, dir1_sq, dir2_sq, dot_atleastone, LINE_NO, LINE_YES)
- /* If at least one of the DLINE is on, and one is definitely
- * off, set the other to definitely on */
- DOT_DLINES;
-#undef HANDLE_DLINE
- }
-#undef H1
-
- }
- }
-
- /* More obscure per-square operations */
- for (j = 0; j < h; ++j) {
- for (i = 0; i < w; ++i) {
- if (square_solved[i + j*w])
- continue;
-
- switch (CLUE_AT(sstate->state, i, j)) {
- case '1':
- if (diff > DIFF_EASY) {
-#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \
- /* At most one of any DLINE can be set */ \
- SET_BIT(sstate->dot_atmostone[i+a + (w + 1) * (j+b)], \
- dline); \
- /* This DLINE provides enough YESes to solve the clue */\
- if (BIT_SET(sstate->dot_atleastone \
- [i+a + (w + 1) * (j+b)], \
- dline)) { \
- solver_progress |= \
- dot_setall_dlines(sstate, OPP_DLINE(dline), \
- i+(1-a), j+(1-b), \
- LINE_UNKNOWN, LINE_NO); \
- }
- SQUARE_DLINES;
-#undef HANDLE_DLINE
- }
- break;
- case '2':
- if (diff > DIFF_EASY) {
-#define H1(dline, dot_at1one, dot_at2one, a, b) \
- if (BIT_SET(sstate->dot_at1one \
- [i+a + (w+1) * (j+b)], dline)) { \
- solver_progress |= \
- SET_BIT(sstate->dot_at2one \
- [i+(1-a) + (w+1) * (j+(1-b))], \
- OPP_DLINE(dline)); \
- }
-#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \
- H1(dline, dot_atleastone, dot_atmostone, a, b); \
- H1(dline, dot_atmostone, dot_atleastone, a, b);
- /* If at least one of one DLINE is set, at most one
- * of the opposing one is and vice versa */
- SQUARE_DLINES;
- }
-#undef HANDLE_DLINE
-#undef H1
- break;
- case '3':
- if (diff > DIFF_EASY) {
-#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \
- /* At least one of any DLINE can be set */ \
- solver_progress |= \
- SET_BIT(sstate->dot_atleastone \
- [i+a + (w + 1) * (j+b)], \
- dline); \
- /* This DLINE provides enough NOs to solve the clue */ \
- if (BIT_SET(sstate->dot_atmostone \
- [i+a + (w + 1) * (j+b)], \
- dline)) { \
- solver_progress |= \
- dot_setall_dlines(sstate, OPP_DLINE(dline), \
- i+(1-a), j+(1-b), \
- LINE_UNKNOWN, LINE_YES); \
- }
- SQUARE_DLINES;
-#undef HANDLE_DLINE
- }
- break;
- }
- }
- }
-
- if (!solver_progress) {
- int edgecount = 0, clues = 0, satclues = 0, sm1clues = 0;
- int shortest_chainlen = DOT_COUNT(sstate->state);
- int loop_found = FALSE;
- int d;
- int dots_connected;
-
- /*
- * Go through the grid and update for all the new edges.
- * Since merge_dots() is idempotent, the simplest way to
- * do this is just to update for _all_ the edges.
- *
- * Also, while we're here, we count the edges, count the
- * clues, count the satisfied clues, and count the
- * satisfied-minus-one clues.
- */
- for (j = 0; j < h+1; ++j) {
- for (i = 0; i < w+1; ++i) {
- if (RIGHTOF_DOT(sstate->state, i, j) == LINE_YES) {
- loop_found |= merge_dots(sstate, i, j, i+1, j);
- edgecount++;
- }
- if (BELOW_DOT(sstate->state, i, j) == LINE_YES) {
- loop_found |= merge_dots(sstate, i, j, i, j+1);
- edgecount++;
- }
-
- if (CLUE_AT(sstate->state, i, j) != ' ') {
- int c = CLUE_AT(sstate->state, i, j) - '0';
- int o = square_order(sstate->state, i, j, LINE_YES);
- if (o == c)
- satclues++;
- else if (o == c-1)
- sm1clues++;
- clues++;
- }
- }
- }
-
- for (i = 0; i < DOT_COUNT(sstate->state); ++i) {
- dots_connected = sstate->looplen[dsf_canonify(sstate->dotdsf,i)];
- if (dots_connected > 1)
- shortest_chainlen = min(shortest_chainlen, dots_connected);
- }
-
- assert(sstate->solver_status == SOLVER_INCOMPLETE);
-
- if (satclues == clues && shortest_chainlen == edgecount) {
- sstate->solver_status = SOLVER_SOLVED;
- /* This discovery clearly counts as progress, even if we haven't
- * just added any lines or anything */
- solver_progress = TRUE;
- goto finished_loop_checking;
- }
-
- /*
- * Now go through looking for LINE_UNKNOWN edges which
- * connect two dots that are already in the same
- * equivalence class. If we find one, test to see if the
- * loop it would create is a solution.
- */
- for (j = 0; j <= h; ++j) {
- for (i = 0; i <= w; ++i) {
- for (d = 0; d < 2; d++) {
- int i2, j2, eqclass, val;
-
- if (d == 0) {
- if (RIGHTOF_DOT(sstate->state, i, j) !=
- LINE_UNKNOWN)
- continue;
- i2 = i+1;
- j2 = j;
- } else {
- if (BELOW_DOT(sstate->state, i, j) !=
- LINE_UNKNOWN)
- continue;
- i2 = i;
- j2 = j+1;
- }
-
- eqclass = dsf_canonify(sstate->dotdsf, j * (w+1) + i);
- if (eqclass != dsf_canonify(sstate->dotdsf,
- j2 * (w+1) + i2))
- continue;
-
- val = LINE_NO; /* loop is bad until proven otherwise */
-
- /*
- * This edge would form a loop. Next
- * question: how long would the loop be?
- * Would it equal the total number of edges
- * (plus the one we'd be adding if we added
- * it)?
- */
- if (sstate->looplen[eqclass] == edgecount + 1) {
- int sm1_nearby;
- int cx, cy;
-
- /*
- * This edge would form a loop which
- * took in all the edges in the entire
- * grid. So now we need to work out
- * whether it would be a valid solution
- * to the puzzle, which means we have to
- * check if it satisfies all the clues.
- * This means that every clue must be
- * either satisfied or satisfied-minus-
- * 1, and also that the number of
- * satisfied-minus-1 clues must be at
- * most two and they must lie on either
- * side of this edge.
- */
- sm1_nearby = 0;
- cx = i - (j2-j);
- cy = j - (i2-i);
- if (CLUE_AT(sstate->state, cx,cy) != ' ' &&
- square_order(sstate->state, cx,cy, LINE_YES) ==
- CLUE_AT(sstate->state, cx,cy) - '0' - 1)
- sm1_nearby++;
- if (CLUE_AT(sstate->state, i, j) != ' ' &&
- square_order(sstate->state, i, j, LINE_YES) ==
- CLUE_AT(sstate->state, i, j) - '0' - 1)
- sm1_nearby++;
- if (sm1clues == sm1_nearby &&
- sm1clues + satclues == clues)
- val = LINE_YES; /* loop is good! */
- }
-
- /*
- * Right. Now we know that adding this edge
- * would form a loop, and we know whether
- * that loop would be a viable solution or
- * not.
- *
- * If adding this edge produces a solution,
- * then we know we've found _a_ solution but
- * we don't know that it's _the_ solution -
- * if it were provably the solution then
- * we'd have deduced this edge some time ago
- * without the need to do loop detection. So
- * in this state we return SOLVER_AMBIGUOUS,
- * which has the effect that hitting Solve
- * on a user-provided puzzle will fill in a
- * solution but using the solver to
- * construct new puzzles won't consider this
- * a reasonable deduction for the user to
- * make.
- */
- if (d == 0) {
- LV_RIGHTOF_DOT(sstate->state, i, j) = val;
- solver_progress = TRUE;
- } else {
- LV_BELOW_DOT(sstate->state, i, j) = val;
- solver_progress = TRUE;
- }
- if (val == LINE_YES) {
- sstate->solver_status = SOLVER_AMBIGUOUS;
- goto finished_loop_checking;
- }
- }
- }
- }
-
- finished_loop_checking:
-
- if (!solver_progress ||
- sstate->solver_status == SOLVER_SOLVED ||
- sstate->solver_status == SOLVER_AMBIGUOUS) {
- break;
- }
- }
- }
-
- sfree(dot_solved); sfree(square_solved);
-
- if (sstate->solver_status == SOLVER_SOLVED ||
- sstate->solver_status == SOLVER_AMBIGUOUS) {
- /* s/LINE_UNKNOWN/LINE_NO/g */
- array_setall(sstate->state->hl, LINE_UNKNOWN, LINE_NO,
- HL_COUNT(sstate->state));
- array_setall(sstate->state->vl, LINE_UNKNOWN, LINE_NO,
- VL_COUNT(sstate->state));
- return sstate;
- }
-
- /* Perform recursive calls */
- if (sstate->recursion_remaining) {
- sstate_saved = dup_solver_state(sstate);
-
- sstate->recursion_remaining--;
-
- recursive_soln_count = 0;
- sstate_rec_solved = NULL;
-
- /* Memory management:
- * sstate_saved won't be modified but needs to be freed when we have
- * finished with it.
- * sstate is expected to contain our 'best' solution by the time we
- * finish this section of code. It's the thing we'll try adding lines
- * to, seeing if they make it more solvable.
- * If sstate_rec_solved is non-NULL, it will supersede sstate
- * eventually. sstate_tmp should not hold a value persistently.
- */
-
- /* NB SOLVER_AMBIGUOUS is like SOLVER_SOLVED except the solver is aware
- * of the possibility of additional solutions. So as soon as we have a
- * SOLVER_AMBIGUOUS we can safely propagate it back to our caller, but
- * if we get a SOLVER_SOLVED we want to keep trying in case we find
- * further solutions and have to mark it ambiguous.
- */
-
-#define DO_RECURSIVE_CALL(dir_dot) \
- if (dir_dot(sstate->state, i, j) == LINE_UNKNOWN) { \
- debug(("Trying " #dir_dot " at [%d,%d]\n", i, j)); \
- LV_##dir_dot(sstate->state, i, j) = LINE_YES; \
- sstate_tmp = solve_game_rec(sstate, diff); \
- switch (sstate_tmp->solver_status) { \
- case SOLVER_AMBIGUOUS: \
- debug(("Solver ambiguous, returning\n")); \
- sstate_rec_solved = sstate_tmp; \
- goto finished_recursion; \
- case SOLVER_SOLVED: \
- switch (++recursive_soln_count) { \
- case 1: \
- debug(("One solution found\n")); \
- sstate_rec_solved = sstate_tmp; \
- break; \
- case 2: \
- debug(("Ambiguous solutions found\n")); \
- free_solver_state(sstate_tmp); \
- sstate_rec_solved->solver_status = SOLVER_AMBIGUOUS;\
- goto finished_recursion; \
- default: \
- assert(!"recursive_soln_count out of range"); \
- break; \
- } \
- break; \
- case SOLVER_MISTAKE: \
- debug(("Non-solution found\n")); \
- free_solver_state(sstate_tmp); \
- free_solver_state(sstate_saved); \
- LV_##dir_dot(sstate->state, i, j) = LINE_NO; \
- goto nonrecursive_solver; \
- case SOLVER_INCOMPLETE: \
- debug(("Recursive step inconclusive\n")); \
- free_solver_state(sstate_tmp); \
- break; \
- } \
- free_solver_state(sstate); \
- sstate = dup_solver_state(sstate_saved); \
- }
-
- for (j = 0; j < h + 1; ++j) {
- for (i = 0; i < w + 1; ++i) {
- /* Only perform recursive calls on 'loose ends' */
- if (dot_order(sstate->state, i, j, LINE_YES) == 1) {
- DO_RECURSIVE_CALL(LEFTOF_DOT);
- DO_RECURSIVE_CALL(RIGHTOF_DOT);
- DO_RECURSIVE_CALL(ABOVE_DOT);
- DO_RECURSIVE_CALL(BELOW_DOT);
- }
- }
- }
-
-finished_recursion:
-
- if (sstate_rec_solved) {
- free_solver_state(sstate);
- sstate = sstate_rec_solved;
- }
- }
-
- return sstate;
-}
-
-/* XXX bits of solver that may come in handy one day */
-#if 0
-#define HANDLE_DLINE(dline, dir1_dot, dir2_dot) \
- /* dline from this dot that's entirely unknown must have
- * both lines identical */ \
- if (dir1_dot(sstate->state, i, j) == LINE_UNKNOWN && \
- dir2_dot(sstate->state, i, j) == LINE_UNKNOWN) { \
- sstate->dline_identical[i + (sstate->state->w + 1) * j] |= \
- 1<<dline; \
- } else if (sstate->dline_identical[i +
- (sstate->state->w + 1) * j] &\
- 1<<dline) { \
- /* If they're identical and one is known do the obvious
- * thing */ \
- t = dir1_dot(sstate->state, i, j); \
- if (t != LINE_UNKNOWN) \
- dir2_dot(sstate->state, i, j) = t; \
- else { \
- t = dir2_dot(sstate->state, i, j); \
- if (t != LINE_UNKNOWN) \
- dir1_dot(sstate->state, i, j) = t; \
- } \
- } \
- DOT_DLINES;
-#undef HANDLE_DLINE
-#endif
-
-#if 0
-#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \
- if (sstate->dline_identical[i+a + \
- (sstate->state->w + 1) * (j+b)] &\
- 1<<dline) { \
- dir1_sq(sstate->state, i, j) = LINE_YES; \
- dir2_sq(sstate->state, i, j) = LINE_YES; \
- }
- /* If two lines are the same they must be on */
- SQUARE_DLINES;
-#undef HANDLE_DLINE
-#endif
-
-
-#if 0
-#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \
- if (sstate->dot_atmostone[i+a + (sstate->state->w + 1) * (j+b)] & \
- 1<<dline) { \
- if (square_order(sstate->state, i, j, LINE_UNKNOWN) - 1 == \
- CLUE_AT(sstate->state, i, j) - '0') { \
- square_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_YES); \
- /* XXX the following may overwrite known data! */ \
- dir1_sq(sstate->state, i, j) = LINE_UNKNOWN; \
- dir2_sq(sstate->state, i, j) = LINE_UNKNOWN; \
- } \
- }
- SQUARE_DLINES;
-#undef HANDLE_DLINE
-#endif
-
-#if 0
-#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \
- if (sstate->dline_identical[i+a +
- (sstate->state->w + 1) * (j+b)] &\
- 1<<dline) { \
- dir1_sq(sstate->state, i, j) = LINE_NO; \
- dir2_sq(sstate->state, i, j) = LINE_NO; \
- }
- /* If two lines are the same they must be off */
- SQUARE_DLINES;
-#undef HANDLE_DLINE
-#endif
-
-static char *solve_game(game_state *state, game_state *currstate,
- char *aux, char **error)
-{
- char *soln = NULL;
- solver_state *sstate, *new_sstate;
-
- sstate = new_solver_state(state);
- new_sstate = solve_game_rec(sstate, DIFFCOUNT);
-
- if (new_sstate->solver_status == SOLVER_SOLVED) {
- soln = encode_solve_move(new_sstate->state);
- } else if (new_sstate->solver_status == SOLVER_AMBIGUOUS) {
- soln = encode_solve_move(new_sstate->state);
- /**error = "Solver found ambiguous solutions"; */
- } else {
- soln = encode_solve_move(new_sstate->state);
- /**error = "Solver failed"; */
- }
-
- free_solver_state(new_sstate);
- free_solver_state(sstate);
-
- return soln;
-}
-
-static char *game_text_format(game_state *state)