ref: b16eece9fc502afb9dfb0aca9fd7bfba2239d3e3
parent: b2d7429d539238258ca6f9061da5a25a0835f2a9
author: Simon Tatham <anakin@pobox.com>
date: Sun Jan 22 09:14:26 EST 2012
New puzzle! Or rather, new-ish, because this one has been lying around in the 'unfinished' directory for a while, and has now been finished up thanks to James Harvey putting in some effort and galvanising me to put in the rest. This is 'Pearl', an implementation of Nikoli's 'Masyu'. The code in Loopy that generates a random loop along grid edges to use as the puzzle solution has been abstracted out into loopgen.[ch] so that Pearl can use it for its puzzle solutions too. I've also introduced a new utility module called 'tdq' (for 'to-do queue'). [originally from svn r9379]
--- a/icons/Makefile
+++ b/icons/Makefile
@@ -2,8 +2,8 @@
PUZZLES = blackbox bridges cube dominosa fifteen filling flip galaxies guess \
inertia keen lightup loopy magnets map mines net netslide pattern \
- pegs range rect samegame signpost singles sixteen slant solo tents \
- towers twiddle unequal untangle
+ pearl pegs range rect samegame signpost singles sixteen slant solo \
+ tents towers twiddle unequal untangle
BASE = $(patsubst %,%-base.png,$(PUZZLES))
WEB = $(patsubst %,%-web.png,$(PUZZLES))
@@ -69,6 +69,7 @@
net-ibase.png : override CROP=193x193 113x113+0+80
netslide-ibase.png : override CROP=289x289 144x144+0+0
pattern-ibase.png : override CROP=384x384 223x223+0+0
+pearl-ibase.png : override CROP=216x216 94x94+108+15
pegs-ibase.png : override CROP=263x263 147x147+116+0
range-ibase.png : override CROP=256x256 98x98+111+15
rect-ibase.png : override CROP=205x205 115x115+90+0
--- /dev/null
+++ b/icons/pearl.sav
@@ -1,0 +1,23 @@
+SAVEFILE:41:Simon Tatham's Portable Puzzle Collection
+VERSION :1:1
+GAME :5:Pearl
+PARAMS :5:6x6dt
+CPARAMS :5:6x6dt
+SEED :15:901944054393278
+DESC :17:BbBfWcWbWBaBeWgWa
+AUXINFO :72:f8bbe71b9be753d5fa143df207d7797ba62a9b3996eb8b8889487e1a2bd659d91a5e73e1
+NSTATES :2:14
+STATEPOS:1:7
+MOVE :55:F4,2,0;F1,1,0;F4,1,0;F1,0,0;F8,0,0;F2,0,1;F8,0,1;F2,0,2
+MOVE :27:F1,0,3;F4,1,3;F1,1,3;F4,2,3
+MOVE :27:F8,3,0;F2,3,1;F8,3,1;F2,3,2
+MOVE :97:F2,4,2;F8,4,1;F2,4,1;F8,4,0;F1,4,0;F4,5,0;F8,5,0;F2,5,1;F8,5,1;F2,5,2;F8,5,2;F2,5,3;F4,5,3;F1,4,3
+MOVE :13:F4,4,2;F1,3,2
+MOVE :13:F4,3,0;F1,2,0
+MOVE :69:F2,2,3;F8,2,2;F2,2,2;F8,2,1;F4,2,1;F1,1,1;F8,1,1;F2,1,2;F4,1,2;F1,0,2
+MOVE :41:F8,0,3;F2,0,4;F8,0,4;F2,0,5;F1,0,5;F4,1,5
+MOVE :27:F1,1,4;F4,2,4;F1,2,4;F4,3,4
+MOVE :13:F8,1,4;F2,1,5
+MOVE :55:F1,3,5;F4,4,5;F1,4,5;F4,5,5;F2,5,5;F8,5,4;F4,5,4;F1,4,4
+MOVE :13:F2,3,5;F8,3,4
+MOVE :13:F2,4,4;F8,4,3
--- /dev/null
+++ b/loopgen.c
@@ -1,0 +1,536 @@
+/*
+ * loopgen.c: loop generation functions for grid.[ch].
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stddef.h>
+#include <string.h>
+#include <assert.h>
+#include <ctype.h>
+#include <math.h>
+
+#include "puzzles.h"
+#include "tree234.h"
+#include "grid.h"
+#include "loopgen.h"
+
+
+/* We're going to store lists of current candidate faces for colouring black
+ * or white.
+ * Each face gets a 'score', which tells us how adding that face right
+ * now would affect the curliness of the solution loop. We're trying to
+ * maximise that quantity so will bias our random selection of faces to
+ * colour those with high scores */
+struct face_score {+ int white_score;
+ int black_score;
+ unsigned long random;
+ /* No need to store a grid_face* here. The 'face_scores' array will
+ * be a list of 'face_score' objects, one for each face of the grid, so
+ * the position (index) within the 'face_scores' array will determine
+ * which face corresponds to a particular face_score.
+ * Having a single 'face_scores' array for all faces simplifies memory
+ * management, and probably improves performance, because we don't have to
+ * malloc/free each individual face_score, and we don't have to maintain
+ * a mapping from grid_face* pointers to face_score* pointers.
+ */
+};
+
+static int generic_sort_cmpfn(void *v1, void *v2, size_t offset)
+{+ struct face_score *f1 = v1;
+ struct face_score *f2 = v2;
+ int r;
+
+ r = *(int *)((char *)f2 + offset) - *(int *)((char *)f1 + offset);
+ if (r) {+ return r;
+ }
+
+ if (f1->random < f2->random)
+ return -1;
+ else if (f1->random > f2->random)
+ return 1;
+
+ /*
+ * It's _just_ possible that two faces might have been given
+ * the same random value. In that situation, fall back to
+ * comparing based on the positions within the face_scores list.
+ * This introduces a tiny directional bias, but not a significant one.
+ */
+ return f1 - f2;
+}
+
+static int white_sort_cmpfn(void *v1, void *v2)
+{+ return generic_sort_cmpfn(v1, v2, offsetof(struct face_score,white_score));
+}
+
+static int black_sort_cmpfn(void *v1, void *v2)
+{+ return generic_sort_cmpfn(v1, v2, offsetof(struct face_score,black_score));
+}
+
+/* 'board' is an array of enum face_colour, indicating which faces are
+ * currently black/white/grey. 'colour' is FACE_WHITE or FACE_BLACK.
+ * Returns whether it's legal to colour the given face with this colour. */
+static int can_colour_face(grid *g, char* board, int face_index,
+ enum face_colour colour)
+{+ int i, j;
+ grid_face *test_face = g->faces + face_index;
+ grid_face *starting_face, *current_face;
+ grid_dot *starting_dot;
+ int transitions;
+ int current_state, s; /* booleans: equal or not-equal to 'colour' */
+ int found_same_coloured_neighbour = FALSE;
+ assert(board[face_index] != colour);
+
+ /* Can only consider a face for colouring if it's adjacent to a face
+ * with the same colour. */
+ for (i = 0; i < test_face->order; i++) {+ grid_edge *e = test_face->edges[i];
+ grid_face *f = (e->face1 == test_face) ? e->face2 : e->face1;
+ if (FACE_COLOUR(f) == colour) {+ found_same_coloured_neighbour = TRUE;
+ break;
+ }
+ }
+ if (!found_same_coloured_neighbour)
+ return FALSE;
+
+ /* Need to avoid creating a loop of faces of this colour around some
+ * differently-coloured faces.
+ * Also need to avoid meeting a same-coloured face at a corner, with
+ * other-coloured faces in between. Here's a simple test that (I believe)
+ * takes care of both these conditions:
+ *
+ * Take the circular path formed by this face's edges, and inflate it
+ * slightly outwards. Imagine walking around this path and consider
+ * the faces that you visit in sequence. This will include all faces
+ * touching the given face, either along an edge or just at a corner.
+ * Count the number of 'colour'/not-'colour' transitions you encounter, as
+ * you walk along the complete loop. This will obviously turn out to be
+ * an even number.
+ * If 0, we're either in the middle of an "island" of this colour (should
+ * be impossible as we're not supposed to create black or white loops),
+ * or we're about to start a new island - also not allowed.
+ * If 4 or greater, there are too many separate coloured regions touching
+ * this face, and colouring it would create a loop or a corner-violation.
+ * The only allowed case is when the count is exactly 2. */
+
+ /* i points to a dot around the test face.
+ * j points to a face around the i^th dot.
+ * The current face will always be:
+ * test_face->dots[i]->faces[j]
+ * We assume dots go clockwise around the test face,
+ * and faces go clockwise around dots. */
+
+ /*
+ * The end condition is slightly fiddly. In sufficiently strange
+ * degenerate grids, our test face may be adjacent to the same
+ * other face multiple times (typically if it's the exterior
+ * face). Consider this, in particular:
+ *
+ * +--+
+ * | |
+ * +--+--+
+ * | | |
+ * +--+--+
+ *
+ * The bottom left face there is adjacent to the exterior face
+ * twice, so we can't just terminate our iteration when we reach
+ * the same _face_ we started at. Furthermore, we can't
+ * condition on having the same (i,j) pair either, because
+ * several (i,j) pairs identify the bottom left contiguity with
+ * the exterior face! We canonicalise the (i,j) pair by taking
+ * one step around before we set the termination tracking.
+ */
+
+ i = j = 0;
+ current_face = test_face->dots[0]->faces[0];
+ if (current_face == test_face) {+ j = 1;
+ current_face = test_face->dots[0]->faces[1];
+ }
+ transitions = 0;
+ current_state = (FACE_COLOUR(current_face) == colour);
+ starting_dot = NULL;
+ starting_face = NULL;
+ while (TRUE) {+ /* Advance to next face.
+ * Need to loop here because it might take several goes to
+ * find it. */
+ while (TRUE) {+ j++;
+ if (j == test_face->dots[i]->order)
+ j = 0;
+
+ if (test_face->dots[i]->faces[j] == test_face) {+ /* Advance to next dot round test_face, then
+ * find current_face around new dot
+ * and advance to the next face clockwise */
+ i++;
+ if (i == test_face->order)
+ i = 0;
+ for (j = 0; j < test_face->dots[i]->order; j++) {+ if (test_face->dots[i]->faces[j] == current_face)
+ break;
+ }
+ /* Must actually find current_face around new dot,
+ * or else something's wrong with the grid. */
+ assert(j != test_face->dots[i]->order);
+ /* Found, so advance to next face and try again */
+ } else {+ break;
+ }
+ }
+ /* (i,j) are now advanced to next face */
+ current_face = test_face->dots[i]->faces[j];
+ s = (FACE_COLOUR(current_face) == colour);
+ if (!starting_dot) {+ starting_dot = test_face->dots[i];
+ starting_face = current_face;
+ current_state = s;
+ } else {+ if (s != current_state) {+ ++transitions;
+ current_state = s;
+ if (transitions > 2)
+ break;
+ }
+ if (test_face->dots[i] == starting_dot &&
+ current_face == starting_face)
+ break;
+ }
+ }
+
+ return (transitions == 2) ? TRUE : FALSE;
+}
+
+/* Count the number of neighbours of 'face', having colour 'colour' */
+static int face_num_neighbours(grid *g, char *board, grid_face *face,
+ enum face_colour colour)
+{+ int colour_count = 0;
+ int i;
+ grid_face *f;
+ grid_edge *e;
+ for (i = 0; i < face->order; i++) {+ e = face->edges[i];
+ f = (e->face1 == face) ? e->face2 : e->face1;
+ if (FACE_COLOUR(f) == colour)
+ ++colour_count;
+ }
+ return colour_count;
+}
+
+/* The 'score' of a face reflects its current desirability for selection
+ * as the next face to colour white or black. We want to encourage moving
+ * into grey areas and increasing loopiness, so we give scores according to
+ * how many of the face's neighbours are currently coloured the same as the
+ * proposed colour. */
+static int face_score(grid *g, char *board, grid_face *face,
+ enum face_colour colour)
+{+ /* Simple formula: score = 0 - num. same-coloured neighbours,
+ * so a higher score means fewer same-coloured neighbours. */
+ return -face_num_neighbours(g, board, face, colour);
+}
+
+/*
+ * Generate a new complete random closed loop for the given grid.
+ *
+ * The method is to generate a WHITE/BLACK colouring of all the faces,
+ * such that the WHITE faces will define the inside of the path, and the
+ * BLACK faces define the outside.
+ * To do this, we initially colour all faces GREY. The infinite space outside
+ * the grid is coloured BLACK, and we choose a random face to colour WHITE.
+ * Then we gradually grow the BLACK and the WHITE regions, eliminating GREY
+ * faces, until the grid is filled with BLACK/WHITE. As we grow the regions,
+ * we avoid creating loops of a single colour, to preserve the topological
+ * shape of the WHITE and BLACK regions.
+ * We also try to make the boundary as loopy and twisty as possible, to avoid
+ * generating paths that are uninteresting.
+ * The algorithm works by choosing a BLACK/WHITE colour, then choosing a GREY
+ * face that can be coloured with that colour (without violating the
+ * topological shape of that region). It's not obvious, but I think this
+ * algorithm is guaranteed to terminate without leaving any GREY faces behind.
+ * Indeed, if there are any GREY faces at all, both the WHITE and BLACK
+ * regions can be grown.
+ * This is checked using assert()ions, and I haven't seen any failures yet.
+ *
+ * Hand-wavy proof: imagine what can go wrong...
+ *
+ * Could the white faces get completely cut off by the black faces, and still
+ * leave some grey faces remaining?
+ * No, because then the black faces would form a loop around both the white
+ * faces and the grey faces, which is disallowed because we continually
+ * maintain the correct topological shape of the black region.
+ * Similarly, the black faces can never get cut off by the white faces. That
+ * means both the WHITE and BLACK regions always have some room to grow into
+ * the GREY regions.
+ * Could it be that we can't colour some GREY face, because there are too many
+ * WHITE/BLACK transitions as we walk round the face? (see the
+ * can_colour_face() function for details)
+ * No. Imagine otherwise, and we see WHITE/BLACK/WHITE/BLACK as we walk
+ * around the face. The two WHITE faces would be connected by a WHITE path,
+ * and the BLACK faces would be connected by a BLACK path. These paths would
+ * have to cross, which is impossible.
+ * Another thing that could go wrong: perhaps we can't find any GREY face to
+ * colour WHITE, because it would create a loop-violation or a corner-violation
+ * with the other WHITE faces?
+ * This is a little bit tricky to prove impossible. Imagine you have such a
+ * GREY face (that is, if you coloured it WHITE, you would create a WHITE loop
+ * or corner violation).
+ * That would cut all the non-white area into two blobs. One of those blobs
+ * must be free of BLACK faces (because the BLACK stuff is a connected blob).
+ * So we have a connected GREY area, completely surrounded by WHITE
+ * (including the GREY face we've tentatively coloured WHITE).
+ * A well-known result in graph theory says that you can always find a GREY
+ * face whose removal leaves the remaining GREY area connected. And it says
+ * there are at least two such faces, so we can always choose the one that
+ * isn't the "tentative" GREY face. Colouring that face WHITE leaves
+ * everything nice and connected, including that "tentative" GREY face which
+ * acts as a gateway to the rest of the non-WHITE grid.
+ */
+void generate_loop(grid *g, char *board, random_state *rs,
+ loopgen_bias_fn_t bias, void *biasctx)
+{+ int i, j;
+ int num_faces = g->num_faces;
+ struct face_score *face_scores; /* Array of face_score objects */
+ struct face_score *fs; /* Points somewhere in the above list */
+ struct grid_face *cur_face;
+ tree234 *lightable_faces_sorted;
+ tree234 *darkable_faces_sorted;
+ int *face_list;
+ int do_random_pass;
+
+ /* Make a board */
+ memset(board, FACE_GREY, num_faces);
+
+ /* Create and initialise the list of face_scores */
+ face_scores = snewn(num_faces, struct face_score);
+ for (i = 0; i < num_faces; i++) {+ face_scores[i].random = random_bits(rs, 31);
+ face_scores[i].black_score = face_scores[i].white_score = 0;
+ }
+
+ /* Colour a random, finite face white. The infinite face is implicitly
+ * coloured black. Together, they will seed the random growth process
+ * for the black and white areas. */
+ i = random_upto(rs, num_faces);
+ board[i] = FACE_WHITE;
+
+ /* We need a way of favouring faces that will increase our loopiness.
+ * We do this by maintaining a list of all candidate faces sorted by
+ * their score and choose randomly from that with appropriate skew.
+ * In order to avoid consistently biasing towards particular faces, 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 face 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 faces in
+ * any one run but that doesn't actually matter. */
+
+ lightable_faces_sorted = newtree234(white_sort_cmpfn);
+ darkable_faces_sorted = newtree234(black_sort_cmpfn);
+
+ /* Initialise the lists of lightable and darkable faces. This is
+ * slightly different from the code inside the while-loop, because we need
+ * to check every face of the board (the grid structure does not keep a
+ * list of the infinite face's neighbours). */
+ for (i = 0; i < num_faces; i++) {+ grid_face *f = g->faces + i;
+ struct face_score *fs = face_scores + i;
+ if (board[i] != FACE_GREY) continue;
+ /* We need the full colourability check here, it's not enough simply
+ * to check neighbourhood. On some grids, a neighbour of the infinite
+ * face is not necessarily darkable. */
+ if (can_colour_face(g, board, i, FACE_BLACK)) {+ fs->black_score = face_score(g, board, f, FACE_BLACK);
+ add234(darkable_faces_sorted, fs);
+ }
+ if (can_colour_face(g, board, i, FACE_WHITE)) {+ fs->white_score = face_score(g, board, f, FACE_WHITE);
+ add234(lightable_faces_sorted, fs);
+ }
+ }
+
+ /* Colour faces one at a time until no more faces are colourable. */
+ while (TRUE)
+ {+ enum face_colour colour;
+ tree234 *faces_to_pick;
+ int c_lightable = count234(lightable_faces_sorted);
+ int c_darkable = count234(darkable_faces_sorted);
+ if (c_lightable == 0 && c_darkable == 0) {+ /* No more faces we can use at all. */
+ break;
+ }
+ assert(c_lightable != 0 && c_darkable != 0);
+
+ /* Choose a colour, and colour the best available face
+ * with that colour. */
+ colour = random_upto(rs, 2) ? FACE_WHITE : FACE_BLACK;
+
+ if (colour == FACE_WHITE)
+ faces_to_pick = lightable_faces_sorted;
+ else
+ faces_to_pick = darkable_faces_sorted;
+ if (bias) {+ /*
+ * Go through all the candidate faces and pick the one the
+ * bias function likes best, breaking ties using the
+ * ordering in our tree234 (which is why we replace only
+ * if score > bestscore, not >=).
+ */
+ int j, k;
+ struct face_score *best = NULL;
+ int score, bestscore = 0;
+
+ for (j = 0;
+ (fs = (struct face_score *)index234(faces_to_pick, j))!=NULL;
+ j++) {+
+ assert(fs);
+ k = fs - face_scores;
+ assert(board[k] == FACE_GREY);
+ board[k] = colour;
+ score = bias(biasctx, board, k);
+ board[k] = FACE_GREY;
+ bias(biasctx, board, k); /* let bias know we put it back */
+
+ if (!best || score > bestscore) {+ bestscore = score;
+ best = fs;
+ }
+ }
+ fs = best;
+ } else {+ fs = (struct face_score *)index234(faces_to_pick, 0);
+ }
+ assert(fs);
+ i = fs - face_scores;
+ assert(board[i] == FACE_GREY);
+ board[i] = colour;
+ if (bias)
+ bias(biasctx, board, i); /* notify bias function of the change */
+
+ /* Remove this newly-coloured face from the lists. These lists should
+ * only contain grey faces. */
+ del234(lightable_faces_sorted, fs);
+ del234(darkable_faces_sorted, fs);
+
+ /* Remember which face we've just coloured */
+ cur_face = g->faces + i;
+
+ /* The face we've just coloured potentially affects the colourability
+ * and the scores of any neighbouring faces (touching at a corner or
+ * edge). So the search needs to be conducted around all faces
+ * touching the one we've just lit. Iterate over its corners, then
+ * over each corner's faces. For each such face, we remove it from
+ * the lists, recalculate any scores, then add it back to the lists
+ * (depending on whether it is lightable, darkable or both). */
+ for (i = 0; i < cur_face->order; i++) {+ grid_dot *d = cur_face->dots[i];
+ for (j = 0; j < d->order; j++) {+ grid_face *f = d->faces[j];
+ int fi; /* face index of f */
+
+ if (f == NULL)
+ continue;
+ if (f == cur_face)
+ continue;
+
+ /* If the face is already coloured, it won't be on our
+ * lightable/darkable lists anyway, so we can skip it without
+ * bothering with the removal step. */
+ if (FACE_COLOUR(f) != FACE_GREY) continue;
+
+ /* Find the face index and face_score* corresponding to f */
+ fi = f - g->faces;
+ fs = face_scores + fi;
+
+ /* Remove from lightable list if it's in there. We do this,
+ * even if it is still lightable, because the score might
+ * be different, and we need to remove-then-add to maintain
+ * correct sort order. */
+ del234(lightable_faces_sorted, fs);
+ if (can_colour_face(g, board, fi, FACE_WHITE)) {+ fs->white_score = face_score(g, board, f, FACE_WHITE);
+ add234(lightable_faces_sorted, fs);
+ }
+ /* Do the same for darkable list. */
+ del234(darkable_faces_sorted, fs);
+ if (can_colour_face(g, board, fi, FACE_BLACK)) {+ fs->black_score = face_score(g, board, f, FACE_BLACK);
+ add234(darkable_faces_sorted, fs);
+ }
+ }
+ }
+ }
+
+ /* Clean up */
+ freetree234(lightable_faces_sorted);
+ freetree234(darkable_faces_sorted);
+ sfree(face_scores);
+
+ /* The next step requires a shuffled list of all faces */
+ face_list = snewn(num_faces, int);
+ for (i = 0; i < num_faces; ++i) {+ face_list[i] = i;
+ }
+ shuffle(face_list, num_faces, sizeof(int), rs);
+
+ /* The above loop-generation algorithm can often leave large clumps
+ * of faces of one colour. In extreme cases, the resulting path can be
+ * degenerate and not very satisfying to solve.
+ * This next step alleviates this problem:
+ * Go through the shuffled list, and flip the colour of any face we can
+ * legally flip, and which is adjacent to only one face of the opposite
+ * colour - this tends to grow 'tendrils' into any clumps.
+ * Repeat until we can find no more faces to flip. This will
+ * eventually terminate, because each flip increases the loop's
+ * perimeter, which cannot increase for ever.
+ * The resulting path will have maximal loopiness (in the sense that it
+ * cannot be improved "locally". Unfortunately, this allows a player to
+ * make some illicit deductions. To combat this (and make the path more
+ * interesting), we do one final pass making random flips. */
+
+ /* Set to TRUE for final pass */
+ do_random_pass = FALSE;
+
+ while (TRUE) {+ /* Remember whether a flip occurred during this pass */
+ int flipped = FALSE;
+
+ for (i = 0; i < num_faces; ++i) {+ int j = face_list[i];
+ enum face_colour opp =
+ (board[j] == FACE_WHITE) ? FACE_BLACK : FACE_WHITE;
+ if (can_colour_face(g, board, j, opp)) {+ grid_face *face = g->faces +j;
+ if (do_random_pass) {+ /* final random pass */
+ if (!random_upto(rs, 10))
+ board[j] = opp;
+ } else {+ /* normal pass - flip when neighbour count is 1 */
+ if (face_num_neighbours(g, board, face, opp) == 1) {+ board[j] = opp;
+ flipped = TRUE;
+ }
+ }
+ }
+ }
+
+ if (do_random_pass) break;
+ if (!flipped) do_random_pass = TRUE;
+ }
+
+ sfree(face_list);
+}
--- /dev/null
+++ b/loopgen.h
@@ -1,0 +1,35 @@
+/*
+ * loopgen.h: interface file for loop generation functions for grid.[ch].
+ */
+
+#ifndef _LOOPGEN_H
+#define _LOOPGEN_H
+
+#include "puzzles.h"
+#include "grid.h"
+
+enum face_colour { FACE_WHITE, FACE_GREY, FACE_BLACK };+
+/* face should be of type grid_face* here. */
+#define FACE_COLOUR(face) \
+ ( (face) == NULL ? FACE_BLACK : \
+ board[(face) - g->faces] )
+
+typedef int (*loopgen_bias_fn_t)(void *ctx, char *board, int face);
+
+/* 'board' should be a char array whose length is the same as
+ * g->num_faces: this will be filled in with FACE_WHITE or FACE_BLACK
+ * after loop generation.
+ *
+ * If 'bias' is non-null, it should be a user-provided function which
+ * rates a half-finished board (i.e. may include some FACE_GREYs) for
+ * desirability; this will cause the loop generator to bias in favour
+ * of loops with a high return value from that function. The 'face'
+ * parameter to the bias function indicates which face of the grid has
+ * been modified since the last call; it is guaranteed that only one
+ * will have been (so that bias functions can work incrementally
+ * rather than re-scanning the whole grid on every call). */
+extern void generate_loop(grid *g, char *board, random_state *rs,
+ loopgen_bias_fn_t bias, void *biasctx);
+
+#endif
--- a/loopy.R
+++ b/loopy.R
@@ -1,6 +1,6 @@
# -*- makefile -*-
-LOOPY_EXTRA = tree234 dsf grid penrose
+LOOPY_EXTRA = tree234 dsf grid penrose loopgen
loopy : [X] GTK COMMON loopy LOOPY_EXTRA loopy-icon|no-icon
--- a/loopy.c
+++ b/loopy.c
@@ -82,6 +82,7 @@
#include "puzzles.h"
#include "tree234.h"
#include "grid.h"
+#include "loopgen.h"
/* Debugging options */
@@ -1277,507 +1278,20 @@
* Loop generation and clue removal
*/
-/* We're going to store lists of current candidate faces for colouring black
- * or white.
- * Each face gets a 'score', which tells us how adding that face right
- * now would affect the curliness of the solution loop. We're trying to
- * maximise that quantity so will bias our random selection of faces to
- * colour those with high scores */
-struct face_score {- int white_score;
- int black_score;
- unsigned long random;
- /* No need to store a grid_face* here. The 'face_scores' array will
- * be a list of 'face_score' objects, one for each face of the grid, so
- * the position (index) within the 'face_scores' array will determine
- * which face corresponds to a particular face_score.
- * Having a single 'face_scores' array for all faces simplifies memory
- * management, and probably improves performance, because we don't have to
- * malloc/free each individual face_score, and we don't have to maintain
- * a mapping from grid_face* pointers to face_score* pointers.
- */
-};
-
-static int generic_sort_cmpfn(void *v1, void *v2, size_t offset)
-{- struct face_score *f1 = v1;
- struct face_score *f2 = v2;
- int r;
-
- r = *(int *)((char *)f2 + offset) - *(int *)((char *)f1 + offset);
- if (r) {- return r;
- }
-
- if (f1->random < f2->random)
- return -1;
- else if (f1->random > f2->random)
- return 1;
-
- /*
- * It's _just_ possible that two faces might have been given
- * the same random value. In that situation, fall back to
- * comparing based on the positions within the face_scores list.
- * This introduces a tiny directional bias, but not a significant one.
- */
- return f1 - f2;
-}
-
-static int white_sort_cmpfn(void *v1, void *v2)
-{- return generic_sort_cmpfn(v1, v2, offsetof(struct face_score,white_score));
-}
-
-static int black_sort_cmpfn(void *v1, void *v2)
-{- return generic_sort_cmpfn(v1, v2, offsetof(struct face_score,black_score));
-}
-
-enum face_colour { FACE_WHITE, FACE_GREY, FACE_BLACK };-
-/* face should be of type grid_face* here. */
-#define FACE_COLOUR(face) \
- ( (face) == NULL ? FACE_BLACK : \
- board[(face) - g->faces] )
-
-/* 'board' is an array of these enums, indicating which faces are
- * currently black/white/grey. 'colour' is FACE_WHITE or FACE_BLACK.
- * Returns whether it's legal to colour the given face with this colour. */
-static int can_colour_face(grid *g, char* board, int face_index,
- enum face_colour colour)
-{- int i, j;
- grid_face *test_face = g->faces + face_index;
- grid_face *starting_face, *current_face;
- grid_dot *starting_dot;
- int transitions;
- int current_state, s; /* booleans: equal or not-equal to 'colour' */
- int found_same_coloured_neighbour = FALSE;
- assert(board[face_index] != colour);
-
- /* Can only consider a face for colouring if it's adjacent to a face
- * with the same colour. */
- for (i = 0; i < test_face->order; i++) {- grid_edge *e = test_face->edges[i];
- grid_face *f = (e->face1 == test_face) ? e->face2 : e->face1;
- if (FACE_COLOUR(f) == colour) {- found_same_coloured_neighbour = TRUE;
- break;
- }
- }
- if (!found_same_coloured_neighbour)
- return FALSE;
-
- /* Need to avoid creating a loop of faces of this colour around some
- * differently-coloured faces.
- * Also need to avoid meeting a same-coloured face at a corner, with
- * other-coloured faces in between. Here's a simple test that (I believe)
- * takes care of both these conditions:
- *
- * Take the circular path formed by this face's edges, and inflate it
- * slightly outwards. Imagine walking around this path and consider
- * the faces that you visit in sequence. This will include all faces
- * touching the given face, either along an edge or just at a corner.
- * Count the number of 'colour'/not-'colour' transitions you encounter, as
- * you walk along the complete loop. This will obviously turn out to be
- * an even number.
- * If 0, we're either in the middle of an "island" of this colour (should
- * be impossible as we're not supposed to create black or white loops),
- * or we're about to start a new island - also not allowed.
- * If 4 or greater, there are too many separate coloured regions touching
- * this face, and colouring it would create a loop or a corner-violation.
- * The only allowed case is when the count is exactly 2. */
-
- /* i points to a dot around the test face.
- * j points to a face around the i^th dot.
- * The current face will always be:
- * test_face->dots[i]->faces[j]
- * We assume dots go clockwise around the test face,
- * and faces go clockwise around dots. */
-
- /*
- * The end condition is slightly fiddly. In sufficiently strange
- * degenerate grids, our test face may be adjacent to the same
- * other face multiple times (typically if it's the exterior
- * face). Consider this, in particular:
- *
- * +--+
- * | |
- * +--+--+
- * | | |
- * +--+--+
- *
- * The bottom left face there is adjacent to the exterior face
- * twice, so we can't just terminate our iteration when we reach
- * the same _face_ we started at. Furthermore, we can't
- * condition on having the same (i,j) pair either, because
- * several (i,j) pairs identify the bottom left contiguity with
- * the exterior face! We canonicalise the (i,j) pair by taking
- * one step around before we set the termination tracking.
- */
-
- i = j = 0;
- current_face = test_face->dots[0]->faces[0];
- if (current_face == test_face) {- j = 1;
- current_face = test_face->dots[0]->faces[1];
- }
- transitions = 0;
- current_state = (FACE_COLOUR(current_face) == colour);
- starting_dot = NULL;
- starting_face = NULL;
- while (TRUE) {- /* Advance to next face.
- * Need to loop here because it might take several goes to
- * find it. */
- while (TRUE) {- j++;
- if (j == test_face->dots[i]->order)
- j = 0;
-
- if (test_face->dots[i]->faces[j] == test_face) {- /* Advance to next dot round test_face, then
- * find current_face around new dot
- * and advance to the next face clockwise */
- i++;
- if (i == test_face->order)
- i = 0;
- for (j = 0; j < test_face->dots[i]->order; j++) {- if (test_face->dots[i]->faces[j] == current_face)
- break;
- }
- /* Must actually find current_face around new dot,
- * or else something's wrong with the grid. */
- assert(j != test_face->dots[i]->order);
- /* Found, so advance to next face and try again */
- } else {- break;
- }
- }
- /* (i,j) are now advanced to next face */
- current_face = test_face->dots[i]->faces[j];
- s = (FACE_COLOUR(current_face) == colour);
- if (!starting_dot) {- starting_dot = test_face->dots[i];
- starting_face = current_face;
- current_state = s;
- } else {- if (s != current_state) {- ++transitions;
- current_state = s;
- if (transitions > 2)
- break;
- }
- if (test_face->dots[i] == starting_dot &&
- current_face == starting_face)
- break;
- }
- }
-
- return (transitions == 2) ? TRUE : FALSE;
-}
-
-/* Count the number of neighbours of 'face', having colour 'colour' */
-static int face_num_neighbours(grid *g, char *board, grid_face *face,
- enum face_colour colour)
-{- int colour_count = 0;
- int i;
- grid_face *f;
- grid_edge *e;
- for (i = 0; i < face->order; i++) {- e = face->edges[i];
- f = (e->face1 == face) ? e->face2 : e->face1;
- if (FACE_COLOUR(f) == colour)
- ++colour_count;
- }
- return colour_count;
-}
-
-/* The 'score' of a face reflects its current desirability for selection
- * as the next face to colour white or black. We want to encourage moving
- * into grey areas and increasing loopiness, so we give scores according to
- * how many of the face's neighbours are currently coloured the same as the
- * proposed colour. */
-static int face_score(grid *g, char *board, grid_face *face,
- enum face_colour colour)
-{- /* Simple formula: score = 0 - num. same-coloured neighbours,
- * so a higher score means fewer same-coloured neighbours. */
- return -face_num_neighbours(g, board, face, colour);
-}
-
-/* Generate a new complete set of clues for the given game_state.
- * The method is to generate a WHITE/BLACK colouring of all the faces,
- * such that the WHITE faces will define the inside of the path, and the
- * BLACK faces define the outside.
- * To do this, we initially colour all faces GREY. The infinite space outside
- * the grid is coloured BLACK, and we choose a random face to colour WHITE.
- * Then we gradually grow the BLACK and the WHITE regions, eliminating GREY
- * faces, until the grid is filled with BLACK/WHITE. As we grow the regions,
- * we avoid creating loops of a single colour, to preserve the topological
- * shape of the WHITE and BLACK regions.
- * We also try to make the boundary as loopy and twisty as possible, to avoid
- * generating paths that are uninteresting.
- * The algorithm works by choosing a BLACK/WHITE colour, then choosing a GREY
- * face that can be coloured with that colour (without violating the
- * topological shape of that region). It's not obvious, but I think this
- * algorithm is guaranteed to terminate without leaving any GREY faces behind.
- * Indeed, if there are any GREY faces at all, both the WHITE and BLACK
- * regions can be grown.
- * This is checked using assert()ions, and I haven't seen any failures yet.
- *
- * Hand-wavy proof: imagine what can go wrong...
- *
- * Could the white faces get completely cut off by the black faces, and still
- * leave some grey faces remaining?
- * No, because then the black faces would form a loop around both the white
- * faces and the grey faces, which is disallowed because we continually
- * maintain the correct topological shape of the black region.
- * Similarly, the black faces can never get cut off by the white faces. That
- * means both the WHITE and BLACK regions always have some room to grow into
- * the GREY regions.
- * Could it be that we can't colour some GREY face, because there are too many
- * WHITE/BLACK transitions as we walk round the face? (see the
- * can_colour_face() function for details)
- * No. Imagine otherwise, and we see WHITE/BLACK/WHITE/BLACK as we walk
- * around the face. The two WHITE faces would be connected by a WHITE path,
- * and the BLACK faces would be connected by a BLACK path. These paths would
- * have to cross, which is impossible.
- * Another thing that could go wrong: perhaps we can't find any GREY face to
- * colour WHITE, because it would create a loop-violation or a corner-violation
- * with the other WHITE faces?
- * This is a little bit tricky to prove impossible. Imagine you have such a
- * GREY face (that is, if you coloured it WHITE, you would create a WHITE loop
- * or corner violation).
- * That would cut all the non-white area into two blobs. One of those blobs
- * must be free of BLACK faces (because the BLACK stuff is a connected blob).
- * So we have a connected GREY area, completely surrounded by WHITE
- * (including the GREY face we've tentatively coloured WHITE).
- * A well-known result in graph theory says that you can always find a GREY
- * face whose removal leaves the remaining GREY area connected. And it says
- * there are at least two such faces, so we can always choose the one that
- * isn't the "tentative" GREY face. Colouring that face WHITE leaves
- * everything nice and connected, including that "tentative" GREY face which
- * acts as a gateway to the rest of the non-WHITE grid.
- */
static void add_full_clues(game_state *state, random_state *rs)
{signed char *clues = state->clues;
- char *board;
grid *g = state->game_grid;
- int i, j;
- int num_faces = g->num_faces;
- struct face_score *face_scores; /* Array of face_score objects */
- struct face_score *fs; /* Points somewhere in the above list */
- struct grid_face *cur_face;
- tree234 *lightable_faces_sorted;
- tree234 *darkable_faces_sorted;
- int *face_list;
- int do_random_pass;
+ char *board = snewn(g->num_faces, char);
+ int i;
- board = snewn(num_faces, char);
+ generate_loop(g, board, rs, NULL, NULL);
- /* Make a board */
- memset(board, FACE_GREY, num_faces);
-
- /* Create and initialise the list of face_scores */
- face_scores = snewn(num_faces, struct face_score);
- for (i = 0; i < num_faces; i++) {- face_scores[i].random = random_bits(rs, 31);
- face_scores[i].black_score = face_scores[i].white_score = 0;
- }
-
- /* Colour a random, finite face white. The infinite face is implicitly
- * coloured black. Together, they will seed the random growth process
- * for the black and white areas. */
- i = random_upto(rs, num_faces);
- board[i] = FACE_WHITE;
-
- /* We need a way of favouring faces that will increase our loopiness.
- * We do this by maintaining a list of all candidate faces sorted by
- * their score and choose randomly from that with appropriate skew.
- * In order to avoid consistently biasing towards particular faces, 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 face 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 faces in
- * any one run but that doesn't actually matter. */
-
- lightable_faces_sorted = newtree234(white_sort_cmpfn);
- darkable_faces_sorted = newtree234(black_sort_cmpfn);
-
- /* Initialise the lists of lightable and darkable faces. This is
- * slightly different from the code inside the while-loop, because we need
- * to check every face of the board (the grid structure does not keep a
- * list of the infinite face's neighbours). */
- for (i = 0; i < num_faces; i++) {- grid_face *f = g->faces + i;
- struct face_score *fs = face_scores + i;
- if (board[i] != FACE_GREY) continue;
- /* We need the full colourability check here, it's not enough simply
- * to check neighbourhood. On some grids, a neighbour of the infinite
- * face is not necessarily darkable. */
- if (can_colour_face(g, board, i, FACE_BLACK)) {- fs->black_score = face_score(g, board, f, FACE_BLACK);
- add234(darkable_faces_sorted, fs);
- }
- if (can_colour_face(g, board, i, FACE_WHITE)) {- fs->white_score = face_score(g, board, f, FACE_WHITE);
- add234(lightable_faces_sorted, fs);
- }
- }
-
- /* Colour faces one at a time until no more faces are colourable. */
- while (TRUE)
- {- enum face_colour colour;
- struct face_score *fs_white, *fs_black;
- int c_lightable = count234(lightable_faces_sorted);
- int c_darkable = count234(darkable_faces_sorted);
- if (c_lightable == 0 && c_darkable == 0) {- /* No more faces we can use at all. */
- break;
- }
- assert(c_lightable != 0 && c_darkable != 0);
-
- fs_white = (struct face_score *)index234(lightable_faces_sorted, 0);
- fs_black = (struct face_score *)index234(darkable_faces_sorted, 0);
-
- /* Choose a colour, and colour the best available face
- * with that colour. */
- colour = random_upto(rs, 2) ? FACE_WHITE : FACE_BLACK;
-
- if (colour == FACE_WHITE)
- fs = fs_white;
- else
- fs = fs_black;
- assert(fs);
- i = fs - face_scores;
- assert(board[i] == FACE_GREY);
- board[i] = colour;
-
- /* Remove this newly-coloured face from the lists. These lists should
- * only contain grey faces. */
- del234(lightable_faces_sorted, fs);
- del234(darkable_faces_sorted, fs);
-
- /* Remember which face we've just coloured */
- cur_face = g->faces + i;
-
- /* The face we've just coloured potentially affects the colourability
- * and the scores of any neighbouring faces (touching at a corner or
- * edge). So the search needs to be conducted around all faces
- * touching the one we've just lit. Iterate over its corners, then
- * over each corner's faces. For each such face, we remove it from
- * the lists, recalculate any scores, then add it back to the lists
- * (depending on whether it is lightable, darkable or both). */
- for (i = 0; i < cur_face->order; i++) {- grid_dot *d = cur_face->dots[i];
- for (j = 0; j < d->order; j++) {- grid_face *f = d->faces[j];
- int fi; /* face index of f */
-
- if (f == NULL)
- continue;
- if (f == cur_face)
- continue;
-
- /* If the face is already coloured, it won't be on our
- * lightable/darkable lists anyway, so we can skip it without
- * bothering with the removal step. */
- if (FACE_COLOUR(f) != FACE_GREY) continue;
-
- /* Find the face index and face_score* corresponding to f */
- fi = f - g->faces;
- fs = face_scores + fi;
-
- /* Remove from lightable list if it's in there. We do this,
- * even if it is still lightable, because the score might
- * be different, and we need to remove-then-add to maintain
- * correct sort order. */
- del234(lightable_faces_sorted, fs);
- if (can_colour_face(g, board, fi, FACE_WHITE)) {- fs->white_score = face_score(g, board, f, FACE_WHITE);
- add234(lightable_faces_sorted, fs);
- }
- /* Do the same for darkable list. */
- del234(darkable_faces_sorted, fs);
- if (can_colour_face(g, board, fi, FACE_BLACK)) {- fs->black_score = face_score(g, board, f, FACE_BLACK);
- add234(darkable_faces_sorted, fs);
- }
- }
- }
- }
-
- /* Clean up */
- freetree234(lightable_faces_sorted);
- freetree234(darkable_faces_sorted);
- sfree(face_scores);
-
- /* The next step requires a shuffled list of all faces */
- face_list = snewn(num_faces, int);
- for (i = 0; i < num_faces; ++i) {- face_list[i] = i;
- }
- shuffle(face_list, num_faces, sizeof(int), rs);
-
- /* The above loop-generation algorithm can often leave large clumps
- * of faces of one colour. In extreme cases, the resulting path can be
- * degenerate and not very satisfying to solve.
- * This next step alleviates this problem:
- * Go through the shuffled list, and flip the colour of any face we can
- * legally flip, and which is adjacent to only one face of the opposite
- * colour - this tends to grow 'tendrils' into any clumps.
- * Repeat until we can find no more faces to flip. This will
- * eventually terminate, because each flip increases the loop's
- * perimeter, which cannot increase for ever.
- * The resulting path will have maximal loopiness (in the sense that it
- * cannot be improved "locally". Unfortunately, this allows a player to
- * make some illicit deductions. To combat this (and make the path more
- * interesting), we do one final pass making random flips. */
-
- /* Set to TRUE for final pass */
- do_random_pass = FALSE;
-
- while (TRUE) {- /* Remember whether a flip occurred during this pass */
- int flipped = FALSE;
-
- for (i = 0; i < num_faces; ++i) {- int j = face_list[i];
- enum face_colour opp =
- (board[j] == FACE_WHITE) ? FACE_BLACK : FACE_WHITE;
- if (can_colour_face(g, board, j, opp)) {- grid_face *face = g->faces +j;
- if (do_random_pass) {- /* final random pass */
- if (!random_upto(rs, 10))
- board[j] = opp;
- } else {- /* normal pass - flip when neighbour count is 1 */
- if (face_num_neighbours(g, board, face, opp) == 1) {- board[j] = opp;
- flipped = TRUE;
- }
- }
- }
- }
-
- if (do_random_pass) break;
- if (!flipped) do_random_pass = TRUE;
- }
-
- sfree(face_list);
-
/* Fill out all the clues by initialising to 0, then iterating over
* all edges and incrementing each clue as we find edges that border
* between BLACK/WHITE faces. While we're at it, we verify that the
* algorithm does work, and there aren't any GREY faces still there. */
- memset(clues, 0, num_faces);
+ memset(clues, 0, g->num_faces);
for (i = 0; i < g->num_edges; i++) {grid_edge *e = g->edges + i;
grid_face *f1 = e->face1;
@@ -1791,7 +1305,6 @@
if (f2) clues[f2 - g->faces]++;
}
}
-
sfree(board);
}
--- /dev/null
+++ b/pearl.R
@@ -1,0 +1,23 @@
+# -*- makefile -*-
+
+PEARL_EXTRA = dsf tree234 grid penrose loopgen tdq
+
+pearl : [X] GTK COMMON pearl PEARL_EXTRA pearl-icon|no-icon
+pearl : [G] WINDOWS COMMON pearl PEARL_EXTRA pearl.res?
+
+pearlbench : [U] pearl[STANDALONE_SOLVER] PEARL_EXTRA STANDALONE m.lib
+pearlbench : [C] pearl[STANDALONE_SOLVER] PEARL_EXTRA STANDALONE
+
+ALL += pearl[COMBINED] PEARL_EXTRA
+
+!begin gtk
+GAMES += pearl
+!end
+
+!begin >list.c
+ A(pearl) \
+!end
+
+!begin >wingames.lst
+pearl.exe:Pearl
+!end
--- /dev/null
+++ b/pearl.c
@@ -1,0 +1,2567 @@
+/*
+ * pearl.c: Nikoli's `Masyu' puzzle.
+ */
+
+/*
+ * TODO:
+ *
+ * - Keyboard-control cursor. (Would probably have to address both
+ * square centres, for laying multiple edges at a time in a
+ * drag-like style, and grid edges for marking particular line
+ * segments as no-go.)
+ *
+ * - Generation is still pretty slow, due to difficulty coming up in
+ * the first place with a loop that makes a soluble puzzle even
+ * with all possible clues filled in.
+ * + A possible alternative strategy to further tuning of the
+ * existing loop generator 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. However, I don't have a
+ * detailed plan for any such mechanism, so it may be a pipe
+ * dream.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <ctype.h>
+#include <math.h>
+
+#include "puzzles.h"
+#include "grid.h"
+#include "loopgen.h"
+
+#define SWAP(i,j) do { int swaptmp = (i); (i) = (j); (j) = swaptmp; } while (0)+
+#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, COL_HIGHLIGHT, COL_LOWLIGHT,
+ COL_BLACK, COL_WHITE,
+ COL_ERROR, COL_GRID, COL_FLASH,
+ COL_DRAGON, COL_DRAGOFF,
+ NCOLOURS
+};
+
+/* Macro ickery copied from slant.c */
+#define DIFFLIST(A) \
+ A(EASY,Easy,e) \
+ A(TRICKY,Tricky,t)
+#define ENUM(upper,title,lower) DIFF_ ## upper,
+#define TITLE(upper,title,lower) #title,
+#define ENCODE(upper,title,lower) #lower
+#define CONFIG(upper,title,lower) ":" #title
+enum { DIFFLIST(ENUM) DIFFCOUNT };+static char const *const pearl_diffnames[] = { DIFFLIST(TITLE) "(count)" };+static char const pearl_diffchars[] = DIFFLIST(ENCODE);
+#define DIFFCONFIG DIFFLIST(CONFIG)
+
+struct game_params {+ int w, h;
+ int difficulty;
+ int nosolve; /* XXX remove me! */
+};
+
+struct shared_state {+ int w, h, sz;
+ char *clues; /* size w*h */
+ int refcnt;
+};
+
+#define INGRID(state, gx, gy) ((gx) >= 0 && (gx) < (state)->shared->w && \
+ (gy) >= 0 && (gy) < (state)->shared->h)
+struct game_state {+ struct shared_state *shared;
+ char *lines; /* size w*h: lines placed */
+ char *errors; /* size w*h: errors detected */
+ char *marks; /* size w*h: 'no line here' marks placed. */
+ int completed, used_solve;
+ int loop_length; /* filled in by check_completion when complete. */
+};
+
+#define DEFAULT_PRESET 3
+
+static const struct game_params pearl_presets[] = {+ {6, 6, DIFF_EASY},+ {6, 6, DIFF_TRICKY},+ {8, 8, DIFF_EASY},+ {8, 8, DIFF_TRICKY},+ {10, 10, DIFF_EASY},+ {10, 10, DIFF_TRICKY},+ {12, 8, DIFF_EASY},+ {12, 8, DIFF_TRICKY},+};
+
+static game_params *default_params(void)
+{+ game_params *ret = snew(game_params);
+
+ *ret = pearl_presets[DEFAULT_PRESET];
+ ret->nosolve = FALSE;
+
+ return ret;
+}
+
+static int game_fetch_preset(int i, char **name, game_params **params)
+{+ game_params *ret;
+ char buf[64];
+
+ if (i < 0 || i >= lenof(pearl_presets)) return FALSE;
+
+ ret = default_params();
+ *ret = pearl_presets[i]; /* struct copy */
+ *params = ret;
+
+ sprintf(buf, "%dx%d %s",
+ pearl_presets[i].w, pearl_presets[i].h,
+ pearl_diffnames[pearl_presets[i].difficulty]);
+ *name = dupstr(buf);
+
+ return TRUE;
+}
+
+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 *ret, char const *string)
+{+ ret->w = ret->h = atoi(string);
+ while (*string && isdigit((unsigned char) *string)) ++string;
+ if (*string == 'x') {+ string++;
+ ret->h = atoi(string);
+ while (*string && isdigit((unsigned char)*string)) string++;
+ }
+
+ ret->difficulty = DIFF_EASY;
+ if (*string == 'd') {+ int i;
+ string++;
+ for (i = 0; i < DIFFCOUNT; i++)
+ if (*string == pearl_diffchars[i])
+ ret->difficulty = i;
+ if (*string) string++;
+ }
+
+ ret->nosolve = FALSE;
+ if (*string == 'n') {+ ret->nosolve = TRUE;
+ string++;
+ }
+}
+
+static char *encode_params(game_params *params, int full)
+{+ char buf[256];
+ sprintf(buf, "%dx%d", params->w, params->h);
+ if (full)
+ sprintf(buf + strlen(buf), "d%c%s",
+ pearl_diffchars[params->difficulty],
+ params->nosolve ? "n" : "");
+ return dupstr(buf);
+}
+
+static config_item *game_configure(game_params *params)
+{+ config_item *ret;
+ char buf[64];
+
+ ret = snewn(5, config_item);
+
+ ret[0].name = "Width";
+ ret[0].type = C_STRING;
+ sprintf(buf, "%d", params->w);
+ ret[0].sval = dupstr(buf);
+ ret[0].ival = 0;
+
+ ret[1].name = "Height";
+ ret[1].type = C_STRING;
+ sprintf(buf, "%d", params->h);
+ ret[1].sval = dupstr(buf);
+ ret[1].ival = 0;
+
+ ret[2].name = "Difficulty";
+ ret[2].type = C_CHOICES;
+ ret[2].sval = DIFFCONFIG;
+ ret[2].ival = params->difficulty;
+
+ ret[3].name = "Allow unsoluble";
+ ret[3].type = C_BOOLEAN;
+ ret[3].sval = NULL;
+ ret[3].ival = params->nosolve;
+
+ ret[4].name = NULL;
+ ret[4].type = C_END;
+ ret[4].sval = NULL;
+ ret[4].ival = 0;
+
+ return ret;
+}
+
+static game_params *custom_params(config_item *cfg)
+{+ game_params *ret = snew(game_params);
+
+ ret->w = atoi(cfg[0].sval);
+ ret->h = atoi(cfg[1].sval);
+ ret->difficulty = cfg[2].ival;
+ ret->nosolve = cfg[3].ival;
+
+ return ret;
+}
+
+static char *validate_params(game_params *params, int full)
+{+ if (params->w < 5) return "Width must be at least five";
+ if (params->h < 5) return "Height must be at least five";
+ if (params->difficulty < 0 || params->difficulty >= DIFFCOUNT)
+ return "Unknown difficulty level";
+
+ return NULL;
+}
+
+/* ----------------------------------------------------------------------
+ * Solver.
+ */
+
+int pearl_solve(int w, int h, char *clues, char *result,
+ int difficulty, int partial)
+{+ 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;
+ }
+
+ /* Further deductions are considered 'tricky'. */
+ if (difficulty == DIFF_EASY) goto done_deductions;
+
+ /*
+ * 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
+ }
+ }
+ }
+ }
+ }
+
+done_deductions:
+
+ if (done_something)
+ continue;
+
+ /*
+ * If we reach here, there is nothing left we can do.
+ * Return 2 for ambiguous puzzle.
+ */
+ ret = 2;
+ break;
+ }
+
+cleanup:
+
+ /*
+ * If ret = 1 then we've successfully achieved a solution. This
+ * means that we expect every square to be nailed down to
+ * exactly one possibility. If this is the case, or if the caller
+ * asked for a partial solution anyway, transcribe those
+ * possibilities into the result array.
+ */
+ if (ret == 1 || partial) {+ 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;
+ }
+ if (ret == 1) assert(b < 0xD); /* we should have had a break by now */
+ }
+ }
+ }
+
+ sfree(dsfsize);
+ sfree(dsf);
+ sfree(workspace);
+ assert(ret >= 0);
+ return ret;
+}
+
+/* ----------------------------------------------------------------------
+ * Loop generator.
+ */
+
+/*
+ * We use the loop generator code from loopy, hard-coding to a square
+ * grid of the appropriate size. Knowing the grid layout and the tile
+ * size we can shrink that to our small grid and then make our line
+ * layout from the face colour info.
+ *
+ * We provide a bias function to the loop generator which tries to
+ * bias in favour of loops with more scope for Pearl black clues. This
+ * seems to improve the success rate of the puzzle generator, in that
+ * such loops have a better chance of being soluble with all valid
+ * clues put in.
+ */
+
+struct pearl_loopgen_bias_ctx {+ /*
+ * Our bias function counts the number of 'black clue' corners
+ * (i.e. corners adjacent to two straights) in both the
+ * BLACK/nonBLACK and WHITE/nonWHITE boundaries. In order to do
+ * this, we must:
+ *
+ * - track the edges that are part of each of those loops
+ * - track the types of vertex in each loop (corner, straight,
+ * none)
+ * - track the current black-clue status of each vertex in each
+ * loop.
+ *
+ * Each of these chunks of data is updated incrementally from the
+ * previous one, to avoid slowdown due to the bias function
+ * rescanning the whole grid every time it's called.
+ *
+ * So we need a lot of separate arrays, plus a tdq for each one,
+ * and we must repeat it all twice for the BLACK and WHITE
+ * boundaries.
+ */
+ struct pearl_loopgen_bias_ctx_boundary {+ int colour; /* FACE_WHITE or FACE_BLACK */
+
+ char *edges; /* is each edge part of the loop? */
+ tdq *edges_todo;
+
+ char *vertextypes; /* bits 0-3 == outgoing edge bitmap;
+ * bit 4 set iff corner clue.
+ * Hence, 0 means non-vertex;
+ * nonzero but bit 4 zero = straight. */
+ int *neighbour[2]; /* indices of neighbour vertices in loop */
+ tdq *vertextypes_todo;
+
+ char *blackclues; /* is each vertex a black clue site? */
+ tdq *blackclues_todo;
+ } boundaries[2]; /* boundaries[0]=WHITE, [1]=BLACK */
+
+ char *faces; /* remember last-seen colour of each face */
+ tdq *faces_todo;
+
+ int score;
+
+ grid *g;
+};
+int pearl_loopgen_bias(void *vctx, char *board, int face)
+{+ struct pearl_loopgen_bias_ctx *ctx = (struct pearl_loopgen_bias_ctx *)vctx;
+ grid *g = ctx->g;
+ int oldface, newface;
+ int i, j, k;
+
+ tdq_add(ctx->faces_todo, face);
+ while ((j = tdq_remove(ctx->faces_todo)) >= 0) {+ oldface = ctx->faces[j];
+ ctx->faces[j] = newface = board[j];
+ for (i = 0; i < 2; i++) {+ struct pearl_loopgen_bias_ctx_boundary *b = &ctx->boundaries[i];
+ int c = b->colour;
+
+ /*
+ * If the face has changed either from or to colour c, we need
+ * to reprocess the edges for this boundary.
+ */
+ if (oldface == c || newface == c) {+ grid_face *f = &g->faces[face];
+ for (k = 0; k < f->order; k++)
+ tdq_add(b->edges_todo, f->edges[k] - g->edges);
+ }
+ }
+ }
+
+ for (i = 0; i < 2; i++) {+ struct pearl_loopgen_bias_ctx_boundary *b = &ctx->boundaries[i];
+ int c = b->colour;
+
+ /*
+ * Go through the to-do list of edges. For each edge, decide
+ * anew whether it's part of this boundary or not. Any edge
+ * that changes state has to have both its endpoints put on
+ * the vertextypes_todo list.
+ */
+ while ((j = tdq_remove(b->edges_todo)) >= 0) {+ grid_edge *e = &g->edges[j];
+ int fc1 = e->face1 ? board[e->face1 - g->faces] : FACE_BLACK;
+ int fc2 = e->face2 ? board[e->face2 - g->faces] : FACE_BLACK;
+ int oldedge = b->edges[j];
+ int newedge = (fc1==c) ^ (fc2==c);
+ if (oldedge != newedge) {+ b->edges[j] = newedge;
+ tdq_add(b->vertextypes_todo, e->dot1 - g->dots);
+ tdq_add(b->vertextypes_todo, e->dot2 - g->dots);
+ }
+ }
+
+ /*
+ * Go through the to-do list of vertices whose types need
+ * refreshing. For each one, decide whether it's a corner, a
+ * straight, or a vertex not in the loop, and in the former
+ * two cases also work out the indices of its neighbour
+ * vertices along the loop. Any vertex that changes state must
+ * be put back on the to-do list for deciding if it's a black
+ * clue site, and so must its two new neighbours _and_ its two
+ * old neighbours.
+ */
+ while ((j = tdq_remove(b->vertextypes_todo)) >= 0) {+ grid_dot *d = &g->dots[j];
+ int neighbours[2], type = 0, n = 0;
+
+ for (k = 0; k < d->order; k++) {+ grid_edge *e = d->edges[k];
+ grid_dot *d2 = (e->dot1 == d ? e->dot2 : e->dot1);
+ /* dir == 0,1,2,3 for an edge going L,U,R,D */
+ int dir = (d->y == d2->y) + 2*(d->x+d->y > d2->x+d2->y);
+ int ei = e - g->edges;
+ if (b->edges[ei]) {+ type |= 1 << dir;
+ neighbours[n] = d2 - g->dots;
+ n++;
+ }
+ }
+
+ /*
+ * Decide if it's a corner, and set the corner flag if so.
+ */
+ if (type != 0 && type != 0x5 && type != 0xA)
+ type |= 0x10;
+
+ if (type != b->vertextypes[j]) {+ /*
+ * Recompute old neighbours, if any.
+ */
+ if (b->vertextypes[j]) {+ tdq_add(b->blackclues_todo, b->neighbour[0][j]);
+ tdq_add(b->blackclues_todo, b->neighbour[1][j]);
+ }
+ /*
+ * Recompute this vertex.
+ */
+ tdq_add(b->blackclues_todo, j);
+ b->vertextypes[j] = type;
+ /*
+ * Recompute new neighbours, if any.
+ */
+ if (b->vertextypes[j]) {+ b->neighbour[0][j] = neighbours[0];
+ b->neighbour[1][j] = neighbours[1];
+ tdq_add(b->blackclues_todo, b->neighbour[0][j]);
+ tdq_add(b->blackclues_todo, b->neighbour[1][j]);
+ }
+ }
+ }
+
+ /*
+ * Go through the list of vertices which we must check to see
+ * if they're black clue sites. Each one is a black clue site
+ * iff it is a corner and its loop neighbours are non-corners.
+ * Adjust the running total of black clues we've counted.
+ */
+ while ((j = tdq_remove(b->blackclues_todo)) >= 0) {+ ctx->score -= b->blackclues[j];
+ b->blackclues[j] = ((b->vertextypes[j] & 0x10) &&
+ !((b->vertextypes[b->neighbour[0][j]] |
+ b->vertextypes[b->neighbour[1][j]])
+ & 0x10));
+ ctx->score += b->blackclues[j];
+ }
+ }
+
+ return ctx->score;
+}
+
+void pearl_loopgen(int w, int h, char *lines, random_state *rs)
+{+ grid *g = grid_new(GRID_SQUARE, w-1, h-1, NULL);
+ char *board = snewn(g->num_faces, char);
+ int i, s = g->tilesize;
+ struct pearl_loopgen_bias_ctx biasctx;
+
+ memset(lines, 0, w*h);
+
+ /*
+ * Initialise the context for the bias function. Initially we fill
+ * all the to-do lists, so that the first call will scan
+ * everything; thereafter the lists stay empty so we make
+ * incremental changes.
+ */
+ biasctx.g = g;
+ biasctx.faces = snewn(g->num_faces, char);
+ biasctx.faces_todo = tdq_new(g->num_faces);
+ tdq_fill(biasctx.faces_todo);
+ biasctx.score = 0;
+ memset(biasctx.faces, FACE_GREY, g->num_faces);
+ for (i = 0; i < 2; i++) {+ biasctx.boundaries[i].edges = snewn(g->num_edges, char);
+ memset(biasctx.boundaries[i].edges, 0, g->num_edges);
+ biasctx.boundaries[i].edges_todo = tdq_new(g->num_edges);
+ tdq_fill(biasctx.boundaries[i].edges_todo);
+ biasctx.boundaries[i].vertextypes = snewn(g->num_dots, char);
+ memset(biasctx.boundaries[i].vertextypes, 0, g->num_dots);
+ biasctx.boundaries[i].neighbour[0] = snewn(g->num_dots, int);
+ biasctx.boundaries[i].neighbour[1] = snewn(g->num_dots, int);
+ biasctx.boundaries[i].vertextypes_todo = tdq_new(g->num_dots);
+ tdq_fill(biasctx.boundaries[i].vertextypes_todo);
+ biasctx.boundaries[i].blackclues = snewn(g->num_dots, char);
+ memset(biasctx.boundaries[i].blackclues, 0, g->num_dots);
+ biasctx.boundaries[i].blackclues_todo = tdq_new(g->num_dots);
+ tdq_fill(biasctx.boundaries[i].blackclues_todo);
+ }
+ biasctx.boundaries[0].colour = FACE_WHITE;
+ biasctx.boundaries[1].colour = FACE_BLACK;
+ generate_loop(g, board, rs, pearl_loopgen_bias, &biasctx);
+ sfree(biasctx.faces);
+ tdq_free(biasctx.faces_todo);
+ for (i = 0; i < 2; i++) {+ sfree(biasctx.boundaries[i].edges);
+ tdq_free(biasctx.boundaries[i].edges_todo);
+ sfree(biasctx.boundaries[i].vertextypes);
+ sfree(biasctx.boundaries[i].neighbour[0]);
+ sfree(biasctx.boundaries[i].neighbour[1]);
+ tdq_free(biasctx.boundaries[i].vertextypes_todo);
+ sfree(biasctx.boundaries[i].blackclues);
+ tdq_free(biasctx.boundaries[i].blackclues_todo);
+ }
+
+ for (i = 0; i < g->num_edges; i++) {+ grid_edge *e = g->edges + i;
+ enum face_colour c1 = FACE_COLOUR(e->face1);
+ enum face_colour c2 = FACE_COLOUR(e->face2);
+ assert(c1 != FACE_GREY);
+ assert(c2 != FACE_GREY);
+ if (c1 != c2) {+ /* This grid edge is on the loop: lay line along it */
+ int x1 = e->dot1->x/s, y1 = e->dot1->y/s;
+ int x2 = e->dot2->x/s, y2 = e->dot2->y/s;
+
+ /* (x1,y1) and (x2,y2) are now in our grid coords (0-w,0-h). */
+ if (x1 == x2) {+ if (y1 > y2) SWAP(y1,y2);
+
+ assert(y1+1 == y2);
+ lines[y1*w+x1] |= D;
+ lines[y2*w+x1] |= U;
+ } else if (y1 == y2) {+ if (x1 > x2) SWAP(x1,x2);
+
+ assert(x1+1 == x2);
+ lines[y1*w+x1] |= R;
+ lines[y1*w+x2] |= L;
+ } else
+ assert(!"grid with diagonal coords?!");
+ }
+ }
+
+ grid_free(g);
+ sfree(board);
+
+#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 = lines[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 int new_clues(game_params *params, random_state *rs,
+ char *clues, char *grid)
+{+ int w = params->w, h = params->h;
+ int ngen = 0, x, y, d, ret, i;
+
+ while (1) {+ ngen++;
+ 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
+
+ if (!params->nosolve) {+ int *cluespace, *straights, *corners;
+ int nstraights, ncorners, nstraightpos, ncornerpos;
+
+ /*
+ * See if we can solve the puzzle just like this.
+ */
+ ret = pearl_solve(w, h, clues, grid, params->difficulty, FALSE);
+ assert(ret > 0); /* shouldn't be inconsistent! */
+ if (ret != 1)
+ continue; /* go round and try again */
+
+ /*
+ * Check this puzzle isn't too easy.
+ */
+ if (params->difficulty > DIFF_EASY) {+ ret = pearl_solve(w, h, clues, grid, params->difficulty-1, FALSE);
+ assert(ret > 0);
+ if (ret == 1)
+ continue; /* too easy: try again */
+ }
+
+ /*
+ * Now shuffle the grid points and gradually remove the
+ * clues to find a minimal set which still leaves the
+ * puzzle soluble.
+ *
+ * We preferentially attempt to remove whichever type of
+ * clue is currently most numerous, to combat a general
+ * tendency of plain random generation to bias in favour
+ * of many white clues and few black.
+ *
+ * 'nstraights' and 'ncorners' count the number of clues
+ * of each type currently remaining in the grid;
+ * 'nstraightpos' and 'ncornerpos' count the clues of each
+ * type we have left to try to remove. (Clues which we
+ * have tried and failed to remove are counted by the
+ * former but not the latter.)
+ */
+ cluespace = snewn(w*h, int);
+ straights = cluespace;
+ nstraightpos = 0;
+ for (i = 0; i < w*h; i++)
+ if (clues[i] == STRAIGHT)
+ straights[nstraightpos++] = i;
+ corners = straights + nstraightpos;
+ ncornerpos = 0;
+ for (i = 0; i < w*h; i++)
+ if (clues[i] == STRAIGHT)
+ corners[ncornerpos++] = i;
+ nstraights = nstraightpos;
+ ncorners = ncornerpos;
+
+ shuffle(straights, nstraightpos, sizeof(*straights), rs);
+ shuffle(corners, ncornerpos, sizeof(*corners), rs);
+ while (nstraightpos > 0 || ncornerpos > 0) {+ int cluepos;
+ int clue;
+
+ /*
+ * Decide which clue to try to remove next. If both
+ * types are available, we choose whichever kind is
+ * currently overrepresented; otherwise we take
+ * whatever we can get.
+ */
+ if (nstraightpos > 0 && ncornerpos > 0) {+ if (nstraights >= ncorners)
+ cluepos = straights[--nstraightpos];
+ else
+ cluepos = straights[--ncornerpos];
+ } else {+ if (nstraightpos > 0)
+ cluepos = straights[--nstraightpos];
+ else
+ cluepos = straights[--ncornerpos];
+ }
+
+ y = cluepos / w;
+ x = cluepos % w;
+
+ clue = clues[y*w+x];
+ clues[y*w+x] = 0; /* try removing this clue */
+
+ ret = pearl_solve(w, h, clues, grid, params->difficulty, FALSE);
+ assert(ret > 0);
+ if (ret != 1)
+ clues[y*w+x] = clue; /* oops, put it back again */
+ }
+ sfree(cluespace);
+ }
+
+#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 */
+ }
+
+ return ngen;
+}
+
+static char *new_game_desc(game_params *params, random_state *rs,
+ char **aux, int interactive)
+{+ char *grid, *clues;
+ char *desc;
+ int ngen, w = params->w, h = params->h, i, j;
+
+ grid = snewn(w*h, char);
+ clues = snewn(w*h, char);
+
+ ngen = new_clues(params, rs, clues, grid);
+
+ debug(("%d %dx%d loops before finished puzzle.\n", ngen, w, h));+
+ desc = snewn(w * h + 1, char);
+ for (i = j = 0; i < w*h; i++) {+ if (clues[i] == NOCLUE && j > 0 &&
+ desc[j-1] >= 'a' && desc[j-1] < 'z')
+ desc[j-1]++;
+ else if (clues[i] == NOCLUE)
+ desc[j++] = 'a';
+ else if (clues[i] == CORNER)
+ desc[j++] = 'B';
+ else if (clues[i] == STRAIGHT)
+ desc[j++] = 'W';
+ }
+ desc[j] = '\0';
+
+ *aux = snewn(w*h+1, char);
+ for (i = 0; i < w*h; i++)
+ (*aux)[i] = (grid[i] < 10) ? (grid[i] + '0') : (grid[i] + 'A' - 10);
+ (*aux)[w*h] = '\0';
+
+ sfree(grid);
+ sfree(clues);
+
+ return desc;
+}
+
+static char *validate_desc(game_params *params, char *desc)
+{+ int i, sizesofar;
+ const int totalsize = params->w * params->h;
+
+ sizesofar = 0;
+ for (i = 0; desc[i]; i++) {+ if (desc[i] >= 'a' && desc[i] <= 'z')
+ sizesofar += desc[i] - 'a' + 1;
+ else if (desc[i] == 'B' || desc[i] == 'W')
+ sizesofar++;
+ else
+ return "unrecognised character in string";
+ }
+
+ if (sizesofar > totalsize)
+ return "string too long";
+ else if (sizesofar < totalsize)
+ return "string too short";
+
+ return NULL;
+}
+
+static game_state *new_game(midend *me, game_params *params, char *desc)
+{+ game_state *state = snew(game_state);
+ int i, j, sz = params->w*params->h;
+
+ state->completed = state->used_solve = FALSE;
+ state->shared = snew(struct shared_state);
+
+ state->shared->w = params->w;
+ state->shared->h = params->h;
+ state->shared->sz = sz;
+ state->shared->refcnt = 1;
+ state->shared->clues = snewn(sz, char);
+ for (i = j = 0; desc[i]; i++) {+ assert(j < sz);
+ if (desc[i] >= 'a' && desc[i] <= 'z') {+ int n = desc[i] - 'a' + 1;
+ assert(j + n <= sz);
+ while (n-- > 0)
+ state->shared->clues[j++] = NOCLUE;
+ } else if (desc[i] == 'B') {+ state->shared->clues[j++] = CORNER;
+ } else if (desc[i] == 'W') {+ state->shared->clues[j++] = STRAIGHT;
+ }
+ }
+
+ state->lines = snewn(sz, char);
+ state->errors = snewn(sz, char);
+ state->marks = snewn(sz, char);
+ for (i = 0; i < sz; i++)
+ state->lines[i] = state->errors[i] = state->marks[i] = BLANK;
+
+ return state;
+}
+
+static game_state *dup_game(game_state *state)
+{+ game_state *ret = snew(game_state);
+ int sz = state->shared->sz, i;
+
+ ret->shared = state->shared;
+ ret->completed = state->completed;
+ ret->used_solve = state->used_solve;
+ ++ret->shared->refcnt;
+
+ ret->lines = snewn(sz, char);
+ ret->errors = snewn(sz, char);
+ ret->marks = snewn(sz, char);
+ for (i = 0; i < sz; i++) {+ ret->lines[i] = state->lines[i];
+ ret->errors[i] = state->errors[i];
+ ret->marks[i] = state->marks[i];
+ }
+
+ return ret;
+}
+
+static void free_game(game_state *state)
+{+ assert(state);
+ if (--state->shared->refcnt == 0) {+ sfree(state->shared->clues);
+ sfree(state->shared);
+ }
+ sfree(state->lines);
+ sfree(state->errors);
+ sfree(state->marks);
+ sfree(state);
+}
+
+static char nbits[16] = { 0, 1, 1, 2,+ 1, 2, 2, 3,
+ 1, 2, 2, 3,
+ 2, 3, 3, 4 };
+#define NBITS(l) ( ((l) < 0 || (l) > 15) ? 4 : nbits[l] )
+
+#define ERROR_CLUE 16
+
+static void dsf_update_completion(game_state *state, int *loopclass,
+ int ax, int ay, char dir,
+ int *dsf, int *dsfsize)
+{+ int w = state->shared->w /*, h = state->shared->h */;
+ int ac = ay*w+ax, ae, bx, by, bc, be;
+
+ if (!(state->lines[ac] & dir)) return; /* no link */
+ bx = ax + DX(dir); by = ay + DY(dir);
+
+ assert(INGRID(state, bx, by)); /* should not have a link off grid */
+
+ bc = by*w+bx;
+#if 0
+ assert(state->lines[bc] & F(dir)); /* should have reciprocal link */
+#endif
+ /* TODO put above assertion back in once we stop generating partially
+ * soluble puzzles. */
+ if (!(state->lines[bc] & F(dir))) return;
+
+ ae = dsf_canonify(dsf, ac);
+ be = dsf_canonify(dsf, bc);
+
+ if (ae == be) { /* detected a loop! */+ if (*loopclass != -1) /* this is the second loop, doom. */
+ return;
+ *loopclass = ae;
+ } else {+ int size = dsfsize[ae] + dsfsize[be];
+ dsf_merge(dsf, ac, bc);
+ ae = dsf_canonify(dsf, ac);
+ dsfsize[ae] = size;
+ }
+ return;
+}
+
+static void check_completion(game_state *state, int mark)
+{+ int w = state->shared->w, h = state->shared->h, x, y, i, d;
+ int had_error = FALSE /*, is_complete = FALSE */, loopclass;
+ int *dsf, *dsfsize;
+
+ if (mark) {+ for (i = 0; i < w*h; i++) {+ state->errors[i] = 0;
+ }
+ }
+
+#define ERROR(x,y,e) do { had_error = TRUE; if (mark) state->errors[(y)*w+(x)] |= (e); } while(0)+
+ /*
+ * First of all: we should have one single closed loop, passing through all clues.
+ */
+ dsf = snewn(w*h, int);
+ dsfsize = snewn(w*h, int);
+ dsf_init(dsf, w*h);
+ for (i = 0; i < w*h; i++) dsfsize[i] = 1;
+ loopclass = -1;
+
+ for (x = 0; x < w; x++) {+ for (y = 0; y < h; y++) {+ dsf_update_completion(state, &loopclass, x, y, R, dsf, dsfsize);
+ dsf_update_completion(state, &loopclass, x, y, D, dsf, dsfsize);
+ }
+ }
+ if (loopclass != -1) {+ /* We have a loop. Check all squares with lines on. */
+ for (x = 0; x < w; x++) {+ for (y = 0; y < h; y++) {+ if (state->lines[y*w+x] == BLANK) {+ if (state->shared->clues[y*w+x] != NOCLUE) {+ /* the loop doesn't include this clue square! */
+ ERROR(x, y, ERROR_CLUE);
+ }
+ } else {+ if (dsf_canonify(dsf, y*w+x) != loopclass) {+ /* these lines are not on the loop: mark them as error. */
+ ERROR(x, y, state->lines[y*w+x]);
+ }
+ }
+ }
+ }
+ }
+
+ /*
+ * Second: check no clues are contradicted.
+ */
+
+ for (x = 0; x < w; x++) {+ for (y = 0; y < h; y++) {+ int type = state->lines[y*w+x];
+ /*
+ * Check that no square has more than two line segments.
+ */
+ if (NBITS(type) > 2) {+ ERROR(x,y,type);
+ }
+ /*
+ * Check that no clues are contradicted. This code is similar to
+ * the code that sets up the maximal clue array for any given
+ * loop.
+ */
+ if (state->shared->clues[y*w+x] == CORNER) {+ /* Supposed to be a corner: will find a contradiction if
+ * it actually contains a straight line, or if it touches any
+ * corners. */
+ if ((bLR|bUD) & (1 << type)) {+ ERROR(x,y,ERROR_CLUE); /* actually straight */
+ }
+ for (d = 1; d <= 8; d += d) if (type & d) {+ int xx = x + DX(d), yy = y + DY(d);
+ if (!INGRID(state, xx, yy)) {+ ERROR(x,y,d); /* leads off grid */
+ } else {+ if ((bLU|bLD|bRU|bRD) & (1 << state->lines[yy*w+xx])) {+ ERROR(x,y,ERROR_CLUE); /* touches corner */
+ }
+ }
+ }
+ } else if (state->shared->clues[y*w+x] == STRAIGHT) {+ /* Supposed to be straight: will find a contradiction if
+ * it actually contains a corner, or if it only touches
+ * straight lines. */
+ if ((bLU|bLD|bRU|bRD) & (1 << type)) {+ ERROR(x,y,ERROR_CLUE); /* actually a corner */
+ }
+ i = 0;
+ for (d = 1; d <= 8; d += d) if (type & d) {+ int xx = x + DX(d), yy = y + DY(d);
+ if (!INGRID(state, xx, yy)) {+ ERROR(x,y,d); /* leads off grid */
+ } else {+ if ((bLR|bUD) & (1 << state->lines[yy*w+xx]))
+ i++; /* a straight */
+ }
+ }
+ if (i >= 2 && NBITS(type) >= 2) {+ ERROR(x,y,ERROR_CLUE); /* everything touched is straight */
+ }
+ }
+ }
+ }
+ if (!had_error && loopclass != -1) {+ state->completed = TRUE;
+ state->loop_length = dsfsize[loopclass];
+ } else {+ state->completed = FALSE;
+ }
+
+ sfree(dsf);
+ sfree(dsfsize);
+
+ return;
+}
+
+/* completion check:
+ *
+ * - no clues must be contradicted (highlight clue itself in error if so)
+ * - if there is a closed loop it must include every line segment laid
+ * - if there's a smaller closed loop then highlight whole loop as error
+ * - no square must have more than 3 lines radiating from centre point
+ * (highlight all lines in that square as error if so)
+ */
+
+static char *solve_for_diff(game_state *state, char *old_lines, char *new_lines)
+{+ int w = state->shared->w, h = state->shared->h, i;
+ char *move = snewn(w*h*40, char), *p = move;
+
+ *p++ = 'S';
+ for (i = 0; i < w*h; i++) {+ if (old_lines[i] != new_lines[i]) {+ p += sprintf(p, ";R%d,%d,%d", new_lines[i], i%w, i/w);
+ }
+ }
+ *p++ = '\0';
+ move = sresize(move, p - move, char);
+
+ return move;
+}
+
+static char *solve_game(game_state *state, game_state *currstate,
+ char *aux, char **error)
+{+ game_state *solved = dup_game(state);
+ int i, ret, sz = state->shared->sz;
+ char *move;
+
+ if (aux) {+ for (i = 0; i < sz; i++) {+ if (aux[i] >= '0' && aux[i] <= '9')
+ solved->lines[i] = aux[i] - '0';
+ else if (aux[i] >= 'A' && aux[i] <= 'F')
+ solved->lines[i] = aux[i] - 'A' + 10;
+ else {+ *error = "invalid char in aux";
+ move = NULL;
+ goto done;
+ }
+ }
+ ret = 1;
+ } else {+ /* Try to solve with present (half-solved) state first: if there's no
+ * solution from there go back to original state. */
+ ret = pearl_solve(currstate->shared->w, currstate->shared->h,
+ currstate->shared->clues, solved->lines,
+ DIFFCOUNT, FALSE);
+ if (ret < 1)
+ ret = pearl_solve(state->shared->w, state->shared->h,
+ state->shared->clues, solved->lines,
+ DIFFCOUNT, FALSE);
+
+ }
+
+ if (ret < 1) {+ *error = "Unable to find solution";
+ move = NULL;
+ } else {+ move = solve_for_diff(solved, currstate->lines, solved->lines);
+ }
+
+done:
+ free_game(solved);
+ return move;
+}
+
+static int game_can_format_as_text_now(game_params *params)
+{+ return FALSE;
+}
+
+static char *game_text_format(game_state *state)
+{+ return NULL;
+}
+
+struct game_ui {+ int *dragcoords; /* list of (y*w+x) coords in drag so far */
+ int ndragcoords; /* number of entries in dragcoords. 0 = no drag. */
+ int clickx, clicky; /* pixel position of initial click */
+};
+
+static game_ui *new_ui(game_state *state)
+{+ game_ui *ui = snew(game_ui);
+ int sz = state->shared->sz;
+
+ ui->ndragcoords = 0;
+ ui->dragcoords = snewn(sz, int);
+
+ return ui;
+}
+
+static void free_ui(game_ui *ui)
+{+ sfree(ui->dragcoords);
+ sfree(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)
+{+}
+
+#define PREFERRED_TILE_SIZE 31
+#define HALFSZ (ds->halfsz)
+#define TILE_SIZE (ds->halfsz*2 + 1)
+
+#define BORDER ((get_gui_style() == GUI_LOOPY) ? (TILE_SIZE/8) : (TILE_SIZE/2))
+
+#define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
+
+#define COORD(x) ( (x) * TILE_SIZE + BORDER )
+#define FROMCOORD(x) ( ((x) < BORDER) ? -1 : ( ((x) - BORDER) / TILE_SIZE) )
+
+#define DS_ESHIFT 4 /* R/U/L/D shift, for error flags */
+#define DS_DSHIFT 8 /* R/U/L/D shift, for drag-in-progress flags */
+#define DS_MSHIFT 12 /* shift for no-line mark */
+
+#define DS_ERROR_CLUE (1 << 20)
+#define DS_FLASH (1 << 21)
+
+enum { GUI_MASYU, GUI_LOOPY };+
+static int get_gui_style(void)
+{+ static int gui_style = -1;
+
+ if (gui_style == -1) {+ char *env = getenv("PEARL_GUI_LOOPY");+ if (env && (env[0] == 'y' || env[0] == 'Y'))
+ gui_style = GUI_LOOPY;
+ else
+ gui_style = GUI_MASYU;
+ }
+ return gui_style;
+}
+
+struct game_drawstate {+ int halfsz;
+ int started;
+
+ int w, h, sz;
+ unsigned int *lflags; /* size w*h */
+
+ char *draglines; /* size w*h; lines flipped by current drag */
+};
+
+static void update_ui_drag(game_state *state, game_ui *ui, int gx, int gy)
+{+ int /* sz = state->shared->sz, */ w = state->shared->w;
+ int i, ox, oy, pos;
+ int lastpos;
+
+ if (!INGRID(state, gx, gy))
+ return; /* square is outside grid */
+
+ pos = gy * w + gx;
+
+ lastpos = ui->dragcoords[ui->ndragcoords > 0 ? ui->ndragcoords-1 : 0];
+ if (pos == lastpos)
+ return; /* same square as last visited one */
+
+ /* Drag confirmed, if it wasn't already. */
+ if (ui->ndragcoords == 0)
+ ui->ndragcoords = 1;
+
+ /*
+ * Dragging the mouse into a square that's already been visited by
+ * the drag path so far has the effect of truncating the path back
+ * to that square, so a player can back out part of an uncommitted
+ * drag without having to let go of the mouse.
+ */
+ for (i = 0; i < ui->ndragcoords; i++)
+ if (pos == ui->dragcoords[i]) {+ ui->ndragcoords = i+1;
+ return;
+ }
+
+ /*
+ * Otherwise, dragging the mouse into a square that's a rook-move
+ * away from the last one on the path extends the path.
+ */
+ oy = ui->dragcoords[ui->ndragcoords-1] / w;
+ ox = ui->dragcoords[ui->ndragcoords-1] % w;
+ if (ox == gx || oy == gy) {+ int dx = (gx < ox ? -1 : gx > ox ? +1 : 0);
+ int dy = (gy < oy ? -1 : gy > oy ? +1 : 0);
+ while (ox != gx || oy != gy) {+ ox += dx;
+ oy += dy;
+ ui->dragcoords[ui->ndragcoords++] = oy * w + ox;
+ }
+ }
+
+ /*
+ * Failing that, we do nothing at all: if the user has dragged
+ * diagonally across the board, they'll just have to return the
+ * mouse to the last known position and do whatever they meant to
+ * do again, more slowly and clearly.
+ */
+}
+
+/*
+ * Routine shared between interpret_move and game_redraw to work out
+ * the intended effect of a drag path on the grid.
+ *
+ * Call it in a loop, like this:
+ *
+ * int clearing = TRUE;
+ * for (i = 0; i < ui->ndragcoords - 1; i++) {+ * int sx, sy, dx, dy, dir, oldstate, newstate;
+ * interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
+ * &dir, &oldstate, &newstate);
+ *
+ * [do whatever is needed to handle the fact that the drag
+ * wants the edge from sx,sy to dx,dy (heading in direction
+ * 'dir' at the sx,sy end) to be changed from state oldstate
+ * to state newstate, each of which equals either 0 or dir]
+ * }
+ */
+static void interpret_ui_drag(game_state *state, game_ui *ui, int *clearing,
+ int i, int *sx, int *sy, int *dx, int *dy,
+ int *dir, int *oldstate, int *newstate)
+{+ int w = state->shared->w;
+ int sp = ui->dragcoords[i], dp = ui->dragcoords[i+1];
+ *sy = sp/w;
+ *sx = sp%w;
+ *dy = dp/w;
+ *dx = dp%w;
+ *dir = (*dy>*sy ? D : *dy<*sy ? U : *dx>*sx ? R : L);
+ *oldstate = state->lines[sp] & *dir;
+ if (*oldstate) {+ /*
+ * The edge we've dragged over was previously
+ * present. Set it to absent, unless we've already
+ * stopped doing that.
+ */
+ *newstate = *clearing ? 0 : *dir;
+ } else {+ /*
+ * The edge we've dragged over was previously
+ * absent. Set it to present, and cancel the
+ * 'clearing' flag so that all subsequent edges in
+ * the drag are set rather than cleared.
+ */
+ *newstate = *dir;
+ *clearing = FALSE;
+ }
+}
+
+static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
+ int x, int y, int button)
+{+ int w = state->shared->w /*, h = state->shared->h, sz = state->shared->sz */;
+ int gx = FROMCOORD(x), gy = FROMCOORD(y), i;
+ char tmpbuf[80];
+
+ if (button == LEFT_BUTTON) {+ if (!INGRID(state, gx, gy)) return NULL;
+
+ ui->clickx = x; ui->clicky = y;
+ ui->dragcoords[0] = gy * w + gx;
+ ui->ndragcoords = 0; /* will be 1 once drag is confirmed */
+
+ return "";
+ }
+
+ if (IS_MOUSE_DRAG(button)) {+ update_ui_drag(state, ui, gx, gy);
+ return "";
+ }
+
+ if (IS_MOUSE_RELEASE(button)) {+ if (ui->ndragcoords) {+ /* End of a drag: process the cached line data. */
+ int buflen = 0, bufsize = 256, tmplen;
+ char *buf = NULL;
+ const char *sep = "";
+ int clearing = TRUE;
+
+ for (i = 0; i < ui->ndragcoords - 1; i++) {+ int sx, sy, dx, dy, dir, oldstate, newstate;
+ interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
+ &dir, &oldstate, &newstate);
+
+ if (oldstate != newstate) {+ if (!buf) buf = snewn(bufsize, char);
+ tmplen = sprintf(tmpbuf, "%sF%d,%d,%d;F%d,%d,%d", sep,
+ dir, sx, sy, F(dir), dx, dy);
+ if (buflen + tmplen >= bufsize) {+ bufsize = (buflen + tmplen) * 5 / 4 + 256;
+ buf = sresize(buf, bufsize, char);
+ }
+ strcpy(buf + buflen, tmpbuf);
+ buflen += tmplen;
+ sep = ";";
+ }
+ }
+
+ ui->ndragcoords = 0;
+
+ return buf ? buf : "";
+ } else {+ /* Click (or tiny drag). Work out which edge we were closest to. */
+ int cx = COORD(gx) + TILE_SIZE/2, cy = COORD(gy) + TILE_SIZE/2;
+ int gx2, gy2, l1, l2, ismark = (button == RIGHT_RELEASE);
+ char movec = ismark ? 'M' : 'F';
+
+ if (!INGRID(state, gx, gy)) return "";
+
+ if (max(abs(x-cx),abs(y-cy)) < TILE_SIZE/4) {+ /* TODO closer to centre of grid: process as a cell click not an edge click. */
+
+ return "";
+ } else {+ if (abs(x-cx) < abs(y-cy)) {+ /* Closest to top/bottom edge. */
+ l1 = (y < cy) ? U : D;
+ } else {+ /* Closest to left/right edge. */
+ l1 = (x < cx) ? L : R;
+ }
+ gx2 = gx + DX(l1); gy2 = gy + DY(l1);
+ l2 = F(l1);
+
+ if (!INGRID(state, gx, gy) || !INGRID(state, gx2, gy2)) return "";
+
+ /* disallow laying a mark over a line, or vice versa. */
+ if (ismark) {+ if ((state->lines[gy*w+gx] & l1) || (state->lines[gy2*w+gx2] & l2))
+ return "";
+ } else {+ if ((state->marks[gy*w+gx] & l1) || (state->marks[gy2*w+gx2] & l2))
+ return "";
+ }
+
+ sprintf(tmpbuf, "%c%d,%d,%d;%c%d,%d,%d",
+ movec, l1, gx, gy, movec, l2, gx2, gy2);
+ return dupstr(tmpbuf);
+ }
+ }
+ }
+
+ if (button == 'H' || button == 'h')
+ return dupstr("H");+
+ /* TODO cursor */
+
+ return NULL;
+}
+
+static game_state *execute_move(game_state *state, char *move)
+{+ int w = state->shared->w, h = state->shared->h;
+ char c;
+ int x, y, l, n;
+ game_state *ret = dup_game(state);
+
+ debug(("move: %s\n", move));+
+ while (*move) {+ c = *move;
+ if (c == 'S') {+ ret->used_solve = TRUE;
+ move++;
+ } else if (c == 'L' || c == 'N' || c == 'R' || c == 'F' || c == 'M') {+ /* 'line' or 'noline' or 'replace' or 'flip' or 'mark' */
+ move++;
+ if (sscanf(move, "%d,%d,%d%n", &l, &x, &y, &n) != 3)
+ goto badmove;
+ if (!INGRID(state, x, y)) goto badmove;
+ if (l < 0 || l > 15) goto badmove;
+
+ /* TODO trying to set a line over a no-line mark should be
+ * a failed move? */
+
+ if (c == 'L')
+ ret->lines[y*w + x] |= (char)l;
+ else if (c == 'N')
+ ret->lines[y*w + x] &= ~((char)l);
+ else if (c == 'R') {+ ret->lines[y*w + x] = (char)l;
+ ret->marks[y*w + x] &= ~((char)l); /* erase marks too */
+ } else if (c == 'F')
+ ret->lines[y*w + x] ^= (char)l;
+ else if (c == 'M')
+ ret->marks[y*w + x] ^= (char)l;
+
+ move += n;
+ } else if (strcmp(move, "H") == 0) {+ pearl_solve(ret->shared->w, ret->shared->h,
+ ret->shared->clues, ret->lines, DIFFCOUNT, TRUE);
+ for (n = 0; n < w*h; n++)
+ ret->marks[n] &= ~ret->lines[n]; /* erase marks too */
+ move++;
+ } else {+ goto badmove;
+ }
+ if (*move == ';')
+ move++;
+ else if (*move)
+ goto badmove;
+ }
+
+ check_completion(ret, TRUE);
+
+ return ret;
+
+badmove:
+ free_game(ret);
+ return NULL;
+}
+
+/* ----------------------------------------------------------------------
+ * Drawing routines.
+ */
+
+#define FLASH_TIME 0.5F
+
+static void game_compute_size(game_params *params, int tilesize,
+ int *x, int *y)
+{+ /* Ick: fake up `ds->tilesize' for macro expansion purposes */
+ struct { int halfsz; } ads, *ds = &ads;+ ads.halfsz = (tilesize-1)/2;
+
+ *x = (params->w) * TILE_SIZE + 2 * BORDER;
+ *y = (params->h) * TILE_SIZE + 2 * BORDER;
+}
+
+static void game_set_size(drawing *dr, game_drawstate *ds,
+ game_params *params, int tilesize)
+{+ ds->halfsz = (tilesize-1)/2;
+}
+
+static float *game_colours(frontend *fe, int *ncolours)
+{+ float *ret = snewn(3 * NCOLOURS, float);
+ int i;
+
+ game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
+
+ for (i = 0; i < 3; i++) {+ ret[COL_BLACK * 3 + i] = 0.0F;
+ ret[COL_WHITE * 3 + i] = 1.0F;
+ ret[COL_GRID * 3 + i] = 0.4F;
+ }
+
+ ret[COL_ERROR * 3 + 0] = 1.0F;
+ ret[COL_ERROR * 3 + 1] = 0.0F;
+ ret[COL_ERROR * 3 + 2] = 0.0F;
+
+ ret[COL_DRAGON * 3 + 0] = 0.0F;
+ ret[COL_DRAGON * 3 + 1] = 0.0F;
+ ret[COL_DRAGON * 3 + 2] = 1.0F;
+
+ ret[COL_DRAGOFF * 3 + 0] = 0.8F;
+ ret[COL_DRAGOFF * 3 + 1] = 0.8F;
+ ret[COL_DRAGOFF * 3 + 2] = 1.0F;
+
+ ret[COL_FLASH * 3 + 0] = 1.0F;
+ ret[COL_FLASH * 3 + 1] = 1.0F;
+ ret[COL_FLASH * 3 + 2] = 1.0F;
+
+ *ncolours = NCOLOURS;
+
+ return ret;
+}
+
+static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
+{+ struct game_drawstate *ds = snew(struct game_drawstate);
+ int i;
+
+ ds->halfsz = 0;
+ ds->started = FALSE;
+
+ ds->w = state->shared->w;
+ ds->h = state->shared->h;
+ ds->sz = state->shared->sz;
+ ds->lflags = snewn(ds->sz, unsigned int);
+ for (i = 0; i < ds->sz; i++)
+ ds->lflags[i] = 0;
+
+ ds->draglines = snewn(ds->sz, char);
+
+ return ds;
+}
+
+static void game_free_drawstate(drawing *dr, game_drawstate *ds)
+{+ sfree(ds->draglines);
+ sfree(ds->lflags);
+ sfree(ds);
+}
+
+static void draw_lines_specific(drawing *dr, game_drawstate *ds,
+ int x, int y, unsigned int lflags,
+ unsigned int shift, int c)
+{+ int ox = COORD(x), oy = COORD(y);
+ int t2 = HALFSZ, t16 = HALFSZ/4;
+ int cx = ox + t2, cy = oy + t2;
+ int d;
+
+ /* Draw each of the four directions, where laid (or error, or drag, etc.) */
+ for (d = 1; d < 16; d *= 2) {+ int xoff = t2 * DX(d), yoff = t2 * DY(d);
+ int xnudge = abs(t16 * DX(C(d))), ynudge = abs(t16 * DY(C(d)));
+
+ if ((lflags >> shift) & d) {+ int lx = cx + ((xoff < 0) ? xoff : 0) - xnudge;
+ int ly = cy + ((yoff < 0) ? yoff : 0) - ynudge;
+
+ if (c == COL_DRAGOFF && !(lflags & d))
+ continue;
+ if (c == COL_DRAGON && (lflags & d))
+ continue;
+
+ draw_rect(dr, lx, ly,
+ abs(xoff)+2*xnudge+1,
+ abs(yoff)+2*ynudge+1, c);
+ /* end cap */
+ draw_rect(dr, cx - t16, cy - t16, 2*t16+1, 2*t16+1, c);
+ }
+ }
+}
+
+static void draw_square(drawing *dr, game_drawstate *ds, game_ui *ui,
+ int x, int y, unsigned int lflags, char clue)
+{+ int ox = COORD(x), oy = COORD(y);
+ int t2 = HALFSZ, t16 = HALFSZ/4;
+ int cx = ox + t2, cy = oy + t2;
+ int d;
+
+ assert(dr);
+
+ /* Clip to the grid square. */
+ clip(dr, ox, oy, TILE_SIZE, TILE_SIZE);
+
+ /* Clear the square. */
+ draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_BACKGROUND);
+
+ if (get_gui_style() == GUI_LOOPY) {+ /* Draw small dot, underneath any lines. */
+ draw_circle(dr, cx, cy, t16, COL_GRID, COL_GRID);
+ } else {+ /* Draw outline of grid square */
+ draw_line(dr, ox, oy, COORD(x+1), oy, COL_GRID);
+ draw_line(dr, ox, oy, ox, COORD(y+1), COL_GRID);
+ }
+
+ /* Draw grid: either thin gridlines, or no-line marks.
+ * We draw these first because the thick laid lines should be on top. */
+ for (d = 1; d < 16; d *= 2) {+ int xoff = t2 * DX(d), yoff = t2 * DY(d);
+
+ if ((x == 0 && d == L) ||
+ (y == 0 && d == U) ||
+ (x == ds->w-1 && d == R) ||
+ (y == ds->h-1 && d == D))
+ continue; /* no gridlines out to the border. */
+
+ if ((lflags >> DS_MSHIFT) & d) {+ /* either a no-line mark ... */
+ int mx = cx + xoff, my = cy + yoff, msz = t16;
+
+ draw_line(dr, mx-msz, my-msz, mx+msz, my+msz, COL_BLACK);
+ draw_line(dr, mx-msz, my+msz, mx+msz, my-msz, COL_BLACK);
+ } else {+ if (get_gui_style() == GUI_LOOPY) {+ /* draw grid lines connecting centre of cells */
+ draw_line(dr, cx, cy, cx+xoff, cy+yoff, COL_GRID);
+ }
+ }
+ }
+
+ /* Draw each of the four directions, where laid (or error, or drag, etc.)
+ * Order is important here, specifically for the eventual colours of the
+ * exposed end caps. */
+ draw_lines_specific(dr, ds, x, y, lflags, 0,
+ (lflags & DS_FLASH ? COL_FLASH : COL_BLACK));
+ draw_lines_specific(dr, ds, x, y, lflags, DS_ESHIFT, COL_ERROR);
+ draw_lines_specific(dr, ds, x, y, lflags, DS_DSHIFT, COL_DRAGOFF);
+ draw_lines_specific(dr, ds, x, y, lflags, DS_DSHIFT, COL_DRAGON);
+
+ /* Draw a clue, if present */
+ if (clue != NOCLUE) {+ int c = (lflags & DS_FLASH) ? COL_FLASH :
+ (clue == CORNER) ? COL_BLACK : COL_WHITE;
+
+ if (lflags & DS_ERROR_CLUE) /* draw a bigger 'error' clue circle. */
+ draw_circle(dr, cx, cy, TILE_SIZE*3/8, COL_ERROR, COL_ERROR);
+
+ draw_circle(dr, cx, cy, TILE_SIZE/4, c, COL_BLACK);
+ }
+
+ unclip(dr);
+ draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
+}
+
+static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
+ game_state *state, int dir, game_ui *ui,
+ float animtime, float flashtime)
+{+ int w = state->shared->w, h = state->shared->h, sz = state->shared->sz;
+ int x, y, force = 0, flashing = 0;
+
+ if (!ds->started) {+ /*
+ * 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, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER,
+ COL_BACKGROUND);
+
+ if (get_gui_style() == GUI_MASYU) {+ /*
+ * Smaller black rectangle which is the main grid.
+ */
+ draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
+ w*TILE_SIZE + 2*BORDER_WIDTH + 1,
+ h*TILE_SIZE + 2*BORDER_WIDTH + 1,
+ COL_GRID);
+ }
+
+ draw_update(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER);
+
+ ds->started = TRUE;
+ force = 1;
+ }
+
+ if (flashtime > 0 &&
+ (flashtime <= FLASH_TIME/3 ||
+ flashtime >= FLASH_TIME*2/3))
+ flashing = DS_FLASH;
+
+ memset(ds->draglines, 0, sz);
+ if (ui->dragcoords) {+ int i, clearing = TRUE;
+ for (i = 0; i < ui->ndragcoords - 1; i++) {+ int sx, sy, dx, dy, dir, oldstate, newstate;
+ interpret_ui_drag(state, ui, &clearing, i, &sx, &sy, &dx, &dy,
+ &dir, &oldstate, &newstate);
+ ds->draglines[sy*w+sx] ^= (oldstate ^ newstate);
+ ds->draglines[dy*w+dx] ^= (F(oldstate) ^ F(newstate));
+ }
+ }
+
+ for (x = 0; x < w; x++) {+ for (y = 0; y < h; y++) {+ unsigned int f = (unsigned int)state->lines[y*w+x];
+ unsigned int eline = (unsigned int)(state->errors[y*w+x] & (R|U|L|D));
+
+ f |= eline << DS_ESHIFT;
+ f |= ((unsigned int)ds->draglines[y*w+x]) << DS_DSHIFT;
+ f |= ((unsigned int)state->marks[y*w+x]) << DS_MSHIFT;
+
+ if (state->errors[y*w+x] & ERROR_CLUE)
+ f |= DS_ERROR_CLUE;
+
+ f |= flashing;
+
+ if (f != ds->lflags[y*w+x] || force) {+ ds->lflags[y*w+x] = f;
+ draw_square(dr, ds, ui, x, y, f, state->shared->clues[y*w+x]);
+ }
+ }
+ }
+}
+
+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)
+{+ if (!oldstate->completed &&
+ newstate->completed && !newstate->used_solve)
+ return FLASH_TIME;
+ else
+ return 0.0F;
+}
+
+static int game_status(game_state *state)
+{+ return state->completed ? +1 : 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)
+{+ int pw, ph;
+
+ /*
+ * I'll use 6mm squares by default.
+ */
+ game_compute_size(params, 600, &pw, &ph);
+ *x = pw / 100.0F;
+ *y = ph / 100.0F;
+}
+
+static void game_print(drawing *dr, game_state *state, int tilesize)
+{+ int w = state->shared->w, h = state->shared->h, x, y;
+ int black = print_mono_colour(dr, 0);
+ int white = print_mono_colour(dr, 1);
+
+ /* No GUI_LOOPY here: only use the familiar masyu style. */
+
+ /* Ick: fake up `ds->tilesize' for macro expansion purposes */
+ game_drawstate *ds = game_new_drawstate(dr, state);
+ game_set_size(dr, ds, NULL, tilesize);
+
+ /* Draw grid outlines (black). */
+ for (x = 0; x <= w; x++)
+ draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), black);
+ for (y = 0; y <= h; y++)
+ draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), black);
+
+ for (x = 0; x < w; x++) {+ for (y = 0; y < h; y++) {+ int cx = COORD(x) + HALFSZ, cy = COORD(y) + HALFSZ;
+ int clue = state->shared->clues[y*w+x];
+
+ draw_lines_specific(dr, ds, x, y, state->lines[y*w+x], 0, black);
+
+ if (clue != NOCLUE) {+ int c = (clue == CORNER) ? black : white;
+ draw_circle(dr, cx, cy, TILE_SIZE/4, c, black);
+ }
+ }
+ }
+
+ game_free_drawstate(dr, ds);
+}
+
+#ifdef COMBINED
+#define thegame pearl
+#endif
+
+const struct game thegame = {+ "Pearl", "games.pearl", "pearl",
+ default_params,
+ game_fetch_preset,
+ decode_params,
+ encode_params,
+ free_params,
+ dup_params,
+ TRUE, game_configure, custom_params,
+ validate_params,
+ new_game_desc,
+ validate_desc,
+ new_game,
+ dup_game,
+ free_game,
+ TRUE, 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,
+ PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
+ game_colours,
+ game_new_drawstate,
+ game_free_drawstate,
+ game_redraw,
+ game_anim_length,
+ game_flash_length,
+ game_status,
+ TRUE, FALSE, game_print_size, game_print,
+ FALSE, /* wants_statusbar */
+ FALSE, game_timing_state,
+ 0, /* flags */
+};
+
+#ifdef STANDALONE_SOLVER
+
+#include <time.h>
+#include <stdarg.h>
+
+const char *quis = NULL;
+
+static void usage(FILE *out) {+ fprintf(out, "usage: %s <params>\n", quis);
+}
+
+static void pnum(int n, int ntot, const char *desc)
+{+ printf("%2.1f%% (%d) %s", (double)n*100.0 / (double)ntot, n, desc);+}
+
+static void start_soak(game_params *p, random_state *rs, int nsecs)
+{+ time_t tt_start, tt_now, tt_last;
+ int n = 0, nsolved = 0, nimpossible = 0, ret;
+ char *grid, *clues;
+
+ tt_start = tt_last = time(NULL);
+
+ /* Currently this generates puzzles of any difficulty (trying to solve it
+ * on the maximum difficulty level and not checking it's not too easy). */
+ printf("Soak-testing a %dx%d grid (any difficulty)", p->w, p->h);+ if (nsecs > 0) printf(" for %d seconds", nsecs);+ printf(".\n");+
+ p->nosolve = TRUE;
+
+ grid = snewn(p->w*p->h, char);
+ clues = snewn(p->w*p->h, char);
+
+ while (1) {+ n += new_clues(p, rs, clues, grid); /* should be 1, with nosolve */
+
+ ret = pearl_solve(p->w, p->h, clues, grid, DIFF_TRICKY, FALSE);
+ if (ret <= 0) nimpossible++;
+ if (ret == 1) nsolved++;
+
+ tt_now = time(NULL);
+ if (tt_now > tt_last) {+ tt_last = tt_now;
+
+ printf("%d total, %3.1f/s, ",+ n, (double)n / ((double)tt_now - tt_start));
+ pnum(nsolved, n, "solved"); printf(", ");+ printf("%3.1f/s", (double)nsolved / ((double)tt_now - tt_start));+ if (nimpossible > 0)
+ pnum(nimpossible, n, "impossible");
+ printf("\n");+ }
+ if (nsecs > 0 && (tt_now - tt_start) > nsecs) {+ printf("\n");+ break;
+ }
+ }
+
+ sfree(grid);
+ sfree(clues);
+}
+
+int main(int argc, const char *argv[])
+{+ game_params *p = NULL;
+ random_state *rs = NULL;
+ time_t seed = time(NULL);
+ char *id = NULL, *err;
+
+ setvbuf(stdout, NULL, _IONBF, 0);
+
+ quis = argv[0];
+
+ while (--argc > 0) {+ char *p = (char*)(*++argv);
+ if (!strcmp(p, "-e") || !strcmp(p, "--seed")) {+ seed = atoi(*++argv);
+ argc--;
+ } else if (*p == '-') {+ fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
+ usage(stderr);
+ exit(1);
+ } else {+ id = p;
+ }
+ }
+
+ rs = random_new((void*)&seed, sizeof(time_t));
+ p = default_params();
+
+ if (id) {+ if (strchr(id, ':')) {+ fprintf(stderr, "soak takes params only.\n");
+ goto done;
+ }
+
+ decode_params(p, id);
+ err = validate_params(p, 1);
+ if (err) {+ fprintf(stderr, "%s: %s", argv[0], err);
+ goto done;
+ }
+
+ start_soak(p, rs, 0); /* run forever */
+ } else {+ int i;
+
+ for (i = 5; i <= 12; i++) {+ p->w = p->h = i;
+ start_soak(p, rs, 5);
+ }
+ }
+
+done:
+ free_params(p);
+ random_free(rs);
+
+ return 0;
+}
+
+#endif
+
+/* vim: set shiftwidth=4 tabstop=8: */
--- a/puzzles.but
+++ b/puzzles.but
@@ -2908,6 +2908,71 @@
\dd Size of grid in squares.
+\C{pearl} \i{Pearl}+
+\cfg{winhelp-topic}{games.pearl}+
+You have a grid of squares. Your job is to draw lines between the
+centres of horizontally or vertically adjacent squares, so that the
+lines form a single closed loop. In the resulting grid, some of the
+squares that the loop passes through will contain corners, and some
+will be straight horizontal or vertical lines. (And some squares can
+be completely empty \dash the loop doesn't have to pass through every
+square.)
+
+Some of the squares contain black and white circles, which are clues
+that the loop must satisfy.
+
+A black circle in a square indicates that that square is a corner, but
+neither of the squares adjacent to it in the loop is also a corner.
+
+A while circle indicates that the square is a straight edge, but \e{at+least one} of the squares adjacent to it in the loop is a corner.
+
+(In both cases, the clue only constrains the two squares adjacent
+\e{in the loop}, that is, the squares that the loop passes into after+leaving the clue square. The squares that are only adjacent \e{in the+grid} are not constrained.)
+
+Credit for this puzzle goes to \i{Nikoli}, who call it \q{Masyu}.+\k{nikoli-pearl}.+
+Thanks to James Harvey for assistance with the implementation.
+
+\B{nikoli-pearl}+\W{http://www.nikoli.co.jp/en/puzzles/masyu/}\cw{http://www.nikoli.co.jp/en/puzzles/masyu/}+
+\H{pearl-controls} \I{controls, for Pearl}Pearl controls+
+Click with the left button on a grid edge to draw a segment of the
+loop through that edge, or to remove a segment once it is drawn.
+
+Drag with the left button through a series of squares to draw more
+than one segment of the loop in one go. Alternatively, drag over an
+existing part of the loop to undraw it, or to undraw part of it and
+then go in a different direction.
+
+Click with the right button on a grid edge to mark it with a cross,
+indicating that you are sure the loop does not go through that edge.
+(For instance, if you have decided which of the squares adjacent to a
+white clue has to be a corner, but don't yet know which way the corner
+turns, you might mark the one way it \e{can't} go with a cross.)+
+(All the actions described in \k{common-actions} are also available.)+
+\H{pearl-parameters} \I{parameters, for Pearl}Pearl parameters+
+These parameters are available from the \q{Custom...} option on the+\q{Type} menu.+
+\dt \e{Width}, \e{Height}+
+\dd Size of grid in squares.
+
+\dt \e{Difficulty}+
+\dd Controls the difficulty of the generated puzzle.
+
\A{licence} \I{MIT licence}\ii{Licence} This software is \i{copyright} 2004-2010 Simon Tatham.--- a/puzzles.h
+++ b/puzzles.h
@@ -348,6 +348,43 @@
void dsf_init(int *dsf, int len);
/*
+ * tdq.c
+ */
+
+/*
+ * Data structure implementing a 'to-do queue', a simple
+ * de-duplicating to-do list mechanism.
+ *
+ * Specification: a tdq is a queue which can hold integers from 0 to
+ * n-1, where n was some constant specified at tdq creation time. No
+ * integer may appear in the queue's current contents more than once;
+ * an attempt to add an already-present integer again will do nothing,
+ * so that that integer is removed from the queue at the position
+ * where it was _first_ inserted. The add and remove operations take
+ * constant time.
+ *
+ * The idea is that you might use this in applications like solvers:
+ * keep a tdq listing the indices of grid squares that you currently
+ * need to process in some way. Whenever you modify a square in a way
+ * that will require you to re-scan its neighbours, add them to the
+ * list with tdq_add; meanwhile you're constantly taking elements off
+ * the list when you need another square to process. In solvers where
+ * deductions are mostly localised, this should prevent repeated
+ * O(N^2) loops over the whole grid looking for something to do. (But
+ * if only _most_ of the deductions are localised, then you should
+ * respond to an empty to-do list by re-adding everything using
+ * tdq_fill, so _then_ you rescan the whole grid looking for newly
+ * enabled non-local deductions. Only if you've done that and emptied
+ * the list again finding nothing new to do are you actually done.)
+ */
+typedef struct tdq tdq;
+tdq *tdq_new(int n);
+void tdq_free(tdq *tdq);
+void tdq_add(tdq *tdq, int k);
+int tdq_remove(tdq *tdq); /* returns -1 if nothing available */
+void tdq_fill(tdq *tdq); /* add everything to the tdq at once */
+
+/*
* laydomino.c
*/
int *domino_layout(int w, int h, random_state *rs);
--- /dev/null
+++ b/tdq.c
@@ -1,0 +1,88 @@
+/*
+ * tdq.c: implement a 'to-do queue', a simple de-duplicating to-do
+ * list mechanism.
+ */
+
+#include <assert.h>
+
+#include "puzzles.h"
+
+/*
+ * Implementation: a tdq consists of a circular buffer of size n
+ * storing the integers currently in the queue, plus an array of n
+ * booleans indicating whether each integer is already there.
+ *
+ * Using a circular buffer of size n to store between 0 and n items
+ * inclusive has an obvious failure mode: if the input and output
+ * pointers are the same, how do you know whether that means the
+ * buffer is full or empty?
+ *
+ * In this application we have a simple way to tell: in the former
+ * case, the flags array is all 1s, and in the latter case it's all
+ * 0s. So we could spot that case and check, say, flags[0].
+ *
+ * However, it's even easier to simply determine whether the queue is
+ * non-empty by testing flags[buffer[op]] - that way we don't even
+ * _have_ to compare ip against op.
+ */
+
+struct tdq {+ int n;
+ int *queue;
+ int ip, op; /* in pointer, out pointer */
+ char *flags;
+};
+
+tdq *tdq_new(int n)
+{+ int i;
+ tdq *tdq = snew(struct tdq);
+ tdq->queue = snewn(n, int);
+ tdq->flags = snewn(n, char);
+ for (i = 0; i < n; i++) {+ tdq->queue[i] = 0;
+ tdq->flags[i] = 0;
+ }
+ tdq->n = n;
+ tdq->ip = tdq->op = 0;
+ return tdq;
+}
+
+void tdq_free(tdq *tdq)
+{+ sfree(tdq->queue);
+ sfree(tdq->flags);
+ sfree(tdq);
+}
+
+void tdq_add(tdq *tdq, int k)
+{+ assert((unsigned)k < (unsigned)tdq->n);
+ if (!tdq->flags[k]) {+ tdq->queue[tdq->ip] = k;
+ tdq->flags[k] = 1;
+ if (++tdq->ip == tdq->n)
+ tdq->ip = 0;
+ }
+}
+
+int tdq_remove(tdq *tdq)
+{+ int ret = tdq->queue[tdq->op];
+
+ if (!tdq->flags[ret])
+ return -1;
+
+ tdq->flags[ret] = 0;
+ if (++tdq->op == tdq->n)
+ tdq->op = 0;
+
+ return ret;
+}
+
+void tdq_fill(tdq *tdq)
+{+ int i;
+ for (i = 0; i < tdq->n; i++)
+ tdq_add(tdq, i);
+}
--- a/unfinished/pearl.R
+++ /dev/null
@@ -1,21 +1,0 @@
-# -*- makefile -*-
-
-PEARL_EXTRA = dsf
-
-pearl : [X] GTK COMMON pearl PEARL_EXTRA pearl-icon|no-icon
-
-pearl : [G] WINDOWS COMMON pearl PEARL_EXTRA pearl.res?
-
-ALL += pearl[COMBINED] PEARL_EXTRA
-
-!begin gtk
-GAMES += pearl
-!end
-
-!begin >list.c
- A(pearl) \
-!end
-
-!begin >wingames.lst
-pearl.exe:Pearl
-!end
--- a/unfinished/pearl.c
+++ /dev/null
@@ -1,1410 +1,0 @@
-/*
- * 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 */
-};