X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/ad599e2b668fb8e62f166457254796fc84443d48..HEAD:/solo.c diff --git a/solo.c b/solo.c index b36eb66..d9bf18d 100644 --- a/solo.c +++ b/solo.c @@ -146,19 +146,19 @@ enum { #define MAX_2SUMS 5 #define MAX_3SUMS 8 #define MAX_4SUMS 12 -unsigned int sum_bits2[18][MAX_2SUMS]; -unsigned int sum_bits3[25][MAX_3SUMS]; -unsigned int sum_bits4[31][MAX_4SUMS]; +unsigned long sum_bits2[18][MAX_2SUMS]; +unsigned long sum_bits3[25][MAX_3SUMS]; +unsigned long sum_bits4[31][MAX_4SUMS]; -static int find_sum_bits(unsigned int *array, int idx, int value_left, +static int find_sum_bits(unsigned long *array, int idx, int value_left, int addends_left, int min_addend, - unsigned int bitmask_so_far) + unsigned long bitmask_so_far) { int i; assert(addends_left >= 2); for (i = min_addend; i < value_left; i++) { - unsigned int new_bitmask = bitmask_so_far | (1 << i); + unsigned long new_bitmask = bitmask_so_far | (1L << i); assert(bitmask_so_far != new_bitmask); if (addends_left == 2) { @@ -167,7 +167,7 @@ static int find_sum_bits(unsigned int *array, int idx, int value_left, break; if (j > 9) continue; - array[idx++] = new_bitmask | (1 << j); + array[idx++] = new_bitmask | (1L << j); } else idx = find_sum_bits(array, idx, value_left - i, addends_left - 1, i + 1, @@ -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, ... @@ -1448,7 +1465,7 @@ static int solver_killer_sums(struct solver_usage *usage, int b, int cr = usage->cr; int i, ret, max_sums; int nsquares = cages->nr_squares[b]; - unsigned int *sumbits, possible_addends; + unsigned long *sumbits, possible_addends; if (clue == 0) { assert(nsquares == 0); @@ -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) { @@ -1514,18 +1531,18 @@ static int solver_killer_sums(struct solver_usage *usage, int b, possible_addends = 0; for (i = 0; i < max_sums; i++) { int j; - unsigned int bits = sumbits[i]; + unsigned long bits = sumbits[i]; if (bits == 0) break; for (j = 0; j < nsquares; j++) { int n; - unsigned int square_bits = bits; + unsigned long square_bits = bits; int x = cages->blocks[b][j]; for (n = 1; n <= cr; n++) if (!cube2(x, n)) - square_bits &= ~(1 << n); + square_bits &= ~(1L << n); if (square_bits == 0) { break; } @@ -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); @@ -2933,8 +2963,8 @@ static int gridgen(int cr, struct block_structure *blocks, /* * Check whether a grid contains a valid complete puzzle. */ -static int check_valid(int cr, struct block_structure *blocks, int xtype, - digit *grid) +static int check_valid(int cr, struct block_structure *blocks, + struct block_structure *kblocks, int xtype, digit *grid) { unsigned char *used; int x, y, i, j, n; @@ -2988,6 +3018,25 @@ static int check_valid(int cr, struct block_structure *blocks, int xtype, } /* + * Check that each Killer cage, if any, contains at most one of + * everything. + */ + if (kblocks) { + for (i = 0; i < kblocks->nr_blocks; i++) { + memset(used, FALSE, cr); + for (j = 0; j < kblocks->nr_squares[i]; j++) + if (grid[kblocks->blocks[i][j]] > 0 && + grid[kblocks->blocks[i][j]] <= cr) { + if (used[grid[kblocks->blocks[i][j]]-1]) { + sfree(used); + return FALSE; + } + used[grid[kblocks->blocks[i][j]]-1] = TRUE; + } + } + } + + /* * Check that each diagonal contains precisely one of everything. */ if (xtype) { @@ -3321,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; @@ -3358,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, @@ -3487,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"); @@ -3523,12 +3612,13 @@ 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); } if (!gridgen(cr, blocks, kblocks, params->xtype, grid, rs, area*area)) continue; - assert(check_valid(cr, blocks, params->xtype, grid)); + assert(check_valid(cr, blocks, kblocks, params->xtype, grid)); /* * Save the solved grid in aux. @@ -3574,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 @@ -3591,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; @@ -3603,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) @@ -3686,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; } @@ -4083,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); } @@ -4409,10 +4508,10 @@ struct game_drawstate { unsigned char *pencil; unsigned char *hl; /* This is scratch space used within a single call to game_redraw. */ - int *entered_items; + 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; @@ -4477,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; /* @@ -4553,8 +4652,8 @@ static game_state *execute_move(game_state *from, char *move) * We've made a real change to the grid. Check to see * if the game has been completed. */ - if (!ret->completed && check_valid(cr, ret->blocks, ret->xtype, - ret->grid)) { + if (!ret->completed && check_valid(cr, ret->blocks, ret->kblocks, + ret->xtype, ret->grid)) { ret->completed = TRUE; } } @@ -4643,7 +4742,15 @@ static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) memset(ds->pencil, 0, cr*cr*cr); ds->hl = snewn(cr*cr, unsigned char); memset(ds->hl, 0, cr*cr); - ds->entered_items = snewn(cr*cr, int); + /* + * ds->entered_items needs one row of cr entries per entity in + * which digits may not be duplicated. That's one for each row, + * each column, each block, each diagonal, and each Killer cage. + */ + ds->nregions = cr*3 + 2; + if (state->kblocks) + ds->nregions += state->kblocks->nr_blocks; + ds->entered_items = snewn(cr * ds->nregions, int); ds->tilesize = 0; /* not decided yet */ return ds; } @@ -4723,10 +4830,37 @@ static void draw_number(drawing *dr, game_drawstate *ds, game_state *state, if (state->kblocks) { int t = GRIDEXTRA * 3; - int kl = cx - 1, kt = cy - 1, kr = cx + cw, kb = cy + ch; + int kcx, kcy, kcw, kch; + int kl, kt, kr, kb; int has_left = 0, has_right = 0, has_top = 0, has_bottom = 0; /* + * In non-jigsaw mode, the Killer cages are placed at a + * fixed offset from the outer edge of the cell dividing + * lines, so that they look right whether those lines are + * thick or thin. In jigsaw mode, however, doing this will + * sometimes cause the cage outlines in adjacent squares to + * fail to match up with each other, so we must offset a + * fixed amount from the _centre_ of the cell dividing + * lines. + */ + if (state->blocks->r == 1) { + kcx = tx; + kcy = ty; + kcw = tw; + kch = th; + } else { + kcx = cx; + kcy = cy; + kcw = cw; + kch = ch; + } + kl = kcx - 1; + kt = kcy - 1; + kr = kcx + kcw; + kb = kcy + kch; + + /* * First, draw the lines dividing this area from neighbouring * different areas. */ @@ -4759,20 +4893,20 @@ static void draw_number(drawing *dr, game_drawstate *ds, game_state *state, if (x+1 < cr && y > 0 && !has_right && !has_top && state->kblocks->whichblock[y*cr+x] != state->kblocks->whichblock[(y-1)*cr+x+1]) { - draw_line(dr, cx + cw - t, kt + t, cx + cw, kt + t, col_killer); - draw_line(dr, cx + cw - t, kt, cx + cw - t, kt + t, col_killer); + draw_line(dr, kcx + kcw - t, kt + t, kcx + kcw, kt + t, col_killer); + draw_line(dr, kcx + kcw - t, kt, kcx + kcw - t, kt + t, col_killer); } if (x > 0 && y+1 < cr && !has_left && !has_bottom && state->kblocks->whichblock[y*cr+x] != state->kblocks->whichblock[(y+1)*cr+x-1]) { - draw_line(dr, kl, cy + ch - t, kl + t, cy + ch - t, col_killer); - draw_line(dr, kl + t, cy + ch - t, kl + t, cy + ch, col_killer); + draw_line(dr, kl, kcy + kch - t, kl + t, kcy + kch - t, col_killer); + draw_line(dr, kl + t, kcy + kch - t, kl + t, kcy + kch, col_killer); } if (x+1 < cr && y+1 < cr && !has_right && !has_bottom && state->kblocks->whichblock[y*cr+x] != state->kblocks->whichblock[(y+1)*cr+x+1]) { - draw_line(dr, cx + cw - t, cy + ch - t, cx + cw - t, cy + ch, col_killer); - draw_line(dr, cx + cw - t, cy + ch - t, cx + cw, cy + ch - t, col_killer); + draw_line(dr, kcx + kcw - t, kcy + kch - t, kcx + kcw - t, kcy + kch, col_killer); + draw_line(dr, kcx + kcw - t, kcy + kch - t, kcx + kcw, kcy + kch - t, col_killer); } } @@ -4943,21 +5077,36 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, * This array is used to keep track of rows, columns and boxes * which contain a number more than once. */ - for (x = 0; x < cr * cr; x++) + for (x = 0; x < cr * ds->nregions; x++) ds->entered_items[x] = 0; for (x = 0; x < cr; x++) for (y = 0; y < cr; y++) { digit d = state->grid[y*cr+x]; if (d) { - int box = state->blocks->whichblock[y*cr+x]; - ds->entered_items[x*cr+d-1] |= ((ds->entered_items[x*cr+d-1] & 1) << 1) | 1; - ds->entered_items[y*cr+d-1] |= ((ds->entered_items[y*cr+d-1] & 4) << 1) | 4; - ds->entered_items[box*cr+d-1] |= ((ds->entered_items[box*cr+d-1] & 16) << 1) | 16; + int box, kbox; + + /* Rows */ + ds->entered_items[x*cr+d-1]++; + + /* Columns */ + ds->entered_items[(y+cr)*cr+d-1]++; + + /* Blocks */ + box = state->blocks->whichblock[y*cr+x]; + ds->entered_items[(box+2*cr)*cr+d-1]++; + + /* Diagonals */ if (ds->xtype) { if (ondiag0(y*cr+x)) - ds->entered_items[d-1] |= ((ds->entered_items[d-1] & 64) << 1) | 64; + ds->entered_items[(3*cr)*cr+d-1]++; if (ondiag1(y*cr+x)) - ds->entered_items[cr+d-1] |= ((ds->entered_items[cr+d-1] & 64) << 1) | 64; + ds->entered_items[(3*cr+1)*cr+d-1]++; + } + + /* Killer cages */ + if (state->kblocks) { + kbox = state->kblocks->whichblock[y*cr+x]; + ds->entered_items[(kbox+3*cr+2)*cr+d-1]++; } } } @@ -4981,11 +5130,17 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, /* Mark obvious errors (ie, numbers which occur more than once * in a single row, column, or box). */ - if (d && ((ds->entered_items[x*cr+d-1] & 2) || - (ds->entered_items[y*cr+d-1] & 8) || - (ds->entered_items[state->blocks->whichblock[y*cr+x]*cr+d-1] & 32) || - (ds->xtype && ((ondiag0(y*cr+x) && (ds->entered_items[d-1] & 128)) || - (ondiag1(y*cr+x) && (ds->entered_items[cr+d-1] & 128)))))) + if (d && (ds->entered_items[x*cr+d-1] > 1 || + ds->entered_items[(y+cr)*cr+d-1] > 1 || + ds->entered_items[(state->blocks->whichblock[y*cr+x] + +2*cr)*cr+d-1] > 1 || + (ds->xtype && ((ondiag0(y*cr+x) && + ds->entered_items[(3*cr)*cr+d-1] > 1) || + (ondiag1(y*cr+x) && + ds->entered_items[(3*cr+1)*cr+d-1]>1)))|| + (state->kblocks && + ds->entered_items[(state->kblocks->whichblock[y*cr+x] + +3*cr+2)*cr+d-1] > 1))) highlight |= 16; if (d && state->kblocks) { @@ -5039,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) @@ -5358,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, @@ -5424,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)":