ref: 432590a05c17b8220efb97ffa038120f1102f5d8
parent: c9b3c3896ca54681d03bd6c25e433affd9809860
author: Simon Tatham <anakin@pobox.com>
date: Tue May 19 17:02:36 EDT 2020
Group: add a special deduction about the group identity. In identity-hidden mode, as soon as you find any table entry that matches the element indexing its row or column (i.e. a product of group elements of the form ab=a or ab=b), then you immediately know which element is the group identity, and you can fill in the rest of its row and column trivially. But the Group solver was not actually able to do this deduction. Proof: it couldn't solve the game id 4i:1d1d1d1, which is trivial if you take this into account. (a^2=a, so a is the identity, and once you fill in ax=xa=x for all x, the rest of the grid is forced.) So I've added dedicated piece of logic to spot the group identity as soon as anything in its row and column is filled in. Now that puzzle can be solved. (A thing that I _haven't_ done here is the higher-level deduction of determining the identity by elimination. Any table entry that _doesn't_ match either its row or column rules out both the row and the column from being the group identity - so as soon as you have enough table entries to rule out all but one element, you know the identity must be the remaining one. At the moment, this is just doing the simple version of the deduction where a single table entry tells you what _is_ the identity.) One slightly tricky part is that because this new identity inference deduction fills in multiple grid entries at a time, it has to be careful to avoid triggering an assertion failure if the puzzle is inconsistent - before filling in each entry, it has to make sure the value it wants to fill in has not been ruled out by something it filled in already. Without that care, an insoluble puzzle can cause the solver to crash - and worse, the same can happen on an insoluble _branch_ of the guesswork-and-backtracking tree in Unreasonable mode. In both cases, the answer is to make sure you detect the problem before hitting the assertion, and return -1 for 'inconsistent puzzle' if you spot it. Then any guesswork branch that ends up in this situation is cleanly abandoned, and we move on to another one.
--- a/unfinished/group.c
+++ b/unfinished/group.c
@@ -280,6 +280,23 @@
* Solver.
*/
+static int find_identity(struct latin_solver *solver)
+{+ int w = solver->o;
+ digit *grid = solver->grid;
+ int i, j;
+
+ for (i = 0; i < w; i++)
+ for (j = 0; j < w; j++) {+ if (grid[i*w+j] == i+1)
+ return j+1;
+ if (grid[i*w+j] == j+1)
+ return i+1;
+ }
+
+ return 0;
+}
+
static int solver_normal(struct latin_solver *solver, void *vctx)
{int w = solver->o;
@@ -357,6 +374,73 @@
}
}
}
+
+ /*
+ * Fill in the row and column for the group identity, if it's not
+ * already known and if we've just found out what it is.
+ */
+ i = find_identity(solver);
+ if (i) {+ bool done_something = false;
+ for (j = 1; j <= w; j++) {+ if (!grid[(i-1)*w+(j-1)] || !grid[(j-1)*w+(i-1)]) {+ done_something = true;
+ }
+ }
+ if (done_something) {+#ifdef STANDALONE_SOLVER
+ if (solver_show_working) {+ printf("%*s%s is the group identity\n",+ solver_recurse_depth*4, "", names[i-1]);
+ }
+#endif
+ for (j = 1; j <= w; j++) {+ if (!grid[(j-1)*w+(i-1)]) {+ if (!cube(i-1, j-1, j)) {+#ifdef STANDALONE_SOLVER
+ if (solver_show_working) {+ printf("%*s but %s cannot go at (%d,%d) - "+ "contradiction!\n",
+ solver_recurse_depth*4, "",
+ names[j-1], i, j);
+ }
+ return -1;
+#endif
+ }
+#ifdef STANDALONE_SOLVER
+ if (solver_show_working) {+ printf("%*s placing %s at (%d,%d)\n",+ solver_recurse_depth*4, "",
+ names[j-1], i, j);
+ }
+#endif
+ latin_solver_place(solver, i-1, j-1, j);
+ }
+ if (!grid[(i-1)*w+(j-1)]) {+ if (!cube(j-1, i-1, j)) {+#ifdef STANDALONE_SOLVER
+ if (solver_show_working) {+ printf("%*s but %s cannot go at (%d,%d) - "+ "contradiction!\n",
+ solver_recurse_depth*4, "",
+ names[j-1], j, i);
+ }
+ return -1;
+#endif
+ }
+#ifdef STANDALONE_SOLVER
+ if (solver_show_working) {+ printf("%*s placing %s at (%d,%d)\n",+ solver_recurse_depth*4, "",
+ names[j-1], j, i);
+ }
+#endif
+ latin_solver_place(solver, j-1, i-1, j);
+ }
+ }
+ return 1;
+ }
+ }
return 0;
}