+++ /dev/null
-/*
- * pearl.c: Nikoli's `Masyu' puzzle. Currently this is a blank
- * puzzle file with nothing but a test solver-generator.
- */
-
-/*
- * TODO:
- *
- * - The generation method appears to be fundamentally flawed. I
- * think generating a random loop and then choosing a clue set
- * is simply not a viable approach, because on a test run of
- * 10,000 attempts, it generated _six_ viable puzzles. All the
- * rest of the randomly generated loops failed to be soluble
- * even given a maximal clue set. Also, the vast majority of the
- * clues were white circles (straight clues); black circles
- * (corners) seem very uncommon.
- * + So what can we do? One possible approach would be to
- * adjust the random loop generation so that it created loops
- * which were in some heuristic sense more likely to be
- * viable Masyu puzzles. Certainly a good start on that would
- * be to arrange that black clues actually _came up_ slightly
- * more often, but I have no idea whether that would be
- * sufficient.
- * + A second option would be to throw the entire mechanism out
- * and instead write a different generator from scratch which
- * evolves the solution along with the puzzle: place a few
- * clues, nail down a bit of the loop, place another clue,
- * nail down some more, etc. It's unclear whether this can
- * sensibly be done, though.
- *
- * - Puzzle playing UI and everything else apart from the
- * generator...
- */
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#include <assert.h>
-#include <ctype.h>
-#include <math.h>
-
-#include "puzzles.h"
-
-#define NOCLUE 0
-#define CORNER 1
-#define STRAIGHT 2
-
-#define R 1
-#define U 2
-#define L 4
-#define D 8
-
-#define DX(d) ( ((d)==R) - ((d)==L) )
-#define DY(d) ( ((d)==D) - ((d)==U) )
-
-#define F(d) (((d << 2) | (d >> 2)) & 0xF)
-#define C(d) (((d << 3) | (d >> 1)) & 0xF)
-#define A(d) (((d << 1) | (d >> 3)) & 0xF)
-
-#define LR (L | R)
-#define RL (R | L)
-#define UD (U | D)
-#define DU (D | U)
-#define LU (L | U)
-#define UL (U | L)
-#define LD (L | D)
-#define DL (D | L)
-#define RU (R | U)
-#define UR (U | R)
-#define RD (R | D)
-#define DR (D | R)
-#define BLANK 0
-#define UNKNOWN 15
-
-#define bLR (1 << LR)
-#define bRL (1 << RL)
-#define bUD (1 << UD)
-#define bDU (1 << DU)
-#define bLU (1 << LU)
-#define bUL (1 << UL)
-#define bLD (1 << LD)
-#define bDL (1 << DL)
-#define bRU (1 << RU)
-#define bUR (1 << UR)
-#define bRD (1 << RD)
-#define bDR (1 << DR)
-#define bBLANK (1 << BLANK)
-
-enum {
- COL_BACKGROUND,
- NCOLOURS
-};
-
-struct game_params {
- int FIXME;
-};
-
-struct game_state {
- int FIXME;
-};
-
-static game_params *default_params(void)
-{
- game_params *ret = snew(game_params);
-
- ret->FIXME = 0;
-
- return ret;
-}
-
-static int game_fetch_preset(int i, char **name, game_params **params)
-{
- return FALSE;
-}
-
-static void free_params(game_params *params)
-{
- sfree(params);
-}
-
-static game_params *dup_params(game_params *params)
-{
- game_params *ret = snew(game_params);
- *ret = *params; /* structure copy */
- return ret;
-}
-
-static void decode_params(game_params *params, char const *string)
-{
-}
-
-static char *encode_params(game_params *params, int full)
-{
- return dupstr("FIXME");
-}
-
-static config_item *game_configure(game_params *params)
-{
- return NULL;
-}
-
-static game_params *custom_params(config_item *cfg)
-{
- return NULL;
-}
-
-static char *validate_params(game_params *params, int full)
-{
- return NULL;
-}
-
-/* ----------------------------------------------------------------------
- * Solver.
- */
-
-int pearl_solve(int w, int h, char *clues, char *result)
-{
- int W = 2*w+1, H = 2*h+1;
- short *workspace;
- int *dsf, *dsfsize;
- int x, y, b, d;
- int ret = -1;
-
- /*
- * workspace[(2*y+1)*W+(2*x+1)] indicates the possible nature
- * of the square (x,y), as a logical OR of bitfields.
- *
- * workspace[(2*y)*W+(2*x+1)], for x odd and y even, indicates
- * whether the horizontal edge between (x,y) and (x+1,y) is
- * connected (1), disconnected (2) or unknown (3).
- *
- * workspace[(2*y+1)*W+(2*x)], indicates the same about the
- * vertical edge between (x,y) and (x,y+1).
- *
- * Initially, every square is considered capable of being in
- * any of the seven possible states (two straights, four
- * corners and empty), except those corresponding to clue
- * squares which are more restricted.
- *
- * Initially, all edges are unknown, except the ones around the
- * grid border which are known to be disconnected.
- */
- workspace = snewn(W*H, short);
- for (x = 0; x < W*H; x++)
- workspace[x] = 0;
- /* Square states */
- for (y = 0; y < h; y++)
- for (x = 0; x < w; x++)
- switch (clues[y*w+x]) {
- case CORNER:
- workspace[(2*y+1)*W+(2*x+1)] = bLU|bLD|bRU|bRD;
- break;
- case STRAIGHT:
- workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD;
- break;
- default:
- workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD|bLU|bLD|bRU|bRD|bBLANK;
- break;
- }
- /* Horizontal edges */
- for (y = 0; y <= h; y++)
- for (x = 0; x < w; x++)
- workspace[(2*y)*W+(2*x+1)] = (y==0 || y==h ? 2 : 3);
- /* Vertical edges */
- for (y = 0; y < h; y++)
- for (x = 0; x <= w; x++)
- workspace[(2*y+1)*W+(2*x)] = (x==0 || x==w ? 2 : 3);
-
- /*
- * We maintain a dsf of connected squares, together with a
- * count of the size of each equivalence class.
- */
- dsf = snewn(w*h, int);
- dsfsize = snewn(w*h, int);
-
- /*
- * Now repeatedly try to find something we can do.
- */
- while (1) {
- int done_something = FALSE;
-
-#ifdef SOLVER_DIAGNOSTICS
- for (y = 0; y < H; y++) {
- for (x = 0; x < W; x++)
- printf("%*x", (x&1) ? 5 : 2, workspace[y*W+x]);
- printf("\n");
- }
-#endif
-
- /*
- * Go through the square state words, and discard any
- * square state which is inconsistent with known facts
- * about the edges around the square.
- */
- for (y = 0; y < h; y++)
- for (x = 0; x < w; x++) {
- for (b = 0; b < 0xD; b++)
- if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) {
- /*
- * If any edge of this square is known to
- * be connected when state b would require
- * it disconnected, or vice versa, discard
- * the state.
- */
- for (d = 1; d <= 8; d += d) {
- int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
- if (workspace[ey*W+ex] ==
- ((b & d) ? 2 : 1)) {
- workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<b);
-#ifdef SOLVER_DIAGNOSTICS
- printf("edge (%d,%d)-(%d,%d) rules out state"
- " %d for square (%d,%d)\n",
- ex/2, ey/2, (ex+1)/2, (ey+1)/2,
- b, x, y);
-#endif
- done_something = TRUE;
- break;
- }
- }
- }
-
- /*
- * Consistency check: each square must have at
- * least one state left!
- */
- if (!workspace[(2*y+1)*W+(2*x+1)]) {
-#ifdef SOLVER_DIAGNOSTICS
- printf("edge check at (%d,%d): inconsistency\n", x, y);
-#endif
- ret = 0;
- goto cleanup;
- }
- }
-
- /*
- * Now go through the states array again, and nail down any
- * unknown edge if one of its neighbouring squares makes it
- * known.
- */
- for (y = 0; y < h; y++)
- for (x = 0; x < w; x++) {
- int edgeor = 0, edgeand = 15;
-
- for (b = 0; b < 0xD; b++)
- if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) {
- edgeor |= b;
- edgeand &= b;
- }
-
- /*
- * Now any bit clear in edgeor marks a disconnected
- * edge, and any bit set in edgeand marks a
- * connected edge.
- */
-
- /* First check consistency: neither bit is both! */
- if (edgeand & ~edgeor) {
-#ifdef SOLVER_DIAGNOSTICS
- printf("square check at (%d,%d): inconsistency\n", x, y);
-#endif
- ret = 0;
- goto cleanup;
- }
-
- for (d = 1; d <= 8; d += d) {
- int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
-
- if (!(edgeor & d) && workspace[ey*W+ex] == 3) {
- workspace[ey*W+ex] = 2;
- done_something = TRUE;
-#ifdef SOLVER_DIAGNOSTICS
- printf("possible states of square (%d,%d) force edge"
- " (%d,%d)-(%d,%d) to be disconnected\n",
- x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2);
-#endif
- } else if ((edgeand & d) && workspace[ey*W+ex] == 3) {
- workspace[ey*W+ex] = 1;
- done_something = TRUE;
-#ifdef SOLVER_DIAGNOSTICS
- printf("possible states of square (%d,%d) force edge"
- " (%d,%d)-(%d,%d) to be connected\n",
- x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2);
-#endif
- }
- }
- }
-
- if (done_something)
- continue;
-
- /*
- * Now for longer-range clue-based deductions (using the
- * rules that a corner clue must connect to two straight
- * squares, and a straight clue must connect to at least
- * one corner square).
- */
- for (y = 0; y < h; y++)
- for (x = 0; x < w; x++)
- switch (clues[y*w+x]) {
- case CORNER:
- for (d = 1; d <= 8; d += d) {
- int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
- int fx = ex + DX(d), fy = ey + DY(d);
- int type = d | F(d);
-
- if (workspace[ey*W+ex] == 1) {
- /*
- * If a corner clue is connected on any
- * edge, then we can immediately nail
- * down the square beyond that edge as
- * being a straight in the appropriate
- * direction.
- */
- if (workspace[fy*W+fx] != (1<<type)) {
- workspace[fy*W+fx] = (1<<type);
- done_something = TRUE;
-#ifdef SOLVER_DIAGNOSTICS
- printf("corner clue at (%d,%d) forces square "
- "(%d,%d) into state %d\n", x, y,
- fx/2, fy/2, type);
-#endif
-
- }
- } else if (workspace[ey*W+ex] == 3) {
- /*
- * Conversely, if a corner clue is
- * separated by an unknown edge from a
- * square which _cannot_ be a straight
- * in the appropriate direction, we can
- * mark that edge as disconnected.
- */
- if (!(workspace[fy*W+fx] & (1<<type))) {
- workspace[ey*W+ex] = 2;
- done_something = TRUE;
-#ifdef SOLVER_DIAGNOSTICS
- printf("corner clue at (%d,%d), plus square "
- "(%d,%d) not being state %d, "
- "disconnects edge (%d,%d)-(%d,%d)\n",
- x, y, fx/2, fy/2, type,
- ex/2, ey/2, (ex+1)/2, (ey+1)/2);
-#endif
-
- }
- }
- }
-
- break;
- case STRAIGHT:
- /*
- * If a straight clue is between two squares
- * neither of which is capable of being a
- * corner connected to it, then the straight
- * clue cannot point in that direction.
- */
- for (d = 1; d <= 2; d += d) {
- int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d);
- int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d);
- int type = d | F(d);
-
- if (!(workspace[(2*y+1)*W+(2*x+1)] & (1<<type)))
- continue;
-
- if (!(workspace[fy*W+fx] & ((1<<(F(d)|A(d))) |
- (1<<(F(d)|C(d))))) &&
- !(workspace[gy*W+gx] & ((1<<( d |A(d))) |
- (1<<( d |C(d)))))) {
- workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<type);
- done_something = TRUE;
-#ifdef SOLVER_DIAGNOSTICS
- printf("straight clue at (%d,%d) cannot corner at "
- "(%d,%d) or (%d,%d) so is not state %d\n",
- x, y, fx/2, fy/2, gx/2, gy/2, type);
-#endif
- }
-
- }
-
- /*
- * If a straight clue with known direction is
- * connected on one side to a known straight,
- * then on the other side it must be a corner.
- */
- for (d = 1; d <= 8; d += d) {
- int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d);
- int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d);
- int type = d | F(d);
-
- if (workspace[(2*y+1)*W+(2*x+1)] != (1<<type))
- continue;
-
- if (!(workspace[fy*W+fx] &~ (bLR|bUD)) &&
- (workspace[gy*W+gx] &~ (bLU|bLD|bRU|bRD))) {
- workspace[gy*W+gx] &= (bLU|bLD|bRU|bRD);
- done_something = TRUE;
-#ifdef SOLVER_DIAGNOSTICS
- printf("straight clue at (%d,%d) connecting to "
- "straight at (%d,%d) makes (%d,%d) a "
- "corner\n", x, y, fx/2, fy/2, gx/2, gy/2);
-#endif
- }
-
- }
- break;
- }
-
- if (done_something)
- continue;
-
- /*
- * Now detect shortcut loops.
- */
-
- {
- int nonblanks, loopclass;
-
- dsf_init(dsf, w*h);
- for (x = 0; x < w*h; x++)
- dsfsize[x] = 1;
-
- /*
- * First go through the edge entries and update the dsf
- * of which squares are connected to which others. We
- * also track the number of squares in each equivalence
- * class, and count the overall number of
- * known-non-blank squares.
- *
- * In the process of doing this, we must notice if a
- * loop has already been formed. If it has, we blank
- * out any square which isn't part of that loop
- * (failing a consistency check if any such square does
- * not have BLANK as one of its remaining options) and
- * exit the deduction loop with success.
- */
- nonblanks = 0;
- loopclass = -1;
- for (y = 1; y < H-1; y++)
- for (x = 1; x < W-1; x++)
- if ((y ^ x) & 1) {
- /*
- * (x,y) are the workspace coordinates of
- * an edge field. Compute the normal-space
- * coordinates of the squares it connects.
- */
- int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax;
- int bx = x/2, by = y/2, bc = by*w+bx;
-
- /*
- * If the edge is connected, do the dsf
- * thing.
- */
- if (workspace[y*W+x] == 1) {
- int ae, be;
-
- ae = dsf_canonify(dsf, ac);
- be = dsf_canonify(dsf, bc);
-
- if (ae == be) {
- /*
- * We have a loop!
- */
- if (loopclass != -1) {
- /*
- * In fact, we have two
- * separate loops, which is
- * doom.
- */
-#ifdef SOLVER_DIAGNOSTICS
- printf("two loops found in grid!\n");
-#endif
- ret = 0;
- goto cleanup;
- }
- loopclass = ae;
- } else {
- /*
- * Merge the two equivalence
- * classes.
- */
- int size = dsfsize[ae] + dsfsize[be];
- dsf_merge(dsf, ac, bc);
- ae = dsf_canonify(dsf, ac);
- dsfsize[ae] = size;
- }
- }
- } else if ((y & x) & 1) {
- /*
- * (x,y) are the workspace coordinates of a
- * square field. If the square is
- * definitely not blank, count it.
- */
- if (!(workspace[y*W+x] & bBLANK))
- nonblanks++;
- }
-
- /*
- * If we discovered an existing loop above, we must now
- * blank every square not part of it, and exit the main
- * deduction loop.
- */
- if (loopclass != -1) {
-#ifdef SOLVER_DIAGNOSTICS
- printf("loop found in grid!\n");
-#endif
- for (y = 0; y < h; y++)
- for (x = 0; x < w; x++)
- if (dsf_canonify(dsf, y*w+x) != loopclass) {
- if (workspace[(y*2+1)*W+(x*2+1)] & bBLANK) {
- workspace[(y*2+1)*W+(x*2+1)] = bBLANK;
- } else {
- /*
- * This square is not part of the
- * loop, but is known non-blank. We
- * have goofed.
- */
-#ifdef SOLVER_DIAGNOSTICS
- printf("non-blank square (%d,%d) found outside"
- " loop!\n", x, y);
-#endif
- ret = 0;
- goto cleanup;
- }
- }
- /*
- * And we're done.
- */
- ret = 1;
- break;
- }
-
- /*
- * Now go through the workspace again and mark any edge
- * which would cause a shortcut loop (i.e. would
- * connect together two squares in the same equivalence
- * class, and that equivalence class does not contain
- * _all_ the known-non-blank squares currently in the
- * grid) as disconnected. Also, mark any _square state_
- * which would cause a shortcut loop as disconnected.
- */
- for (y = 1; y < H-1; y++)
- for (x = 1; x < W-1; x++)
- if ((y ^ x) & 1) {
- /*
- * (x,y) are the workspace coordinates of
- * an edge field. Compute the normal-space
- * coordinates of the squares it connects.
- */
- int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax;
- int bx = x/2, by = y/2, bc = by*w+bx;
-
- /*
- * If the edge is currently unknown, and
- * sits between two squares in the same
- * equivalence class, and the size of that
- * class is less than nonblanks, then
- * connecting this edge would be a shortcut
- * loop and so we must not do so.
- */
- if (workspace[y*W+x] == 3) {
- int ae, be;
-
- ae = dsf_canonify(dsf, ac);
- be = dsf_canonify(dsf, bc);
-
- if (ae == be) {
- /*
- * We have a loop. Is it a shortcut?
- */
- if (dsfsize[ae] < nonblanks) {
- /*
- * Yes! Mark this edge disconnected.
- */
- workspace[y*W+x] = 2;
- done_something = TRUE;
-#ifdef SOLVER_DIAGNOSTICS
- printf("edge (%d,%d)-(%d,%d) would create"
- " a shortcut loop, hence must be"
- " disconnected\n", x/2, y/2,
- (x+1)/2, (y+1)/2);
-#endif
- }
- }
- }
- } else if ((y & x) & 1) {
- /*
- * (x,y) are the workspace coordinates of a
- * square field. Go through its possible
- * (non-blank) states and see if any gives
- * rise to a shortcut loop.
- *
- * This is slightly fiddly, because we have
- * to check whether this square is already
- * part of the same equivalence class as
- * the things it's joining.
- */
- int ae = dsf_canonify(dsf, (y/2)*w+(x/2));
-
- for (b = 2; b < 0xD; b++)
- if (workspace[y*W+x] & (1<<b)) {
- /*
- * Find the equivalence classes of
- * the two squares this one would
- * connect if it were in this
- * state.
- */
- int e = -1;
-
- for (d = 1; d <= 8; d += d) if (b & d) {
- int xx = x/2 + DX(d), yy = y/2 + DY(d);
- int ee = dsf_canonify(dsf, yy*w+xx);
-
- if (e == -1)
- ee = e;
- else if (e != ee)
- e = -2;
- }
-
- if (e >= 0) {
- /*
- * This square state would form
- * a loop on equivalence class
- * e. Measure the size of that
- * loop, and see if it's a
- * shortcut.
- */
- int loopsize = dsfsize[e];
- if (e != ae)
- loopsize++;/* add the square itself */
- if (loopsize < nonblanks) {
- /*
- * It is! Mark this square
- * state invalid.
- */
- workspace[y*W+x] &= ~(1<<b);
- done_something = TRUE;
-#ifdef SOLVER_DIAGNOSTICS
- printf("square (%d,%d) would create a "
- "shortcut loop in state %d, "
- "hence cannot be\n",
- x/2, y/2, b);
-#endif
- }
- }
- }
- }
- }
-
- if (done_something)
- continue;
-
- /*
- * If we reach here, there is nothing left we can do.
- * Return 2 for ambiguous puzzle.
- */
- ret = 2;
- goto cleanup;
- }
-
- /*
- * If we reach _here_, it's by `break' out of the main loop,
- * which means we've successfully achieved a solution. This
- * means that we expect every square to be nailed down to
- * exactly one possibility. Transcribe those possibilities into
- * the result array.
- */
- for (y = 0; y < h; y++)
- for (x = 0; x < w; x++) {
- for (b = 0; b < 0xD; b++)
- if (workspace[(2*y+1)*W+(2*x+1)] == (1<<b)) {
- result[y*w+x] = b;
- break;
- }
- assert(b < 0xD); /* we should have had a break by now */
- }
-
- cleanup:
- sfree(dsfsize);
- sfree(dsf);
- sfree(workspace);
- assert(ret >= 0);
- return ret;
-}
-
-/* ----------------------------------------------------------------------
- * Loop generator.
- */
-
-void pearl_loopgen(int w, int h, char *grid, random_state *rs)
-{
- int *options, *mindist, *maxdist, *list;
- int x, y, d, total, n, area, limit;
-
- /*
- * We're eventually going to have to return a w-by-h array
- * containing line segment data. However, it's more convenient
- * while actually generating the loop to consider the problem
- * as a (w-1) by (h-1) array in which some squares are `inside'
- * and some `outside'.
- *
- * I'm going to use the top left corner of my return array in
- * the latter manner until the end of the function.
- */
-
- /*
- * To begin with, all squares are outside (0), except for one
- * randomly selected one which is inside (1).
- */
- memset(grid, 0, w*h);
- x = random_upto(rs, w-1);
- y = random_upto(rs, h-1);
- grid[y*w+x] = 1;
-
- /*
- * I'm also going to need an array to store the possible
- * options for the next extension of the grid.
- */
- options = snewn(w*h, int);
- for (x = 0; x < w*h; x++)
- options[x] = 0;
-
- /*
- * And some arrays and a list for breadth-first searching.
- */
- mindist = snewn(w*h, int);
- maxdist = snewn(w*h, int);
- list = snewn(w*h, int);
-
- /*
- * Now we repeatedly scan the grid for feasible squares into
- * which we can extend our loop, pick one, and do it.
- */
- area = 1;
-
- while (1) {
-#ifdef LOOPGEN_DIAGNOSTICS
- for (y = 0; y < h; y++) {
- for (x = 0; x < w; x++)
- printf("%d", grid[y*w+x]);
- printf("\n");
- }
- printf("\n");
-#endif
-
- /*
- * Our primary aim in growing this loop is to make it
- * reasonably _dense_ in the target rectangle. That is, we
- * want the maximum over all squares of the minimum
- * distance from that square to the loop to be small.
- *
- * Therefore, we start with a breadth-first search of the
- * grid to find those minimum distances.
- */
- {
- int head = 0, tail = 0;
- int i;
-
- for (i = 0; i < w*h; i++) {
- mindist[i] = -1;
- if (grid[i]) {
- mindist[i] = 0;
- list[tail++] = i;
- }
- }
-
- while (head < tail) {
- i = list[head++];
- y = i / w;
- x = i % w;
- for (d = 1; d <= 8; d += d) {
- int xx = x + DX(d), yy = y + DY(d);
- if (xx >= 0 && xx < w && yy >= 0 && yy < h &&
- mindist[yy*w+xx] < 0) {
- mindist[yy*w+xx] = mindist[i] + 1;
- list[tail++] = yy*w+xx;
- }
- }
- }
-
- /*
- * Having done the BFS, we now backtrack along its path
- * to determine the most distant square that each
- * square is on the shortest path to. This tells us
- * which of the loop extension candidates (all of which
- * are squares marked 1) is most desirable to extend
- * into in terms of minimising the maximum distance
- * from any empty square to the nearest loop square.
- */
- for (head = tail; head-- > 0 ;) {
- int max;
-
- i = list[head];
- y = i / w;
- x = i % w;
-
- max = mindist[i];
-
- for (d = 1; d <= 8; d += d) {
- int xx = x + DX(d), yy = y + DY(d);
- if (xx >= 0 && xx < w && yy >= 0 && yy < h &&
- mindist[yy*w+xx] > mindist[i] &&
- maxdist[yy*w+xx] > max) {
- max = maxdist[yy*w+xx];
- }
- }
-
- maxdist[i] = max;
- }
- }
-
- /*
- * A square is a viable candidate for extension of our loop
- * if and only if the following conditions are all met:
- * - It is currently labelled 0.
- * - At least one of its four orthogonal neighbours is
- * labelled 1.
- * - If you consider its eight orthogonal and diagonal
- * neighbours to form a ring, that ring contains at most
- * one contiguous run of 1s. (It must also contain at
- * _least_ one, of course, but that's already guaranteed
- * by the previous condition so there's no need to test
- * it separately.)
- */
- total = 0;
- for (y = 0; y < h-1; y++)
- for (x = 0; x < w-1; x++) {
- int ring[8];
- int rx, neighbours, runs, dist;
-
- dist = maxdist[y*w+x];
- options[y*w+x] = 0;
-
- if (grid[y*w+x])
- continue; /* it isn't labelled 0 */
-
- neighbours = 0;
- for (rx = 0, d = 1; d <= 8; rx += 2, d += d) {
- int x2 = x + DX(d), y2 = y + DY(d);
- int x3 = x2 + DX(A(d)), y3 = y2 + DY(A(d));
- int g2 = (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h ?
- grid[y2*w+x2] : 0);
- int g3 = (x3 >= 0 && x3 < w && y3 >= 0 && y3 < h ?
- grid[y3*w+x3] : 0);
- ring[rx] = g2;
- ring[rx+1] = g3;
- if (g2)
- neighbours++;
- }
-
- if (!neighbours)
- continue; /* it doesn't have a 1 neighbour */
-
- runs = 0;
- for (rx = 0; rx < 8; rx++)
- if (ring[rx] && !ring[(rx+1) & 7])
- runs++;
-
- if (runs > 1)
- continue; /* too many runs of 1s */
-
- /*
- * Now we know this square is a viable extension
- * candidate. Mark it.
- *
- * FIXME: probabilistic prioritisation based on
- * perimeter perturbation? (Wow, must keep that
- * phrase.)
- */
- options[y*w+x] = dist * (4-neighbours) * (4-neighbours);
- total += options[y*w+x];
- }
-
- if (!total)
- break; /* nowhere to go! */
-
- /*
- * Now pick a random one of the viable extension squares,
- * and extend into it.
- */
- n = random_upto(rs, total);
- for (y = 0; y < h-1; y++)
- for (x = 0; x < w-1; x++) {
- assert(n >= 0);
- if (options[y*w+x] > n)
- goto found; /* two-level break */
- n -= options[y*w+x];
- }
- assert(!"We shouldn't ever get here");
- found:
- grid[y*w+x] = 1;
- area++;
-
- /*
- * We terminate the loop when around 7/12 of the grid area
- * is full, but we also require that the loop has reached
- * all four edges.
- */
- limit = random_upto(rs, (w-1)*(h-1)) + 13*(w-1)*(h-1);
- if (24 * area > limit) {
- int l = FALSE, r = FALSE, u = FALSE, d = FALSE;
- for (x = 0; x < w; x++) {
- if (grid[0*w+x])
- u = TRUE;
- if (grid[(h-2)*w+x])
- d = TRUE;
- }
- for (y = 0; y < h; y++) {
- if (grid[y*w+0])
- l = TRUE;
- if (grid[y*w+(w-2)])
- r = TRUE;
- }
- if (l && r && u && d)
- break;
- }
- }
-
- sfree(list);
- sfree(maxdist);
- sfree(mindist);
- sfree(options);
-
-#ifdef LOOPGEN_DIAGNOSTICS
- printf("final loop:\n");
- for (y = 0; y < h; y++) {
- for (x = 0; x < w; x++)
- printf("%d", grid[y*w+x]);
- printf("\n");
- }
- printf("\n");
-#endif
-
- /*
- * Now convert this array of 0s and 1s into an array of path
- * components.
- */
- for (y = h; y-- > 0 ;) {
- for (x = w; x-- > 0 ;) {
- /*
- * Examine the four grid squares of which (x,y) are in
- * the bottom right, to determine the output for this
- * square.
- */
- int ul = (x > 0 && y > 0 ? grid[(y-1)*w+(x-1)] : 0);
- int ur = (y > 0 ? grid[(y-1)*w+x] : 0);
- int dl = (x > 0 ? grid[y*w+(x-1)] : 0);
- int dr = grid[y*w+x];
- int type = 0;
-
- if (ul != ur) type |= U;
- if (dl != dr) type |= D;
- if (ul != dl) type |= L;
- if (ur != dr) type |= R;
-
- assert((bLR|bUD|bLU|bLD|bRU|bRD|bBLANK) & (1 << type));
-
- grid[y*w+x] = type;
-
- }
- }
-
-#if defined LOOPGEN_DIAGNOSTICS && !defined GENERATION_DIAGNOSTICS
- printf("as returned:\n");
- for (y = 0; y < h; y++) {
- for (x = 0; x < w; x++) {
- int type = grid[y*w+x];
- char s[5], *p = s;
- if (type & L) *p++ = 'L';
- if (type & R) *p++ = 'R';
- if (type & U) *p++ = 'U';
- if (type & D) *p++ = 'D';
- *p = '\0';
- printf("%3s", s);
- }
- printf("\n");
- }
- printf("\n");
-#endif
-}
-
-static char *new_game_desc(game_params *params, random_state *rs,
- char **aux, int interactive)
-{
- char *grid, *clues;
- int *clueorder;
- int w = 10, h = 10;
- int x, y, d, ret, i;
-
-#if 0
- clues = snewn(7*7, char);
- memcpy(clues,
- "\0\1\0\0\2\0\0"
- "\0\0\0\2\0\0\0"
- "\0\0\0\2\0\0\1"
- "\2\0\0\2\0\0\0"
- "\2\0\0\0\0\0\1"
- "\0\0\1\0\0\2\0"
- "\0\0\2\0\0\0\0", 7*7);
- grid = snewn(7*7, char);
- printf("%d\n", pearl_solve(7, 7, clues, grid));
-#elif 0
- clues = snewn(10*10, char);
- memcpy(clues,
- "\0\0\2\0\2\0\0\0\0\0"
- "\0\0\0\0\2\0\0\0\1\0"
- "\0\0\1\0\1\0\2\0\0\0"
- "\0\0\0\2\0\0\2\0\0\0"
- "\1\0\0\0\0\2\0\0\0\2"
- "\0\0\2\0\0\0\0\2\0\0"
- "\0\0\1\0\0\0\2\0\0\0"
- "\2\0\0\0\1\0\0\0\0\2"
- "\0\0\0\0\0\0\2\2\0\0"
- "\0\0\1\0\0\0\0\0\0\1", 10*10);
- grid = snewn(10*10, char);
- printf("%d\n", pearl_solve(10, 10, clues, grid));
-#elif 0
- clues = snewn(10*10, char);
- memcpy(clues,
- "\0\0\0\0\0\0\1\0\0\0"
- "\0\1\0\1\2\0\0\0\0\2"
- "\0\0\0\0\0\0\0\0\0\1"
- "\2\0\0\1\2\2\1\0\0\0"
- "\1\0\0\0\0\0\0\1\0\0"
- "\0\0\2\0\0\0\0\0\0\2"
- "\0\0\0\2\1\2\1\0\0\2"
- "\2\0\0\0\0\0\0\0\0\0"
- "\2\0\0\0\0\1\1\0\2\0"
- "\0\0\0\2\0\0\0\0\0\0", 10*10);
- grid = snewn(10*10, char);
- printf("%d\n", pearl_solve(10, 10, clues, grid));
-#endif
-
- grid = snewn(w*h, char);
- clues = snewn(w*h, char);
- clueorder = snewn(w*h, int);
-
- while (1) {
- pearl_loopgen(w, h, grid, rs);
-
-#ifdef GENERATION_DIAGNOSTICS
- printf("grid array:\n");
- for (y = 0; y < h; y++) {
- for (x = 0; x < w; x++) {
- int type = grid[y*w+x];
- char s[5], *p = s;
- if (type & L) *p++ = 'L';
- if (type & R) *p++ = 'R';
- if (type & U) *p++ = 'U';
- if (type & D) *p++ = 'D';
- *p = '\0';
- printf("%2s ", s);
- }
- printf("\n");
- }
- printf("\n");
-#endif
-
- /*
- * Set up the maximal clue array.
- */
- for (y = 0; y < h; y++)
- for (x = 0; x < w; x++) {
- int type = grid[y*w+x];
-
- clues[y*w+x] = NOCLUE;
-
- if ((bLR|bUD) & (1 << type)) {
- /*
- * This is a straight; see if it's a viable
- * candidate for a straight clue. It qualifies if
- * at least one of the squares it connects to is a
- * corner.
- */
- for (d = 1; d <= 8; d += d) if (type & d) {
- int xx = x + DX(d), yy = y + DY(d);
- assert(xx >= 0 && xx < w && yy >= 0 && yy < h);
- if ((bLU|bLD|bRU|bRD) & (1 << grid[yy*w+xx]))
- break;
- }
- if (d <= 8) /* we found one */
- clues[y*w+x] = STRAIGHT;
- } else if ((bLU|bLD|bRU|bRD) & (1 << type)) {
- /*
- * This is a corner; see if it's a viable candidate
- * for a corner clue. It qualifies if all the
- * squares it connects to are straights.
- */
- for (d = 1; d <= 8; d += d) if (type & d) {
- int xx = x + DX(d), yy = y + DY(d);
- assert(xx >= 0 && xx < w && yy >= 0 && yy < h);
- if (!((bLR|bUD) & (1 << grid[yy*w+xx])))
- break;
- }
- if (d > 8) /* we didn't find a counterexample */
- clues[y*w+x] = CORNER;
- }
- }
-
-#ifdef GENERATION_DIAGNOSTICS
- printf("clue array:\n");
- for (y = 0; y < h; y++) {
- for (x = 0; x < w; x++) {
- printf("%c", " *O"[(unsigned char)clues[y*w+x]]);
- }
- printf("\n");
- }
- printf("\n");
-#endif
-
- /*
- * See if we can solve the puzzle just like this.
- */
- ret = pearl_solve(w, h, clues, grid);
- assert(ret > 0); /* shouldn't be inconsistent! */
- if (ret != 1)
- continue; /* go round and try again */
-
- /*
- * Now shuffle the grid points and gradually remove the
- * clues to find a minimal set which still leaves the
- * puzzle soluble.
- */
- for (i = 0; i < w*h; i++)
- clueorder[i] = i;
- shuffle(clueorder, w*h, sizeof(*clueorder), rs);
- for (i = 0; i < w*h; i++) {
- int clue;
-
- y = clueorder[i] / w;
- x = clueorder[i] % w;
-
- if (clues[y*w+x] == 0)
- continue;
-
- clue = clues[y*w+x];
- clues[y*w+x] = 0; /* try removing this clue */
-
- ret = pearl_solve(w, h, clues, grid);
- assert(ret > 0);
- if (ret != 1)
- clues[y*w+x] = clue; /* oops, put it back again */
- }
-
-#ifdef FINISHED_PUZZLE
- printf("clue array:\n");
- for (y = 0; y < h; y++) {
- for (x = 0; x < w; x++) {
- printf("%c", " *O"[(unsigned char)clues[y*w+x]]);
- }
- printf("\n");
- }
- printf("\n");
-#endif
-
- break; /* got it */
- }
-
- sfree(grid);
- sfree(clues);
- sfree(clueorder);
-
- return dupstr("FIXME");
-}
-
-static char *validate_desc(game_params *params, char *desc)
-{
- return NULL;
-}
-
-static game_state *new_game(midend *me, game_params *params, char *desc)
-{
- game_state *state = snew(game_state);
-
- state->FIXME = 0;
-
- return state;
-}
-
-static game_state *dup_game(game_state *state)
-{
- game_state *ret = snew(game_state);
-
- ret->FIXME = state->FIXME;
-
- return ret;
-}
-
-static void free_game(game_state *state)
-{
- sfree(state);
-}
-
-static char *solve_game(game_state *state, game_state *currstate,
- char *aux, char **error)
-{
- return NULL;
-}
-
-static int game_can_format_as_text_now(game_params *params)
-{
- return TRUE;
-}
-
-static char *game_text_format(game_state *state)
-{
- return NULL;
-}
-
-static game_ui *new_ui(game_state *state)
-{
- return NULL;
-}
-
-static void free_ui(game_ui *ui)
-{
-}
-
-static char *encode_ui(game_ui *ui)
-{
- return NULL;
-}
-
-static void decode_ui(game_ui *ui, char *encoding)
-{
-}
-
-static void game_changed_state(game_ui *ui, game_state *oldstate,
- game_state *newstate)
-{
-}
-
-struct game_drawstate {
- int tilesize;
- int FIXME;
-};
-
-static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
- int x, int y, int button)
-{
- return NULL;
-}
-
-static game_state *execute_move(game_state *state, char *move)
-{
- return NULL;
-}
-
-/* ----------------------------------------------------------------------
- * Drawing routines.
- */
-
-static void game_compute_size(game_params *params, int tilesize,
- int *x, int *y)
-{
- *x = *y = 10 * tilesize; /* FIXME */
-}
-
-static void game_set_size(drawing *dr, game_drawstate *ds,
- game_params *params, int tilesize)
-{
- ds->tilesize = tilesize;
-}
-
-static float *game_colours(frontend *fe, int *ncolours)
-{
- float *ret = snewn(3 * NCOLOURS, float);
-
- frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
-
- *ncolours = NCOLOURS;
- return ret;
-}
-
-static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
-{
- struct game_drawstate *ds = snew(struct game_drawstate);
-
- ds->tilesize = 0;
- ds->FIXME = 0;
-
- return ds;
-}
-
-static void game_free_drawstate(drawing *dr, game_drawstate *ds)
-{
- sfree(ds);
-}
-
-static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
- game_state *state, int dir, game_ui *ui,
- float animtime, float flashtime)
-{
- /*
- * The initial contents of the window are not guaranteed and
- * can vary with front ends. To be on the safe side, all games
- * should start by drawing a big background-colour rectangle
- * covering the whole window.
- */
- draw_rect(dr, 0, 0, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND);
-}
-
-static float game_anim_length(game_state *oldstate, game_state *newstate,
- int dir, game_ui *ui)
-{
- return 0.0F;
-}
-
-static float game_flash_length(game_state *oldstate, game_state *newstate,
- int dir, game_ui *ui)
-{
- return 0.0F;
-}
-
-static int game_status(game_state *state)
-{
- return 0;
-}
-
-static int game_timing_state(game_state *state, game_ui *ui)
-{
- return TRUE;
-}
-
-static void game_print_size(game_params *params, float *x, float *y)
-{
-}
-
-static void game_print(drawing *dr, game_state *state, int tilesize)
-{
-}
-
-#ifdef COMBINED
-#define thegame pearl
-#endif
-
-const struct game thegame = {
- "Pearl", NULL, NULL,
- default_params,
- game_fetch_preset,
- decode_params,
- encode_params,
- free_params,
- dup_params,
- FALSE, game_configure, custom_params,
- validate_params,
- new_game_desc,
- validate_desc,
- new_game,
- dup_game,
- free_game,
- FALSE, solve_game,
- FALSE, game_can_format_as_text_now, game_text_format,
- new_ui,
- free_ui,
- encode_ui,
- decode_ui,
- game_changed_state,
- interpret_move,
- execute_move,
- 20 /* FIXME */, game_compute_size, game_set_size,
- game_colours,
- game_new_drawstate,
- game_free_drawstate,
- game_redraw,
- game_anim_length,
- game_flash_length,
- game_status,
- FALSE, FALSE, game_print_size, game_print,
- FALSE, /* wants_statusbar */
- FALSE, game_timing_state,
- 0, /* flags */
-};
~mdw / sgt / puzzles / blobdiff