#define PREFERRED_TILE_SIZE 32
#define TILE_SIZE (ds->tilesize)
-#define LINEWIDTH TILE_SIZE / 16
+#define LINEWIDTH (ds->linewidth)
#define BORDER (TILE_SIZE / 2)
#define FLASH_TIME 0.5F
#define OPP(dir) (dir == LINE_UNKNOWN ? LINE_UNKNOWN : \
dir == LINE_YES ? LINE_NO : LINE_YES)
+#define BIT_SET(field, bit) ((field) & (1<<(bit)))
+
+#define SET_BIT(field, bit) (BIT_SET(field, bit) ? FALSE : \
+ ((field) |= (1<<(bit)), TRUE))
+
+#define CLEAR_BIT(field, bit) (BIT_SET(field, bit) ? \
+ ((field) &= ~(1<<(bit)), TRUE) : FALSE)
+
static char *game_text_format(game_state *state);
enum {
#define ENCODE(upper,title,lower) #lower
#define CONFIG(upper,title,lower) ":" #title
enum { DIFFLIST(ENUM) DIFFCOUNT };
-static char const *const loopy_diffnames[] = { DIFFLIST(TITLE) };
+/* static char const *const loopy_diffnames[] = { DIFFLIST(TITLE) }; */
static char const loopy_diffchars[] = DIFFLIST(ENCODE);
#define DIFFCONFIG DIFFLIST(CONFIG)
typedef struct solver_state {
game_state *state;
- /* XXX dot_atleastone[i,j, dline] is equivalent to */
- /* dot_atmostone[i,j,OPP_DLINE(dline)] */
char *dot_atleastone;
char *dot_atmostone;
/* char *dline_identical; */
int recursion_remaining;
enum solver_status solver_status;
+ /* NB looplen is the number of dots that are joined together at a point, ie a
+ * looplen of 1 means there are no lines to a particular dot */
int *dotdsf, *looplen;
} solver_state;
#endif
ret->recursion_remaining = state->recursion_depth;
- ret->solver_status = SOLVER_INCOMPLETE; /* XXX This may be a lie */
+ ret->solver_status = SOLVER_INCOMPLETE;
ret->dotdsf = snewn(DOT_COUNT(state), int);
ret->looplen = snewn(DOT_COUNT(state), int);
* Merge two dots due to the existence of an edge between them.
* Updates the dsf tracking equivalence classes, and keeps track of
* the length of path each dot is currently a part of.
+ * Returns TRUE if the dots were already linked, ie if they are part of a
+ * closed loop, and false otherwise.
*/
-static void merge_dots(solver_state *sstate, int x1, int y1, int x2, int y2)
+static int merge_dots(solver_state *sstate, int x1, int y1, int x2, int y2)
{
int i, j, len;
i = dsf_canonify(sstate->dotdsf, i);
j = dsf_canonify(sstate->dotdsf, j);
- if (i != j) {
+ if (i == j) {
+ return TRUE;
+ } else {
len = sstate->looplen[i] + sstate->looplen[j];
dsf_merge(sstate->dotdsf, i, j);
i = dsf_canonify(sstate->dotdsf, i);
sstate->looplen[i] = len;
+ return FALSE;
}
}
return n;
}
-/* Set all lines bordering a dot of type old_type to type new_type */
-static void dot_setall(game_state *state, int i, int j,
+/* Set all lines bordering a dot of type old_type to type new_type
+ * Return value tells caller whether this function actually did anything */
+static int dot_setall(game_state *state, int i, int j,
char old_type, char new_type)
{
-/* printf("dot_setall([%d,%d], %d, %d)\n", i, j, old_type, new_type); */
- if (i > 0 && LEFTOF_DOT(state, i, j) == old_type)
+ int retval = FALSE;
+ if (old_type == new_type)
+ return FALSE;
+
+ if (i > 0 && LEFTOF_DOT(state, i, j) == old_type) {
LV_LEFTOF_DOT(state, i, j) = new_type;
- if (i < state->w && RIGHTOF_DOT(state, i, j) == old_type)
+ retval = TRUE;
+ }
+
+ if (i < state->w && RIGHTOF_DOT(state, i, j) == old_type) {
LV_RIGHTOF_DOT(state, i, j) = new_type;
- if (j > 0 && ABOVE_DOT(state, i, j) == old_type)
+ retval = TRUE;
+ }
+
+ if (j > 0 && ABOVE_DOT(state, i, j) == old_type) {
LV_ABOVE_DOT(state, i, j) = new_type;
- if (j < state->h && BELOW_DOT(state, i, j) == old_type)
+ retval = TRUE;
+ }
+
+ if (j < state->h && BELOW_DOT(state, i, j) == old_type) {
LV_BELOW_DOT(state, i, j) = new_type;
+ retval = TRUE;
+ }
+
+ return retval;
}
/* Set all lines bordering a square of type old_type to type new_type */
static void square_setall(game_state *state, int i, int j,
{ "7x7 Easy", { 7, 7, DIFF_EASY, 0 } },
{ "7x7 Normal", { 7, 7, DIFF_NORMAL, 0 } },
{ "10x10 Easy", { 10, 10, DIFF_EASY, 0 } },
-#ifndef SLOW_SYSTEM
{ "10x10 Normal", { 10, 10, DIFF_NORMAL, 0 } },
+#ifndef SLOW_SYSTEM
{ "15x15 Easy", { 15, 15, DIFF_EASY, 0 } },
- { "30x20 Easy", { 30, 20, DIFF_EASY, 0 } }
+ { "15x15 Normal", { 15, 15, DIFF_NORMAL, 0 } },
+ { "30x20 Easy", { 30, 20, DIFF_EASY, 0 } },
+ { "30x20 Normal", { 30, 20, DIFF_NORMAL, 0 } }
#endif
};
enum { LOOP_NONE=0, LOOP_SOLN, LOOP_NOT_SOLN };
-/* Starting at dot [i,j] moves around 'state' removing lines until it's clear
- * whether or not the starting dot was on a loop. Returns boolean specifying
- * whether a loop was found. loop_status calls this and assumes that if state
- * has any lines set, this function will always remove at least one. */
-static int destructively_find_loop(game_state *state)
-{
- int a, b, i, j, new_i, new_j, n;
- char *lp;
-
- lp = (char *)memchr(state->hl, LINE_YES, HL_COUNT(state));
- if (!lp) {
- /* We know we're going to return false but we have to fulfil our
- * contract */
- lp = (char *)memchr(state->vl, LINE_YES, VL_COUNT(state));
- if (lp)
- *lp = LINE_NO;
-
- return FALSE;
- }
-
- n = lp - state->hl;
-
- i = n % state->w;
- j = n / state->w;
-
- assert(i + j * state->w == n); /* because I'm feeling stupid */
- /* Save start position */
- a = i;
- b = j;
-
- /* Delete one line from the potential loop */
- if (LEFTOF_DOT(state, i, j) == LINE_YES) {
- LV_LEFTOF_DOT(state, i, j) = LINE_NO;
- i--;
- } else if (ABOVE_DOT(state, i, j) == LINE_YES) {
- LV_ABOVE_DOT(state, i, j) = LINE_NO;
- j--;
- } else if (RIGHTOF_DOT(state, i, j) == LINE_YES) {
- LV_RIGHTOF_DOT(state, i, j) = LINE_NO;
- i++;
- } else if (BELOW_DOT(state, i, j) == LINE_YES) {
- LV_BELOW_DOT(state, i, j) = LINE_NO;
- j++;
- } else {
- return FALSE;
- }
-
- do {
- /* From the current position of [i,j] there needs to be exactly one
- * line */
- new_i = new_j = -1;
-
-#define HANDLE_DIR(dir_dot, x, y) \
- if (dir_dot(state, i, j) == LINE_YES) { \
- if (new_i != -1 || new_j != -1) \
- return FALSE; \
- new_i = (i)+(x); \
- new_j = (j)+(y); \
- LV_##dir_dot(state, i, j) = LINE_NO; \
- }
- HANDLE_DIR(ABOVE_DOT, 0, -1);
- HANDLE_DIR(BELOW_DOT, 0, +1);
- HANDLE_DIR(LEFTOF_DOT, -1, 0);
- HANDLE_DIR(RIGHTOF_DOT, +1, 0);
-#undef HANDLE_DIR
- if (new_i == -1 || new_j == -1) {
- return FALSE;
- }
-
- i = new_i;
- j = new_j;
- } while (i != a || j != b);
-
- return TRUE;
-}
-
-static int loop_status(game_state *state)
-{
- int i, j, n;
- game_state *tmpstate;
- int loop_found = FALSE, non_loop_found = FALSE, any_lines_found = FALSE;
-
-#define BAD_LOOP_FOUND \
- do { free_game(tmpstate); return LOOP_NOT_SOLN; } while(0)
-
- /* Repeatedly look for loops until we either run out of lines to consider
- * or discover for sure that the board fails on the grounds of having no
- * loop */
- tmpstate = dup_game(state);
-
- while (TRUE) {
- if (!memchr(tmpstate->hl, LINE_YES, HL_COUNT(tmpstate)) &&
- !memchr(tmpstate->vl, LINE_YES, VL_COUNT(tmpstate))) {
- break;
- }
- any_lines_found = TRUE;
-
- if (loop_found)
- BAD_LOOP_FOUND;
- if (destructively_find_loop(tmpstate)) {
- loop_found = TRUE;
- if (non_loop_found)
- BAD_LOOP_FOUND;
- } else {
- non_loop_found = TRUE;
- }
- }
-
- free_game(tmpstate);
-
- if (!any_lines_found)
- return LOOP_NONE;
-
- if (non_loop_found) {
- assert(!loop_found); /* should have dealt with this already */
- return LOOP_NONE;
- }
-
- /* Check that every clue is satisfied */
- for (j = 0; j < state->h; ++j) {
- for (i = 0; i < state->w; ++i) {
- n = CLUE_AT(state, i, j);
- if (n != ' ') {
- if (square_order(state, i, j, LINE_YES) != n - '0') {
- return LOOP_NOT_SOLN;
- }
- }
- }
- }
-
- return LOOP_SOLN;
-}
-
/* Sums the lengths of the numbers in range [0,n) */
/* See equivalent function in solo.c for justification of this. */
static int len_0_to_n(int n)
}
}
-
-static int game_states_equal(const game_state *state1,
- const game_state *state2)
-{
- /* This deliberately doesn't check _all_ fields, just the ones that make a
- * game state 'interesting' from the POV of the solver */
- /* XXX review this */
- if (state1 == state2)
- return 1;
-
- if (!state1 || !state2)
- return 0;
-
- if (state1->w != state2->w || state1->h != state2->h)
- return 0;
-
- if (memcmp(state1->hl, state2->hl, HL_COUNT(state1)))
- return 0;
-
- if (memcmp(state1->vl, state2->vl, VL_COUNT(state1)))
- return 0;
-
- return 1;
-}
-
-static int solver_states_equal(const solver_state *sstate1,
- const solver_state *sstate2)
-{
- if (!sstate1) {
- if (!sstate2)
- return TRUE;
- else
- return FALSE;
- }
-
- if (!game_states_equal(sstate1->state, sstate2->state)) {
- return 0;
- }
-
- /* XXX fields missing, needs review */
- /* XXX we're deliberately not looking at solver_state as it's only a cache */
-
- if (memcmp(sstate1->dot_atleastone, sstate2->dot_atleastone,
- DOT_COUNT(sstate1->state))) {
- return 0;
- }
-
- if (memcmp(sstate1->dot_atmostone, sstate2->dot_atmostone,
- DOT_COUNT(sstate1->state))) {
- return 0;
- }
-
- /* handle dline_identical here */
-
- return 1;
-}
-
-static void dot_setall_dlines(solver_state *sstate, enum dline dl, int i, int j,
- enum line_state line_old, enum line_state line_new)
+static int dot_setall_dlines(solver_state *sstate, enum dline dl, int i, int j,
+ enum line_state line_old, enum line_state line_new)
{
game_state *state = sstate->state;
+ int retval = FALSE;
+
+ if (line_old == line_new)
+ return FALSE;
/* First line in dline */
switch (dl) {
case DLINE_UL:
case DLINE_UR:
case DLINE_VERT:
- if (j > 0 && ABOVE_DOT(state, i, j) == line_old)
+ if (j > 0 && ABOVE_DOT(state, i, j) == line_old) {
LV_ABOVE_DOT(state, i, j) = line_new;
+ retval = TRUE;
+ }
break;
case DLINE_DL:
case DLINE_DR:
- if (j <= (state)->h && BELOW_DOT(state, i, j) == line_old)
+ if (j <= (state)->h && BELOW_DOT(state, i, j) == line_old) {
LV_BELOW_DOT(state, i, j) = line_new;
+ retval = TRUE;
+ }
break;
case DLINE_HORIZ:
- if (i > 0 && LEFTOF_DOT(state, i, j) == line_old)
+ if (i > 0 && LEFTOF_DOT(state, i, j) == line_old) {
LV_LEFTOF_DOT(state, i, j) = line_new;
+ retval = TRUE;
+ }
break;
}
switch (dl) {
case DLINE_UL:
case DLINE_DL:
- if (i > 0 && LEFTOF_DOT(state, i, j) == line_old)
+ if (i > 0 && LEFTOF_DOT(state, i, j) == line_old) {
LV_LEFTOF_DOT(state, i, j) = line_new;
+ retval = TRUE;
+ }
break;
case DLINE_UR:
case DLINE_DR:
case DLINE_HORIZ:
- if (i <= (state)->w && RIGHTOF_DOT(state, i, j) == line_old)
+ if (i <= (state)->w && RIGHTOF_DOT(state, i, j) == line_old) {
LV_RIGHTOF_DOT(state, i, j) = line_new;
+ retval = TRUE;
+ }
break;
case DLINE_VERT:
- if (j <= (state)->h && BELOW_DOT(state, i, j) == line_old)
+ if (j <= (state)->h && BELOW_DOT(state, i, j) == line_old) {
LV_BELOW_DOT(state, i, j) = line_new;
+ retval = TRUE;
+ }
break;
}
-}
-static void update_solver_status(solver_state *sstate)
-{
- if (sstate->solver_status == SOLVER_INCOMPLETE) {
- switch (loop_status(sstate->state)) {
- case LOOP_NONE:
- sstate->solver_status = SOLVER_INCOMPLETE;
- break;
- case LOOP_SOLN:
- if (sstate->solver_status != SOLVER_AMBIGUOUS)
- sstate->solver_status = SOLVER_SOLVED;
- break;
- case LOOP_NOT_SOLN:
- sstate->solver_status = SOLVER_MISTAKE;
- break;
- }
- }
+ return retval;
}
#if 0
* solved grid */
static solver_state *solve_game_rec(const solver_state *sstate_start, int diff)
{
- int i, j;
+ int i, j, w, h;
int current_yes, current_no, desired;
solver_state *sstate, *sstate_saved, *sstate_tmp;
int t;
-/* char *text; */
solver_state *sstate_rec_solved;
int recursive_soln_count;
+ char *square_solved;
+ char *dot_solved;
+ int solver_progress;
+
+ h = sstate_start->state->h;
+ w = sstate_start->state->w;
+
+ dot_solved = snewn(DOT_COUNT(sstate_start->state), char);
+ square_solved = snewn(SQUARE_COUNT(sstate_start->state), char);
+ memset(dot_solved, FALSE, DOT_COUNT(sstate_start->state));
+ memset(square_solved, FALSE, SQUARE_COUNT(sstate_start->state));
#if 0
printf("solve_game_rec: recursion_remaining = %d\n",
sstate = dup_solver_state((solver_state *)sstate_start);
-#if 0
- text = game_text_format(sstate->state);
- printf("%s\n", text);
- sfree(text);
-#endif
-
-#define RETURN_IF_SOLVED \
- do { \
- update_solver_status(sstate); \
- if (sstate->solver_status != SOLVER_INCOMPLETE) { \
- free_solver_state(sstate_saved); \
- return sstate; \
- } \
- } while (0)
-
#define FOUND_MISTAKE \
do { \
sstate->solver_status = SOLVER_MISTAKE; \
+ sfree(dot_solved); sfree(square_solved); \
free_solver_state(sstate_saved); \
return sstate; \
} while (0)
-
sstate_saved = NULL;
- RETURN_IF_SOLVED;
nonrecursive_solver:
while (1) {
- sstate_saved = dup_solver_state(sstate);
+ solver_progress = FALSE;
/* First we do the 'easy' work, that might cause concrete results */
/* Per-square deductions */
- for (j = 0; j < sstate->state->h; ++j) {
- for (i = 0; i < sstate->state->w; ++i) {
+ for (j = 0; j < h; ++j) {
+ for (i = 0; i < w; ++i) {
/* Begin rules that look at the clue (if there is one) */
+ if (square_solved[i + j*w])
+ continue;
+
desired = CLUE_AT(sstate->state, i, j);
if (desired == ' ')
continue;
+
desired = desired - '0';
current_yes = square_order(sstate->state, i, j, LINE_YES);
current_no = square_order(sstate->state, i, j, LINE_NO);
+ if (current_yes + current_no == 4) {
+ square_solved[i + j*w] = TRUE;
+ continue;
+ }
+
if (desired < current_yes)
FOUND_MISTAKE;
if (desired == current_yes) {
square_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO);
+ square_solved[i + j*w] = TRUE;
+ solver_progress = TRUE;
continue;
}
FOUND_MISTAKE;
if (4 - desired == current_no) {
square_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_YES);
+ square_solved[i + j*w] = TRUE;
+ solver_progress = TRUE;
}
}
}
- RETURN_IF_SOLVED;
-
/* Per-dot deductions */
- for (j = 0; j < sstate->state->h + 1; ++j) {
- for (i = 0; i < sstate->state->w + 1; ++i) {
+ for (j = 0; j < h + 1; ++j) {
+ for (i = 0; i < w + 1; ++i) {
+ if (dot_solved[i + j*(w+1)])
+ continue;
+
switch (dot_order(sstate->state, i, j, LINE_YES)) {
case 0:
- if (dot_order(sstate->state, i, j, LINE_NO) == 3) {
- dot_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO);
+ switch (dot_order(sstate->state, i, j, LINE_NO)) {
+ case 3:
+ dot_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO);
+ solver_progress = TRUE;
+ /* fall through */
+ case 4:
+ dot_solved[i + j*(w+1)] = TRUE;
+ break;
}
break;
case 1:
#define H1(dline, dir1_dot, dir2_dot, dot_howmany) \
if (dir1_dot(sstate->state, i, j) == LINE_UNKNOWN) { \
if (dir2_dot(sstate->state, i, j) == LINE_UNKNOWN){ \
- sstate->dot_howmany \
- [i + (sstate->state->w + 1) * j] |= 1<<dline; \
+ solver_progress |= \
+ SET_BIT(sstate->dot_howmany[i + (w + 1) * j], \
+ dline); \
} \
}
case 1:
case 2: /* 1 yes, 2 no */
dot_setall(sstate->state, i, j,
LINE_UNKNOWN, LINE_YES);
+ dot_solved[i + j*(w+1)] = TRUE;
+ solver_progress = TRUE;
+ break;
+ case 3: /* 1 yes, 3 no */
+ FOUND_MISTAKE;
break;
}
break;
case 2:
- dot_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO);
+ if (dot_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO)) {
+ solver_progress = TRUE;
+ }
+ dot_solved[i + j*(w+1)] = TRUE;
break;
case 3:
+ case 4:
FOUND_MISTAKE;
break;
}
if (diff > DIFF_EASY) {
#define HANDLE_DLINE(dline, dir1_dot, dir2_dot) \
- if (sstate->dot_atleastone \
- [i + (sstate->state->w + 1) * j] & 1<<dline) { \
- sstate->dot_atmostone \
- [i + (sstate->state->w + 1) * j] |= 1<<OPP_DLINE(dline); \
+ if (BIT_SET(sstate->dot_atleastone[i + (w + 1) * j], dline)) { \
+ solver_progress |= \
+ SET_BIT(sstate->dot_atmostone[i + (w + 1) * j], \
+ OPP_DLINE(dline)); \
}
/* If at least one of a dline in a dot is YES, at most one
* of the opposite dline to that dot must be YES. */
DOT_DLINES;
}
#undef HANDLE_DLINE
- }
- }
-
- /* More obscure per-square operations */
- for (j = 0; j < sstate->state->h; ++j) {
- for (i = 0; i < sstate->state->w; ++i) {
-#define H1(dline, dir1_sq, dir2_sq, a, b, dot_howmany, line_query, line_set) \
- if (sstate->dot_howmany[i+a + (sstate->state->w + 1) * (j+b)] &\
- 1<<dline) { \
+
+#define H1(dline, dir1_sq, dir2_sq, dot_howmany, line_query, line_set) \
+ if (BIT_SET(sstate->dot_howmany[i + (w+1) * j], dline)) { \
t = dir1_sq(sstate->state, i, j); \
- if (t == line_query) \
- dir2_sq(sstate->state, i, j) = line_set; \
- else { \
+ if (t == line_query) { \
+ if (dir2_sq(sstate->state, i, j) != line_set) { \
+ LV_##dir2_sq(sstate->state, i, j) = line_set; \
+ solver_progress = TRUE; \
+ } \
+ } else { \
t = dir2_sq(sstate->state, i, j); \
- if (t == line_query) \
- dir1_sq(sstate->state, i, j) = line_set; \
+ if (t == line_query) { \
+ if (dir1_sq(sstate->state, i, j) != line_set) { \
+ LV_##dir1_sq(sstate->state, i, j) = line_set; \
+ solver_progress = TRUE; \
+ } \
+ } \
} \
}
if (diff > DIFF_EASY) {
-#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \
- H1(dline, dir1_sq, dir2_sq, a, b, dot_atmostone, \
- LINE_YES, LINE_NO)
+#define HANDLE_DLINE(dline, dir1_sq, dir2_sq) \
+ H1(dline, dir1_sq, dir2_sq, dot_atmostone, LINE_YES, LINE_NO)
/* If at most one of the DLINE is on, and one is definitely
* on, set the other to definitely off */
- SQUARE_DLINES;
+ DOT_DLINES;
#undef HANDLE_DLINE
}
if (diff > DIFF_EASY) {
-#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \
- H1(dline, dir1_sq, dir2_sq, a, b, dot_atleastone, \
- LINE_NO, LINE_YES)
+#define HANDLE_DLINE(dline, dir1_sq, dir2_sq) \
+ H1(dline, dir1_sq, dir2_sq, dot_atleastone, LINE_NO, LINE_YES)
/* If at least one of the DLINE is on, and one is definitely
* off, set the other to definitely on */
- SQUARE_DLINES;
+ DOT_DLINES;
#undef HANDLE_DLINE
}
#undef H1
+ }
+ }
+
+ /* More obscure per-square operations */
+ for (j = 0; j < h; ++j) {
+ for (i = 0; i < w; ++i) {
+ if (square_solved[i + j*w])
+ continue;
+
switch (CLUE_AT(sstate->state, i, j)) {
- case '0':
case '1':
if (diff > DIFF_EASY) {
#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \
/* At most one of any DLINE can be set */ \
- sstate->dot_atmostone \
- [i+a + (sstate->state->w + 1) * (j+b)] |= 1<<dline; \
+ SET_BIT(sstate->dot_atmostone[i+a + (w + 1) * (j+b)], \
+ dline); \
/* This DLINE provides enough YESes to solve the clue */\
- if (sstate->dot_atleastone \
- [i+a + (sstate->state->w + 1) * (j+b)] & \
- 1<<dline) { \
- dot_setall_dlines(sstate, OPP_DLINE(dline), \
- i+(1-a), j+(1-b), \
- LINE_UNKNOWN, LINE_NO); \
+ if (BIT_SET(sstate->dot_atleastone \
+ [i+a + (w + 1) * (j+b)], \
+ dline)) { \
+ solver_progress |= \
+ dot_setall_dlines(sstate, OPP_DLINE(dline), \
+ i+(1-a), j+(1-b), \
+ LINE_UNKNOWN, LINE_NO); \
}
SQUARE_DLINES;
#undef HANDLE_DLINE
case '2':
if (diff > DIFF_EASY) {
#define H1(dline, dot_at1one, dot_at2one, a, b) \
- if (sstate->dot_at1one \
- [i+a + (sstate->state->w + 1) * (j+b)] & \
- 1<<dline) { \
- sstate->dot_at2one \
- [i+(1-a) + (sstate->state->w + 1) * (j+(1-b))] |= \
- 1<<OPP_DLINE(dline); \
+ if (BIT_SET(sstate->dot_at1one \
+ [i+a + (w+1) * (j+b)], dline)) { \
+ solver_progress |= \
+ SET_BIT(sstate->dot_at2one \
+ [i+(1-a) + (w+1) * (j+(1-b))], \
+ OPP_DLINE(dline)); \
}
#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \
H1(dline, dot_atleastone, dot_atmostone, a, b); \
#undef H1
break;
case '3':
- case '4':
if (diff > DIFF_EASY) {
#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \
/* At least one of any DLINE can be set */ \
- sstate->dot_atleastone \
- [i+a + (sstate->state->w + 1) * (j+b)] |= 1<<dline; \
+ solver_progress |= \
+ SET_BIT(sstate->dot_atleastone \
+ [i+a + (w + 1) * (j+b)], \
+ dline); \
/* This DLINE provides enough NOs to solve the clue */ \
- if (sstate->dot_atmostone \
- [i+a + (sstate->state->w + 1) * (j+b)] & \
- 1<<dline) { \
- dot_setall_dlines(sstate, OPP_DLINE(dline), \
- i+(1-a), j+(1-b), \
- LINE_UNKNOWN, LINE_YES); \
+ if (BIT_SET(sstate->dot_atmostone \
+ [i+a + (w + 1) * (j+b)], \
+ dline)) { \
+ solver_progress |= \
+ dot_setall_dlines(sstate, OPP_DLINE(dline), \
+ i+(1-a), j+(1-b), \
+ LINE_UNKNOWN, LINE_YES); \
}
SQUARE_DLINES;
#undef HANDLE_DLINE
}
}
}
-
- if (solver_states_equal(sstate, sstate_saved)) {
+
+ if (!solver_progress) {
int edgecount = 0, clues = 0, satclues = 0, sm1clues = 0;
+ int shortest_chainlen = DOT_COUNT(sstate->state);
+ int loop_found = FALSE;
int d;
+ int dots_connected;
/*
* Go through the grid and update for all the new edges.
* clues, count the satisfied clues, and count the
* satisfied-minus-one clues.
*/
- for (j = 0; j <= sstate->state->h; ++j) {
- for (i = 0; i <= sstate->state->w; ++i) {
+ for (j = 0; j < h+1; ++j) {
+ for (i = 0; i < w+1; ++i) {
if (RIGHTOF_DOT(sstate->state, i, j) == LINE_YES) {
- merge_dots(sstate, i, j, i+1, j);
+ loop_found |= merge_dots(sstate, i, j, i+1, j);
edgecount++;
}
if (BELOW_DOT(sstate->state, i, j) == LINE_YES) {
- merge_dots(sstate, i, j, i, j+1);
+ loop_found |= merge_dots(sstate, i, j, i, j+1);
edgecount++;
}
}
}
+ for (i = 0; i < DOT_COUNT(sstate->state); ++i) {
+ dots_connected = sstate->looplen[dsf_canonify(sstate->dotdsf,i)];
+ if (dots_connected > 1)
+ shortest_chainlen = min(shortest_chainlen, dots_connected);
+ }
+
+ assert(sstate->solver_status == SOLVER_INCOMPLETE);
+
+ if (satclues == clues && shortest_chainlen == edgecount) {
+ sstate->solver_status = SOLVER_SOLVED;
+ /* This discovery clearly counts as progress, even if we haven't
+ * just added any lines or anything */
+ solver_progress = TRUE;
+ goto finished_loop_checking;
+ }
+
/*
* Now go through looking for LINE_UNKNOWN edges which
* connect two dots that are already in the same
* equivalence class. If we find one, test to see if the
* loop it would create is a solution.
*/
- for (j = 0; j <= sstate->state->h; ++j) {
- for (i = 0; i <= sstate->state->w; ++i) {
+ for (j = 0; j <= h; ++j) {
+ for (i = 0; i <= w; ++i) {
for (d = 0; d < 2; d++) {
int i2, j2, eqclass, val;
j2 = j+1;
}
- eqclass = dsf_canonify(sstate->dotdsf,
- j * (sstate->state->w+1) + i);
+ eqclass = dsf_canonify(sstate->dotdsf, j * (w+1) + i);
if (eqclass != dsf_canonify(sstate->dotdsf,
- j2 * (sstate->state->w+1) +
- i2))
+ j2 * (w+1) + i2))
continue;
val = LINE_NO; /* loop is bad until proven otherwise */
* a reasonable deduction for the user to
* make.
*/
- if (d == 0)
+ if (d == 0) {
LV_RIGHTOF_DOT(sstate->state, i, j) = val;
- else
+ solver_progress = TRUE;
+ } else {
LV_BELOW_DOT(sstate->state, i, j) = val;
+ solver_progress = TRUE;
+ }
if (val == LINE_YES) {
sstate->solver_status = SOLVER_AMBIGUOUS;
goto finished_loop_checking;
finished_loop_checking:
- RETURN_IF_SOLVED;
- }
-
- if (solver_states_equal(sstate, sstate_saved)) {
- /* Solver has stopped making progress so we terminate */
- free_solver_state(sstate_saved);
- break;
+ if (!solver_progress ||
+ sstate->solver_status == SOLVER_SOLVED ||
+ sstate->solver_status == SOLVER_AMBIGUOUS) {
+ break;
+ }
}
-
- free_solver_state(sstate_saved);
}
+ sfree(dot_solved); sfree(square_solved);
+
if (sstate->solver_status == SOLVER_SOLVED ||
sstate->solver_status == SOLVER_AMBIGUOUS) {
/* s/LINE_UNKNOWN/LINE_NO/g */
sstate = dup_solver_state(sstate_saved); \
}
- for (j = 0; j < sstate->state->h + 1; ++j) {
- for (i = 0; i < sstate->state->w + 1; ++i) {
+ for (j = 0; j < h + 1; ++j) {
+ for (i = 0; i < w + 1; ++i) {
/* Only perform recursive calls on 'loose ends' */
if (dot_order(sstate->state, i, j, LINE_YES) == 1) {
DO_RECURSIVE_CALL(LEFTOF_DOT);
struct game_drawstate {
int started;
- int tilesize;
+ int tilesize, linewidth;
int flashing;
char *hl, *vl;
char *clue_error;
game_params *params, int tilesize)
{
ds->tilesize = tilesize;
+ ds->linewidth = max(1,tilesize/16);
}
-static float *game_colours(frontend *fe, game_state *state, int *ncolours)
+static float *game_colours(frontend *fe, int *ncolours)
{
float *ret = snewn(4 * NCOLOURS, float);
{
struct game_drawstate *ds = snew(struct game_drawstate);
- ds->tilesize = 0;
+ ds->tilesize = ds->linewidth = 0;
ds->started = 0;
ds->hl = snewn(HL_COUNT(state), char);
ds->vl = snewn(VL_COUNT(state), char);
clue_mistake = (square_order(state, i, j, LINE_YES) > n ||
square_order(state, i, j, LINE_NO ) > (4-n));
- if (clue_mistake != ds->clue_error[i * w + j]) {
+ if (clue_mistake != ds->clue_error[j * w + i]) {
draw_rect(dr,
BORDER + i * TILE_SIZE + CROSS_SIZE,
BORDER + j * TILE_SIZE + CROSS_SIZE,
draw_update(dr, i * TILE_SIZE + BORDER, j * TILE_SIZE + BORDER,
TILE_SIZE, TILE_SIZE);
- ds->clue_error[i * w + j] = clue_mistake;
+ ds->clue_error[j * w + i] = clue_mistake;
}
}
}
return 0.0F;
}
-static int game_wants_statusbar(void)
-{
- return FALSE;
-}
-
static int game_timing_state(game_state *state, game_ui *ui)
{
return TRUE;
int ink = print_mono_colour(dr, 0);
int x, y;
game_drawstate ads, *ds = &ads;
- ds->tilesize = tilesize;
+
+ game_set_size(dr, ds, NULL, tilesize);
/*
* Dots. I'll deliberately make the dots a bit wider than the
game_anim_length,
game_flash_length,
TRUE, FALSE, game_print_size, game_print,
- game_wants_statusbar,
+ FALSE, /* wants_statusbar */
FALSE, game_timing_state,
- 0, /* mouse_priorities */
+ 0, /* flags */
};
~mdw / sgt / puzzles / blobdiff