X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/7c568a48f46bd88d9f298a1c29ac0f64a88266c0..36d01ffa8154db198db95b4cc3f788a430c7fee2:/solo.c diff --git a/solo.c b/solo.c index d991536..c9c6412 100644 --- a/solo.c +++ b/solo.c @@ -3,20 +3,12 @@ * * TODO: * - * - can we do anything about nasty centring of text in GTK? It - * seems to be taking ascenders/descenders into account when - * centring. Ick. - * * - it might still be nice to do some prioritisation on the * removal of numbers from the grid * + one possibility is to try to minimise the maximum number * of filled squares in any block, which in particular ought * to enforce never leaving a completely filled block in the * puzzle as presented. - * + be careful of being too clever here, though, until after - * I've tried implementing difficulty levels. It's not - * impossible that those might impose much more important - * constraints on this process. * * - alternative interface modes * + sudoku.com's Windows program has a palette of possible @@ -115,7 +107,7 @@ struct game_state { int c, r; digit *grid; unsigned char *immutable; /* marks which digits are clues */ - int completed; + int completed, cheated; }; static game_params *default_params(void) @@ -124,7 +116,7 @@ static game_params *default_params(void) ret->c = ret->r = 3; ret->symm = SYMM_ROT2; /* a plausible default */ - ret->diff = DIFF_SIMPLE; /* so is this */ + ret->diff = DIFF_BLOCK; /* so is this */ return ret; } @@ -149,9 +141,11 @@ static int game_fetch_preset(int i, char **name, game_params **params) } presets[] = { { "2x2 Trivial", { 2, 2, SYMM_ROT2, DIFF_BLOCK } }, { "2x3 Basic", { 2, 3, SYMM_ROT2, DIFF_SIMPLE } }, + { "3x3 Trivial", { 3, 3, SYMM_ROT2, DIFF_BLOCK } }, { "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 } }, }; @@ -171,6 +165,7 @@ static game_params *decode_params(char const *string) ret->c = ret->r = atoi(string); ret->symm = SYMM_ROT2; + ret->diff = DIFF_BLOCK; while (*string && isdigit((unsigned char)*string)) string++; if (*string == 'x') { string++; @@ -201,6 +196,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 */ } @@ -247,7 +244,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; @@ -1124,7 +1121,7 @@ static int nsolve(int c, int r, digit *grid) #ifdef STANDALONE_SOLVER , "intersectional analysis," " row %d vs block (%d,%d)", - 1+YUNTRANS(y), 1+x, 1+y%r + 1+YUNTRANS(y), 1+x/r, 1+y%r #endif ) || nsolve_intersect(usage, cubepos(x,y%r,n), r*cr, @@ -1132,7 +1129,7 @@ static int nsolve(int c, int r, digit *grid) #ifdef STANDALONE_SOLVER , "intersectional analysis," " block (%d,%d) vs row %d", - 1+x, 1+y%r, 1+YUNTRANS(y) + 1+x/r, 1+y%r, 1+YUNTRANS(y) #endif ))) { diff = max(diff, DIFF_INTERSECT); @@ -1359,7 +1356,13 @@ static int symmetries(game_params *params, int x, int y, int *output, int s) return i; } -static char *new_game_seed(game_params *params, random_state *rs) +struct game_aux_info { + int c, r; + digit *grid; +}; + +static char *new_game_seed(game_params *params, random_state *rs, + game_aux_info **aux) { int c = params->c, r = params->r, cr = c*r; int area = cr*cr; @@ -1370,7 +1373,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 @@ -1401,11 +1404,24 @@ static char *new_game_seed(game_params *params, random_state *rs) assert(ret == 1); assert(check_valid(c, r, grid)); + /* + * Save the solved grid in the aux_info. + */ + { + game_aux_info *ai = snew(game_aux_info); + ai->c = c; + ai->r = r; + ai->grid = snewn(cr * cr, digit); + memcpy(ai->grid, grid, cr * cr * sizeof(digit)); + *aux = ai; + } + /* * Now we have a solved grid, start removing things from it * while preserving solubility. */ symmetry_limit(params, &xlim, &ylim, params->symm); + recursing = FALSE; while (1) { int x, y, i, j; @@ -1442,6 +1458,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; @@ -1450,7 +1468,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; @@ -1459,15 +1482,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); @@ -1521,6 +1551,12 @@ static char *new_game_seed(game_params *params, random_state *rs) return seed; } +static void game_free_aux_info(game_aux_info *aux) +{ + sfree(aux->grid); + sfree(aux); +} + static char *validate_seed(game_params *params, char *seed) { int area = params->r * params->r * params->c * params->c; @@ -1562,7 +1598,7 @@ static game_state *new_game(game_params *params, char *seed) state->immutable = snewn(area, unsigned char); memset(state->immutable, FALSE, area); - state->completed = FALSE; + state->completed = state->cheated = FALSE; i = 0; while (*seed) { @@ -1604,6 +1640,7 @@ static game_state *dup_game(game_state *state) memcpy(ret->immutable, state->immutable, area); ret->completed = state->completed; + ret->cheated = state->cheated; return ret; } @@ -1615,6 +1652,104 @@ static void free_game(game_state *state) sfree(state); } +static game_state *solve_game(game_state *state, game_aux_info *ai, + char **error) +{ + game_state *ret; + int c = state->c, r = state->r, cr = c*r; + int rsolve_ret; + + ret = dup_game(state); + ret->completed = ret->cheated = TRUE; + + /* + * If we already have the solution in the aux_info, save + * ourselves some time. + */ + if (ai) { + + assert(c == ai->c); + assert(r == ai->r); + memcpy(ret->grid, ai->grid, cr * cr * sizeof(digit)); + + } else { + rsolve_ret = rsolve(c, r, ret->grid, NULL, 2); + + if (rsolve_ret != 1) { + free_game(ret); + if (rsolve_ret == 0) + *error = "No solution exists for this puzzle"; + else + *error = "Multiple solutions exist for this puzzle"; + return NULL; + } + } + + return ret; +} + +static char *grid_text_format(int c, int r, digit *grid) +{ + int cr = c*r; + int x, y; + int maxlen; + char *ret, *p; + + /* + * There are cr lines of digits, plus r-1 lines of block + * separators. Each line contains cr digits, cr-1 separating + * spaces, and c-1 two-character block separators. Thus, the + * total length of a line is 2*cr+2*c-3 (not counting the + * newline), and there are cr+r-1 of them. + */ + maxlen = (cr+r-1) * (2*cr+2*c-2); + ret = snewn(maxlen+1, char); + p = ret; + + for (y = 0; y < cr; y++) { + for (x = 0; x < cr; x++) { + int ch = grid[y * cr + x]; + if (ch == 0) + ch = ' '; + else if (ch <= 9) + ch = '0' + ch; + else + ch = 'a' + ch-10; + *p++ = ch; + if (x+1 < cr) { + *p++ = ' '; + if ((x+1) % r == 0) { + *p++ = '|'; + *p++ = ' '; + } + } + } + *p++ = '\n'; + if (y+1 < cr && (y+1) % c == 0) { + for (x = 0; x < cr; x++) { + *p++ = '-'; + if (x+1 < cr) { + *p++ = '-'; + if ((x+1) % r == 0) { + *p++ = '+'; + *p++ = '-'; + } + } + } + *p++ = '\n'; + } + } + + assert(p - ret == maxlen); + *p = '\0'; + return ret; +} + +static char *game_text_format(game_state *state) +{ + return grid_text_format(state->c, state->r, state->grid); +} + struct game_ui { /* * These are the coordinates of the currently highlighted @@ -1646,6 +1781,8 @@ static game_state *make_move(game_state *from, game_ui *ui, int x, int y, int tx, ty; game_state *ret; + button &= ~MOD_NUM_KEYPAD; /* we treat this the same as normal */ + tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1; ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1; @@ -1880,7 +2017,8 @@ static float game_anim_length(game_state *oldstate, game_state *newstate, static float game_flash_length(game_state *oldstate, game_state *newstate, int dir) { - if (!oldstate->completed && newstate->completed) + if (!oldstate->completed && newstate->completed && + !oldstate->cheated && !newstate->cheated) return FLASH_TIME; return 0.0F; } @@ -1895,21 +2033,23 @@ static int game_wants_statusbar(void) #endif const struct game thegame = { - "Solo", "games.solo", TRUE, + "Solo", "games.solo", default_params, game_fetch_preset, decode_params, encode_params, free_params, dup_params, - game_configure, - custom_params, + TRUE, game_configure, custom_params, validate_params, new_game_seed, + game_free_aux_info, validate_seed, new_game, dup_game, free_game, + TRUE, solve_game, + TRUE, game_text_format, new_ui, free_ui, make_move, @@ -2031,50 +2171,19 @@ int main(int argc, char **argv) else ret = DIFF_AMBIGUOUS; } - printf("difficulty rating: %s\n", - ret==DIFF_BLOCK ? "blockwise positional elimination only": - ret==DIFF_SIMPLE ? "row/column/number elimination required": - ret==DIFF_INTERSECT ? "intersectional analysis required": - ret==DIFF_SET ? "set elimination required": - ret==DIFF_RECURSIVE ? "guesswork and backtracking required": - ret==DIFF_AMBIGUOUS ? "multiple solutions exist": - ret==DIFF_IMPOSSIBLE ? "no solution exists": + printf("Difficulty rating: %s\n", + ret==DIFF_BLOCK ? "Trivial (blockwise positional elimination only)": + ret==DIFF_SIMPLE ? "Basic (row/column/number elimination required)": + ret==DIFF_INTERSECT ? "Intermediate (intersectional analysis required)": + ret==DIFF_SET ? "Advanced (set elimination required)": + ret==DIFF_RECURSIVE ? "Unreasonable (guesswork and backtracking required)": + ret==DIFF_AMBIGUOUS ? "Ambiguous (multiple solutions exist)": + ret==DIFF_IMPOSSIBLE ? "Impossible (no solution exists)": "INTERNAL ERROR: unrecognised difficulty code"); } } - for (y = 0; y < p->c * p->r; y++) { - for (x = 0; x < p->c * p->r; x++) { - int c = s->grid[y * p->c * p->r + x]; - if (c == 0) - c = ' '; - else if (c <= 9) - c = '0' + c; - else - c = 'a' + c-10; - printf("%c", c); - if (x+1 < p->c * p->r) { - if ((x+1) % p->c) - printf(" "); - else - printf(" | "); - } - } - printf("\n"); - if (y+1 < p->c * p->r && (y+1) % p->r == 0) { - for (x = 0; x < p->c * p->r; x++) { - printf("-"); - if (x+1 < p->c * p->r) { - if ((x+1) % p->c) - printf("-"); - else - printf("-+-"); - } - } - printf("\n"); - } - } - printf("\n"); + printf("%s\n", grid_text_format(p->c, p->r, s->grid)); return 0; }