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]

diff --git a/solo.c b/solo.c
index f8d8d6ba418ca2302fe99c41a0e64fba390a2673..165e683745be869ed41a5095654e889bf64cc090 100644 (file)
--- a/solo.c
+++ b/solo.c
@@ -1674,8 +1674,8 @@ static char *new_game_desc(game_params *params, random_state *rs,
     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
@@ -1691,31 +1691,6 @@ static char *new_game_desc(game_params *params, random_state *rs,
     locs = snewn(area, struct xy);
     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
@@ -1748,62 +1723,55 @@ static char *new_game_desc(game_params *params, random_state *rs,
          * 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++;
                 }
             }
 
-            /*
-             * 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 shuffle that list.
+         */
+        shuffle(locs, nlocs, sizeof(*locs), rs);
 
-                x = locs[i].x;
-                y = locs[i].y;
+        /*
+         * 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;
 
-                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;
+            x = locs[i].x;
+            y = locs[i].y;
 
-               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;
-                }
-            }
+            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;
 
-            if (i == nlocs) {
-                /*
-                 * There was nothing we could remove without
-                 * destroying solvability. Give up.
-                 */
-                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;
             }
         }
 
@@ -1813,8 +1781,6 @@ static char *new_game_desc(game_params *params, random_state *rs,
     sfree(grid2);
     sfree(locs);
 
-    sfree(symmclasses);
-
     /*
      * Now we have the grid as it will be presented to the user.
      * Encode it in a game desc.