X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/6c04c334a27151e4bf1dbd4421eb9b347e4b3842..88ceda407be72bd6cae67c480ceaa0a77f0f0b55:/dominosa.c diff --git a/dominosa.c b/dominosa.c index 766ccfe..0264675 100644 --- a/dominosa.c +++ b/dominosa.c @@ -9,8 +9,34 @@ * * - improve solver so as to use more interesting forms of * deduction - * * odd area + * + * * rule out a domino placement if it would divide an unfilled + * region such that at least one resulting region had an odd + * area + * + use b.f.s. to determine the area of an unfilled region + * + a square is unfilled iff it has at least two possible + * placements, and two adjacent unfilled squares are part + * of the same region iff the domino placement joining + * them is possible + * * * perhaps set analysis + * + look at all unclaimed squares containing a given number + * + for each one, find the set of possible numbers that it + * can connect to (i.e. each neighbouring tile such that + * the placement between it and that neighbour has not yet + * been ruled out) + * + now proceed similarly to Solo set analysis: try to find + * a subset of the squares such that the union of their + * possible numbers is the same size as the subset. If so, + * rule out those possible numbers for all other squares. + * * important wrinkle: the double dominoes complicate + * matters. Connecting a number to itself uses up _two_ + * of the unclaimed squares containing a number. Thus, + * when finding the initial subset we must never + * include two adjacent squares; and also, when ruling + * things out after finding the subset, we must be + * careful that we don't rule out precisely the domino + * placement that was _included_ in our set! */ #include @@ -530,6 +556,35 @@ static char *new_game_desc(game_params *params, random_state *rs, grid2 = snewn(wh, int); list = snewn(2*wh, int); + /* + * I haven't been able to think of any particularly clever + * techniques for generating instances of Dominosa with a + * unique solution. Many of the deductions used in this puzzle + * are based on information involving half the grid at a time + * (`of all the 6s, exactly one is next to a 3'), so a strategy + * of partially solving the grid and then perturbing the place + * where the solver got stuck seems particularly likely to + * accidentally destroy the information which the solver had + * used in getting that far. (Contrast with, say, Mines, in + * which most deductions are local so this is an excellent + * strategy.) + * + * Therefore I resort to the basest of brute force methods: + * generate a random grid, see if it's solvable, throw it away + * and try again if not. My only concession to sophistication + * and cleverness is to at least _try_ not to generate obvious + * 2x2 ambiguous sections (see comment below in the domino- + * flipping section). + * + * During tests performed on 2005-07-15, I found that the brute + * force approach without that tweak had to throw away about 87 + * grids on average (at the default n=6) before finding a + * unique one, or a staggering 379 at n=9; good job the + * generator and solver are fast! When I added the + * ambiguous-section avoidance, those numbers came down to 19 + * and 26 respectively, which is a lot more sensible. + */ + do { /* * To begin with, set grid[i] = i for all i to indicate @@ -783,7 +838,61 @@ static char *new_game_desc(game_params *params, random_state *rs, for (i = 0; i < wh; i++) if (grid[i] > i) { /* Optionally flip the domino round. */ - int flip = random_upto(rs, 2); + int flip = -1; + + if (params->unique) { + int t1, t2; + /* + * If we're after a unique solution, we can do + * something here to improve the chances. If + * we're placing a domino so that it forms a + * 2x2 rectangle with one we've already placed, + * and if that domino and this one share a + * number, we can try not to put them so that + * the identical numbers are diagonally + * separated, because that automatically causes + * non-uniqueness: + * + * +---+ +-+-+ + * |2 3| |2|3| + * +---+ -> | | | + * |4 2| |4|2| + * +---+ +-+-+ + */ + t1 = i; + t2 = grid[i]; + if (t2 == t1 + w) { /* this domino is vertical */ + if (t1 % w > 0 &&/* and not on the left hand edge */ + grid[t1-1] == t2-1 &&/* alongside one to left */ + (grid2[t1-1] == list[j] || /* and has a number */ + grid2[t1-1] == list[j+1] || /* in common */ + grid2[t2-1] == list[j] || + grid2[t2-1] == list[j+1])) { + if (grid2[t1-1] == list[j] || + grid2[t2-1] == list[j+1]) + flip = 0; + else + flip = 1; + } + } else { /* this domino is horizontal */ + if (t1 / w > 0 &&/* and not on the top edge */ + grid[t1-w] == t2-w &&/* alongside one above */ + (grid2[t1-w] == list[j] || /* and has a number */ + grid2[t1-w] == list[j+1] || /* in common */ + grid2[t2-w] == list[j] || + grid2[t2-w] == list[j+1])) { + if (grid2[t1-w] == list[j] || + grid2[t2-w] == list[j+1]) + flip = 0; + else + flip = 1; + } + } + } + + if (flip < 0) + flip = random_upto(rs, 2); + grid2[i] = list[j + flip]; grid2[grid[i]] = list[j + 1 - flip]; j += 2; @@ -918,7 +1027,7 @@ static char *validate_desc(game_params *params, char *desc) return ret; } -static game_state *new_game(midend_data *me, game_params *params, char *desc) +static game_state *new_game(midend *me, game_params *params, char *desc) { int n = params->n, w = n+2, h = n+1, wh = w*h; game_state *state = snew(game_state); @@ -984,6 +1093,7 @@ static game_state *dup_game(game_state *state) static void free_game(game_state *state) { sfree(state->grid); + sfree(state->edges); if (--state->numbers->refcount <= 0) { sfree(state->numbers->numbers); sfree(state->numbers); @@ -1045,7 +1155,7 @@ static char *solve_game(game_state *state, game_state *currstate, int p2 = (i & 1) ? p1+1 : p1+w; extra = sprintf(buf, ";%c%d,%d", - v==-1 ? 'E' : 'D', p1, p2); + (int)(v==-1 ? 'E' : 'D'), p1, p2); if (retlen + extra + 1 >= retsize) { retsize = retlen + extra + 256; @@ -1148,7 +1258,7 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, (state->grid[d1] != d1 || state->grid[d2] != d2)) return NULL; - sprintf(buf, "%c%d,%d", button == RIGHT_BUTTON ? 'E' : 'D', d1, d2); + sprintf(buf, "%c%d,%d", (int)(button == RIGHT_BUTTON ? 'E' : 'D'), d1, d2); return dupstr(buf); } @@ -1323,13 +1433,13 @@ static void game_compute_size(game_params *params, int tilesize, *y = h * TILESIZE + 2*BORDER; } -static void game_set_size(game_drawstate *ds, game_params *params, - int tilesize) +static void game_set_size(drawing *dr, game_drawstate *ds, + game_params *params, int tilesize) { ds->tilesize = tilesize; } -static float *game_colours(frontend *fe, game_state *state, int *ncolours) +static float *game_colours(frontend *fe, int *ncolours) { float *ret = snewn(3 * NCOLOURS, float); @@ -1359,7 +1469,7 @@ static float *game_colours(frontend *fe, game_state *state, int *ncolours) return ret; } -static game_drawstate *game_new_drawstate(game_state *state) +static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) { struct game_drawstate *ds = snew(struct game_drawstate); int i; @@ -1375,7 +1485,7 @@ static game_drawstate *game_new_drawstate(game_state *state) return ds; } -static void game_free_drawstate(game_drawstate *ds) +static void game_free_drawstate(drawing *dr, game_drawstate *ds) { sfree(ds->visible); sfree(ds); @@ -1390,7 +1500,7 @@ enum { TYPE_MASK = 0x0F }; -static void draw_tile(frontend *fe, game_drawstate *ds, game_state *state, +static void draw_tile(drawing *dr, game_drawstate *ds, game_state *state, int x, int y, int type) { int w = state->w /*, h = state->h */; @@ -1399,7 +1509,7 @@ static void draw_tile(frontend *fe, game_drawstate *ds, game_state *state, char str[80]; int flags; - draw_rect(fe, cx, cy, TILESIZE, TILESIZE, COL_BACKGROUND); + draw_rect(dr, cx, cy, TILESIZE, TILESIZE, COL_BACKGROUND); flags = type &~ TYPE_MASK; type &= TYPE_MASK; @@ -1428,16 +1538,16 @@ static void draw_tile(frontend *fe, game_drawstate *ds, game_state *state, } if (type == TYPE_L || type == TYPE_T) - draw_circle(fe, cx+DOMINO_COFFSET, cy+DOMINO_COFFSET, + draw_circle(dr, cx+DOMINO_COFFSET, cy+DOMINO_COFFSET, DOMINO_RADIUS, bg, bg); if (type == TYPE_R || type == TYPE_T) - draw_circle(fe, cx+TILESIZE-1-DOMINO_COFFSET, cy+DOMINO_COFFSET, + draw_circle(dr, cx+TILESIZE-1-DOMINO_COFFSET, cy+DOMINO_COFFSET, DOMINO_RADIUS, bg, bg); if (type == TYPE_L || type == TYPE_B) - draw_circle(fe, cx+DOMINO_COFFSET, cy+TILESIZE-1-DOMINO_COFFSET, + draw_circle(dr, cx+DOMINO_COFFSET, cy+TILESIZE-1-DOMINO_COFFSET, DOMINO_RADIUS, bg, bg); if (type == TYPE_R || type == TYPE_B) - draw_circle(fe, cx+TILESIZE-1-DOMINO_COFFSET, + draw_circle(dr, cx+TILESIZE-1-DOMINO_COFFSET, cy+TILESIZE-1-DOMINO_COFFSET, DOMINO_RADIUS, bg, bg); @@ -1449,40 +1559,40 @@ static void draw_tile(frontend *fe, game_drawstate *ds, game_state *state, x2 = cx + TILESIZE-1 - (i ? DOMINO_GUTTER : DOMINO_COFFSET); y2 = cy + TILESIZE-1 - (i ? DOMINO_COFFSET : DOMINO_GUTTER); if (type == TYPE_L) - x2 = cx + TILESIZE-1; + x2 = cx + TILESIZE + TILESIZE/16; else if (type == TYPE_R) - x1 = cx; + x1 = cx - TILESIZE/16; else if (type == TYPE_T) - y2 = cy + TILESIZE-1; + y2 = cy + TILESIZE + TILESIZE/16; else if (type == TYPE_B) - y1 = cy; + y1 = cy - TILESIZE/16; - draw_rect(fe, x1, y1, x2-x1+1, y2-y1+1, bg); + draw_rect(dr, x1, y1, x2-x1+1, y2-y1+1, bg); } } else { if (flags & EDGE_T) - draw_rect(fe, cx+DOMINO_GUTTER, cy, + draw_rect(dr, cx+DOMINO_GUTTER, cy, TILESIZE-2*DOMINO_GUTTER, 1, COL_EDGE); if (flags & EDGE_B) - draw_rect(fe, cx+DOMINO_GUTTER, cy+TILESIZE-1, + draw_rect(dr, cx+DOMINO_GUTTER, cy+TILESIZE-1, TILESIZE-2*DOMINO_GUTTER, 1, COL_EDGE); if (flags & EDGE_L) - draw_rect(fe, cx, cy+DOMINO_GUTTER, + draw_rect(dr, cx, cy+DOMINO_GUTTER, 1, TILESIZE-2*DOMINO_GUTTER, COL_EDGE); if (flags & EDGE_R) - draw_rect(fe, cx+TILESIZE-1, cy+DOMINO_GUTTER, + draw_rect(dr, cx+TILESIZE-1, cy+DOMINO_GUTTER, 1, TILESIZE-2*DOMINO_GUTTER, COL_EDGE); nc = COL_TEXT; } sprintf(str, "%d", state->numbers->numbers[y*w+x]); - draw_text(fe, cx+TILESIZE/2, cy+TILESIZE/2, FONT_VARIABLE, TILESIZE/2, + draw_text(dr, cx+TILESIZE/2, cy+TILESIZE/2, FONT_VARIABLE, TILESIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE, nc, str); - draw_update(fe, cx, cy, TILESIZE, TILESIZE); + draw_update(dr, cx, cy, TILESIZE, TILESIZE); } -static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, +static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, game_state *state, int dir, game_ui *ui, float animtime, float flashtime) { @@ -1493,8 +1603,8 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, if (!ds->started) { int pw, ph; game_compute_size(&state->params, TILESIZE, &pw, &ph); - draw_rect(fe, 0, 0, pw, ph, COL_BACKGROUND); - draw_update(fe, 0, 0, pw, ph); + draw_rect(dr, 0, 0, pw, ph, COL_BACKGROUND); + draw_update(dr, 0, 0, pw, ph); ds->started = TRUE; } @@ -1549,7 +1659,7 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, c |= 0x40; /* we're flashing */ if (ds->visible[n] != c) { - draw_tile(fe, ds, state, x, y, c); + draw_tile(dr, ds, state, x, y, c); ds->visible[n] = c; } } @@ -1572,14 +1682,57 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, return 0.0F; } -static int game_wants_statusbar(void) +static int game_timing_state(game_state *state, game_ui *ui) { - return FALSE; + return TRUE; } -static int game_timing_state(game_state *state, game_ui *ui) +static void game_print_size(game_params *params, float *x, float *y) { - return TRUE; + int pw, ph; + + /* + * I'll use 6mm squares by default. + */ + game_compute_size(params, 600, &pw, &ph); + *x = pw / 100.0; + *y = ph / 100.0; +} + +static void game_print(drawing *dr, game_state *state, int tilesize) +{ + int w = state->w, h = state->h; + int c, x, y; + + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + game_drawstate ads, *ds = &ads; + game_set_size(dr, ds, NULL, tilesize); + + c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND); + c = print_mono_colour(dr, 0); assert(c == COL_TEXT); + c = print_mono_colour(dr, 0); assert(c == COL_DOMINO); + c = print_mono_colour(dr, 0); assert(c == COL_DOMINOCLASH); + c = print_mono_colour(dr, 1); assert(c == COL_DOMINOTEXT); + c = print_mono_colour(dr, 0); assert(c == COL_EDGE); + + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + int n = y*w+x; + unsigned long c; + + if (state->grid[n] == n-1) + c = TYPE_R; + else if (state->grid[n] == n+1) + c = TYPE_L; + else if (state->grid[n] == n-w) + c = TYPE_B; + else if (state->grid[n] == n+w) + c = TYPE_T; + else + c = TYPE_BLANK; + + draw_tile(dr, ds, state, x, y, c); + } } #ifdef COMBINED @@ -1587,7 +1740,7 @@ static int game_timing_state(game_state *state, game_ui *ui) #endif const struct game thegame = { - "Dominosa", "games.dominosa", + "Dominosa", "games.dominosa", "dominosa", default_params, game_fetch_preset, decode_params, @@ -1617,7 +1770,8 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, - game_wants_statusbar, + TRUE, FALSE, game_print_size, game_print, + FALSE, /* wants_statusbar */ FALSE, game_timing_state, - 0, /* mouse_priorities */ + 0, /* flags */ };