-/* 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;
-}
-