X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/997065cf756f7f031d3ab0e7cf7a6a8d80d143bb..HEAD:/solo.c diff --git a/solo.c b/solo.c index a298d15..d9bf18d 100644 --- a/solo.c +++ b/solo.c @@ -582,7 +582,6 @@ static struct block_structure *dup_block_structure(struct block_structure *b) nb->blocks[i] = nb->blocks_data + i*nb->max_nr_squares; #ifdef STANDALONE_SOLVER - nb->blocknames = (char **)smalloc(b->c * b->r *(sizeof(char *)+80)); memcpy(nb->blocknames, b->blocknames, b->c * b->r *(sizeof(char *)+80)); { int i; @@ -831,6 +830,24 @@ static void solver_place(struct solver_usage *usage, int x, int y, int n) } } +#if defined STANDALONE_SOLVER && defined __GNUC__ +/* + * Forward-declare the functions taking printf-like format arguments + * with __attribute__((format)) so as to ensure the argument syntax + * gets debugged. + */ +struct solver_scratch; +static int solver_elim(struct solver_usage *usage, int *indices, + char *fmt, ...) __attribute__((format(printf,3,4))); +static int solver_intersect(struct solver_usage *usage, + int *indices1, int *indices2, char *fmt, ...) + __attribute__((format(printf,4,5))); +static int solver_set(struct solver_usage *usage, + struct solver_scratch *scratch, + int *indices, char *fmt, ...) + __attribute__((format(printf,4,5))); +#endif + static int solver_elim(struct solver_usage *usage, int *indices #ifdef STANDALONE_SOLVER , char *fmt, ... @@ -1456,7 +1473,7 @@ static int solver_killer_sums(struct solver_usage *usage, int b, } assert(nsquares > 0); - if (nsquares > 4) + if (nsquares < 2 || nsquares > 4) return 0; if (!cage_is_region) { @@ -1697,7 +1714,10 @@ static void solver(int cr, struct block_structure *blocks, usage->cube = snewn(cr*cr*cr, unsigned char); usage->grid = grid; /* write straight back to the input */ if (kgrid) { - int nclues = kblocks->nr_blocks; + int nclues; + + assert(kblocks); + nclues = kblocks->nr_blocks; /* * Allow for expansion of the killer regions, the absolute * limit is obviously one region per square. @@ -1753,9 +1773,16 @@ static void solver(int cr, struct block_structure *blocks, * Place all the clue numbers we are given. */ for (x = 0; x < cr; x++) - for (y = 0; y < cr; y++) - if (grid[y*cr+x]) + for (y = 0; y < cr; y++) { + int n = grid[y*cr+x]; + if (n) { + if (!cube(x,y,n)) { + diff = DIFF_IMPOSSIBLE; + goto got_result; + } solver_place(usage, x, y, grid[y*cr+x]); + } + } /* * Now loop over the grid repeatedly trying all permitted modes @@ -2021,7 +2048,7 @@ static void solver(int cr, struct block_structure *blocks, ); if (ret > 0) { changed = TRUE; - kdiff = max(kdiff, DIFF_KINTERSECT); + kdiff = max(kdiff, DIFF_KSUMS); } else if (ret < 0) { diff = DIFF_IMPOSSIBLE; goto got_result; @@ -2237,7 +2264,7 @@ static void solver(int cr, struct block_structure *blocks, #ifdef STANDALONE_SOLVER , "intersectional analysis," " %d in \\-diagonal vs block %s", - n, 1+x, usage->blocks->blocknames[b] + n, usage->blocks->blocknames[b] #endif ) || solver_intersect(usage, scratch->indexlist2, @@ -2245,7 +2272,7 @@ static void solver(int cr, struct block_structure *blocks, #ifdef STANDALONE_SOLVER , "intersectional analysis," " %d in block %s vs \\-diagonal", - n, usage->blocks->blocknames[b], 1+x + n, usage->blocks->blocknames[b] #endif )) { diff = max(diff, DIFF_INTERSECT); @@ -2270,7 +2297,7 @@ static void solver(int cr, struct block_structure *blocks, #ifdef STANDALONE_SOLVER , "intersectional analysis," " %d in /-diagonal vs block %s", - n, 1+x, usage->blocks->blocknames[b] + n, usage->blocks->blocknames[b] #endif ) || solver_intersect(usage, scratch->indexlist2, @@ -2278,7 +2305,7 @@ static void solver(int cr, struct block_structure *blocks, #ifdef STANDALONE_SOLVER , "intersectional analysis," " %d in block %s vs /-diagonal", - n, usage->blocks->blocknames[b], 1+x + n, usage->blocks->blocknames[b] #endif )) { diff = max(diff, DIFF_INTERSECT); @@ -2382,7 +2409,7 @@ static void solver(int cr, struct block_structure *blocks, scratch->indexlist[i*cr+n-1] = cubepos2(diag1(i), n); ret = solver_set(usage, scratch, scratch->indexlist #ifdef STANDALONE_SOLVER - , "set elimination, \\-diagonal" + , "set elimination, /-diagonal" #endif ); if (ret < 0) { @@ -2589,6 +2616,8 @@ static void solver(int cr, struct block_structure *blocks, "one solution"); #endif + sfree(usage->sq2region); + sfree(usage->regions); sfree(usage->cube); sfree(usage->row); sfree(usage->col); @@ -2598,6 +2627,7 @@ static void solver(int cr, struct block_structure *blocks, free_block_structure(usage->extra_cages); sfree(usage->extra_clues); } + if (usage->kclues) sfree(usage->kclues); sfree(usage); solver_free_scratch(scratch); @@ -3340,32 +3370,70 @@ static void merge_blocks(struct block_structure *b, int n1, int n2) b->nr_blocks = n1; } -static void merge_some_cages(struct block_structure *b, int cr, int area, +static int merge_some_cages(struct block_structure *b, int cr, int area, digit *grid, random_state *rs) { - do { - /* Find two candidates for merging. */ - int i, n1, n2; - int x = 1 + random_bits(rs, 20) % (cr - 2); - int y = 1 + random_bits(rs, 20) % (cr - 2); - int xy = y*cr + x; - int off = random_bits(rs, 1) == 0 ? -1 : 1; - int other = xy; - unsigned int digits_found; + /* + * Make a list of all the pairs of adjacent blocks. + */ + int i, j, k; + struct pair { + int b1, b2; + } *pairs; + int npairs; - if (random_bits(rs, 1) == 0) - other = xy + off; - else - other = xy + off * cr; - n1 = b->whichblock[xy]; - n2 = b->whichblock[other]; - if (n1 == n2) - continue; + pairs = snewn(b->nr_blocks * b->nr_blocks, struct pair); + npairs = 0; - assert(n1 >= 0 && n2 >= 0 && n1 < b->nr_blocks && n2 < b->nr_blocks); + for (i = 0; i < b->nr_blocks; i++) { + for (j = i+1; j < b->nr_blocks; j++) { - if (b->nr_squares[n1] + b->nr_squares[n2] > b->max_nr_squares) - continue; + /* + * Rule the merger out of consideration if it's + * obviously not viable. + */ + if (b->nr_squares[i] + b->nr_squares[j] > b->max_nr_squares) + continue; /* we couldn't merge these anyway */ + + /* + * See if these two blocks have a pair of squares + * adjacent to each other. + */ + for (k = 0; k < b->nr_squares[i]; k++) { + int xy = b->blocks[i][k]; + int y = xy / cr, x = xy % cr; + if ((y > 0 && b->whichblock[xy - cr] == j) || + (y+1 < cr && b->whichblock[xy + cr] == j) || + (x > 0 && b->whichblock[xy - 1] == j) || + (x+1 < cr && b->whichblock[xy + 1] == j)) { + /* + * Yes! Add this pair to our list. + */ + pairs[npairs].b1 = i; + pairs[npairs].b2 = j; + break; + } + } + } + } + + /* + * Now go through that list in random order until we find a pair + * of blocks we can merge. + */ + while (npairs > 0) { + int n1, n2; + unsigned int digits_found; + + /* + * Pick a random pair, and remove it from the list. + */ + i = random_upto(rs, npairs); + n1 = pairs[i].b1; + n2 = pairs[i].b2; + if (i != npairs-1) + pairs[i] = pairs[npairs-1]; + npairs--; /* Guarantee that the merged cage would still be a region. */ digits_found = 0; @@ -3377,9 +3445,16 @@ static void merge_some_cages(struct block_structure *b, int cr, int area, if (i != b->nr_squares[n2]) continue; + /* + * Got one! Do the merge. + */ merge_blocks(b, n1, n2); - break; - } while (1); + sfree(pairs); + return TRUE; + } + + sfree(pairs); + return FALSE; } static void compute_kclues(struct block_structure *cages, digit *kclues, @@ -3506,13 +3581,8 @@ static char *new_game_desc(game_params *params, random_state *rs, blocks = alloc_block_structure (c, r, area, cr, cr); - if (params->killer) { - kblocks = alloc_block_structure (c, r, area, cr, area); - kgrid = snewn(area, digit); - } else { - kblocks = NULL; - kgrid = NULL; - } + kblocks = NULL; + kgrid = (params->killer) ? snewn(area, digit) : NULL; #ifdef STANDALONE_SOLVER assert(!"This should never happen, so we don't need to create blocknames"); @@ -3542,6 +3612,7 @@ static char *new_game_desc(game_params *params, random_state *rs, make_blocks_from_whichblock(blocks); if (params->killer) { + if (kblocks) free_block_structure(kblocks); kblocks = gen_killer_cages(cr, rs, params->kdiff > DIFF_KSINGLE); } @@ -3593,7 +3664,8 @@ static char *new_game_desc(game_params *params, random_state *rs, free_block_structure(good_cages); ntries = 0; good_cages = dup_block_structure(kblocks); - merge_some_cages(kblocks, cr, area, grid2, rs); + if (!merge_some_cages(kblocks, cr, area, grid2, rs)) + break; } else if (dlev.diff > dlev.maxdiff || dlev.kdiff > dlev.maxkdiff) { /* * Give up after too many tries and either use the good one we @@ -3610,7 +3682,8 @@ static char *new_game_desc(game_params *params, random_state *rs, if (good_cages != NULL) { free_block_structure(kblocks); kblocks = dup_block_structure(good_cages); - merge_some_cages(kblocks, cr, area, grid2, rs); + if (!merge_some_cages(kblocks, cr, area, grid2, rs)) + break; } else { if (last_cages == NULL) break; @@ -3622,7 +3695,8 @@ static char *new_game_desc(game_params *params, random_state *rs, if (last_cages) free_block_structure(last_cages); last_cages = dup_block_structure(kblocks); - merge_some_cages(kblocks, cr, area, grid2, rs); + if (!merge_some_cages(kblocks, cr, area, grid2, rs)) + break; } } if (last_cages) @@ -3705,6 +3779,11 @@ static char *new_game_desc(game_params *params, random_state *rs, desc = encode_puzzle_desc(params, grid, blocks, kgrid, kblocks); sfree(grid); + free_block_structure(blocks); + if (params->killer) { + free_block_structure(kblocks); + sfree(kgrid); + } return desc; } @@ -4102,6 +4181,7 @@ static void free_game(game_state *state) sfree(state->immutable); sfree(state->pencil); sfree(state->grid); + if (state->kgrid) sfree(state->kgrid); sfree(state); } @@ -4431,7 +4511,7 @@ struct game_drawstate { int nregions, *entered_items; }; -static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, +static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate *ds, int x, int y, int button) { int cr = state->cr; @@ -4496,13 +4576,13 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, ((button >= '0' && button <= '9' && button - '0' <= cr) || (button >= 'a' && button <= 'z' && button - 'a' + 10 <= cr) || (button >= 'A' && button <= 'Z' && button - 'A' + 10 <= cr) || - button == CURSOR_SELECT2 || button == '\010' || button == '\177')) { + button == CURSOR_SELECT2 || button == '\b')) { int n = button - '0'; if (button >= 'A' && button <= 'Z') n = button - 'A' + 10; if (button >= 'a' && button <= 'z') n = button - 'a' + 10; - if (button == CURSOR_SELECT2 || button == '\010' || button == '\177') + if (button == CURSOR_SELECT2 || button == '\b') n = 0; /* @@ -5114,6 +5194,11 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, return 0.0F; } +static int game_status(game_state *state) +{ + return state->completed ? +1 : 0; +} + static int game_timing_state(game_state *state, game_ui *ui) { if (state->completed) @@ -5433,6 +5518,7 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, + game_status, TRUE, FALSE, game_print_size, game_print, FALSE, /* wants_statusbar */ FALSE, game_timing_state, @@ -5499,7 +5585,7 @@ int main(int argc, char **argv) dlev.diff==DIFF_IMPOSSIBLE ? "Impossible (no solution exists)": "INTERNAL ERROR: unrecognised difficulty code"); if (p->killer) - printf("Killer diffculty: %s\n", + printf("Killer difficulty: %s\n", dlev.kdiff==DIFF_KSINGLE ? "Trivial (single square cages only)": dlev.kdiff==DIFF_KMINMAX ? "Simple (maximum sum analysis required)": dlev.kdiff==DIFF_KSUMS ? "Intermediate (sum possibilities)":