Aha, here's a nice easy way to generate really hard puzzles. Added

the missing fifth difficulty level to Solo: `Unreasonable', in which
even set-based reasoning is insufficient and there's no alternative
but to guess a number and backtrack if it didn't work. (Solutions
are still guaranteed unique, however.) In fact it now seems to take
less time to generate a puzzle of this grade than `Advanced'!

git-svn-id: svn://svn.tartarus.org/sgt/puzzles@5756 cda61777-01e9-0310-a592-d414129be87e

diff --git a/puzzles.but b/puzzles.but
index 1e6c0fa..7d90f43 100644 (file)
--- a/puzzles.but
+++ b/puzzles.but
@@ -691,9 +691,10 @@ particular, on difficulty levels \q{Trivial} and \q{Basic} there
 will be a square you can fill in with a single number at all times,
 whereas at \q{Intermediate} level and beyond you will have to make
 partial deductions about the \e{set} of squares a number could be in
-(or the set of numbers that could be in a square). None of the
-difficulty levels generated by this program ever requires making a
-guess and backtracking if it turns out to be wrong.
+(or the set of numbers that could be in a square). At
+\q{Unreasonable} level, even this is not enough, and you will
+eventually have to make a guess, and then backtrack if it turns out
+to be wrong.
 
 Generating difficult puzzles is itself difficult: if you select
 \q{Intermediate} or \q{Advanced} difficulty, Solo may have to make
@@ -738,6 +739,8 @@ parameters:
 
 \b \cq{da} for Advanced difficulty level
 
+\b \cq{du} for Unreasonable difficulty level
+
 So, for example, you can make Solo generate asymmetric 3x4 grids by
 running \cq{solo 3x4a}, or 4-way rotationally symmetric 2x3 grids by
 running \cq{solo 2x3r4}, or \q{Advanced}-level 2x3 grids by running

diff --git a/solo.c b/solo.c
index eb35e00..3cb050d 100644 (file)
--- a/solo.c
+++ b/solo.c
@@ -144,6 +144,7 @@ static int game_fetch_preset(int i, char **name, game_params **params)
         { "3x3 Basic", { 3, 3, SYMM_ROT2, DIFF_SIMPLE } },
         { "3x3 Intermediate", { 3, 3, SYMM_ROT2, DIFF_INTERSECT } },
         { "3x3 Advanced", { 3, 3, SYMM_ROT2, DIFF_SET } },
+        { "3x3 Unreasonable", { 3, 3, SYMM_ROT2, DIFF_RECURSIVE } },
         { "3x4 Basic", { 3, 4, SYMM_ROT2, DIFF_SIMPLE } },
         { "4x4 Basic", { 4, 4, SYMM_ROT2, DIFF_SIMPLE } },
     };
@@ -193,6 +194,8 @@ static game_params *decode_params(char const *string)
                 string++, ret->diff = DIFF_INTERSECT;
             else if (*string == 'a')   /* advanced */
                 string++, ret->diff = DIFF_SET;
+            else if (*string == 'u')   /* unreasonable */
+                string++, ret->diff = DIFF_RECURSIVE;
         } else
             string++;                  /* eat unknown character */
     }
@@ -239,7 +242,7 @@ static config_item *game_configure(game_params *params)
 
     ret[3].name = "Difficulty";
     ret[3].type = C_CHOICES;
-    ret[3].sval = ":Trivial:Basic:Intermediate:Advanced";
+    ret[3].sval = ":Trivial:Basic:Intermediate:Advanced:Unreasonable";
     ret[3].ival = params->diff;
 
     ret[4].name = NULL;
@@ -1368,7 +1371,7 @@ static char *new_game_seed(game_params *params, random_state *rs,
     char *seed;
     int coords[16], ncoords;
     int xlim, ylim;
-    int maxdiff;
+    int maxdiff, recursing;
 
     /*
      * Adjust the maximum difficulty level to be consistent with
@@ -1416,6 +1419,7 @@ static char *new_game_seed(game_params *params, random_state *rs,
          * while preserving solubility.
          */
         symmetry_limit(params, &xlim, &ylim, params->symm);
+       recursing = FALSE;
         while (1) {
             int x, y, i, j;
 
@@ -1452,6 +1456,8 @@ static char *new_game_seed(game_params *params, random_state *rs,
              * nsolve.
              */
             for (i = 0; i < nlocs; i++) {
+               int ret;
+
                 x = locs[i].x;
                 y = locs[i].y;
 
@@ -1460,7 +1466,12 @@ static char *new_game_seed(game_params *params, random_state *rs,
                 for (j = 0; j < ncoords; j++)
                     grid2[coords[2*j+1]*cr+coords[2*j]] = 0;
 
-                if (nsolve(c, r, grid2) <= maxdiff) {
+               if (recursing)
+                   ret = (rsolve(c, r, grid2, NULL, 2) == 1);
+               else
+                   ret = (nsolve(c, r, grid2) <= maxdiff);
+
+                if (ret) {
                     for (j = 0; j < ncoords; j++)
                         grid[coords[2*j+1]*cr+coords[2*j]] = 0;
                     break;
@@ -1469,15 +1480,22 @@ static char *new_game_seed(game_params *params, random_state *rs,
 
             if (i == nlocs) {
                 /*
-                 * There was nothing we could remove without destroying
-                 * solvability.
+                 * There was nothing we could remove without
+                 * destroying solvability. If we're trying to
+                 * generate a recursion-only grid and haven't
+                 * switched over to rsolve yet, we now do;
+                 * otherwise we give up.
                  */
-                break;
+               if (maxdiff == DIFF_RECURSIVE && !recursing) {
+                   recursing = TRUE;
+               } else {
+                   break;
+               }
             }
         }
 
         memcpy(grid2, grid, area);
-    } while (nsolve(c, r, grid2) != maxdiff);
+    } while (nsolve(c, r, grid2) < maxdiff);
 
     sfree(grid2);
     sfree(locs);