Add hinting feature to Guess.

Pressing H now suggests the lexicographically first row consistent
with all previous feedback.

The previous function of the H key to toggle a hold marker on the
current peg is now performed by Space / CURSOR_SELECT2, which is more
in line with other puzzles anyway.

diff --git a/guess.c b/guess.c
index 37030d1e402367396ae87ccffd8fe0d330df3e05..df9b7f628c9d117d614257d93b3f44794b20fed5 100644 (file)
--- a/guess.c
+++ b/guess.c
@@ -421,6 +421,7 @@ struct game_ui {
     int drag_opeg; /* peg index, if dragged from a peg (from current guess), otherwise -1 */
 
     int show_labels;                   /* label the colours with letters */
+    pegrow hint;
 };
 
 static game_ui *new_ui(const game_state *state)
@@ -437,6 +438,8 @@ static game_ui *new_ui(const game_state *state)
 
 static void free_ui(game_ui *ui)
 {
+    if (ui->hint)
+        free_pegrow(ui->hint);
     free_pegrow(ui->curr_pegs);
     sfree(ui->holds);
     sfree(ui);
@@ -487,6 +490,11 @@ static void game_changed_state(game_ui *ui, const game_state *oldstate,
 {
     int i;
 
+    if (newstate->next_go < oldstate->next_go) {
+        sfree(ui->hint);
+        ui->hint = NULL;
+    }
+
     /* Implement holds, clear other pegs.
      * This does something that is arguably the Right Thing even
      * for undo. */
@@ -571,7 +579,7 @@ static void set_peg(const game_params *params, game_ui *ui, int peg, int col)
     ui->markable = is_markable(params, ui->curr_pegs);
 }
 
-static int mark_pegs(pegrow guess, pegrow solution, int ncols)
+static int mark_pegs(pegrow guess, const pegrow solution, int ncols)
 {
     int nc_place = 0, nc_colour = 0, i, j;
 
@@ -633,6 +641,125 @@ static char *encode_move(const game_state *from, game_ui *ui)
     return buf;
 }
 
+static void compute_hint(const game_state *state, game_ui *ui)
+{
+    /* Suggest the lexicographically first row consistent with all
+     * previous feedback.  This is not only a useful hint, but also
+     * a reasonable strategy if applied consistently.  If the user
+     * uses hints in every turn, they may be able to intuit this
+     * strategy, or one similar to it.  I (Jonas Kölker) came up
+     * with something close to it without seeing it in action. */
+
+    /* Some performance characteristics: I want to ask for each n,
+     * how many solutions are guessed in exactly n guesses if you
+     * use the hint in each turn.
+     *
+     * With 4 pegs and 6 colours you get the following histogram:
+     *
+     *  1 guesses:     1 solution
+     *  2 guesses:     4 solutions
+     *  3 guesses:    25 solutions
+     *  4 guesses:   108 solutions
+     *  5 guesses:   305 solutions
+     *  6 guesses:   602 solutions
+     *  7 guesses:   196 solutions
+     *  8 guesses:    49 solutions
+     *  9 guesses:     6 solutions
+     * (note: the tenth guess is never necessary.)
+     *
+     * With 5 pegs and 8 colours you get the following histogram:
+     *
+     *  1 guesses:     1 solution
+     *  2 guesses:     5 solutions
+     *  3 guesses:    43 solutions
+     *  4 guesses:   278 solutions
+     *  5 guesses:  1240 solutions
+     *  6 guesses:  3515 solutions
+     *  7 guesses:  7564 solutions
+     *  8 guesses: 14086 solutions
+     *  9 guesses:  4614 solutions
+     * 10 guesses:  1239 solutions
+     * 11 guesses:   175 solutions
+     * 12 guesses:     7 solutions
+     * 13 guesses:     1 solution
+     *
+     * The solution which takes too many guesses is {8, 8, 5, 6, 7}.
+     * The game ID is c8p5g12Bm:4991e5e41a. */
+
+    int mincolour = 1, maxcolour = 0, i, j;
+
+    /* For large values of npegs and ncolours, the lexicographically
+     * next guess make take a while to find.  Finding upper and
+     * lower limits on which colours we have to consider will speed
+     * this up, as will caching our progress from one invocation to
+     * the next.  The latter strategy works, since if we have ruled
+     * out a candidate we will never reverse this judgment in the
+     * light of new information.  Removing information, i.e. undo,
+     * will require us to backtrack somehow.  We backtrack by fully
+     * forgetting our progress (and recomputing it if required). */
+
+    for (i = 0; i < state->next_go; ++i)
+        for (j = 0; j < state->params.npegs; ++j)
+            if (state->guesses[i]->pegs[j] > maxcolour)
+                maxcolour = state->guesses[i]->pegs[j];
+    maxcolour = min(maxcolour + 1, state->params.ncolours);
+
+increase_mincolour:
+    for (i = 0; i < state->next_go; ++i) {
+        if (state->guesses[i]->feedback[0])
+            goto next_iteration;
+        for (j = 0; j < state->params.npegs; ++j)
+            if (state->guesses[i]->pegs[j] != mincolour)
+                goto next_iteration;
+        ++mincolour;
+        goto increase_mincolour;
+    next_iteration:
+        ;
+    }
+
+    if (!ui->hint) {
+        ui->hint = new_pegrow(state->params.npegs);
+        for (i = 0; i < state->params.npegs; ++i)
+            ui->hint->pegs[i] = 1;
+    }
+
+    while (ui->hint->pegs[0] <= state->params.ncolours) {
+        for (i = 0; i < state->next_go; ++i) {
+            mark_pegs(ui->hint, state->guesses[i], maxcolour);
+            for (j = 0; j < state->params.npegs; ++j)
+                if (ui->hint->feedback[j] != state->guesses[i]->feedback[j])
+                    goto increment_pegrow;
+        }
+        /* a valid guess was found; install it and return */
+        for (i = 0; i < state->params.npegs; ++i)
+            ui->curr_pegs->pegs[i] = ui->hint->pegs[i];
+
+        ui->markable = TRUE;
+        ui->peg_cur = state->params.npegs;
+        ui->display_cur = 1;
+        return;
+
+    increment_pegrow:
+        for (i = ui->hint->npegs;
+             ++ui->hint->pegs[--i], i && ui->hint->pegs[i] > maxcolour;
+             ui->hint->pegs[i] = mincolour);
+    }
+    /* No solution is compatible with the given hints.  Impossible! */
+    /* (hack new_game_desc to create invalid solutions to get here) */
+
+    /* For some values of npegs and ncolours, the hinting function takes a
+     * long time to complete.  To visually indicate completion with failure,
+     * should it ever happen, update the ui in some trivial way.  This gives
+     * the user a sense of broken(ish)ness and futility. */
+    if (!ui->display_cur) {
+        ui->display_cur = 1;
+    } else if (state->params.npegs == 1) {
+        ui->display_cur = 0;
+    } else {
+        ui->peg_cur = (ui->peg_cur + 1) % state->params.npegs;
+    }
+}
+
 static char *interpret_move(const game_state *from, game_ui *ui,
                             const game_drawstate *ds,
                             int x, int y, int button)
@@ -754,6 +881,9 @@ static char *interpret_move(const game_state *from, game_ui *ui,
         if (button == CURSOR_UP && ui->colour_cur > 0)
             ui->colour_cur--;
         ret = "";
+    } else if (button == 'h' || button == 'H' || button == '?') {
+        compute_hint(from, ui);
+        ret = "";
     } else if (button == CURSOR_LEFT || button == CURSOR_RIGHT) {
         int maxcur = from->params.npegs;
         if (ui->markable) maxcur++;
@@ -776,7 +906,7 @@ static char *interpret_move(const game_state *from, game_ui *ui,
         ui->display_cur = 1;
         set_peg(&from->params, ui, ui->peg_cur, 0);
         ret = "";
-    } else if (button == 'H' || button == 'h') {
+    } else if (button == CURSOR_SELECT2) {
         if (ui->peg_cur == from->params.npegs)
             return NULL;
         ui->display_cur = 1;

diff --git a/puzzles.but b/puzzles.but
index 8ad466fa6ac56945926b6aa3247a0177aff8dcd0..def571e59f72d548ccc1db39becf560d03ae5593 100644 (file)
--- a/puzzles.but
+++ b/puzzles.but
@@ -1324,7 +1324,11 @@ Alternatively, with the keyboard, the up and down cursor keys can be
 used to select a peg colour, the left and right keys to select a
 peg position, and the space bar or Enter key to place a peg of the
 selected colour in the chosen position. \q{D} or Backspace removes a
-peg, and \q{H} adds a hold marker.
+peg, and Space adds a hold marker.
+
+Pressing \q{h} or \q{?} will fill the current guess with a suggested
+guess.  Using this is not recommended for 10 or more pegs as it is
+slow.
 
 When the guess is complete, the smaller feedback pegs will be highlighted;
 clicking on these (or moving the peg cursor to them with the arrow keys