shithub: puzzles

Download patch

ref: 083de051cbc88f391c6bd28481b856013e293ce9
parent: 1fcb61cffe538c11a11fc2ec94d6470a61df019e
author: Simon Tatham <anakin@pobox.com>
date: Mon Mar 29 16:49:17 EDT 2021

Filling: remove directional bias in grid generation.

The method of generating a solved Filling grid (before winnowing
clues) is to loop over every square of the board, and for each one, if
it has a neighbour which is part of a different region of the same
size (i.e. the board is not currently legal), fix it by merging with
one of its neighbours. We pick a neighbour to merge with based on the
size of its region - but we always loop over the four possible
neighbours in the same order, which introduces a directional bias into
the breaking of ties in that comparison.

Now we iterate over the four directions in random order.

--- a/filling.c

+++ b/filling.c

@@ -414,10 +414,15 @@

             int merge = SENTINEL, min = maxsize - size + 1;

 	    bool error = false;

             int neighbour, neighbour_size, j;

+	    int directions[4];

+            for (j = 0; j < 4; ++j)

+		directions[j] = j;

+	    shuffle(directions, 4, sizeof(int), rs);

+

             for (j = 0; j < 4; ++j) {

-                const int x = (board[i] % w) + dx[j];

-                const int y = (board[i] / w) + dy[j];

+                const int x = (board[i] % w) + dx[directions[j]];

+                const int y = (board[i] / w) + dy[directions[j]];

                 if (x < 0 || x >= w || y < 0 || y >= h) continue;

                 neighbour = dsf_canonify(dsf, w*y + x);