-#if 0
- text = game_text_format(sstate->state);
- printf("%s\n", text);
- sfree(text);
-#endif
-
-#define RETURN_IF_SOLVED \
- do { \
- update_solver_status(sstate); \
- if (sstate->solver_status != SOLVER_INCOMPLETE) { \
- free_solver_state(sstate_saved); \
- return sstate; \
- } \
- } while (0)
-
-#define FOUND_MISTAKE \
- do { \
- sstate->solver_status = SOLVER_MISTAKE; \
- free_solver_state(sstate_saved); \
- return sstate; \
- } while (0)
-
-
- sstate_saved = NULL;
- RETURN_IF_SOLVED;
-
-nonrecursive_solver:
-
- while (1) {
- sstate_saved = dup_solver_state(sstate);
-
- /* First we do the 'easy' work, that might cause concrete results */
-
- /* Per-square deductions */
- for (j = 0; j < sstate->state->h; ++j) {
- for (i = 0; i < sstate->state->w; ++i) {
- /* Begin rules that look at the clue (if there is one) */
- 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 (desired < current_yes)
- FOUND_MISTAKE;
- if (desired == current_yes) {
- square_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO);
- continue;
- }
-
- if (4 - desired < current_no)
- FOUND_MISTAKE;
- if (4 - desired == current_no) {
- square_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_YES);
- }
- }
- }
-
- RETURN_IF_SOLVED;
-
- /* Per-dot deductions */
- for (j = 0; j < sstate->state->h + 1; ++j) {
- for (i = 0; i < sstate->state->w + 1; ++i) {
- switch (dot_order(sstate->state, i, j, LINE_YES)) {
- case 0:
- if (dot_order(sstate->state, i, j, LINE_NO) == 3) {
- dot_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO);
- }
- 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){ \
- sstate->dot_howmany \
- [i + (sstate->state->w + 1) * j] |= 1<<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);
- break;
- }
- break;
- case 2:
- dot_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO);
- break;
- case 3:
- FOUND_MISTAKE;
- break;
- }
- if (diff > DIFF_EASY) {
-#define HANDLE_DLINE(dline, dir1_dot, dir2_dot) \
- if (sstate->dot_atleastone \
- [i + (sstate->state->w + 1) * j] & 1<<dline) { \
- sstate->dot_atmostone \
- [i + (sstate->state->w + 1) * j] |= 1<<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
- }
- }
-
- /* More obscure per-square operations */
- for (j = 0; j < sstate->state->h; ++j) {
- for (i = 0; i < sstate->state->w; ++i) {
-#define H1(dline, dir1_sq, dir2_sq, a, b, dot_howmany, line_query, line_set) \
- if (sstate->dot_howmany[i+a + (sstate->state->w + 1) * (j+b)] &\
- 1<<dline) { \
- t = dir1_sq(sstate->state, i, j); \
- if (t == line_query) \
- dir2_sq(sstate->state, i, j) = line_set; \
- else { \
- t = dir2_sq(sstate->state, i, j); \
- if (t == line_query) \
- dir1_sq(sstate->state, i, j) = line_set; \
- } \
- }
- if (diff > DIFF_EASY) {
-#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \
- H1(dline, dir1_sq, dir2_sq, a, b, 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 */
- SQUARE_DLINES;
-#undef HANDLE_DLINE
- }
-
- if (diff > DIFF_EASY) {
-#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \
- H1(dline, dir1_sq, dir2_sq, a, b, 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 */
- SQUARE_DLINES;
-#undef HANDLE_DLINE
- }
-#undef H1
-
- switch (CLUE_AT(sstate->state, i, j)) {
- case '0':
- 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 */ \
- sstate->dot_atmostone \
- [i+a + (sstate->state->w + 1) * (j+b)] |= 1<<dline; \
- /* This DLINE provides enough YESes to solve the clue */\
- if (sstate->dot_atleastone \
- [i+a + (sstate->state->w + 1) * (j+b)] & \
- 1<<dline) { \
- 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 (sstate->dot_at1one \
- [i+a + (sstate->state->w + 1) * (j+b)] & \
- 1<<dline) { \
- sstate->dot_at2one \
- [i+(1-a) + (sstate->state->w + 1) * (j+(1-b))] |= \
- 1<<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':
- case '4':
- if (diff > DIFF_EASY) {
-#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \
- /* At least one of any DLINE can be set */ \
- sstate->dot_atleastone \
- [i+a + (sstate->state->w + 1) * (j+b)] |= 1<<dline; \
- /* This DLINE provides enough NOs to solve the clue */ \
- if (sstate->dot_atmostone \
- [i+a + (sstate->state->w + 1) * (j+b)] & \
- 1<<dline) { \
- 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_states_equal(sstate, sstate_saved)) {
- int edgecount = 0, clues = 0, satclues = 0, sm1clues = 0;
- int d;
-
- /*
- * 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 <= sstate->state->h; ++j) {
- for (i = 0; i <= sstate->state->w; ++i) {
- if (RIGHTOF_DOT(sstate->state, i, j) == LINE_YES) {
- merge_dots(sstate, i, j, i+1, j);
- edgecount++;
- }
- if (BELOW_DOT(sstate->state, i, j) == LINE_YES) {
- 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++;
- }
- }
- }
-
- /*
- * 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 <= sstate->state->h; ++j) {
- for (i = 0; i <= sstate->state->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 * (sstate->state->w+1) + i);
- if (eqclass != dsf_canonify(sstate->dotdsf,
- j2 * (sstate->state->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;
- else
- LV_BELOW_DOT(sstate->state, i, j) = val;
- if (val == LINE_YES) {
- sstate->solver_status = SOLVER_AMBIGUOUS;
- goto finished_loop_checking;
- }
- }
- }
- }
-
- finished_loop_checking:
-
- RETURN_IF_SOLVED;
- }
-
- if (solver_states_equal(sstate, sstate_saved)) {
- /* Solver has stopped making progress so we terminate */
- free_solver_state(sstate_saved);
- break;
- }
-
- free_solver_state(sstate_saved);
- }
-
- 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 < sstate->state->h + 1; ++j) {
- for (i = 0; i < sstate->state->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