ref: e55838bc9b0d173ca539d0cfe714495b5c12b9dd
parent: 414330d9ad00e3b788d48b1d928e46ad7698c508
author: Simon Tatham <anakin@pobox.com>
date: Thu Aug 4 07:16:10 EDT 2005
I am COMPLETELY GORMLESS. The Solo grid generator, when eliminating clues from a filled grid, was using the algorithm - loop over the whole grid looking for a clue (or symmetry group of clues) which can be safely removed - remove it - loop over the whole grid again, and so on. This was due to my vague feeling that removing one clue might affect whether another can be removed. Of course this can happen - two clues can be alternative ways of deducing the same vital fact so that removing one makes the other necessary - but what _can't_ happen is for removing one clue to make another _become_ removable, since you can only do that by _adding_ information. In other words, after testing a clue and determining that it can't be removed, you never need to test it again. Thus, a much simpler algorithm is - loop over the possible clues (or symmetry groups) _once_, in a random order - for each clue (group), if it is removable, remove it. This still guarantees to leave the grid in a state where no further clues can be removed, but it greatly cuts down puzzle generation time and also simplifies the code. I am a fool for not having spotted this in three and a half months! [originally from svn r6160]
--- a/solo.c
+++ b/solo.c
@@ -1674,8 +1674,8 @@
int nlocs;
char *desc;
int coords[16], ncoords;
- int *symmclasses, nsymmclasses;
- int maxdiff, recursing;
+ int maxdiff;
+ int x, y, i, j;
/*
* Adjust the maximum difficulty level to be consistent with
@@ -1692,31 +1692,6 @@
grid2 = snewn(area, digit);
/*
- * Find the set of equivalence classes of squares permitted
- * by the selected symmetry. We do this by enumerating all
- * the grid squares which have no symmetric companion
- * sorting lower than themselves.
- */
- nsymmclasses = 0;
- symmclasses = snewn(cr * cr, int);
- {- int x, y;
-
- for (y = 0; y < cr; y++)
- for (x = 0; x < cr; x++) {- int i = y*cr+x;
- int j;
-
- ncoords = symmetries(params, x, y, coords, params->symm);
- for (j = 0; j < ncoords; j++)
- if (coords[2*j+1]*cr+coords[2*j] < i)
- break;
- if (j == ncoords)
- symmclasses[nsymmclasses++] = i;
- }
- }
-
- /*
* Loop until we get a grid of the required difficulty. This is
* nasty, but it seems to be unpleasantly hard to generate
* difficult grids otherwise.
@@ -1748,20 +1723,24 @@
* Now we have a solved grid, start removing things from it
* while preserving solubility.
*/
- recursing = FALSE;
- while (1) {- int x, y, i, j;
- /*
- * Iterate over the grid and enumerate all the filled
- * squares we could empty.
- */
- nlocs = 0;
+ /*
+ * Find the set of equivalence classes of squares permitted
+ * by the selected symmetry. We do this by enumerating all
+ * the grid squares which have no symmetric companion
+ * sorting lower than themselves.
+ */
+ nlocs = 0;
+ for (y = 0; y < cr; y++)
+ for (x = 0; x < cr; x++) {+ int i = y*cr+x;
+ int j;
- for (i = 0; i < nsymmclasses; i++) {- x = symmclasses[i] % cr;
- y = symmclasses[i] / cr;
- if (grid[y*cr+x]) {+ ncoords = symmetries(params, x, y, coords, params->symm);
+ for (j = 0; j < ncoords; j++)
+ if (coords[2*j+1]*cr+coords[2*j] < i)
+ break;
+ if (j == ncoords) {locs[nlocs].x = x;
locs[nlocs].y = y;
nlocs++;
@@ -1768,43 +1747,32 @@
}
}
- /*
- * Now shuffle that list.
- */
- shuffle(locs, nlocs, sizeof(*locs), rs);
+ /*
+ * Now shuffle that list.
+ */
+ shuffle(locs, nlocs, sizeof(*locs), rs);
- /*
- * Now loop over the shuffled list and, for each element,
- * see whether removing that element (and its reflections)
- * from the grid will still leave the grid soluble by
- * solver.
- */
- for (i = 0; i < nlocs; i++) {- int ret;
+ /*
+ * Now loop over the shuffled list and, for each element,
+ * see whether removing that element (and its reflections)
+ * from the grid will still leave the grid soluble.
+ */
+ for (i = 0; i < nlocs; i++) {+ int ret;
- x = locs[i].x;
- y = locs[i].y;
+ x = locs[i].x;
+ y = locs[i].y;
- memcpy(grid2, grid, area);
- ncoords = symmetries(params, x, y, coords, params->symm);
- for (j = 0; j < ncoords; j++)
- grid2[coords[2*j+1]*cr+coords[2*j]] = 0;
+ memcpy(grid2, grid, area);
+ ncoords = symmetries(params, x, y, coords, params->symm);
+ for (j = 0; j < ncoords; j++)
+ grid2[coords[2*j+1]*cr+coords[2*j]] = 0;
- ret = solver(c, r, grid2, maxdiff);
- if (ret != DIFF_IMPOSSIBLE && ret != DIFF_AMBIGUOUS) {- for (j = 0; j < ncoords; j++)
- grid[coords[2*j+1]*cr+coords[2*j]] = 0;
- break;
- }
+ ret = solver(c, r, grid2, maxdiff);
+ if (ret != DIFF_IMPOSSIBLE && ret != DIFF_AMBIGUOUS) {+ for (j = 0; j < ncoords; j++)
+ grid[coords[2*j+1]*cr+coords[2*j]] = 0;
}
-
- if (i == nlocs) {- /*
- * There was nothing we could remove without
- * destroying solvability. Give up.
- */
- break;
- }
}
memcpy(grid2, grid, area);
@@ -1812,8 +1780,6 @@
sfree(grid2);
sfree(locs);
-
- sfree(symmclasses);
/*
* Now we have the grid as it will be presented to the user.