+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:
+ ;