X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=solo.c;h=a8a67e81445ea7240cfecc5ace84c8986ec9388e;hb=3ce69e84cad15844282d691fa03e711c5353c05e;hp=cbf1b81a4f0d56c068f98a6db3a896a35258657e;hpb=66efa90048752afec0de6861ed9b31aef3027efd;p=sgt-puzzles.git diff --git a/solo.c b/solo.c index cbf1b81..a8a67e8 100644 --- a/solo.c +++ b/solo.c @@ -289,7 +289,7 @@ static void free_params(game_params *params) sfree(params); } -static game_params *dup_params(game_params *params) +static game_params *dup_params(const game_params *params) { game_params *ret = snew(game_params); *ret = *params; /* structure copy */ @@ -399,7 +399,7 @@ static void decode_params(game_params *ret, char const *string) } } -static char *encode_params(game_params *params, int full) +static char *encode_params(const game_params *params, int full) { char str[80]; @@ -435,7 +435,7 @@ static char *encode_params(game_params *params, int full) return dupstr(str); } -static config_item *game_configure(game_params *params) +static config_item *game_configure(const game_params *params) { config_item *ret; char buf[80]; @@ -489,7 +489,7 @@ static config_item *game_configure(game_params *params) return ret; } -static game_params *custom_params(config_item *cfg) +static game_params *custom_params(const config_item *cfg) { game_params *ret = snew(game_params); @@ -508,7 +508,7 @@ static game_params *custom_params(config_item *cfg) return ret; } -static char *validate_params(game_params *params, int full) +static char *validate_params(const game_params *params, int full) { if (params->c < 2) return "Both dimensions must be at least 2"; @@ -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); @@ -2930,11 +2960,46 @@ static int gridgen(int cr, struct block_structure *blocks, * End of grid generator code. */ +static int check_killer_cage_sum(struct block_structure *kblocks, + digit *kgrid, digit *grid, int blk) +{ + /* + * Returns: -1 if the cage has any empty square; 0 if all squares + * are full but the sum is wrong; +1 if all squares are full and + * they have the right sum. + * + * Does not check uniqueness of numbers within the cage; that's + * done elsewhere (because in error highlighting it needs to be + * detected separately so as to flag the error in a visually + * different way). + */ + int n_squares = kblocks->nr_squares[blk]; + int sum = 0, clue = 0; + int i; + + for (i = 0; i < n_squares; i++) { + int xy = kblocks->blocks[blk][i]; + + if (grid[xy] == 0) + return -1; + sum += grid[xy]; + + if (kgrid[xy]) { + assert(clue == 0); + clue = kgrid[xy]; + } + } + + assert(clue != 0); + return sum == clue; +} + /* * 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, + digit *kgrid, int xtype, digit *grid) { unsigned char *used; int x, y, i, j, n; @@ -2987,6 +3052,32 @@ 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 we also know the clues for those cages (which we + * might not, when this function is called early in puzzle + * generation), we also check that they all have the right sum. + */ + 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; + } + + if (kgrid && check_killer_cage_sum(kblocks, kgrid, grid, i) != 1) { + sfree(used); + return FALSE; + } + } + } + /* * Check that each diagonal contains precisely one of everything. */ @@ -3014,7 +3105,8 @@ static int check_valid(int cr, struct block_structure *blocks, int xtype, return TRUE; } -static int symmetries(game_params *params, int x, int y, int *output, int s) +static int symmetries(const game_params *params, int x, int y, + int *output, int s) { int c = params->c, r = params->r, cr = c*r; int i = 0; @@ -3256,7 +3348,7 @@ static int blocks_encode_space(struct block_structure *blocks) return grid_encode_space(area); } -static char *encode_puzzle_desc(game_params *params, digit *grid, +static char *encode_puzzle_desc(const game_params *params, digit *grid, struct block_structure *blocks, digit *kgrid, struct block_structure *kblocks) @@ -3321,32 +3413,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 +3488,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, @@ -3454,7 +3591,7 @@ static struct block_structure *gen_killer_cages(int cr, random_state *rs, return b; } -static char *new_game_desc(game_params *params, random_state *rs, +static char *new_game_desc(const game_params *params, random_state *rs, char **aux, int interactive) { int c = params->c, r = params->r, cr = c*r; @@ -3487,13 +3624,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 +3655,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, NULL, params->xtype, grid)); /* * Save the solved grid in aux. @@ -3574,7 +3707,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 +3725,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 +3738,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,11 +3822,16 @@ 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; } -static char *spec_to_grid(char *desc, digit *grid, int area) +static const char *spec_to_grid(const char *desc, digit *grid, int area) { int i = 0; while (*desc && *desc != ',') { @@ -3720,9 +3861,9 @@ static char *spec_to_grid(char *desc, digit *grid, int area) * end of the block spec, and return an error string or NULL if everything * is OK. The DSF is stored in *PDSF. */ -static char *spec_to_dsf(char **pdesc, int **pdsf, int cr, int area) +static char *spec_to_dsf(const char **pdesc, int **pdsf, int cr, int area) { - char *desc = *pdesc; + const char *desc = *pdesc; int pos = 0; int *dsf; @@ -3741,7 +3882,7 @@ static char *spec_to_dsf(char **pdesc, int **pdsf, int cr, int area) } desc++; - adv = (c != 25); /* 'z' is a special case */ + adv = (c != 26); /* 'z' is a special case */ while (c-- > 0) { int p0, p1; @@ -3750,7 +3891,11 @@ static char *spec_to_dsf(char **pdesc, int **pdsf, int cr, int area) * Non-edge; merge the two dsf classes on either * side of it. */ - assert(pos < 2*cr*(cr-1)); + if (pos >= 2*cr*(cr-1)) { + sfree(dsf); + return "Too much data in block structure specification"; + } + if (pos < cr*(cr-1)) { int y = pos/(cr-1); int x = pos%(cr-1); @@ -3784,9 +3929,9 @@ static char *spec_to_dsf(char **pdesc, int **pdsf, int cr, int area) return NULL; } -static char *validate_grid_desc(char **pdesc, int range, int area) +static char *validate_grid_desc(const char **pdesc, int range, int area) { - char *desc = *pdesc; + const char *desc = *pdesc; int squares = 0; while (*desc && *desc != ',') { int n = *desc++; @@ -3814,7 +3959,7 @@ static char *validate_grid_desc(char **pdesc, int range, int area) return NULL; } -static char *validate_block_desc(char **pdesc, int cr, int area, +static char *validate_block_desc(const char **pdesc, int cr, int area, int min_nr_blocks, int max_nr_blocks, int min_nr_squares, int max_nr_squares) { @@ -3891,7 +4036,7 @@ static char *validate_block_desc(char **pdesc, int cr, int area, return NULL; } -static char *validate_desc(game_params *params, char *desc) +static char *validate_desc(const game_params *params, const char *desc) { int cr = params->c * params->r, area = cr*cr; char *err; @@ -3935,7 +4080,8 @@ static char *validate_desc(game_params *params, char *desc) return NULL; } -static game_state *new_game(midend *me, game_params *params, char *desc) +static game_state *new_game(midend *me, const game_params *params, + const char *desc) { game_state *state = snew(game_state); int c = params->c, r = params->r, cr = c*r, area = cr * cr; @@ -4037,7 +4183,7 @@ static game_state *new_game(midend *me, game_params *params, char *desc) return state; } -static game_state *dup_game(game_state *state) +static game_state *dup_game(const game_state *state) { game_state *ret = snew(game_state); int cr = state->cr, area = cr * cr; @@ -4083,11 +4229,12 @@ static void free_game(game_state *state) sfree(state->immutable); sfree(state->pencil); sfree(state->grid); + if (state->kgrid) sfree(state->kgrid); sfree(state); } -static char *solve_game(game_state *state, game_state *currstate, - char *ai, char **error) +static char *solve_game(const game_state *state, const game_state *currstate, + const char *ai, char **error) { int cr = state->cr; char *ret; @@ -4314,7 +4461,7 @@ static char *grid_text_format(int cr, struct block_structure *blocks, return ret; } -static int game_can_format_as_text_now(game_params *params) +static int game_can_format_as_text_now(const game_params *params) { /* * Formatting Killer puzzles as text is currently unsupported. I @@ -4327,7 +4474,7 @@ static int game_can_format_as_text_now(game_params *params) return TRUE; } -static char *game_text_format(game_state *state) +static char *game_text_format(const game_state *state) { assert(!state->kblocks); return grid_text_format(state->cr, state->blocks, state->xtype, @@ -4361,7 +4508,7 @@ struct game_ui { int hcursor; }; -static game_ui *new_ui(game_state *state) +static game_ui *new_ui(const game_state *state) { game_ui *ui = snew(game_ui); @@ -4376,17 +4523,17 @@ static void free_ui(game_ui *ui) sfree(ui); } -static char *encode_ui(game_ui *ui) +static char *encode_ui(const game_ui *ui) { return NULL; } -static void decode_ui(game_ui *ui, char *encoding) +static void decode_ui(game_ui *ui, const char *encoding) { } -static void game_changed_state(game_ui *ui, game_state *oldstate, - game_state *newstate) +static void game_changed_state(game_ui *ui, const game_state *oldstate, + const game_state *newstate) { int cr = newstate->cr; /* @@ -4409,11 +4556,12 @@ 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, - int x, int y, int button) +static char *interpret_move(const game_state *state, game_ui *ui, + const game_drawstate *ds, + int x, int y, int button) { int cr = state->cr; int tx, ty; @@ -4477,13 +4625,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; /* @@ -4508,17 +4656,20 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, return dupstr(buf); } + if (button == 'M' || button == 'm') + return dupstr("M"); + return NULL; } -static game_state *execute_move(game_state *from, char *move) +static game_state *execute_move(const game_state *from, const char *move) { int cr = from->cr; game_state *ret; int x, y, n; if (move[0] == 'S') { - char *p; + const char *p; ret = dup_game(from); ret->completed = ret->cheated = TRUE; @@ -4553,12 +4704,28 @@ 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->kgrid, + ret->xtype, ret->grid)) { ret->completed = TRUE; } } return ret; + } else if (move[0] == 'M') { + /* + * Fill in absolutely all pencil marks in unfilled squares, + * for those who like to play by the rigorous approach of + * starting off in that state and eliminating things. + */ + ret = dup_game(from); + for (y = 0; y < cr; y++) { + for (x = 0; x < cr; x++) { + if (!ret->grid[y*cr+x]) { + memset(ret->pencil + (y*cr+x)*cr, 1, cr); + } + } + } + return ret; } else return NULL; /* couldn't parse move string */ } @@ -4570,8 +4737,8 @@ static game_state *execute_move(game_state *from, char *move) #define SIZE(cr) ((cr) * TILE_SIZE + 2*BORDER + 1) #define GETTILESIZE(cr, w) ( (double)(w-1) / (double)(cr+1) ) -static void game_compute_size(game_params *params, int tilesize, - int *x, int *y) +static void game_compute_size(const game_params *params, int tilesize, + int *x, int *y) { /* Ick: fake up `ds->tilesize' for macro expansion purposes */ struct { int tilesize; } ads, *ds = &ads; @@ -4582,7 +4749,7 @@ static void game_compute_size(game_params *params, int tilesize, } static void game_set_size(drawing *dr, game_drawstate *ds, - game_params *params, int tilesize) + const game_params *params, int tilesize) { ds->tilesize = tilesize; } @@ -4629,7 +4796,7 @@ static float *game_colours(frontend *fe, int *ncolours) return ret; } -static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) +static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) { struct game_drawstate *ds = snew(struct game_drawstate); int cr = state->cr; @@ -4643,7 +4810,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; } @@ -4657,8 +4832,8 @@ static void game_free_drawstate(drawing *dr, game_drawstate *ds) sfree(ds); } -static void draw_number(drawing *dr, game_drawstate *ds, game_state *state, - int x, int y, int hl) +static void draw_number(drawing *dr, game_drawstate *ds, + const game_state *state, int x, int y, int hl) { int cr = state->cr; int tx, ty, tw, th; @@ -4940,9 +5115,10 @@ static void draw_number(drawing *dr, game_drawstate *ds, game_state *state, ds->hl[y*cr+x] = hl; } -static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, - game_state *state, int dir, game_ui *ui, - float animtime, float flashtime) +static void game_redraw(drawing *dr, game_drawstate *ds, + const game_state *oldstate, const game_state *state, + int dir, const game_ui *ui, + float animtime, float flashtime) { int cr = state->cr; int x, y; @@ -4970,21 +5146,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]++; } } } @@ -5008,34 +5199,24 @@ 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) { - int i, b = state->kblocks->whichblock[y*cr+x]; - int n_squares = state->kblocks->nr_squares[b]; - int sum = 0, clue = 0; - for (i = 0; i < n_squares; i++) { - int xy = state->kblocks->blocks[b][i]; - if (state->grid[xy] == 0) - break; - - sum += state->grid[xy]; - if (state->kgrid[xy]) { - assert(clue == 0); - clue = state->kgrid[xy]; - } - } - - if (i == n_squares) { - assert(clue != 0); - if (sum != clue) - highlight |= 32; - } + if (check_killer_cage_sum( + state->kblocks, state->kgrid, state->grid, + state->kblocks->whichblock[y*cr+x]) == 0) + highlight |= 32; } draw_number(dr, ds, state, x, y, highlight); @@ -5051,14 +5232,14 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, } } -static float game_anim_length(game_state *oldstate, game_state *newstate, - int dir, game_ui *ui) +static float game_anim_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) { return 0.0F; } -static float game_flash_length(game_state *oldstate, game_state *newstate, - int dir, game_ui *ui) +static float game_flash_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) { if (!oldstate->completed && newstate->completed && !oldstate->cheated && !newstate->cheated) @@ -5066,14 +5247,19 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, return 0.0F; } -static int game_timing_state(game_state *state, game_ui *ui) +static int game_status(const game_state *state) +{ + return state->completed ? +1 : 0; +} + +static int game_timing_state(const game_state *state, game_ui *ui) { if (state->completed) return FALSE; return TRUE; } -static void game_print_size(game_params *params, float *x, float *y) +static void game_print_size(const game_params *params, float *x, float *y) { int pw, ph; @@ -5100,7 +5286,7 @@ static void game_print_size(game_params *params, float *x, float *y) * the interior of the affected squares. */ static void outline_block_structure(drawing *dr, game_drawstate *ds, - game_state *state, + const game_state *state, struct block_structure *blocks, int ink, int inset) { @@ -5256,7 +5442,7 @@ static void outline_block_structure(drawing *dr, game_drawstate *ds, sfree(coords); } -static void game_print(drawing *dr, game_state *state, int tilesize) +static void game_print(drawing *dr, const game_state *state, int tilesize) { int cr = state->cr; int ink = print_mono_colour(dr, 0); @@ -5385,6 +5571,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, @@ -5451,7 +5638,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)":