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