*
* - 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 <stdio.h>
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
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;
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);
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);
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;
(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);
}
*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);
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;
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);
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 */;
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;
}
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);
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)
{
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;
}
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;
}
}
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
#endif
const struct game thegame = {
- "Dominosa", "games.dominosa",
+ "Dominosa", "games.dominosa", "dominosa",
default_params,
game_fetch_preset,
decode_params,
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 */
};
~ian / sgt-puzzles.git / blobdiff