}
static const struct {
- char *name;
+ const char *name;
game_params params;
} guess_presets[] = {
{"Standard", {6, 4, 10, FALSE, TRUE}},
ret[0].name = "Colours";
ret[0].type = C_STRING;
sprintf(buf, "%d", params->ncolours);
- ret[0].sval = dupstr(buf);
- ret[0].ival = 0;
+ ret[0].u.string.sval = dupstr(buf);
ret[1].name = "Pegs per guess";
ret[1].type = C_STRING;
sprintf(buf, "%d", params->npegs);
- ret[1].sval = dupstr(buf);
- ret[1].ival = 0;
+ ret[1].u.string.sval = dupstr(buf);
ret[2].name = "Guesses";
ret[2].type = C_STRING;
sprintf(buf, "%d", params->nguesses);
- ret[2].sval = dupstr(buf);
- ret[2].ival = 0;
+ ret[2].u.string.sval = dupstr(buf);
ret[3].name = "Allow blanks";
ret[3].type = C_BOOLEAN;
- ret[3].sval = NULL;
- ret[3].ival = params->allow_blank;
+ ret[3].u.boolean.bval = params->allow_blank;
ret[4].name = "Allow duplicates";
ret[4].type = C_BOOLEAN;
- ret[4].sval = NULL;
- ret[4].ival = params->allow_multiple;
+ ret[4].u.boolean.bval = params->allow_multiple;
ret[5].name = NULL;
ret[5].type = C_END;
- ret[5].sval = NULL;
- ret[5].ival = 0;
return ret;
}
{
game_params *ret = snew(game_params);
- ret->ncolours = atoi(cfg[0].sval);
- ret->npegs = atoi(cfg[1].sval);
- ret->nguesses = atoi(cfg[2].sval);
+ ret->ncolours = atoi(cfg[0].u.string.sval);
+ ret->npegs = atoi(cfg[1].u.string.sval);
+ ret->nguesses = atoi(cfg[2].u.string.sval);
- ret->allow_blank = cfg[3].ival;
- ret->allow_multiple = cfg[4].ival;
+ ret->allow_blank = cfg[3].u.boolean.bval;
+ ret->allow_multiple = cfg[4].u.boolean.bval;
return ret;
}
-static char *validate_params(const game_params *params, int full)
+static const char *validate_params(const game_params *params, int full)
{
if (params->ncolours < 2 || params->npegs < 2)
return "Trivial solutions are uninteresting";
return ret;
}
-static char *validate_desc(const game_params *params, const char *desc)
+static const char *validate_desc(const game_params *params, const char *desc)
{
unsigned char *bmp;
int i;
}
static char *solve_game(const game_state *state, const game_state *currstate,
- const char *aux, char **error)
+ const char *aux, const char **error)
{
return dupstr("S");
}
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)
static void free_ui(game_ui *ui)
{
+ if (ui->hint)
+ free_pegrow(ui->hint);
free_pegrow(ui->curr_pegs);
sfree(ui->holds);
sfree(ui);
static char *encode_ui(const game_ui *ui)
{
- char *ret, *p, *sep;
+ char *ret, *p;
+ const char *sep;
int i;
/*
{
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. */
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;
static char *encode_move(const game_state *from, game_ui *ui)
{
- char *buf, *p, *sep;
+ char *buf, *p;
+ const char *sep;
int len, i;
len = ui->curr_pegs->npegs * 20 + 2;
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)
*/
if (button == 'l' || button == 'L') {
ui->show_labels = !ui->show_labels;
- return "";
+ return UI_UPDATE;
}
if (from->solved) return NULL;
ui->drag_y = y;
debug(("Start dragging, col = %d, (%d,%d)",
ui->drag_col, ui->drag_x, ui->drag_y));
- ret = "";
+ ret = UI_UPDATE;
}
} else if (button == LEFT_DRAG && ui->drag_col) {
ui->drag_x = x;
ui->drag_y = y;
debug(("Keep dragging, (%d,%d)", ui->drag_x, ui->drag_y));
- ret = "";
+ ret = UI_UPDATE;
} else if (button == LEFT_RELEASE && ui->drag_col) {
if (over_guess > -1) {
debug(("Dropping colour %d onto guess peg %d",
ui->drag_opeg = -1;
ui->display_cur = 0;
debug(("Stop dragging."));
- ret = "";
+ ret = UI_UPDATE;
} else if (button == RIGHT_BUTTON) {
if (over_guess > -1) {
/* we use ths feedback in the game_ui to signify
* 'carry this peg to the next guess as well'. */
ui->holds[over_guess] = 1 - ui->holds[over_guess];
- ret = "";
+ ret = UI_UPDATE;
}
} else if (button == LEFT_RELEASE && over_hint && ui->markable) {
/* NB this won't trigger if on the end of a drag; that's on
ui->colour_cur++;
if (button == CURSOR_UP && ui->colour_cur > 0)
ui->colour_cur--;
- ret = "";
+ ret = UI_UPDATE;
+ } else if (button == 'h' || button == 'H' || button == '?') {
+ compute_hint(from, ui);
+ ret = UI_UPDATE;
} else if (button == CURSOR_LEFT || button == CURSOR_RIGHT) {
int maxcur = from->params.npegs;
if (ui->markable) maxcur++;
ui->peg_cur++;
if (button == CURSOR_LEFT && ui->peg_cur > 0)
ui->peg_cur--;
- ret = "";
+ ret = UI_UPDATE;
} else if (IS_CURSOR_SELECT(button)) {
ui->display_cur = 1;
if (ui->peg_cur == from->params.npegs) {
ret = encode_move(from, ui);
} else {
set_peg(&from->params, ui, ui->peg_cur, ui->colour_cur+1);
- ret = "";
+ ret = UI_UPDATE;
}
} else if (button == 'D' || button == 'd' || button == '\b') {
ui->display_cur = 1;
set_peg(&from->params, ui, ui->peg_cur, 0);
- ret = "";
- } else if (button == 'H' || button == 'h') {
+ ret = UI_UPDATE;
+ } else if (button == CURSOR_SELECT2) {
if (ui->peg_cur == from->params.npegs)
return NULL;
ui->display_cur = 1;
ui->holds[ui->peg_cur] = 1 - ui->holds[ui->peg_cur];
- ret = "";
+ ret = UI_UPDATE;
}
return ret;
}
const struct game thegame = {
"Guess", "games.guess", "guess",
default_params,
- game_fetch_preset,
+ game_fetch_preset, NULL,
decode_params,
encode_params,
free_params,
~ian / sgt-puzzles.git / blobdiff