Commit my work so far on a generator for Nikoli's `Block Puzzle'. It
authorsimon <simon@cda61777-01e9-0310-a592-d414129be87e>
Sat, 25 Aug 2007 14:10:49 +0000 (14:10 +0000)
committersimon <simon@cda61777-01e9-0310-a592-d414129be87e>
Sat, 25 Aug 2007 14:10:49 +0000 (14:10 +0000)
works, but it's slow, and the puzzles are currently at a relatively
low level of difficulty. Also this is a generator only: no UI yet
(because I'm waiting to see if I can make the generator practical
before bothering to write the rest).

git-svn-id: svn://svn.tartarus.org/sgt/puzzles@7700 cda61777-01e9-0310-a592-d414129be87e

unfinished/separate.R [new file with mode: 0644]
unfinished/separate.c [new file with mode: 0644]

diff --git a/unfinished/separate.R b/unfinished/separate.R
new file mode 100644 (file)
index 0000000..53b6e85
--- /dev/null
@@ -0,0 +1,21 @@
+# -*- makefile -*-
+
+SEPARATE = separate divvy dsf
+
+separate : [X] GTK COMMON SEPARATE separate-icon|no-icon
+
+separate : [G] WINDOWS COMMON SEPARATE separate.res|noicon.res
+
+ALL += separate
+
+!begin gtk
+GAMES += separate
+!end
+
+!begin >list.c
+    A(separate) \
+!end
+
+!begin >wingames.lst
+separate.exe:Separate
+!end
diff --git a/unfinished/separate.c b/unfinished/separate.c
new file mode 100644 (file)
index 0000000..d6542a1
--- /dev/null
@@ -0,0 +1,845 @@
+/*
+ * separate.c: Implementation of `Block Puzzle', a Japanese-only
+ * Nikoli puzzle seen at
+ *   http://www.nikoli.co.jp/ja/puzzles/block_puzzle/
+ * 
+ * It's difficult to be absolutely sure of the rules since online
+ * Japanese translators are so bad, but looking at the sample
+ * puzzle it seems fairly clear that the rules of this one are
+ * very simple. You have an mxn grid in which every square
+ * contains a letter, there are k distinct letters with k dividing
+ * mn, and every letter occurs the same number of times; your aim
+ * is to find a partition of the grid into disjoint k-ominoes such
+ * that each k-omino contains exactly one of each letter.
+ * 
+ * (It may be that Nikoli always have m,n,k equal to one another.
+ * However, I don't see that that's critical to the puzzle; k|mn
+ * is the only really important constraint, and even that could
+ * probably be dispensed with if some squares were marked as
+ * unused.)
+ */
+
+/*
+ * Current status: only the solver/generator is yet written, and
+ * although working in principle it's _very_ slow. It generates
+ * 5x5n5 or 6x6n4 readily enough, 6x6n6 with a bit of effort, and
+ * 7x7n7 only with a serious strain. I haven't dared try it higher
+ * than that yet.
+ * 
+ * One idea to speed it up is to implement more of the solver.
+ * Ideas I've so far had include:
+ * 
+ *  - Generalise the deduction currently expressed as `an
+ *    undersized chain with only one direction to extend must take
+ *    it'. More generally, the deduction should say `if all the
+ *    possible k-ominoes containing a given chain also contain
+ *    square x, then mark square x as part of that k-omino'.
+ *     + For example, consider this case:
+ * 
+ *         a ? b    This represents the top left of a board; the letters
+ *         ? ? ?    a,b,c do not represent the letters used in the puzzle,
+ *         c ? ?    but indicate that those three squares are known to be
+ *                  of different ominoes. Now if k >= 4, we can immediately
+ *         deduce that the square midway between b and c belongs to the
+ *         same omino as a, because there is no way we can make a 4-or-
+ *         more-omino containing a which does not also contain that square.
+ *         (Most easily seen by imagining cutting that square out of the 
+ *         grid; then, clearly, the omino containing a has only two
+ *         squares to expand into, and needs at least three.)
+ * 
+ *    The key difficulty with this mode of reasoning is
+ *    identifying such squares. I can't immediately think of a
+ *    simple algorithm for finding them on a wholesale basis.
+ * 
+ *  - Bfs out from a chain looking for the letters it lacks. For
+ *    example, in this situation (top three rows of a 7x7n7 grid):
+ * 
+ *        +-----------+-+
+ *        |E-A-F-B-C D|D|
+ *        +-------     ||
+ *        |E-C-G-D G|G E|
+ *        +-+---        |
+ *        |E|E G A B F A|
+ *
+ *    In this situation we can be sure that the top left chain
+ *    E-A-F-B-C does extend rightwards to the D, because there is
+ *    no other D within reach of that chain. Note also that the
+ *    bfs can skip squares which are known to belong to other
+ *    ominoes than this one.
+ * 
+ *    (This deduction, I fear, should only be used in an
+ *    emergency, because it relies on _all_ squares within range
+ *    of the bfs having particular values and so using it during
+ *    incremental generation rather nails down a lot of the grid.)
+ * 
+ * It's conceivable that another thing we could do would be to
+ * increase the flexibility in the grid generator: instead of
+ * nailing down the _value_ of any square depended on, merely nail
+ * down its equivalence to other squares. Unfortunately this turns
+ * the letter-selection phase of generation into a general graph
+ * colouring problem (we must draw a graph with equivalence
+ * classes of squares as the vertices, and an edge between any two
+ * vertices representing equivalence classes which contain squares
+ * that share an omino, and then k-colour the result) and hence
+ * requires recursion, which bodes ill for something we're doing
+ * that many times per generation.
+ * 
+ * I suppose a simple thing I could try would be tuning the retry
+ * count, just in case it's set too high or too low for efficient
+ * generation.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <ctype.h>
+#include <math.h>
+
+#include "puzzles.h"
+
+enum {
+    COL_BACKGROUND,
+    NCOLOURS
+};
+
+struct game_params {
+    int w, h, k;
+};
+
+struct game_state {
+    int FIXME;
+};
+
+static game_params *default_params(void)
+{
+    game_params *ret = snew(game_params);
+
+    ret->w = ret->h = ret->k = 5;      /* FIXME: a bit bigger? */
+
+    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)
+{
+    params->w = params->h = params->k = atoi(string);
+    while (*string && isdigit((unsigned char)*string)) string++;
+    if (*string == 'x') {
+        string++;
+        params->h = atoi(string);
+       while (*string && isdigit((unsigned char)*string)) string++;
+    }
+    if (*string == 'n') {
+        string++;
+        params->k = atoi(string);
+       while (*string && isdigit((unsigned char)*string)) string++;
+    }
+}
+
+static char *encode_params(game_params *params, int full)
+{
+    char buf[256];
+    sprintf(buf, "%dx%dn%d", params->w, params->h, params->k);
+    return dupstr(buf);
+}
+
+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 and generator.
+ */
+
+struct solver_scratch {
+    int w, h, k;
+
+    /*
+     * Tracks connectedness between squares.
+     */
+    int *dsf;
+
+    /*
+     * size[dsf_canonify(dsf, yx)] tracks the size of the
+     * connected component containing yx.
+     */
+    int *size;
+
+    /*
+     * contents[dsf_canonify(dsf, yx)*k+i] tracks whether or not
+     * the connected component containing yx includes letter i. If
+     * the value is -1, it doesn't; otherwise its value is the
+     * index in the main grid of the square which contributes that
+     * letter to the component.
+     */
+    int *contents;
+
+    /*
+     * disconnect[dsf_canonify(dsf, yx1)*w*h + dsf_canonify(dsf, yx2)]
+     * tracks whether or not the connected components containing
+     * yx1 and yx2 are known to be distinct.
+     */
+    unsigned char *disconnect;
+
+    /*
+     * Temporary space used only inside particular solver loops.
+     */
+    int *tmp;
+};
+
+struct solver_scratch *solver_scratch_new(int w, int h, int k)
+{
+    int wh = w*h;
+    struct solver_scratch *sc = snew(struct solver_scratch);
+
+    sc->w = w;
+    sc->h = h;
+    sc->k = k;
+
+    sc->dsf = snew_dsf(wh);
+    sc->size = snewn(wh, int);
+    sc->contents = snewn(wh * k, int);
+    sc->disconnect = snewn(wh*wh, unsigned char);
+    sc->tmp = snewn(wh, int);
+
+    return sc;
+}
+
+void solver_scratch_free(struct solver_scratch *sc)
+{
+    sfree(sc->dsf);
+    sfree(sc->size);
+    sfree(sc->contents);
+    sfree(sc->disconnect);
+    sfree(sc->tmp);
+    sfree(sc);
+}
+
+void solver_connect(struct solver_scratch *sc, int yx1, int yx2)
+{
+    int w = sc->w, h = sc->h, k = sc->k;
+    int wh = w*h;
+    int i, yxnew;
+
+    yx1 = dsf_canonify(sc->dsf, yx1);
+    yx2 = dsf_canonify(sc->dsf, yx2);
+    assert(yx1 != yx2);
+
+    /*
+     * To connect two components together into a bigger one, we
+     * start by merging them in the dsf itself.
+     */
+    dsf_merge(sc->dsf, yx1, yx2);
+    yxnew = dsf_canonify(sc->dsf, yx2);
+
+    /*
+     * The size of the new component is the sum of the sizes of the
+     * old ones.
+     */
+    sc->size[yxnew] = sc->size[yx1] + sc->size[yx2];
+
+    /*
+     * The contents bitmap of the new component is the union of the
+     * contents of the old ones.
+     * 
+     * Given two numbers at most one of which is not -1, we can
+     * find the other one by adding the two and adding 1; this
+     * will yield -1 if both were -1 to begin with, otherwise the
+     * other.
+     * 
+     * (A neater approach would be to take their bitwise AND, but
+     * this is unfortunately not well-defined standard C when done
+     * to signed integers.)
+     */
+    for (i = 0; i < k; i++) {
+       assert(sc->contents[yx1*k+i] < 0 || sc->contents[yx2*k+i] < 0);
+       sc->contents[yxnew*k+i] = (sc->contents[yx1*k+i] +
+                                  sc->contents[yx2*k+i] + 1);
+    }
+
+    /*
+     * We must combine the rows _and_ the columns in the disconnect
+     * matrix.
+     */
+    for (i = 0; i < wh; i++)
+       sc->disconnect[yxnew*wh+i] = (sc->disconnect[yx1*wh+i] ||
+                                     sc->disconnect[yx2*wh+i]);
+    for (i = 0; i < wh; i++)
+       sc->disconnect[i*wh+yxnew] = (sc->disconnect[i*wh+yx1] ||
+                                     sc->disconnect[i*wh+yx2]);
+}
+
+void solver_disconnect(struct solver_scratch *sc, int yx1, int yx2)
+{
+    int w = sc->w, h = sc->h;
+    int wh = w*h;
+
+    yx1 = dsf_canonify(sc->dsf, yx1);
+    yx2 = dsf_canonify(sc->dsf, yx2);
+    assert(yx1 != yx2);
+    assert(!sc->disconnect[yx1*wh+yx2]);
+    assert(!sc->disconnect[yx2*wh+yx1]);
+
+    /*
+     * Mark the components as disconnected from each other in the
+     * disconnect matrix.
+     */
+    sc->disconnect[yx1*wh+yx2] = sc->disconnect[yx2*wh+yx1] = 1;
+}
+
+void solver_init(struct solver_scratch *sc)
+{
+    int w = sc->w, h = sc->h;
+    int wh = w*h;
+    int i;
+
+    /*
+     * Set up most of the scratch space. We don't set up the
+     * contents array, however, because this will change if we
+     * adjust the letter arrangement and re-run the solver.
+     */
+    dsf_init(sc->dsf, wh);
+    for (i = 0; i < wh; i++) sc->size[i] = 1;
+    memset(sc->disconnect, 0, wh*wh);
+}
+
+int solver_attempt(struct solver_scratch *sc, const unsigned char *grid,
+                  unsigned char *gen_lock)
+{
+    int w = sc->w, h = sc->h, k = sc->k;
+    int wh = w*h;
+    int i, x, y;
+    int done_something_overall = FALSE;
+
+    /*
+     * Set up the contents array from the grid.
+     */
+    for (i = 0; i < wh*k; i++)
+       sc->contents[i] = -1;
+    for (i = 0; i < wh; i++)
+       sc->contents[dsf_canonify(sc->dsf, i)*k+grid[i]] = i;
+
+    while (1) {
+       int done_something = FALSE;
+
+       /*
+        * Go over the grid looking for reasons to add to the
+        * disconnect matrix. We're after pairs of squares which:
+        * 
+        *  - are adjacent in the grid
+        *  - belong to distinct dsf components
+        *  - their components are not already marked as
+        *    disconnected
+        *  - their components share a letter in common.
+        */
+       for (y = 0; y < h; y++) {
+           for (x = 0; x < w; x++) {
+               int dir;
+               for (dir = 0; dir < 2; dir++) {
+                   int x2 = x + dir, y2 = y + 1 - dir;
+                   int yx = y*w+x, yx2 = y2*w+x2;
+
+                   if (x2 >= w || y2 >= h)
+                       continue;      /* one square is outside the grid */
+
+                   yx = dsf_canonify(sc->dsf, yx);
+                   yx2 = dsf_canonify(sc->dsf, yx2);
+                   if (yx == yx2)
+                       continue;      /* same dsf component */
+
+                   if (sc->disconnect[yx*wh+yx2])
+                       continue;      /* already known disconnected */
+
+                   for (i = 0; i < k; i++)
+                       if (sc->contents[yx*k+i] >= 0 &&
+                           sc->contents[yx2*k+i] >= 0)
+                           break;
+                   if (i == k)
+                       continue;      /* no letter in common */
+
+                   /*
+                    * We've found one. Mark yx and yx2 as
+                    * disconnected from each other.
+                    */
+#ifdef SOLVER_DIAGNOSTICS
+                   printf("Disconnecting %d and %d (%c)\n", yx, yx2, 'A'+i);
+#endif
+                   solver_disconnect(sc, yx, yx2);
+                   done_something = done_something_overall = TRUE;
+
+                   /*
+                    * We have just made a deduction which hinges
+                    * on two particular grid squares being the
+                    * same. If we are feeding back to a generator
+                    * loop, we must therefore mark those squares
+                    * as fixed in the generator, so that future
+                    * rearrangement of the grid will not break
+                    * the information on which we have already
+                    * based deductions.
+                    */
+                   if (gen_lock) {
+                       gen_lock[sc->contents[yx*k+i]] = 1;
+                       gen_lock[sc->contents[yx2*k+i]] = 1;
+                   }
+               }
+           }
+       }
+
+       /*
+        * Now go over the grid looking for dsf components which
+        * are below maximum size and only have one way to extend,
+        * and extending them.
+        */
+       for (i = 0; i < wh; i++)
+           sc->tmp[i] = -1;
+       for (y = 0; y < h; y++) {
+           for (x = 0; x < w; x++) {
+               int yx = dsf_canonify(sc->dsf, y*w+x);
+               int dir;
+
+               if (sc->size[yx] == k)
+                   continue;
+
+               for (dir = 0; dir < 4; dir++) {
+                   int x2 = x + (dir==0 ? -1 : dir==2 ? 1 : 0);
+                   int y2 = y + (dir==1 ? -1 : dir==3 ? 1 : 0);
+                   int yx2, yx2c;
+
+                   if (y2 < 0 || y2 >= h || x2 < 0 || x2 >= w)
+                       continue;
+                   yx2 = y2*w+x2;
+                   yx2c = dsf_canonify(sc->dsf, yx2);
+
+                   if (yx2c != yx && !sc->disconnect[yx2c*wh+yx]) {
+                       /*
+                        * Component yx can be extended into square
+                        * yx2.
+                        */
+                       if (sc->tmp[yx] == -1)
+                           sc->tmp[yx] = yx2;
+                       else if (sc->tmp[yx] != yx2)
+                           sc->tmp[yx] = -2;   /* multiple choices found */
+                   }
+               }
+           }
+       }
+       for (i = 0; i < wh; i++) {
+           if (sc->tmp[i] >= 0) {
+               /*
+                * Make sure we haven't connected the two already
+                * during this loop (which could happen if for
+                * _both_ components this was the only way to
+                * extend them).
+                */
+               if (dsf_canonify(sc->dsf, i) ==
+                   dsf_canonify(sc->dsf, sc->tmp[i]))
+                   continue;
+
+#ifdef SOLVER_DIAGNOSTICS
+               printf("Connecting %d and %d\n", i, sc->tmp[i]);
+#endif
+               solver_connect(sc, i, sc->tmp[i]);
+               done_something = done_something_overall = TRUE;
+               break;
+           }
+       }
+
+       if (!done_something)
+           break;
+    }
+
+    /*
+     * Return 0 if we haven't made any progress; 1 if we've done
+     * something but not solved it completely; 2 if we've solved
+     * it completely.
+     */
+    for (i = 0; i < wh; i++)
+       if (sc->size[dsf_canonify(sc->dsf, i)] != k)
+           break;
+    if (i == wh)
+       return 2;
+    if (done_something_overall)
+       return 1;
+    return 0;
+}
+
+unsigned char *generate(int w, int h, int k, random_state *rs)
+{
+    int wh = w*h;
+    int n = wh/k;
+    struct solver_scratch *sc;
+    unsigned char *grid;
+    unsigned char *shuffled;
+    int i, j, m, retries;
+    int *permutation;
+    unsigned char *gen_lock;
+    extern int *divvy_rectangle(int w, int h, int k, random_state *rs);
+
+    sc = solver_scratch_new(w, h, k);
+    grid = snewn(wh, unsigned char);
+    shuffled = snewn(k, unsigned char);
+    permutation = snewn(wh, int);
+    gen_lock = snewn(wh, unsigned char);
+
+    do {
+       int *dsf = divvy_rectangle(w, h, k, rs);
+
+       /*
+        * Go through the dsf and find the indices of all the
+        * squares involved in each omino, in a manner conducive
+        * to per-omino indexing. We set permutation[i*k+j] to be
+        * the index of the jth square (ordered arbitrarily) in
+        * omino i.
+        */
+       for (i = j = 0; i < wh; i++)
+           if (dsf_canonify(dsf, i) == i) {
+               sc->tmp[i] = j;
+               /*
+                * During this loop and the following one, we use
+                * the last element of each row of permutation[]
+                * as a counter of the number of indices so far
+                * placed in it. When we place the final index of
+                * an omino, that counter is overwritten, but that
+                * doesn't matter because we'll never use it
+                * again. Of course this depends critically on
+                * divvy_rectangle() having returned correct
+                * results, or else chaos would ensue.
+                */
+               permutation[j*k+k-1] = 0;
+               j++;
+           }
+       for (i = 0; i < wh; i++) {
+           j = sc->tmp[dsf_canonify(dsf, i)];
+           m = permutation[j*k+k-1]++;
+           permutation[j*k+m] = i;
+       }
+
+       /*
+        * Track which squares' letters we have already depended
+        * on for deductions. This is gradually updated by
+        * solver_attempt().
+        */
+       memset(gen_lock, 0, wh);
+
+       /*
+        * Now repeatedly fill the grid with letters, and attempt
+        * to solve it. If the solver makes progress but does not
+        * fail completely, then gen_lock will have been updated
+        * and we try again. On a complete failure, though, we
+        * have no option but to give up and abandon this set of
+        * ominoes.
+        */
+       solver_init(sc);
+       retries = k*k;
+       while (1) {
+           /*
+            * Fill the grid with letters. We can safely use
+            * sc->tmp to hold the set of letters required at each
+            * stage, since it's at least size k and is currently
+            * unused.
+            */
+           for (i = 0; i < n; i++) {
+               /*
+                * First, determine the set of letters already
+                * placed in this omino by gen_lock.
+                */
+               for (j = 0; j < k; j++)
+                   sc->tmp[j] = j;
+               for (j = 0; j < k; j++) {
+                   int index = permutation[i*k+j];
+                   int letter = grid[index];
+                   if (gen_lock[index])
+                       sc->tmp[letter] = -1;
+               }
+               /*
+                * Now collect together all the remaining letters
+                * and randomly shuffle them.
+                */
+               for (j = m = 0; j < k; j++)
+                   if (sc->tmp[j] >= 0)
+                       sc->tmp[m++] = sc->tmp[j];
+               shuffle(sc->tmp, m, sizeof(*sc->tmp), rs);
+               /*
+                * Finally, write the shuffled letters into the
+                * grid.
+                */
+               for (j = 0; j < k; j++) {
+                   int index = permutation[i*k+j];
+                   if (!gen_lock[index])
+                       grid[index] = sc->tmp[--m];
+               }
+               assert(m == 0);
+           }
+
+           /*
+            * Now we have a candidate grid. Attempt to progress
+            * the solution.
+            */
+           m = solver_attempt(sc, grid, gen_lock);
+           if (m == 2 ||              /* success */
+               (m == 0 && retries-- <= 0))   /* failure */
+               break;
+           if (m == 1)
+               retries = k*k;         /* reset this counter, and continue */
+       }
+
+       sfree(dsf);
+    } while (m == 0);
+
+    sfree(gen_lock);
+    sfree(permutation);
+    sfree(shuffled);
+    solver_scratch_free(sc);
+
+    return grid;
+}
+
+/* ----------------------------------------------------------------------
+ * End of solver/generator code.
+ */
+
+static char *new_game_desc(game_params *params, random_state *rs,
+                          char **aux, int interactive)
+{
+    int w = params->w, h = params->h, wh = w*h, k = params->k;
+    unsigned char *grid;
+    char *desc;
+    int i;
+
+    grid = generate(w, h, k, rs);
+
+    desc = snewn(wh+1, char);
+    for (i = 0; i < wh; i++)
+       desc[i] = 'A' + grid[i];
+    desc[wh] = '\0';
+
+    sfree(grid);
+
+    return desc;
+}
+
+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 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_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 nullgame
+#endif
+
+const struct game thegame = {
+    "Null Game", 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_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,
+    FALSE, FALSE, game_print_size, game_print,
+    FALSE,                            /* wants_statusbar */
+    FALSE, game_timing_state,
+    0,                                /* flags */
+};