ref: f1c8e4092cf1f31bbf5a3889bd47cbe1c5955f87
parent: 68363231f062192156799af7a153fc3ab3a0f5ed
author: Simon Tatham <anakin@pobox.com>
date: Tue Apr 2 14:42:01 EDT 2019
Dominosa: add a command-line solver. I've made the existing optional solver diagnostics appear as the verbose output of the solver program. They're not particularly legible at the moment, but they're better than nothing.
--- a/.gitignore
+++ b/.gitignore
@@ -4,6 +4,7 @@
/bridges
/cube
/dominosa
+/dominosasolver
/fifteen
/fifteensolver
/filling
--- a/dominosa.R
+++ b/dominosa.R
@@ -8,6 +8,9 @@
ALL += dominosa[COMBINED] DOMINOSA_EXTRA
+dominosasolver : [U] dominosa[STANDALONE_SOLVER] DOMINOSA_EXTRA STANDALONE
+dominosasolver : [C] dominosa[STANDALONE_SOLVER] DOMINOSA_EXTRA STANDALONE
+
!begin am gtk
GAMES += dominosa
!end
--- a/dominosa.c
+++ b/dominosa.c
@@ -229,6 +229,11 @@
* Solver.
*/
+#ifdef STANDALONE_SOLVER
+#define SOLVER_DIAGNOSTICS
+bool solver_diagnostics = false;
+#endif
+
static int find_overlaps(int w, int h, int placement, int *set)
{int x, y, n;
@@ -339,16 +344,17 @@
}
#ifdef SOLVER_DIAGNOSTICS
- printf("before solver:\n");- for (i = 0; i <= n; i++)
- for (j = 0; j <= i; j++) {- int k, m;
- m = 0;
- printf("%2d [%d %d]:", DINDEX(i, j), i, j);- for (k = heads[DINDEX(i,j)]; k >= 0; k = placements[k])
- printf(" %3d [%d,%d,%c]", k, k/2%w, k/2/w, k%2?'h':'v');- printf("\n");- }
+ if (solver_diagnostics) {+ printf("before solver:\n");+ for (i = 0; i <= n; i++)
+ for (j = 0; j <= i; j++) {+ int k;
+ printf("%2d [%d %d]:", DINDEX(i, j), i, j);+ for (k = heads[DINDEX(i,j)]; k >= 0; k = placements[k])
+ printf(" %3d [%d,%d,%c]", k, k/2%w, k/2/w, k%2?'h':'v');+ printf("\n");+ }
+ }
#endif
while (1) {@@ -412,8 +418,10 @@
p2 = (j & 1) ? p1 + 1 : p1 + w;
di = DINDEX(grid[p1], grid[p2]);
#ifdef SOLVER_DIAGNOSTICS
- printf("considering domino %d: ruling out placement %d"- " for %d\n", i, j, di);
+ if (solver_diagnostics) {+ printf("considering domino %d: ruling out placement %d"+ " for %d\n", i, j, di);
+ }
#endif
/*
@@ -493,8 +501,10 @@
if (nn > n) {done_something = true;
#ifdef SOLVER_DIAGNOSTICS
- printf("considering square %d,%d: reducing placements "- "of domino %d\n", x, y, adi);
+ if (solver_diagnostics) {+ printf("considering square %d,%d: reducing placements "+ "of domino %d\n", x, y, adi);
+ }
#endif
/*
* Set all other placements on the list to
@@ -521,16 +531,17 @@
}
#ifdef SOLVER_DIAGNOSTICS
- printf("after solver:\n");- for (i = 0; i <= n; i++)
- for (j = 0; j <= i; j++) {- int k, m;
- m = 0;
- printf("%2d [%d %d]:", DINDEX(i, j), i, j);- for (k = heads[DINDEX(i,j)]; k >= 0; k = placements[k])
- printf(" %3d [%d,%d,%c]", k, k/2%w, k/2/w, k%2?'h':'v');- printf("\n");- }
+ if (solver_diagnostics) {+ printf("after solver:\n");+ for (i = 0; i <= n; i++)
+ for (j = 0; j <= i; j++) {+ int k;
+ printf("%2d [%d %d]:", DINDEX(i, j), i, j);+ for (k = heads[DINDEX(i,j)]; k >= 0; k = placements[k])
+ printf(" %3d [%d,%d,%c]", k, k/2%w, k/2/w, k%2?'h':'v');+ printf("\n");+ }
+ }
#endif
ret = 1;
@@ -898,6 +909,58 @@
sfree(state);
}
+static int *solution_placements(int n, int *numbers, int *solver_retval)
+{+ int w = n+2, h = n+1, wh = w*h;
+ int i, retd;
+ int *placements = snewn(wh*2, int);
+
+ for (i = 0; i < wh*2; i++)
+ placements[i] = -3;
+
+ retd = solver(w, h, n, numbers, placements);
+
+ if (solver_retval)
+ *solver_retval = retd;
+ return placements;
+}
+
+static char *solution_move_string(int n, int *placements)
+{+ int w = n+2, h = n+1, wh = w*h;
+ char *ret;
+ int retlen, retsize;
+ int i, v;
+
+ /*
+ * First make a pass putting in edges for -1, then make a pass
+ * putting in dominoes for +1.
+ */
+ retsize = 256;
+ ret = snewn(retsize, char);
+ retlen = sprintf(ret, "S");
+
+ for (v = -1; v <= +1; v += 2)
+ for (i = 0; i < wh*2; i++)
+ if (placements[i] == v) {+ int p1 = i / 2;
+ int p2 = (i & 1) ? p1+1 : p1+w;
+ char buf[80];
+
+ int extra = sprintf(buf, ";%c%d,%d",
+ (int)(v==-1 ? 'E' : 'D'), p1, p2);
+
+ if (retlen + extra + 1 >= retsize) {+ retsize = retlen + extra + 256;
+ ret = sresize(ret, retsize, char);
+ }
+ strcpy(ret + retlen, buf);
+ retlen += extra;
+ }
+
+ return ret;
+}
+
static char *solve_game(const game_state *state, const game_state *currstate,
const char *aux, const char **error)
{@@ -905,7 +968,7 @@
int *placements;
char *ret;
int retlen, retsize;
- int i, v;
+ int i;
char buf[80];
int extra;
@@ -931,37 +994,8 @@
}
} else {-
- placements = snewn(wh*2, int);
- for (i = 0; i < wh*2; i++)
- placements[i] = -3;
- solver(w, h, n, state->numbers->numbers, placements);
-
- /*
- * First make a pass putting in edges for -1, then make a pass
- * putting in dominoes for +1.
- */
- retsize = 256;
- ret = snewn(retsize, char);
- retlen = sprintf(ret, "S");
-
- for (v = -1; v <= +1; v += 2)
- for (i = 0; i < wh*2; i++)
- if (placements[i] == v) {- int p1 = i / 2;
- int p2 = (i & 1) ? p1+1 : p1+w;
-
- extra = sprintf(buf, ";%c%d,%d",
- (int)(v==-1 ? 'E' : 'D'), p1, p2);
-
- if (retlen + extra + 1 >= retsize) {- retsize = retlen + extra + 256;
- ret = sresize(ret, retsize, char);
- }
- strcpy(ret + retlen, buf);
- retlen += extra;
- }
-
+ placements = solution_placements(n, state->numbers->numbers, NULL);
+ ret = solution_move_string(n, placements);
sfree(placements);
}
@@ -1769,6 +1803,75 @@
false, game_timing_state,
0, /* flags */
};
+
+#ifdef STANDALONE_SOLVER
+
+int main(int argc, char **argv)
+{+ game_params *p;
+ game_state *s, *s2;
+ char *id = NULL, *desc;
+ const char *err;
+ bool diagnostics = false;
+ int retd;
+
+ while (--argc > 0) {+ char *p = *++argv;
+ if (!strcmp(p, "-v")) {+ diagnostics = true;
+ } else if (*p == '-') {+ fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
+ return 1;
+ } else {+ id = p;
+ }
+ }
+
+ if (!id) {+ fprintf(stderr, "usage: %s [-v] <game_id>\n", argv[0]);
+ return 1;
+ }
+
+ desc = strchr(id, ':');
+ if (!desc) {+ fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
+ return 1;
+ }
+ *desc++ = '\0';
+
+ p = default_params();
+ decode_params(p, id);
+ err = validate_desc(p, desc);
+ if (err) {+ fprintf(stderr, "%s: %s\n", argv[0], err);
+ return 1;
+ }
+ s = new_game(NULL, p, desc);
+
+ solver_diagnostics = diagnostics;
+ int *placements = solution_placements(p->n, s->numbers->numbers, &retd);
+ if (retd == 0) {+ printf("Puzzle is inconsistent\n");+ } else {+ char *move, *text;
+ move = solution_move_string(p->n, placements);
+ s2 = execute_move(s, move);
+ text = game_text_format(s2);
+ sfree(move);
+ fputs(text, stdout);
+ sfree(text);
+ free_game(s2);
+ if (retd > 1)
+ printf("Could not deduce a unique solution\n");+ }
+ sfree(placements);
+ free_game(s);
+ free_params(p);
+
+ return 0;
+}
+
+#endif
/* vim: set shiftwidth=4 :set textwidth=80: */