-/* Generate a new complete set of clues for the given game_state (respecting
- * the dimensions provided by said game_state) */
-static void add_full_clues(game_state *state, random_state *rs)
-{
- signed char *clues;
- char *board;
- int i, j, a, b, c;
- int board_area = SQUARE_COUNT(state);
- int t;
-
- struct square *square, *tmpsquare, *sq;
- struct square square_pos;
-
- /* These will contain exactly the same information, sorted into different
- * orders */
- tree234 *lightable_squares_sorted, *lightable_squares_gettable;
-
-#define SQUARE_REACHABLE(i,j) \
- (t = (SQUARE_STATE(i-1, j) == SQUARE_LIT || \
- SQUARE_STATE(i+1, j) == SQUARE_LIT || \
- SQUARE_STATE(i, j-1) == SQUARE_LIT || \
- SQUARE_STATE(i, j+1) == SQUARE_LIT), \
- t)
-
- /* One situation in which we may not light a square is if that'll leave one
- * square above/below and one left/right of us unlit, separated by a lit
- * square diagnonal from us */
-#define SQUARE_DIAGONAL_VIOLATION(i, j, h, v) \
- (t = (SQUARE_STATE((i)+(h), (j)) == SQUARE_UNLIT && \
- SQUARE_STATE((i), (j)+(v)) == SQUARE_UNLIT && \
- SQUARE_STATE((i)+(h), (j)+(v)) == SQUARE_LIT), \
- t)
-
- /* We also may not light a square if it will form a loop of lit squares
- * around some unlit squares, as then the game soln won't have a single
- * loop */
-#define SQUARE_LOOP_VIOLATION(i, j, lit1, lit2) \
- (SQUARE_STATE((i)+1, (j)) == lit1 && \
- SQUARE_STATE((i)-1, (j)) == lit1 && \
- SQUARE_STATE((i), (j)+1) == lit2 && \
- SQUARE_STATE((i), (j)-1) == lit2)
-
-#define CAN_LIGHT_SQUARE(i, j) \
- (SQUARE_REACHABLE(i, j) && \
- !SQUARE_DIAGONAL_VIOLATION(i, j, -1, -1) && \
- !SQUARE_DIAGONAL_VIOLATION(i, j, +1, -1) && \
- !SQUARE_DIAGONAL_VIOLATION(i, j, -1, +1) && \
- !SQUARE_DIAGONAL_VIOLATION(i, j, +1, +1) && \
- !SQUARE_LOOP_VIOLATION(i, j, SQUARE_LIT, SQUARE_UNLIT) && \
- !SQUARE_LOOP_VIOLATION(i, j, SQUARE_UNLIT, SQUARE_LIT))
-
-#define IS_LIGHTING_CANDIDATE(i, j) \
- (SQUARE_STATE(i, j) == SQUARE_UNLIT && \
- CAN_LIGHT_SQUARE(i,j))
-
- /* The 'score' of a square reflects its current desirability for selection
- * as the next square to light. We want to encourage moving into uncharted
- * areas so we give scores according to how many of the square's neighbours
- * are currently unlit. */
-
- /* UNLIT SCORE
- * 3 2
- * 2 0
- * 1 -2
- */
-#define SQUARE_SCORE(i,j) \
- (2*((SQUARE_STATE(i-1, j) == SQUARE_UNLIT) + \
- (SQUARE_STATE(i+1, j) == SQUARE_UNLIT) + \
- (SQUARE_STATE(i, j-1) == SQUARE_UNLIT) + \
- (SQUARE_STATE(i, j+1) == SQUARE_UNLIT)) - 4)
-
- /* When a square gets lit, this defines how far away from that square we
- * need to go recomputing scores */
-#define SCORE_DISTANCE 1
-
- board = snewn(board_area, char);
- clues = state->clues;
-
- /* Make a board */
- memset(board, SQUARE_UNLIT, board_area);
-
- /* Seed the board with a single lit square near the middle */
- i = state->w / 2;
- j = state->h / 2;
- if (state->w & 1 && random_bits(rs, 1))
- ++i;
- if (state->h & 1 && random_bits(rs, 1))
- ++j;
-
- LV_SQUARE_STATE(i, j) = SQUARE_LIT;
-
- /* We need a way of favouring squares that will increase our loopiness.
- * We do this by maintaining a list of all candidate squares sorted by
- * their score and choose randomly from that with appropriate skew.
- * In order to avoid consistently biasing towards particular squares, we
- * need the sort order _within_ each group of scores to be completely
- * random. But it would be abusing the hospitality of the tree234 data
- * structure if our comparison function were nondeterministic :-). So with
- * each square we associate a random number that does not change during a
- * particular run of the generator, and use that as a secondary sort key.
- * Yes, this means we will be biased towards particular random squares in
- * any one run but that doesn't actually matter. */
-
- lightable_squares_sorted = newtree234(square_sort_cmpfn);
- lightable_squares_gettable = newtree234(get_square_cmpfn);
-#define ADD_SQUARE(s) \
- do { \
- sq = add234(lightable_squares_sorted, s); \
- assert(sq == s); \
- sq = add234(lightable_squares_gettable, s); \
- assert(sq == s); \
- } while (0)
-
-#define REMOVE_SQUARE(s) \
- do { \
- sq = del234(lightable_squares_sorted, s); \
- assert(sq); \
- sq = del234(lightable_squares_gettable, s); \
- assert(sq); \
- } while (0)
-
-#define HANDLE_DIR(a, b) \
- square = snew(struct square); \
- square->x = (i)+(a); \
- square->y = (j)+(b); \
- square->score = 2; \
- square->random = random_bits(rs, 31); \
- ADD_SQUARE(square);
- HANDLE_DIR(-1, 0);
- HANDLE_DIR( 1, 0);
- HANDLE_DIR( 0,-1);
- HANDLE_DIR( 0, 1);
-#undef HANDLE_DIR
-
- /* Light squares one at a time until the board is interesting enough */
- while (TRUE)
- {
- /* We have count234(lightable_squares) possibilities, and in
- * lightable_squares_sorted they are sorted with the most desirable
- * first. */
- c = count234(lightable_squares_sorted);
- if (c == 0)
- break;
- assert(c == count234(lightable_squares_gettable));
-
- /* Check that the best square available is any good */
- square = (struct square *)index234(lightable_squares_sorted, 0);
- assert(square);
-
- /*
- * We never want to _decrease_ the loop's perimeter. Making
- * moves that leave the perimeter the same is occasionally
- * useful: if it were _never_ done then the user would be
- * able to deduce illicitly that any degree-zero vertex was
- * on the outside of the loop. So we do it sometimes but
- * not always.
- */
- if (square->score < 0 || (square->score == 0 &&
- random_upto(rs, 2) == 0)) {
- break;
- }
-
- assert(square->score == SQUARE_SCORE(square->x, square->y));
- assert(SQUARE_STATE(square->x, square->y) == SQUARE_UNLIT);
- assert(square->x >= 0 && square->x < state->w);
- assert(square->y >= 0 && square->y < state->h);
-
- /* Update data structures */
- LV_SQUARE_STATE(square->x, square->y) = SQUARE_LIT;
- REMOVE_SQUARE(square);
-
- /* We might have changed the score of any squares up to 2 units away in
- * any direction */
- for (b = -SCORE_DISTANCE; b <= SCORE_DISTANCE; b++) {
- for (a = -SCORE_DISTANCE; a <= SCORE_DISTANCE; a++) {
- if (!a && !b)
- continue;
- square_pos.x = square->x + a;
- square_pos.y = square->y + b;
- if (square_pos.x < 0 || square_pos.x >= state->w ||
- square_pos.y < 0 || square_pos.y >= state->h) {
- continue;
- }
- tmpsquare = find234(lightable_squares_gettable, &square_pos,
- NULL);
- if (tmpsquare) {
- assert(tmpsquare->x == square_pos.x);
- assert(tmpsquare->y == square_pos.y);
- assert(SQUARE_STATE(tmpsquare->x, tmpsquare->y) ==
- SQUARE_UNLIT);
- REMOVE_SQUARE(tmpsquare);
- } else {
- tmpsquare = snew(struct square);
- tmpsquare->x = square_pos.x;
- tmpsquare->y = square_pos.y;
- tmpsquare->random = random_bits(rs, 31);
- }
- tmpsquare->score = SQUARE_SCORE(tmpsquare->x, tmpsquare->y);
-
- if (IS_LIGHTING_CANDIDATE(tmpsquare->x, tmpsquare->y)) {
- ADD_SQUARE(tmpsquare);
- } else {
- sfree(tmpsquare);
- }
- }
- }
- sfree(square);
- }
-
- /* Clean up */
- while ((square = delpos234(lightable_squares_gettable, 0)) != NULL)
- sfree(square);
- freetree234(lightable_squares_gettable);
- freetree234(lightable_squares_sorted);
-
- /* Copy out all the clues */
- FORALL_SQUARES(state, i, j) {
- c = SQUARE_STATE(i, j);
- LV_CLUE_AT(state, i, j) = 0;
- if (SQUARE_STATE(i-1, j) != c) ++LV_CLUE_AT(state, i, j);
- if (SQUARE_STATE(i+1, j) != c) ++LV_CLUE_AT(state, i, j);
- if (SQUARE_STATE(i, j-1) != c) ++LV_CLUE_AT(state, i, j);
- if (SQUARE_STATE(i, j+1) != c) ++LV_CLUE_AT(state, i, j);
- }
-
- sfree(board);
-}
-
-static int game_has_unique_soln(const game_state *state, int diff)
-{
- int ret;
- solver_state *sstate_new;
- solver_state *sstate = new_solver_state((game_state *)state, diff);
-
- sstate_new = solve_game_rec(sstate, diff);
-
- assert(sstate_new->solver_status != SOLVER_MISTAKE);
- ret = (sstate_new->solver_status == SOLVER_SOLVED);
-
- free_solver_state(sstate_new);
- free_solver_state(sstate);
-
- return ret;
-}