};
/* ------ Solver state ------ */
-typedef struct normal {
- /* For each dline, store a bitmask for whether we know:
- * (bit 0) at least one is YES
- * (bit 1) at most one is YES */
- char *dlines;
-} normal_mode_state;
-
-typedef struct hard {
- int *linedsf;
-} hard_mode_state;
-
typedef struct solver_state {
game_state *state;
enum solver_status solver_status;
* looplen of 1 means there are no lines to a particular dot */
int *looplen;
+ /* Difficulty level of solver. Used by solver functions that want to
+ * vary their behaviour depending on the requested difficulty level. */
+ int diff;
+
/* caches */
char *dot_yes_count;
char *dot_no_count;
char *dot_solved, *face_solved;
int *dotdsf;
- normal_mode_state *normal;
- hard_mode_state *hard;
+ /* Information for Normal level deductions:
+ * For each dline, store a bitmask for whether we know:
+ * (bit 0) at least one is YES
+ * (bit 1) at most one is YES */
+ char *dlines;
+
+ /* Hard level information */
+ int *linedsf;
} solver_state;
/*
*/
#define DIFFLIST(A) \
- A(EASY,Easy,e,easy_mode_deductions) \
- A(NORMAL,Normal,n,normal_mode_deductions) \
- A(HARD,Hard,h,hard_mode_deductions)
-#define ENUM(upper,title,lower,fn) DIFF_ ## upper,
-#define TITLE(upper,title,lower,fn) #title,
-#define ENCODE(upper,title,lower,fn) #lower
-#define CONFIG(upper,title,lower,fn) ":" #title
-#define SOLVER_FN_DECL(upper,title,lower,fn) static int fn(solver_state *);
-#define SOLVER_FN(upper,title,lower,fn) &fn,
+ A(EASY,Easy,e) \
+ A(NORMAL,Normal,n) \
+ A(TRICKY,Tricky,t) \
+ A(HARD,Hard,h)
+#define ENUM(upper,title,lower) DIFF_ ## upper,
+#define TITLE(upper,title,lower) #title,
+#define ENCODE(upper,title,lower) #lower
+#define CONFIG(upper,title,lower) ":" #title
enum { DIFFLIST(ENUM) DIFF_MAX };
static char const *const diffnames[] = { DIFFLIST(TITLE) };
static char const diffchars[] = DIFFLIST(ENCODE);
#define DIFFCONFIG DIFFLIST(CONFIG)
-DIFFLIST(SOLVER_FN_DECL)
-static int (*(solver_fns[]))(solver_state *) = { DIFFLIST(SOLVER_FN) };
+
+/*
+ * Solver routines, sorted roughly in order of computational cost.
+ * The solver will run the faster deductions first, and slower deductions are
+ * only invoked when the faster deductions are unable to make progress.
+ * Each function is associated with a difficulty level, so that the generated
+ * puzzles are solvable by applying only the functions with the chosen
+ * difficulty level or lower.
+ */
+#define SOLVERLIST(A) \
+ A(trivial_deductions, DIFF_EASY) \
+ A(dline_deductions, DIFF_NORMAL) \
+ A(linedsf_deductions, DIFF_HARD) \
+ A(loop_deductions, DIFF_EASY)
+#define SOLVER_FN_DECL(fn,diff) static int fn(solver_state *);
+#define SOLVER_FN(fn,diff) &fn,
+#define SOLVER_DIFF(fn,diff) diff,
+SOLVERLIST(SOLVER_FN_DECL)
+static int (*(solver_fns[]))(solver_state *) = { SOLVERLIST(SOLVER_FN) };
+static int const solver_diffs[] = { SOLVERLIST(SOLVER_DIFF) };
+const int NUM_SOLVERS = sizeof(solver_diffs)/sizeof(*solver_diffs);
struct game_params {
int w, h;
static char *validate_desc(game_params *params, char *desc);
static int dot_order(const game_state* state, int i, char line_type);
static int face_order(const game_state* state, int i, char line_type);
-static solver_state *solve_game_rec(const solver_state *sstate,
- int diff);
+static solver_state *solve_game_rec(const solver_state *sstate);
#ifdef DEBUG_CACHES
static void check_caches(const solver_state* sstate);
ret->state = dup_game(state);
ret->solver_status = SOLVER_INCOMPLETE;
+ ret->diff = diff;
ret->dotdsf = snew_dsf(num_dots);
ret->looplen = snewn(num_dots, int);
memset(ret->face_no_count, 0, num_faces);
if (diff < DIFF_NORMAL) {
- ret->normal = NULL;
+ ret->dlines = NULL;
} else {
- ret->normal = snew(normal_mode_state);
- ret->normal->dlines = snewn(2*num_edges, char);
- memset(ret->normal->dlines, 0, 2*num_edges);
+ ret->dlines = snewn(2*num_edges, char);
+ memset(ret->dlines, 0, 2*num_edges);
}
if (diff < DIFF_HARD) {
- ret->hard = NULL;
+ ret->linedsf = NULL;
} else {
- ret->hard = snew(hard_mode_state);
- ret->hard->linedsf = snew_dsf(state->game_grid->num_edges);
+ ret->linedsf = snew_dsf(state->game_grid->num_edges);
}
return ret;
sfree(sstate->face_yes_count);
sfree(sstate->face_no_count);
- if (sstate->normal) {
- sfree(sstate->normal->dlines);
- sfree(sstate->normal);
- }
-
- if (sstate->hard) {
- sfree(sstate->hard->linedsf);
- sfree(sstate->hard);
- }
+ /* OK, because sfree(NULL) is a no-op */
+ sfree(sstate->dlines);
+ sfree(sstate->linedsf);
sfree(sstate);
}
ret->state = state = dup_game(sstate->state);
ret->solver_status = sstate->solver_status;
+ ret->diff = sstate->diff;
ret->dotdsf = snewn(num_dots, int);
ret->looplen = snewn(num_dots, int);
ret->face_no_count = snewn(num_faces, char);
memcpy(ret->face_no_count, sstate->face_no_count, num_faces);
- if (sstate->normal) {
- ret->normal = snew(normal_mode_state);
- ret->normal->dlines = snewn(2*num_edges, char);
- memcpy(ret->normal->dlines, sstate->normal->dlines,
+ if (sstate->dlines) {
+ ret->dlines = snewn(2*num_edges, char);
+ memcpy(ret->dlines, sstate->dlines,
2*num_edges);
} else {
- ret->normal = NULL;
+ ret->dlines = NULL;
}
- if (sstate->hard) {
- ret->hard = snew(hard_mode_state);
- ret->hard->linedsf = snewn(num_edges, int);
- memcpy(ret->hard->linedsf, sstate->hard->linedsf,
+ if (sstate->linedsf) {
+ ret->linedsf = snewn(num_edges, int);
+ memcpy(ret->linedsf, sstate->linedsf,
num_edges * sizeof(int));
} else {
- ret->hard = NULL;
+ ret->linedsf = NULL;
}
return ret;
assert(i < sstate->state->game_grid->num_edges);
assert(j < sstate->state->game_grid->num_edges);
- i = edsf_canonify(sstate->hard->linedsf, i, &inv_tmp);
+ i = edsf_canonify(sstate->linedsf, i, &inv_tmp);
inverse ^= inv_tmp;
- j = edsf_canonify(sstate->hard->linedsf, j, &inv_tmp);
+ j = edsf_canonify(sstate->linedsf, j, &inv_tmp);
inverse ^= inv_tmp;
- edsf_merge(sstate->hard->linedsf, i, j, inverse);
+ edsf_merge(sstate->linedsf, i, j, inverse);
#ifdef SHOW_WORKING
if (i != j) {
solver_state *sstate_new;
solver_state *sstate = new_solver_state((game_state *)state, diff);
- sstate_new = solve_game_rec(sstate, diff);
+ sstate_new = solve_game_rec(sstate);
assert(sstate_new->solver_status != SOLVER_MISTAKE);
ret = (sstate_new->solver_status == SOLVER_SOLVED);
* Easy Mode
* Just implement the rules of the game.
*
- * Normal Mode
+ * Normal and Tricky Modes
* For each (adjacent) pair of lines through each dot we store a bit for
* whether at least one of them is on and whether at most one is on. (If we
* know both or neither is on that's already stored more directly.)
continue;
/* Found opposite UNKNOWNS and they're next to each other */
opp_dline_index = dline_index_from_dot(g, d, opp);
- return set_atleastone(sstate->normal->dlines, opp_dline_index);
+ return set_atleastone(sstate->dlines, opp_dline_index);
}
return FALSE;
}
continue;
/* Found two UNKNOWNS */
- can1 = edsf_canonify(sstate->hard->linedsf, line1_index, &inv1);
- can2 = edsf_canonify(sstate->hard->linedsf, line2_index, &inv2);
+ can1 = edsf_canonify(sstate->linedsf, line1_index, &inv1);
+ can2 = edsf_canonify(sstate->linedsf, line2_index, &inv2);
if (can1 == can2 && inv1 == inv2) {
solver_set_line(sstate, line1_index, line_new);
solver_set_line(sstate, line2_index, line_new);
{
game_state *state = sstate->state;
int diff = DIFF_MAX;
- int *linedsf = sstate->hard->linedsf;
+ int *linedsf = sstate->linedsf;
if (unknown_count == 2) {
/* Lines are known alike/opposite, depending on inv. */
* Answer: first all squares then all dots.
*/
-static int easy_mode_deductions(solver_state *sstate)
+static int trivial_deductions(solver_state *sstate)
{
int i, current_yes, current_no;
game_state *state = sstate->state;
return diff;
}
-static int normal_mode_deductions(solver_state *sstate)
+static int dline_deductions(solver_state *sstate)
{
game_state *state = sstate->state;
grid *g = state->game_grid;
- char *dlines = sstate->normal->dlines;
+ char *dlines = sstate->dlines;
int i;
int diff = DIFF_MAX;
diff = min(diff, DIFF_EASY);
}
- /* Now see if we can make dline deduction for edges{j,j+1} */
- e = f->edges[k];
- if (state->lines[e - g->edges] != LINE_UNKNOWN)
- /* Only worth doing this for an UNKNOWN,UNKNOWN pair.
- * Dlines where one of the edges is known, are handled in the
- * dot-deductions */
- continue;
-
- dline_index = dline_index_from_face(g, f, k);
- k++;
- if (k >= N) k = 0;
-
- /* minimum YESs in the complement of this dline */
- if (mins[k][j] > clue - 2) {
- /* Adding 2 YESs would break the clue */
- if (set_atmostone(dlines, dline_index))
- diff = min(diff, DIFF_NORMAL);
- }
- /* maximum YESs in the complement of this dline */
- if (maxs[k][j] < clue) {
- /* Adding 2 NOs would mean not enough YESs */
- if (set_atleastone(dlines, dline_index))
- diff = min(diff, DIFF_NORMAL);
+ /* More advanced deduction that allows propagation along diagonal
+ * chains of faces connected by dots, for example, 3-2-...-2-3
+ * in square grids. */
+ if (sstate->diff >= DIFF_TRICKY) {
+ /* Now see if we can make dline deduction for edges{j,j+1} */
+ e = f->edges[k];
+ if (state->lines[e - g->edges] != LINE_UNKNOWN)
+ /* Only worth doing this for an UNKNOWN,UNKNOWN pair.
+ * Dlines where one of the edges is known, are handled in the
+ * dot-deductions */
+ continue;
+
+ dline_index = dline_index_from_face(g, f, k);
+ k++;
+ if (k >= N) k = 0;
+
+ /* minimum YESs in the complement of this dline */
+ if (mins[k][j] > clue - 2) {
+ /* Adding 2 YESs would break the clue */
+ if (set_atmostone(dlines, dline_index))
+ diff = min(diff, DIFF_NORMAL);
+ }
+ /* maximum YESs in the complement of this dline */
+ if (maxs[k][j] < clue) {
+ /* Adding 2 NOs would mean not enough YESs */
+ if (set_atleastone(dlines, dline_index))
+ diff = min(diff, DIFF_NORMAL);
+ }
}
}
}
}
}
- /* If we have atleastone set for this dline, infer
- * atmostone for each "opposite" dline (that is, each
- * dline without edges in common with this one).
- * Again, this test is only worth doing if both these
- * lines are UNKNOWN. For if one of these lines were YES,
- * the (yes == 1) test above would kick in instead. */
- if (is_atleastone(dlines, dline_index)) {
- int opp;
- for (opp = 0; opp < N; opp++) {
- int opp_dline_index;
- if (opp == j || opp == j+1 || opp == j-1)
- continue;
- if (j == 0 && opp == N-1)
- continue;
- if (j == N-1 && opp == 0)
- continue;
- opp_dline_index = dline_index_from_dot(g, d, opp);
- if (set_atmostone(dlines, opp_dline_index))
- diff = min(diff, DIFF_NORMAL);
- }
-
- if (yes == 0 && is_atmostone(dlines, dline_index)) {
- /* This dline has *exactly* one YES and there are no
- * other YESs. This allows more deductions. */
- if (unknown == 3) {
- /* Third unknown must be YES */
- for (opp = 0; opp < N; opp++) {
- int opp_index;
- if (opp == j || opp == k)
- continue;
- opp_index = d->edges[opp] - g->edges;
- if (state->lines[opp_index] == LINE_UNKNOWN) {
- solver_set_line(sstate, opp_index, LINE_YES);
- diff = min(diff, DIFF_EASY);
+ /* More advanced deduction that allows propagation along diagonal
+ * chains of faces connected by dots, for example: 3-2-...-2-3
+ * in square grids. */
+ if (sstate->diff >= DIFF_TRICKY) {
+ /* If we have atleastone set for this dline, infer
+ * atmostone for each "opposite" dline (that is, each
+ * dline without edges in common with this one).
+ * Again, this test is only worth doing if both these
+ * lines are UNKNOWN. For if one of these lines were YES,
+ * the (yes == 1) test above would kick in instead. */
+ if (is_atleastone(dlines, dline_index)) {
+ int opp;
+ for (opp = 0; opp < N; opp++) {
+ int opp_dline_index;
+ if (opp == j || opp == j+1 || opp == j-1)
+ continue;
+ if (j == 0 && opp == N-1)
+ continue;
+ if (j == N-1 && opp == 0)
+ continue;
+ opp_dline_index = dline_index_from_dot(g, d, opp);
+ if (set_atmostone(dlines, opp_dline_index))
+ diff = min(diff, DIFF_NORMAL);
+ }
+ if (yes == 0 && is_atmostone(dlines, dline_index)) {
+ /* This dline has *exactly* one YES and there are no
+ * other YESs. This allows more deductions. */
+ if (unknown == 3) {
+ /* Third unknown must be YES */
+ for (opp = 0; opp < N; opp++) {
+ int opp_index;
+ if (opp == j || opp == k)
+ continue;
+ opp_index = d->edges[opp] - g->edges;
+ if (state->lines[opp_index] == LINE_UNKNOWN) {
+ solver_set_line(sstate, opp_index,
+ LINE_YES);
+ diff = min(diff, DIFF_EASY);
+ }
}
+ } else if (unknown == 4) {
+ /* Exactly one of opposite UNKNOWNS is YES. We've
+ * already set atmostone, so set atleastone as
+ * well.
+ */
+ if (dline_set_opp_atleastone(sstate, d, j))
+ diff = min(diff, DIFF_NORMAL);
}
- } else if (unknown == 4) {
- /* Exactly one of opposite UNKNOWNS is YES. We've
- * already set atmostone, so set atleastone as well.
- */
- if (dline_set_opp_atleastone(sstate, d, j))
- diff = min(diff, DIFF_NORMAL);
}
}
}
return diff;
}
-static int hard_mode_deductions(solver_state *sstate)
+static int linedsf_deductions(solver_state *sstate)
{
game_state *state = sstate->state;
grid *g = state->game_grid;
- char *dlines = sstate->normal->dlines;
+ char *dlines = sstate->dlines;
int i;
int diff = DIFF_MAX;
int diff_tmp;
if (state->lines[line2_index] != LINE_UNKNOWN)
continue;
/* Infer dline flags from linedsf */
- can1 = edsf_canonify(sstate->hard->linedsf, line1_index, &inv1);
- can2 = edsf_canonify(sstate->hard->linedsf, line2_index, &inv2);
+ can1 = edsf_canonify(sstate->linedsf, line1_index, &inv1);
+ can2 = edsf_canonify(sstate->linedsf, line2_index, &inv2);
if (can1 == can2 && inv1 != inv2) {
/* These are opposites, so set dline atmostone/atleastone */
if (set_atmostone(dlines, dline_index))
for (i = 0; i < g->num_edges; i++) {
int can, inv;
enum line_state s;
- can = edsf_canonify(sstate->hard->linedsf, i, &inv);
+ can = edsf_canonify(sstate->linedsf, i, &inv);
if (can == i)
continue;
s = sstate->state->lines[can];
/* This will return a dynamically allocated solver_state containing the (more)
* solved grid */
-static solver_state *solve_game_rec(const solver_state *sstate_start,
- int diff)
+static solver_state *solve_game_rec(const solver_state *sstate_start)
{
- solver_state *sstate, *sstate_saved;
- int solver_progress;
- game_state *state;
+ solver_state *sstate;
- /* Indicates which solver we should call next. This is a sensible starting
- * point */
- int current_solver = DIFF_EASY, next_solver;
+ /* Index of the solver we should call next. */
+ int i = 0;
+
+ /* As a speed-optimisation, we avoid re-running solvers that we know
+ * won't make any progress. This happens when a high-difficulty
+ * solver makes a deduction that can only help other high-difficulty
+ * solvers.
+ * For example: if a new 'dline' flag is set by dline_deductions, the
+ * trivial_deductions solver cannot do anything with this information.
+ * If we've already run the trivial_deductions solver (because it's
+ * earlier in the list), there's no point running it again.
+ *
+ * Therefore: if a solver is earlier in the list than "threshold_index",
+ * we don't bother running it if it's difficulty level is less than
+ * "threshold_diff".
+ */
+ int threshold_diff = 0;
+ int threshold_index = 0;
+
sstate = dup_solver_state(sstate_start);
- /* Cache the values of some variables for readability */
- state = sstate->state;
-
- sstate_saved = NULL;
-
- solver_progress = FALSE;
-
check_caches(sstate);
- do {
+ while (i < NUM_SOLVERS) {
if (sstate->solver_status == SOLVER_MISTAKE)
return sstate;
-
- next_solver = solver_fns[current_solver](sstate);
-
- if (next_solver == DIFF_MAX) {
- if (current_solver < diff && current_solver + 1 < DIFF_MAX) {
- /* Try next beefier solver */
- next_solver = current_solver + 1;
- } else {
- next_solver = loop_deductions(sstate);
- }
- }
-
if (sstate->solver_status == SOLVER_SOLVED ||
sstate->solver_status == SOLVER_AMBIGUOUS) {
-/* fprintf(stderr, "Solver completed\n"); */
+ /* solver finished */
break;
}
- /* Once we've looped over all permitted solvers then the loop
- * deductions without making any progress, we'll exit this while loop */
- current_solver = next_solver;
- } while (current_solver < DIFF_MAX);
+ if ((solver_diffs[i] >= threshold_diff || i >= threshold_index)
+ && solver_diffs[i] <= sstate->diff) {
+ /* current_solver is eligible, so use it */
+ int next_diff = solver_fns[i](sstate);
+ if (next_diff != DIFF_MAX) {
+ /* solver made progress, so use new thresholds and
+ * start again at top of list. */
+ threshold_diff = next_diff;
+ threshold_index = i;
+ i = 0;
+ continue;
+ }
+ }
+ /* current_solver is ineligible, or failed to make progress, so
+ * go to the next solver in the list */
+ i++;
+ }
if (sstate->solver_status == SOLVER_SOLVED ||
sstate->solver_status == SOLVER_AMBIGUOUS) {
solver_state *sstate, *new_sstate;
sstate = new_solver_state(state, DIFF_MAX);
- new_sstate = solve_game_rec(sstate, DIFF_MAX);
+ new_sstate = solve_game_rec(sstate);
if (new_sstate->solver_status == SOLVER_SOLVED) {
soln = encode_solve_move(new_sstate->state);
solver_state *sstate_new;
solver_state *sstate = new_solver_state((game_state *)s, diff);
- sstate_new = solve_game_rec(sstate, diff);
+ sstate_new = solve_game_rec(sstate);
if (sstate_new->solver_status == SOLVER_MISTAKE)
ret = 0;
/* If we supported a verbose solver, we'd set verbosity here */
- sstate_new = solve_game_rec(sstate, diff);
+ sstate_new = solve_game_rec(sstate);
if (sstate_new->solver_status == SOLVER_MISTAKE)
printf("Puzzle is inconsistent\n");
~mdw / sgt / puzzles / commitdiff