ref: 5030d87903191d581586ecda2382ad5bcd70f63d
parent: 517b14e666b0b71fc0bcd5da1b22cdc90d3434c9
author: Simon Tatham <anakin@pobox.com>
date: Sun Feb 5 05:29:42 EST 2023
latin_solver_alloc: handle clashing numbers in input grid. In the setup phase of the centralised latin.c solver, we start by going over the input grid containing already-placed clue numbers, and calling latin_solver_place to enter each on into the solver's data structure. This has the side effect of ruling out each number from the rest of the row and column, and _also_ checking by assertion that the number being placed is not ruled out. Those are a bad combination, because it means that if you give an obviously inconsistent input grid to latin_solver_alloc (e.g. with two identical numbers in a row already), it will fail an assertion. In that situation, you want the solver run as a whole to return diff_impossible so that the error is reported cleanly. This assertion failure could be provoked by giving either Towers or Group a manually-constructed game description inconsistent in that way, and hitting Solve. Worse, it could be provoked during live play in Unequal, by filling in a number clashing with a clue and then pressing 'h' to get hints.
--- a/latin.c
+++ b/latin.c
@@ -563,7 +563,7 @@
sfree(scratch);
}
-void latin_solver_alloc(struct latin_solver *solver, digit *grid, int o)
+bool latin_solver_alloc(struct latin_solver *solver, digit *grid, int o)
{int x, y;
@@ -577,14 +577,23 @@
memset(solver->row, 0, o*o);
memset(solver->col, 0, o*o);
- for (x = 0; x < o; x++)
- for (y = 0; y < o; y++)
- if (grid[y*o+x])
- latin_solver_place(solver, x, y, grid[y*o+x]);
-
#ifdef STANDALONE_SOLVER
solver->names = NULL;
#endif
+
+ for (x = 0; x < o; x++) {+ for (y = 0; y < o; y++) {+ int n = grid[y*o+x];
+ if (n) {+ if (cube(x, y, n))
+ latin_solver_place(solver, x, y, n);
+ else
+ return false; /* puzzle is already inconsistent */
+ }
+ }
+ }
+
+ return true;
}
void latin_solver_free(struct latin_solver *solver)
@@ -810,15 +819,17 @@
} else {newctx = ctx;
}
- latin_solver_alloc(&subsolver, outgrid, o);
#ifdef STANDALONE_SOLVER
subsolver.names = solver->names;
#endif
- ret = latin_solver_top(&subsolver, diff_recursive,
- diff_simple, diff_set_0, diff_set_1,
- diff_forcing, diff_recursive,
- usersolvers, valid, newctx,
- ctxnew, ctxfree);
+ if (latin_solver_alloc(&subsolver, outgrid, o))
+ ret = latin_solver_top(&subsolver, diff_recursive,
+ diff_simple, diff_set_0, diff_set_1,
+ diff_forcing, diff_recursive,
+ usersolvers, valid, newctx,
+ ctxnew, ctxfree);
+ else
+ ret = diff_impossible;
latin_solver_free(&subsolver);
if (ctxnew)
ctxfree(newctx);
@@ -1059,11 +1070,13 @@
struct latin_solver solver;
int diff;
- latin_solver_alloc(&solver, grid, o);
- diff = latin_solver_main(&solver, maxdiff,
- diff_simple, diff_set_0, diff_set_1,
- diff_forcing, diff_recursive,
- usersolvers, valid, ctx, ctxnew, ctxfree);
+ if (latin_solver_alloc(&solver, grid, o))
+ diff = latin_solver_main(&solver, maxdiff,
+ diff_simple, diff_set_0, diff_set_1,
+ diff_forcing, diff_recursive,
+ usersolvers, valid, ctx, ctxnew, ctxfree);
+ else
+ diff = diff_impossible;
latin_solver_free(&solver);
return diff;
}
--- a/latin.h
+++ b/latin.h
@@ -61,10 +61,13 @@
/* --- Solver allocation --- */
/* Fills in (and allocates members for) a latin_solver struct.
- * Will allocate members of snew, but not snew itself
+ * Will allocate members of solver, but not solver itself
* (allowing 'struct latin_solver' to be the first element in a larger
- * struct, for example). */
-void latin_solver_alloc(struct latin_solver *solver, digit *grid, int o);
+ * struct, for example).
+ *
+ * latin_solver_alloc returns false if the digits already in the grid
+ * could not be legally placed. */
+bool latin_solver_alloc(struct latin_solver *solver, digit *grid, int o);
void latin_solver_free(struct latin_solver *solver);
/* Allocates scratch space (for _set and _forcing) */
--- a/unequal.c
+++ b/unequal.c
@@ -890,14 +890,15 @@
struct latin_solver solver;
int diff;
- latin_solver_alloc(&solver, state->nums, state->order);
+ if (!latin_solver_alloc(&solver, state->nums, state->order))
+ diff = latin_solver_main(&solver, maxdiff,
+ DIFF_LATIN, DIFF_SET, DIFF_EXTREME,
+ DIFF_EXTREME, DIFF_RECURSIVE,
+ unequal_solvers, unequal_valid, ctx,
+ clone_ctx, free_ctx);
+ else
+ diff = DIFF_IMPOSSIBLE;
- diff = latin_solver_main(&solver, maxdiff,
- DIFF_LATIN, DIFF_SET, DIFF_EXTREME,
- DIFF_EXTREME, DIFF_RECURSIVE,
- unequal_solvers, unequal_valid, ctx,
- clone_ctx, free_ctx);
-
memcpy(state->hints, solver.cube, state->order*state->order*state->order);
free_ctx(ctx);
@@ -2256,13 +2257,14 @@
solver_show_working = debug;
game_debug(state);
- latin_solver_alloc(&solver, state->nums, state->order);
-
- diff = latin_solver_main(&solver, DIFF_RECURSIVE,
- DIFF_LATIN, DIFF_SET, DIFF_EXTREME,
- DIFF_EXTREME, DIFF_RECURSIVE,
- unequal_solvers, unequal_valid, ctx,
- clone_ctx, free_ctx);
+ if (latin_solver_alloc(&solver, state->nums, state->order))
+ diff = latin_solver_main(&solver, DIFF_RECURSIVE,
+ DIFF_LATIN, DIFF_SET, DIFF_EXTREME,
+ DIFF_EXTREME, DIFF_RECURSIVE,
+ unequal_solvers, unequal_valid, ctx,
+ clone_ctx, free_ctx);
+ else
+ diff = DIFF_IMPOSSIBLE;
free_ctx(ctx);
--- a/unfinished/group.c
+++ b/unfinished/group.c
@@ -580,13 +580,11 @@
int w = params->w;
int ret;
struct latin_solver solver;
+
#ifdef STANDALONE_SOLVER
char *p, text[100], *names[50];
int i;
-#endif
- latin_solver_alloc(&solver, grid, w);
-#ifdef STANDALONE_SOLVER
for (i = 0, p = text; i < w; i++) {names[i] = p;
*p++ = TOCHAR(i+1, params->id);
@@ -595,10 +593,13 @@
solver.names = names;
#endif
- ret = latin_solver_main(&solver, maxdiff,
- DIFF_TRIVIAL, DIFF_HARD, DIFF_EXTREME,
- DIFF_EXTREME, DIFF_UNREASONABLE,
- group_solvers, group_valid, NULL, NULL, NULL);
+ if (latin_solver_alloc(&solver, grid, w))
+ ret = latin_solver_main(&solver, maxdiff,
+ DIFF_TRIVIAL, DIFF_HARD, DIFF_EXTREME,
+ DIFF_EXTREME, DIFF_UNREASONABLE,
+ group_solvers, group_valid, NULL, NULL, NULL);
+ else
+ ret = diff_impossible;
latin_solver_free(&solver);