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.

4 files changed, 60 insertions, 41 deletions

diff --git a/latin.c b/latin.c
index 3993016..59f306d 100644
--- a/latin.c
+++ b/latin.c
@@ -563,7 +563,7 @@ void latin_solver_free_scratch(struct latin_solver_scratch *scratch)
     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 @@ void latin_solver_alloc(struct latin_solver *solver, digit *grid, int o)
     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 @@ static int latin_solver_recurse
 	    } 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 @@ int latin_solver(digit *grid, int o, int maxdiff,
     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;
 }
diff --git a/latin.h b/latin.h
index bb172ec..96a0480 100644
--- a/latin.h
+++ b/latin.h
@@ -61,10 +61,13 @@ int latin_solver_forcing(struct latin_solver *solver,
 /* --- 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) */
diff --git a/unequal.c b/unequal.c
index ed03c0b..f2328b6 100644
--- a/unequal.c
+++ b/unequal.c
@@ -890,13 +890,14 @@ static int solver_state(game_state *state, int maxdiff)
     struct latin_solver solver;
     int diff;
 
-    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);
+    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;
 
     memcpy(state->hints, solver.cube, state->order*state->order*state->order);
 
@@ -2256,13 +2257,14 @@ static int solve(game_params *p, char *desc, int debug)
     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);
 
diff --git a/unfinished/group.c b/unfinished/group.c
index e72e3ce..2eca7c4 100644
--- a/unfinished/group.c
+++ b/unfinished/group.c
@@ -580,13 +580,11 @@ static int solver(const game_params *params, digit *grid, int maxdiff)
     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 @@ static int solver(const game_params *params, digit *grid, int maxdiff)
     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);