2 * map.c: Game involving four-colouring a map.
9 * - better four-colouring algorithm?
22 * In standalone solver mode, `verbose' is a variable which can be
23 * set by command-line option; in debugging mode it's simply always
26 #if defined STANDALONE_SOLVER
27 #define SOLVER_DIAGNOSTICS
29 #elif defined SOLVER_DIAGNOSTICS
34 * I don't seriously anticipate wanting to change the number of
35 * colours used in this game, but it doesn't cost much to use a
36 * #define just in case :-)
39 #define THREE (FOUR-1)
44 * Ghastly run-time configuration option, just for Gareth (again).
46 static int flash_type
= -1;
47 static float flash_length
;
50 * Difficulty levels. I do some macro ickery here to ensure that my
51 * enum and the various forms of my name list always match up.
57 A(RECURSE,Unreasonable,u)
58 #define ENUM(upper,title,lower) DIFF_ ## upper,
59 #define TITLE(upper,title,lower) #title,
60 #define ENCODE(upper,title,lower) #lower
61 #define CONFIG(upper,title,lower) ":" #title
62 enum { DIFFLIST(ENUM
) DIFFCOUNT
};
63 static char const *const map_diffnames
[] = { DIFFLIST(TITLE
) };
64 static char const map_diffchars
[] = DIFFLIST(ENCODE
);
65 #define DIFFCONFIG DIFFLIST(CONFIG)
67 enum { TE
, BE
, LE
, RE
}; /* top/bottom/left/right edges */
72 COL_0
, COL_1
, COL_2
, COL_3
,
73 COL_ERROR
, COL_ERRTEXT
,
88 int *edgex
, *edgey
; /* position of a point on each edge */
89 int *regionx
, *regiony
; /* position of a point in each region */
95 int *colouring
, *pencil
;
96 int completed
, cheated
;
99 static game_params
*default_params(void)
101 game_params
*ret
= snew(game_params
);
106 ret
->diff
= DIFF_NORMAL
;
111 static const struct game_params map_presets
[] = {
112 {20, 15, 30, DIFF_EASY
},
113 {20, 15, 30, DIFF_NORMAL
},
114 {20, 15, 30, DIFF_HARD
},
115 {20, 15, 30, DIFF_RECURSE
},
116 {30, 25, 75, DIFF_NORMAL
},
117 {30, 25, 75, DIFF_HARD
},
120 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
125 if (i
< 0 || i
>= lenof(map_presets
))
128 ret
= snew(game_params
);
129 *ret
= map_presets
[i
];
131 sprintf(str
, "%dx%d, %d regions, %s", ret
->w
, ret
->h
, ret
->n
,
132 map_diffnames
[ret
->diff
]);
139 static void free_params(game_params
*params
)
144 static game_params
*dup_params(game_params
*params
)
146 game_params
*ret
= snew(game_params
);
147 *ret
= *params
; /* structure copy */
151 static void decode_params(game_params
*params
, char const *string
)
153 char const *p
= string
;
156 while (*p
&& isdigit((unsigned char)*p
)) p
++;
160 while (*p
&& isdigit((unsigned char)*p
)) p
++;
162 params
->h
= params
->w
;
167 while (*p
&& (*p
== '.' || isdigit((unsigned char)*p
))) p
++;
169 params
->n
= params
->w
* params
->h
/ 8;
174 for (i
= 0; i
< DIFFCOUNT
; i
++)
175 if (*p
== map_diffchars
[i
])
181 static char *encode_params(game_params
*params
, int full
)
185 sprintf(ret
, "%dx%dn%d", params
->w
, params
->h
, params
->n
);
187 sprintf(ret
+ strlen(ret
), "d%c", map_diffchars
[params
->diff
]);
192 static config_item
*game_configure(game_params
*params
)
197 ret
= snewn(5, config_item
);
199 ret
[0].name
= "Width";
200 ret
[0].type
= C_STRING
;
201 sprintf(buf
, "%d", params
->w
);
202 ret
[0].sval
= dupstr(buf
);
205 ret
[1].name
= "Height";
206 ret
[1].type
= C_STRING
;
207 sprintf(buf
, "%d", params
->h
);
208 ret
[1].sval
= dupstr(buf
);
211 ret
[2].name
= "Regions";
212 ret
[2].type
= C_STRING
;
213 sprintf(buf
, "%d", params
->n
);
214 ret
[2].sval
= dupstr(buf
);
217 ret
[3].name
= "Difficulty";
218 ret
[3].type
= C_CHOICES
;
219 ret
[3].sval
= DIFFCONFIG
;
220 ret
[3].ival
= params
->diff
;
230 static game_params
*custom_params(config_item
*cfg
)
232 game_params
*ret
= snew(game_params
);
234 ret
->w
= atoi(cfg
[0].sval
);
235 ret
->h
= atoi(cfg
[1].sval
);
236 ret
->n
= atoi(cfg
[2].sval
);
237 ret
->diff
= cfg
[3].ival
;
242 static char *validate_params(game_params
*params
, int full
)
244 if (params
->w
< 2 || params
->h
< 2)
245 return "Width and height must be at least two";
247 return "Must have at least five regions";
248 if (params
->n
> params
->w
* params
->h
)
249 return "Too many regions to fit in grid";
253 /* ----------------------------------------------------------------------
254 * Cumulative frequency table functions.
258 * Initialise a cumulative frequency table. (Hardly worth writing
259 * this function; all it does is to initialise everything in the
262 static void cf_init(int *table
, int n
)
266 for (i
= 0; i
< n
; i
++)
271 * Increment the count of symbol `sym' by `count'.
273 static void cf_add(int *table
, int n
, int sym
, int count
)
290 * Cumulative frequency lookup: return the total count of symbols
291 * with value less than `sym'.
293 static int cf_clookup(int *table
, int n
, int sym
)
295 int bit
, index
, limit
, count
;
300 assert(0 < sym
&& sym
<= n
);
302 count
= table
[0]; /* start with the whole table size */
312 * Find the least number with its lowest set bit in this
313 * position which is greater than or equal to sym.
315 index
= ((sym
+ bit
- 1) &~ (bit
* 2 - 1)) + bit
;
318 count
-= table
[index
];
329 * Single frequency lookup: return the count of symbol `sym'.
331 static int cf_slookup(int *table
, int n
, int sym
)
335 assert(0 <= sym
&& sym
< n
);
339 for (bit
= 1; sym
+bit
< n
&& !(sym
& bit
); bit
<<= 1)
340 count
-= table
[sym
+bit
];
346 * Return the largest symbol index such that the cumulative
347 * frequency up to that symbol is less than _or equal to_ count.
349 static int cf_whichsym(int *table
, int n
, int count
) {
352 assert(count
>= 0 && count
< table
[0]);
363 if (count
>= top
- table
[sym
+bit
])
366 top
-= table
[sym
+bit
];
375 /* ----------------------------------------------------------------------
378 * FIXME: this isn't entirely optimal at present, because it
379 * inherently prioritises growing the largest region since there
380 * are more squares adjacent to it. This acts as a destabilising
381 * influence leading to a few large regions and mostly small ones.
382 * It might be better to do it some other way.
385 #define WEIGHT_INCREASED 2 /* for increased perimeter */
386 #define WEIGHT_DECREASED 4 /* for decreased perimeter */
387 #define WEIGHT_UNCHANGED 3 /* for unchanged perimeter */
390 * Look at a square and decide which colours can be extended into
393 * If called with index < 0, it adds together one of
394 * WEIGHT_INCREASED, WEIGHT_DECREASED or WEIGHT_UNCHANGED for each
395 * colour that has a valid extension (according to the effect that
396 * it would have on the perimeter of the region being extended) and
397 * returns the overall total.
399 * If called with index >= 0, it returns one of the possible
400 * colours depending on the value of index, in such a way that the
401 * number of possible inputs which would give rise to a given
402 * return value correspond to the weight of that value.
404 static int extend_options(int w
, int h
, int n
, int *map
,
405 int x
, int y
, int index
)
411 if (map
[y
*w
+x
] >= 0) {
413 return 0; /* can't do this square at all */
417 * Fetch the eight neighbours of this square, in order around
420 for (dy
= -1; dy
<= +1; dy
++)
421 for (dx
= -1; dx
<= +1; dx
++) {
422 int index
= (dy
< 0 ?
6-dx
: dy
> 0 ?
2+dx
: 2*(1+dx
));
423 if (x
+dx
>= 0 && x
+dx
< w
&& y
+dy
>= 0 && y
+dy
< h
)
424 col
[index
] = map
[(y
+dy
)*w
+(x
+dx
)];
430 * Iterate over each colour that might be feasible.
432 * FIXME: this routine currently has O(n) running time. We
433 * could turn it into O(FOUR) by only bothering to iterate over
434 * the colours mentioned in the four neighbouring squares.
437 for (c
= 0; c
< n
; c
++) {
438 int count
, neighbours
, runs
;
441 * One of the even indices of col (representing the
442 * orthogonal neighbours of this square) must be equal to
443 * c, or else this square is not adjacent to region c and
444 * obviously cannot become an extension of it at this time.
447 for (i
= 0; i
< 8; i
+= 2)
454 * Now we know this square is adjacent to region c. The
455 * next question is, would extending it cause the region to
456 * become non-simply-connected? If so, we mustn't do it.
458 * We determine this by looking around col to see if we can
459 * find more than one separate run of colour c.
462 for (i
= 0; i
< 8; i
++)
463 if (col
[i
] == c
&& col
[(i
+1) & 7] != c
)
471 * This square is a possibility. Determine its effect on
472 * the region's perimeter (computed from the number of
473 * orthogonal neighbours - 1 means a perimeter increase, 3
474 * a decrease, 2 no change; 4 is impossible because the
475 * region would already not be simply connected) and we're
478 assert(neighbours
> 0 && neighbours
< 4);
479 count
= (neighbours
== 1 ? WEIGHT_INCREASED
:
480 neighbours
== 2 ? WEIGHT_UNCHANGED
: WEIGHT_DECREASED
);
483 if (index
>= 0 && index
< count
)
494 static void genmap(int w
, int h
, int n
, int *map
, random_state
*rs
)
501 tmp
= snewn(wh
, int);
504 * Clear the map, and set up `tmp' as a list of grid indices.
506 for (i
= 0; i
< wh
; i
++) {
512 * Place the region seeds by selecting n members from `tmp'.
515 for (i
= 0; i
< n
; i
++) {
516 int j
= random_upto(rs
, k
);
522 * Re-initialise `tmp' as a cumulative frequency table. This
523 * will store the number of possible region colours we can
524 * extend into each square.
529 * Go through the grid and set up the initial cumulative
532 for (y
= 0; y
< h
; y
++)
533 for (x
= 0; x
< w
; x
++)
534 cf_add(tmp
, wh
, y
*w
+x
,
535 extend_options(w
, h
, n
, map
, x
, y
, -1));
538 * Now repeatedly choose a square we can extend a region into,
542 int k
= random_upto(rs
, tmp
[0]);
547 sq
= cf_whichsym(tmp
, wh
, k
);
548 k
-= cf_clookup(tmp
, wh
, sq
);
551 colour
= extend_options(w
, h
, n
, map
, x
, y
, k
);
556 * Re-scan the nine cells around the one we've just
559 for (yy
= max(y
-1, 0); yy
< min(y
+2, h
); yy
++)
560 for (xx
= max(x
-1, 0); xx
< min(x
+2, w
); xx
++) {
561 cf_add(tmp
, wh
, yy
*w
+xx
,
562 -cf_slookup(tmp
, wh
, yy
*w
+xx
) +
563 extend_options(w
, h
, n
, map
, xx
, yy
, -1));
568 * Finally, go through and normalise the region labels into
569 * order, meaning that indistinguishable maps are actually
572 for (i
= 0; i
< n
; i
++)
575 for (i
= 0; i
< wh
; i
++) {
579 map
[i
] = tmp
[map
[i
]];
585 /* ----------------------------------------------------------------------
586 * Functions to handle graphs.
590 * Having got a map in a square grid, convert it into a graph
593 static int gengraph(int w
, int h
, int n
, int *map
, int *graph
)
598 * Start by setting the graph up as an adjacency matrix. We'll
599 * turn it into a list later.
601 for (i
= 0; i
< n
*n
; i
++)
605 * Iterate over the map looking for all adjacencies.
607 for (y
= 0; y
< h
; y
++)
608 for (x
= 0; x
< w
; x
++) {
611 if (x
+1 < w
&& (vx
= map
[y
*w
+(x
+1)]) != v
)
612 graph
[v
*n
+vx
] = graph
[vx
*n
+v
] = 1;
613 if (y
+1 < h
&& (vy
= map
[(y
+1)*w
+x
]) != v
)
614 graph
[v
*n
+vy
] = graph
[vy
*n
+v
] = 1;
618 * Turn the matrix into a list.
620 for (i
= j
= 0; i
< n
*n
; i
++)
627 static int graph_edge_index(int *graph
, int n
, int ngraph
, int i
, int j
)
634 while (top
- bot
> 1) {
635 mid
= (top
+ bot
) / 2;
638 else if (graph
[mid
] < v
)
646 #define graph_adjacent(graph, n, ngraph, i, j) \
647 (graph_edge_index((graph), (n), (ngraph), (i), (j)) >= 0)
649 static int graph_vertex_start(int *graph
, int n
, int ngraph
, int i
)
656 while (top
- bot
> 1) {
657 mid
= (top
+ bot
) / 2;
666 /* ----------------------------------------------------------------------
667 * Generate a four-colouring of a graph.
669 * FIXME: it would be nice if we could convert this recursion into
670 * pseudo-recursion using some sort of explicit stack array, for
671 * the sake of the Palm port and its limited stack.
674 static int fourcolour_recurse(int *graph
, int n
, int ngraph
,
675 int *colouring
, int *scratch
, random_state
*rs
)
677 int nfree
, nvert
, start
, i
, j
, k
, c
, ci
;
681 * Find the smallest number of free colours in any uncoloured
682 * vertex, and count the number of such vertices.
685 nfree
= FIVE
; /* start off bigger than FOUR! */
687 for (i
= 0; i
< n
; i
++)
688 if (colouring
[i
] < 0 && scratch
[i
*FIVE
+FOUR
] <= nfree
) {
689 if (nfree
> scratch
[i
*FIVE
+FOUR
]) {
690 nfree
= scratch
[i
*FIVE
+FOUR
];
697 * If there aren't any uncoloured vertices at all, we're done.
700 return TRUE
; /* we've got a colouring! */
703 * Pick a random vertex in that set.
705 j
= random_upto(rs
, nvert
);
706 for (i
= 0; i
< n
; i
++)
707 if (colouring
[i
] < 0 && scratch
[i
*FIVE
+FOUR
] == nfree
)
711 start
= graph_vertex_start(graph
, n
, ngraph
, i
);
714 * Loop over the possible colours for i, and recurse for each
718 for (c
= 0; c
< FOUR
; c
++)
719 if (scratch
[i
*FIVE
+c
] == 0)
721 shuffle(cs
, ci
, sizeof(*cs
), rs
);
727 * Fill in this colour.
732 * Update the scratch space to reflect a new neighbour
733 * of this colour for each neighbour of vertex i.
735 for (j
= start
; j
< ngraph
&& graph
[j
] < n
*(i
+1); j
++) {
737 if (scratch
[k
*FIVE
+c
] == 0)
738 scratch
[k
*FIVE
+FOUR
]--;
745 if (fourcolour_recurse(graph
, n
, ngraph
, colouring
, scratch
, rs
))
746 return TRUE
; /* got one! */
749 * If that didn't work, clean up and try again with a
752 for (j
= start
; j
< ngraph
&& graph
[j
] < n
*(i
+1); j
++) {
755 if (scratch
[k
*FIVE
+c
] == 0)
756 scratch
[k
*FIVE
+FOUR
]++;
762 * If we reach here, we were unable to find a colouring at all.
763 * (This doesn't necessarily mean the Four Colour Theorem is
764 * violated; it might just mean we've gone down a dead end and
765 * need to back up and look somewhere else. It's only an FCT
766 * violation if we get all the way back up to the top level and
772 static void fourcolour(int *graph
, int n
, int ngraph
, int *colouring
,
779 * For each vertex and each colour, we store the number of
780 * neighbours that have that colour. Also, we store the number
781 * of free colours for the vertex.
783 scratch
= snewn(n
* FIVE
, int);
784 for (i
= 0; i
< n
* FIVE
; i
++)
785 scratch
[i
] = (i
% FIVE
== FOUR ? FOUR
: 0);
788 * Clear the colouring to start with.
790 for (i
= 0; i
< n
; i
++)
793 i
= fourcolour_recurse(graph
, n
, ngraph
, colouring
, scratch
, rs
);
794 assert(i
); /* by the Four Colour Theorem :-) */
799 /* ----------------------------------------------------------------------
800 * Non-recursive solver.
803 struct solver_scratch
{
804 unsigned char *possible
; /* bitmap of colours for each region */
812 #ifdef SOLVER_DIAGNOSTICS
819 static struct solver_scratch
*new_scratch(int *graph
, int n
, int ngraph
)
821 struct solver_scratch
*sc
;
823 sc
= snew(struct solver_scratch
);
827 sc
->possible
= snewn(n
, unsigned char);
829 sc
->bfsqueue
= snewn(n
, int);
830 sc
->bfscolour
= snewn(n
, int);
831 #ifdef SOLVER_DIAGNOSTICS
832 sc
->bfsprev
= snewn(n
, int);
838 static void free_scratch(struct solver_scratch
*sc
)
842 sfree(sc
->bfscolour
);
843 #ifdef SOLVER_DIAGNOSTICS
850 * Count the bits in a word. Only needs to cope with FOUR bits.
852 static int bitcount(int word
)
854 assert(FOUR
<= 4); /* or this needs changing */
855 word
= ((word
& 0xA) >> 1) + (word
& 0x5);
856 word
= ((word
& 0xC) >> 2) + (word
& 0x3);
860 #ifdef SOLVER_DIAGNOSTICS
861 static const char colnames
[FOUR
] = { 'R', 'Y', 'G', 'B' };
864 static int place_colour(struct solver_scratch
*sc
,
865 int *colouring
, int index
, int colour
866 #ifdef SOLVER_DIAGNOSTICS
871 int *graph
= sc
->graph
, n
= sc
->n
, ngraph
= sc
->ngraph
;
874 if (!(sc
->possible
[index
] & (1 << colour
))) {
875 #ifdef SOLVER_DIAGNOSTICS
877 printf("%*scannot place %c in region %d\n", 2*sc
->depth
, "",
878 colnames
[colour
], index
);
880 return FALSE
; /* can't do it */
883 sc
->possible
[index
] = 1 << colour
;
884 colouring
[index
] = colour
;
886 #ifdef SOLVER_DIAGNOSTICS
888 printf("%*s%s %c in region %d\n", 2*sc
->depth
, "",
889 verb
, colnames
[colour
], index
);
893 * Rule out this colour from all the region's neighbours.
895 for (j
= graph_vertex_start(graph
, n
, ngraph
, index
);
896 j
< ngraph
&& graph
[j
] < n
*(index
+1); j
++) {
897 k
= graph
[j
] - index
*n
;
898 #ifdef SOLVER_DIAGNOSTICS
899 if (verbose
&& (sc
->possible
[k
] & (1 << colour
)))
900 printf("%*s ruling out %c in region %d\n", 2*sc
->depth
, "",
901 colnames
[colour
], k
);
903 sc
->possible
[k
] &= ~(1 << colour
);
909 #ifdef SOLVER_DIAGNOSTICS
910 static char *colourset(char *buf
, int set
)
916 for (i
= 0; i
< FOUR
; i
++)
917 if (set
& (1 << i
)) {
918 p
+= sprintf(p
, "%s%c", sep
, colnames
[i
]);
927 * Returns 0 for impossible, 1 for success, 2 for failure to
928 * converge (i.e. puzzle is either ambiguous or just too
931 static int map_solver(struct solver_scratch
*sc
,
932 int *graph
, int n
, int ngraph
, int *colouring
,
937 if (sc
->depth
== 0) {
939 * Initialise scratch space.
941 for (i
= 0; i
< n
; i
++)
942 sc
->possible
[i
] = (1 << FOUR
) - 1;
947 for (i
= 0; i
< n
; i
++)
948 if (colouring
[i
] >= 0) {
949 if (!place_colour(sc
, colouring
, i
, colouring
[i
]
950 #ifdef SOLVER_DIAGNOSTICS
954 #ifdef SOLVER_DIAGNOSTICS
956 printf("%*sinitial clue set is inconsistent\n",
959 return 0; /* the clues aren't even consistent! */
965 * Now repeatedly loop until we find nothing further to do.
968 int done_something
= FALSE
;
970 if (difficulty
< DIFF_EASY
)
971 break; /* can't do anything at all! */
974 * Simplest possible deduction: find a region with only one
977 for (i
= 0; i
< n
; i
++) if (colouring
[i
] < 0) {
978 int p
= sc
->possible
[i
];
981 #ifdef SOLVER_DIAGNOSTICS
983 printf("%*sregion %d has no possible colours left\n",
986 return 0; /* puzzle is inconsistent */
989 if ((p
& (p
-1)) == 0) { /* p is a power of two */
991 for (c
= 0; c
< FOUR
; c
++)
995 ret
= place_colour(sc
, colouring
, i
, c
996 #ifdef SOLVER_DIAGNOSTICS
1001 * place_colour() can only fail if colour c was not
1002 * even a _possibility_ for region i, and we're
1003 * pretty sure it was because we checked before
1004 * calling place_colour(). So we can safely assert
1005 * here rather than having to return a nice
1006 * friendly error code.
1009 done_something
= TRUE
;
1016 if (difficulty
< DIFF_NORMAL
)
1017 break; /* can't do anything harder */
1020 * Failing that, go up one level. Look for pairs of regions
1021 * which (a) both have the same pair of possible colours,
1022 * (b) are adjacent to one another, (c) are adjacent to the
1023 * same region, and (d) that region still thinks it has one
1024 * or both of those possible colours.
1026 * Simplest way to do this is by going through the graph
1027 * edge by edge, so that we start with property (b) and
1028 * then look for (a) and finally (c) and (d).
1030 for (i
= 0; i
< ngraph
; i
++) {
1031 int j1
= graph
[i
] / n
, j2
= graph
[i
] % n
;
1033 #ifdef SOLVER_DIAGNOSTICS
1034 int started
= FALSE
;
1038 continue; /* done it already, other way round */
1040 if (colouring
[j1
] >= 0 || colouring
[j2
] >= 0)
1041 continue; /* they're not undecided */
1043 if (sc
->possible
[j1
] != sc
->possible
[j2
])
1044 continue; /* they don't have the same possibles */
1046 v
= sc
->possible
[j1
];
1048 * See if v contains exactly two set bits.
1050 v2
= v
& -v
; /* find lowest set bit */
1051 v2
= v
& ~v2
; /* clear it */
1052 if (v2
== 0 || (v2
& (v2
-1)) != 0) /* not power of 2 */
1056 * We've found regions j1 and j2 satisfying properties
1057 * (a) and (b): they have two possible colours between
1058 * them, and since they're adjacent to one another they
1059 * must use _both_ those colours between them.
1060 * Therefore, if they are both adjacent to any other
1061 * region then that region cannot be either colour.
1063 * Go through the neighbours of j1 and see if any are
1066 for (j
= graph_vertex_start(graph
, n
, ngraph
, j1
);
1067 j
< ngraph
&& graph
[j
] < n
*(j1
+1); j
++) {
1068 k
= graph
[j
] - j1
*n
;
1069 if (graph_adjacent(graph
, n
, ngraph
, k
, j2
) &&
1070 (sc
->possible
[k
] & v
)) {
1071 #ifdef SOLVER_DIAGNOSTICS
1075 printf("%*sadjacent regions %d,%d share colours"
1076 " %s\n", 2*sc
->depth
, "", j1
, j2
,
1079 printf("%*s ruling out %s in region %d\n",2*sc
->depth
,
1080 "", colourset(buf
, sc
->possible
[k
] & v
), k
);
1083 sc
->possible
[k
] &= ~v
;
1084 done_something
= TRUE
;
1092 if (difficulty
< DIFF_HARD
)
1093 break; /* can't do anything harder */
1096 * Right; now we get creative. Now we're going to look for
1097 * `forcing chains'. A forcing chain is a path through the
1098 * graph with the following properties:
1100 * (a) Each vertex on the path has precisely two possible
1103 * (b) Each pair of vertices which are adjacent on the
1104 * path share at least one possible colour in common.
1106 * (c) Each vertex in the middle of the path shares _both_
1107 * of its colours with at least one of its neighbours
1108 * (not the same one with both neighbours).
1110 * These together imply that at least one of the possible
1111 * colour choices at one end of the path forces _all_ the
1112 * rest of the colours along the path. In order to make
1113 * real use of this, we need further properties:
1115 * (c) Ruling out some colour C from the vertex at one end
1116 * of the path forces the vertex at the other end to
1119 * (d) The two end vertices are mutually adjacent to some
1122 * (e) That third vertex currently has C as a possibility.
1124 * If we can find all of that lot, we can deduce that at
1125 * least one of the two ends of the forcing chain has
1126 * colour C, and that therefore the mutually adjacent third
1129 * To find forcing chains, we're going to start a bfs at
1130 * each suitable vertex of the graph, once for each of its
1131 * two possible colours.
1133 for (i
= 0; i
< n
; i
++) {
1136 if (colouring
[i
] >= 0 || bitcount(sc
->possible
[i
]) != 2)
1139 for (c
= 0; c
< FOUR
; c
++)
1140 if (sc
->possible
[i
] & (1 << c
)) {
1141 int j
, k
, gi
, origc
, currc
, head
, tail
;
1143 * Try a bfs from this vertex, ruling out
1146 * Within this loop, we work in colour bitmaps
1147 * rather than actual colours, because
1148 * converting back and forth is a needless
1149 * computational expense.
1154 for (j
= 0; j
< n
; j
++) {
1155 sc
->bfscolour
[j
] = -1;
1156 #ifdef SOLVER_DIAGNOSTICS
1157 sc
->bfsprev
[j
] = -1;
1161 sc
->bfsqueue
[tail
++] = i
;
1162 sc
->bfscolour
[i
] = sc
->possible
[i
] &~ origc
;
1164 while (head
< tail
) {
1165 j
= sc
->bfsqueue
[head
++];
1166 currc
= sc
->bfscolour
[j
];
1169 * Try neighbours of j.
1171 for (gi
= graph_vertex_start(graph
, n
, ngraph
, j
);
1172 gi
< ngraph
&& graph
[gi
] < n
*(j
+1); gi
++) {
1173 k
= graph
[gi
] - j
*n
;
1176 * To continue with the bfs in vertex
1177 * k, we need k to be
1178 * (a) not already visited
1179 * (b) have two possible colours
1180 * (c) those colours include currc.
1183 if (sc
->bfscolour
[k
] < 0 &&
1185 bitcount(sc
->possible
[k
]) == 2 &&
1186 (sc
->possible
[k
] & currc
)) {
1187 sc
->bfsqueue
[tail
++] = k
;
1189 sc
->possible
[k
] &~ currc
;
1190 #ifdef SOLVER_DIAGNOSTICS
1196 * One other possibility is that k
1197 * might be the region in which we can
1198 * make a real deduction: if it's
1199 * adjacent to i, contains currc as a
1200 * possibility, and currc is equal to
1201 * the original colour we ruled out.
1203 if (currc
== origc
&&
1204 graph_adjacent(graph
, n
, ngraph
, k
, i
) &&
1205 (sc
->possible
[k
] & currc
)) {
1206 #ifdef SOLVER_DIAGNOSTICS
1208 char buf
[80], *sep
= "";
1211 printf("%*sforcing chain, colour %s, ",
1213 colourset(buf
, origc
));
1214 for (r
= j
; r
!= -1; r
= sc
->bfsprev
[r
]) {
1215 printf("%s%d", sep
, r
);
1218 printf("\n%*s ruling out %s in region"
1219 " %d\n", 2*sc
->depth
, "",
1220 colourset(buf
, origc
), k
);
1223 sc
->possible
[k
] &= ~origc
;
1224 done_something
= TRUE
;
1233 if (!done_something
)
1238 * See if we've got a complete solution, and return if so.
1240 for (i
= 0; i
< n
; i
++)
1241 if (colouring
[i
] < 0)
1244 #ifdef SOLVER_DIAGNOSTICS
1246 printf("%*sone solution found\n", 2*sc
->depth
, "");
1248 return 1; /* success! */
1252 * If recursion is not permissible, we now give up.
1254 if (difficulty
< DIFF_RECURSE
) {
1255 #ifdef SOLVER_DIAGNOSTICS
1257 printf("%*sunable to proceed further without recursion\n",
1260 return 2; /* unable to complete */
1264 * Now we've got to do something recursive. So first hunt for a
1265 * currently-most-constrained region.
1269 struct solver_scratch
*rsc
;
1270 int *subcolouring
, *origcolouring
;
1272 int we_already_got_one
;
1277 for (i
= 0; i
< n
; i
++) if (colouring
[i
] < 0) {
1278 int p
= sc
->possible
[i
];
1279 enum { compile_time_assertion
= 1 / (FOUR
<= 4) };
1282 /* Count the set bits. */
1283 c
= (p
& 5) + ((p
>> 1) & 5);
1284 c
= (c
& 3) + ((c
>> 2) & 3);
1285 assert(c
> 1); /* or colouring[i] would be >= 0 */
1293 assert(best
>= 0); /* or we'd be solved already */
1295 #ifdef SOLVER_DIAGNOSTICS
1297 printf("%*srecursing on region %d\n", 2*sc
->depth
, "", best
);
1301 * Now iterate over the possible colours for this region.
1303 rsc
= new_scratch(graph
, n
, ngraph
);
1304 rsc
->depth
= sc
->depth
+ 1;
1305 origcolouring
= snewn(n
, int);
1306 memcpy(origcolouring
, colouring
, n
* sizeof(int));
1307 subcolouring
= snewn(n
, int);
1308 we_already_got_one
= FALSE
;
1311 for (i
= 0; i
< FOUR
; i
++) {
1312 if (!(sc
->possible
[best
] & (1 << i
)))
1315 memcpy(rsc
->possible
, sc
->possible
, n
);
1316 memcpy(subcolouring
, origcolouring
, n
* sizeof(int));
1318 place_colour(rsc
, subcolouring
, best
, i
1319 #ifdef SOLVER_DIAGNOSTICS
1324 subret
= map_solver(rsc
, graph
, n
, ngraph
,
1325 subcolouring
, difficulty
);
1327 #ifdef SOLVER_DIAGNOSTICS
1329 printf("%*sretracting %c in region %d; found %s\n",
1330 2*sc
->depth
, "", colnames
[i
], best
,
1331 subret
== 0 ?
"no solutions" :
1332 subret
== 1 ?
"one solution" : "multiple solutions");
1337 * If this possibility turned up more than one valid
1338 * solution, or if it turned up one and we already had
1339 * one, we're definitely ambiguous.
1341 if (subret
== 2 || (subret
== 1 && we_already_got_one
)) {
1347 * If this possibility turned up one valid solution and
1348 * it's the first we've seen, copy it into the output.
1351 memcpy(colouring
, subcolouring
, n
* sizeof(int));
1352 we_already_got_one
= TRUE
;
1357 * Otherwise, this guess led to a contradiction, so we
1362 sfree(subcolouring
);
1365 #ifdef SOLVER_DIAGNOSTICS
1366 if (verbose
&& sc
->depth
== 0) {
1367 printf("%*s%s found\n",
1369 ret
== 0 ?
"no solutions" :
1370 ret
== 1 ?
"one solution" : "multiple solutions");
1377 /* ----------------------------------------------------------------------
1378 * Game generation main function.
1381 static char *new_game_desc(game_params
*params
, random_state
*rs
,
1382 char **aux
, int interactive
)
1384 struct solver_scratch
*sc
= NULL
;
1385 int *map
, *graph
, ngraph
, *colouring
, *colouring2
, *regions
;
1386 int i
, j
, w
, h
, n
, solveret
, cfreq
[FOUR
];
1389 #ifdef GENERATION_DIAGNOSTICS
1393 int retlen
, retsize
;
1402 map
= snewn(wh
, int);
1403 graph
= snewn(n
*n
, int);
1404 colouring
= snewn(n
, int);
1405 colouring2
= snewn(n
, int);
1406 regions
= snewn(n
, int);
1409 * This is the minimum difficulty below which we'll completely
1410 * reject a map design. Normally we set this to one below the
1411 * requested difficulty, ensuring that we have the right
1412 * result. However, for particularly dense maps or maps with
1413 * particularly few regions it might not be possible to get the
1414 * desired difficulty, so we will eventually drop this down to
1415 * -1 to indicate that any old map will do.
1417 mindiff
= params
->diff
;
1425 genmap(w
, h
, n
, map
, rs
);
1427 #ifdef GENERATION_DIAGNOSTICS
1428 for (y
= 0; y
< h
; y
++) {
1429 for (x
= 0; x
< w
; x
++) {
1434 putchar('a' + v
-36);
1436 putchar('A' + v
-10);
1445 * Convert the map into a graph.
1447 ngraph
= gengraph(w
, h
, n
, map
, graph
);
1449 #ifdef GENERATION_DIAGNOSTICS
1450 for (i
= 0; i
< ngraph
; i
++)
1451 printf("%d-%d\n", graph
[i
]/n
, graph
[i
]%n
);
1457 fourcolour(graph
, n
, ngraph
, colouring
, rs
);
1459 #ifdef GENERATION_DIAGNOSTICS
1460 for (i
= 0; i
< n
; i
++)
1461 printf("%d: %d\n", i
, colouring
[i
]);
1463 for (y
= 0; y
< h
; y
++) {
1464 for (x
= 0; x
< w
; x
++) {
1465 int v
= colouring
[map
[y
*w
+x
]];
1467 putchar('a' + v
-36);
1469 putchar('A' + v
-10);
1478 * Encode the solution as an aux string.
1480 if (*aux
) /* in case we've come round again */
1482 retlen
= retsize
= 0;
1484 for (i
= 0; i
< n
; i
++) {
1487 if (colouring
[i
] < 0)
1490 len
= sprintf(buf
, "%s%d:%d", i ?
";" : "S;", colouring
[i
], i
);
1491 if (retlen
+ len
>= retsize
) {
1492 retsize
= retlen
+ len
+ 256;
1493 ret
= sresize(ret
, retsize
, char);
1495 strcpy(ret
+ retlen
, buf
);
1501 * Remove the region colours one by one, keeping
1502 * solubility. Also ensure that there always remains at
1503 * least one region of every colour, so that the user can
1504 * drag from somewhere.
1506 for (i
= 0; i
< FOUR
; i
++)
1508 for (i
= 0; i
< n
; i
++) {
1510 cfreq
[colouring
[i
]]++;
1512 for (i
= 0; i
< FOUR
; i
++)
1516 shuffle(regions
, n
, sizeof(*regions
), rs
);
1518 if (sc
) free_scratch(sc
);
1519 sc
= new_scratch(graph
, n
, ngraph
);
1521 for (i
= 0; i
< n
; i
++) {
1524 if (cfreq
[colouring
[j
]] == 1)
1525 continue; /* can't remove last region of colour */
1527 memcpy(colouring2
, colouring
, n
*sizeof(int));
1529 solveret
= map_solver(sc
, graph
, n
, ngraph
, colouring2
,
1531 assert(solveret
>= 0); /* mustn't be impossible! */
1532 if (solveret
== 1) {
1533 cfreq
[colouring
[j
]]--;
1538 #ifdef GENERATION_DIAGNOSTICS
1539 for (i
= 0; i
< n
; i
++)
1540 if (colouring
[i
] >= 0) {
1544 putchar('a' + i
-36);
1546 putchar('A' + i
-10);
1549 printf(": %d\n", colouring
[i
]);
1554 * Finally, check that the puzzle is _at least_ as hard as
1555 * required, and indeed that it isn't already solved.
1556 * (Calling map_solver with negative difficulty ensures the
1557 * latter - if a solver which _does nothing_ can solve it,
1560 memcpy(colouring2
, colouring
, n
*sizeof(int));
1561 if (map_solver(sc
, graph
, n
, ngraph
, colouring2
,
1562 mindiff
- 1) == 1) {
1564 * Drop minimum difficulty if necessary.
1566 if (mindiff
> 0 && (n
< 9 || n
> 2*wh
/3)) {
1568 mindiff
= 0; /* give up and go for Easy */
1577 * Encode as a game ID. We do this by:
1579 * - first going along the horizontal edges row by row, and
1580 * then the vertical edges column by column
1581 * - encoding the lengths of runs of edges and runs of
1583 * - the decoder will reconstitute the region boundaries from
1584 * this and automatically number them the same way we did
1585 * - then we encode the initial region colours in a Slant-like
1586 * fashion (digits 0-3 interspersed with letters giving
1587 * lengths of runs of empty spaces).
1589 retlen
= retsize
= 0;
1596 * Start with a notional non-edge, so that there'll be an
1597 * explicit `a' to distinguish the case where we start with
1603 for (i
= 0; i
< w
*(h
-1) + (w
-1)*h
; i
++) {
1604 int x
, y
, dx
, dy
, v
;
1607 /* Horizontal edge. */
1613 /* Vertical edge. */
1614 x
= (i
- w
*(h
-1)) / h
;
1615 y
= (i
- w
*(h
-1)) % h
;
1620 if (retlen
+ 10 >= retsize
) {
1621 retsize
= retlen
+ 256;
1622 ret
= sresize(ret
, retsize
, char);
1625 v
= (map
[y
*w
+x
] != map
[(y
+dy
)*w
+(x
+dx
)]);
1628 ret
[retlen
++] = 'a'-1 + run
;
1633 * 'z' is a special case in this encoding. Rather
1634 * than meaning a run of 26 and a state switch, it
1635 * means a run of 25 and _no_ state switch, because
1636 * otherwise there'd be no way to encode runs of
1640 ret
[retlen
++] = 'z';
1647 ret
[retlen
++] = 'a'-1 + run
;
1648 ret
[retlen
++] = ',';
1651 for (i
= 0; i
< n
; i
++) {
1652 if (retlen
+ 10 >= retsize
) {
1653 retsize
= retlen
+ 256;
1654 ret
= sresize(ret
, retsize
, char);
1657 if (colouring
[i
] < 0) {
1659 * In _this_ encoding, 'z' is a run of 26, since
1660 * there's no implicit state switch after each run.
1661 * Confusingly different, but more compact.
1664 ret
[retlen
++] = 'z';
1670 ret
[retlen
++] = 'a'-1 + run
;
1671 ret
[retlen
++] = '0' + colouring
[i
];
1676 ret
[retlen
++] = 'a'-1 + run
;
1679 assert(retlen
< retsize
);
1692 static char *parse_edge_list(game_params
*params
, char **desc
, int *map
)
1694 int w
= params
->w
, h
= params
->h
, wh
= w
*h
, n
= params
->n
;
1695 int i
, k
, pos
, state
;
1698 dsf_init(map
+wh
, wh
);
1704 * Parse the game description to get the list of edges, and
1705 * build up a disjoint set forest as we go (by identifying
1706 * pairs of squares whenever the edge list shows a non-edge).
1708 while (*p
&& *p
!= ',') {
1709 if (*p
< 'a' || *p
> 'z')
1710 return "Unexpected character in edge list";
1721 } else if (pos
< w
*(h
-1)) {
1722 /* Horizontal edge. */
1727 } else if (pos
< 2*wh
-w
-h
) {
1728 /* Vertical edge. */
1729 x
= (pos
- w
*(h
-1)) / h
;
1730 y
= (pos
- w
*(h
-1)) % h
;
1734 return "Too much data in edge list";
1736 dsf_merge(map
+wh
, y
*w
+x
, (y
+dy
)*w
+(x
+dx
));
1744 assert(pos
<= 2*wh
-w
-h
);
1746 return "Too little data in edge list";
1749 * Now go through again and allocate region numbers.
1752 for (i
= 0; i
< wh
; i
++)
1754 for (i
= 0; i
< wh
; i
++) {
1755 k
= dsf_canonify(map
+wh
, i
);
1761 return "Edge list defines the wrong number of regions";
1768 static char *validate_desc(game_params
*params
, char *desc
)
1770 int w
= params
->w
, h
= params
->h
, wh
= w
*h
, n
= params
->n
;
1775 map
= snewn(2*wh
, int);
1776 ret
= parse_edge_list(params
, &desc
, map
);
1782 return "Expected comma before clue list";
1783 desc
++; /* eat comma */
1787 if (*desc
>= '0' && *desc
< '0'+FOUR
)
1789 else if (*desc
>= 'a' && *desc
<= 'z')
1790 area
+= *desc
- 'a' + 1;
1792 return "Unexpected character in clue list";
1796 return "Too little data in clue list";
1798 return "Too much data in clue list";
1803 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
1805 int w
= params
->w
, h
= params
->h
, wh
= w
*h
, n
= params
->n
;
1808 game_state
*state
= snew(game_state
);
1811 state
->colouring
= snewn(n
, int);
1812 for (i
= 0; i
< n
; i
++)
1813 state
->colouring
[i
] = -1;
1814 state
->pencil
= snewn(n
, int);
1815 for (i
= 0; i
< n
; i
++)
1816 state
->pencil
[i
] = 0;
1818 state
->completed
= state
->cheated
= FALSE
;
1820 state
->map
= snew(struct map
);
1821 state
->map
->refcount
= 1;
1822 state
->map
->map
= snewn(wh
*4, int);
1823 state
->map
->graph
= snewn(n
*n
, int);
1825 state
->map
->immutable
= snewn(n
, int);
1826 for (i
= 0; i
< n
; i
++)
1827 state
->map
->immutable
[i
] = FALSE
;
1833 ret
= parse_edge_list(params
, &p
, state
->map
->map
);
1838 * Set up the other three quadrants in `map'.
1840 for (i
= wh
; i
< 4*wh
; i
++)
1841 state
->map
->map
[i
] = state
->map
->map
[i
% wh
];
1847 * Now process the clue list.
1851 if (*p
>= '0' && *p
< '0'+FOUR
) {
1852 state
->colouring
[pos
] = *p
- '0';
1853 state
->map
->immutable
[pos
] = TRUE
;
1856 assert(*p
>= 'a' && *p
<= 'z');
1857 pos
+= *p
- 'a' + 1;
1863 state
->map
->ngraph
= gengraph(w
, h
, n
, state
->map
->map
, state
->map
->graph
);
1866 * Attempt to smooth out some of the more jagged region
1867 * outlines by the judicious use of diagonally divided squares.
1870 random_state
*rs
= random_new(desc
, strlen(desc
));
1871 int *squares
= snewn(wh
, int);
1874 for (i
= 0; i
< wh
; i
++)
1876 shuffle(squares
, wh
, sizeof(*squares
), rs
);
1879 done_something
= FALSE
;
1880 for (i
= 0; i
< wh
; i
++) {
1881 int y
= squares
[i
] / w
, x
= squares
[i
] % w
;
1882 int c
= state
->map
->map
[y
*w
+x
];
1885 if (x
== 0 || x
== w
-1 || y
== 0 || y
== h
-1)
1888 if (state
->map
->map
[TE
* wh
+ y
*w
+x
] !=
1889 state
->map
->map
[BE
* wh
+ y
*w
+x
])
1892 tc
= state
->map
->map
[BE
* wh
+ (y
-1)*w
+x
];
1893 bc
= state
->map
->map
[TE
* wh
+ (y
+1)*w
+x
];
1894 lc
= state
->map
->map
[RE
* wh
+ y
*w
+(x
-1)];
1895 rc
= state
->map
->map
[LE
* wh
+ y
*w
+(x
+1)];
1898 * If this square is adjacent on two sides to one
1899 * region and on the other two sides to the other
1900 * region, and is itself one of the two regions, we can
1901 * adjust it so that it's a diagonal.
1903 if (tc
!= bc
&& (tc
== c
|| bc
== c
)) {
1904 if ((lc
== tc
&& rc
== bc
) ||
1905 (lc
== bc
&& rc
== tc
)) {
1906 state
->map
->map
[TE
* wh
+ y
*w
+x
] = tc
;
1907 state
->map
->map
[BE
* wh
+ y
*w
+x
] = bc
;
1908 state
->map
->map
[LE
* wh
+ y
*w
+x
] = lc
;
1909 state
->map
->map
[RE
* wh
+ y
*w
+x
] = rc
;
1910 done_something
= TRUE
;
1914 } while (done_something
);
1920 * Analyse the map to find a canonical line segment
1921 * corresponding to each edge, and a canonical point
1922 * corresponding to each region. The former are where we'll
1923 * eventually put error markers; the latter are where we'll put
1924 * per-region flags such as numbers (when in diagnostic mode).
1927 int *bestx
, *besty
, *an
, pass
;
1928 float *ax
, *ay
, *best
;
1930 ax
= snewn(state
->map
->ngraph
+ n
, float);
1931 ay
= snewn(state
->map
->ngraph
+ n
, float);
1932 an
= snewn(state
->map
->ngraph
+ n
, int);
1933 bestx
= snewn(state
->map
->ngraph
+ n
, int);
1934 besty
= snewn(state
->map
->ngraph
+ n
, int);
1935 best
= snewn(state
->map
->ngraph
+ n
, float);
1937 for (i
= 0; i
< state
->map
->ngraph
+ n
; i
++) {
1938 bestx
[i
] = besty
[i
] = -1;
1939 best
[i
] = 2*(w
+h
)+1;
1940 ax
[i
] = ay
[i
] = 0.0F
;
1945 * We make two passes over the map, finding all the line
1946 * segments separating regions and all the suitable points
1947 * within regions. In the first pass, we compute the
1948 * _average_ x and y coordinate of all the points in a
1949 * given class; in the second pass, for each such average
1950 * point, we find the candidate closest to it and call that
1953 * Line segments are considered to have coordinates in
1954 * their centre. Thus, at least one coordinate for any line
1955 * segment is always something-and-a-half; so we store our
1956 * coordinates as twice their normal value.
1958 for (pass
= 0; pass
< 2; pass
++) {
1961 for (y
= 0; y
< h
; y
++)
1962 for (x
= 0; x
< w
; x
++) {
1963 int ex
[4], ey
[4], ea
[4], eb
[4], en
= 0;
1966 * Look for an edge to the right of this
1967 * square, an edge below it, and an edge in the
1968 * middle of it. Also look to see if the point
1969 * at the bottom right of this square is on an
1970 * edge (and isn't a place where more than two
1975 ea
[en
] = state
->map
->map
[RE
* wh
+ y
*w
+x
];
1976 eb
[en
] = state
->map
->map
[LE
* wh
+ y
*w
+(x
+1)];
1983 ea
[en
] = state
->map
->map
[BE
* wh
+ y
*w
+x
];
1984 eb
[en
] = state
->map
->map
[TE
* wh
+ (y
+1)*w
+x
];
1990 ea
[en
] = state
->map
->map
[TE
* wh
+ y
*w
+x
];
1991 eb
[en
] = state
->map
->map
[BE
* wh
+ y
*w
+x
];
1996 if (x
+1 < w
&& y
+1 < h
) {
1997 /* bottom right corner */
1998 int oct
[8], othercol
, nchanges
;
1999 oct
[0] = state
->map
->map
[RE
* wh
+ y
*w
+x
];
2000 oct
[1] = state
->map
->map
[LE
* wh
+ y
*w
+(x
+1)];
2001 oct
[2] = state
->map
->map
[BE
* wh
+ y
*w
+(x
+1)];
2002 oct
[3] = state
->map
->map
[TE
* wh
+ (y
+1)*w
+(x
+1)];
2003 oct
[4] = state
->map
->map
[LE
* wh
+ (y
+1)*w
+(x
+1)];
2004 oct
[5] = state
->map
->map
[RE
* wh
+ (y
+1)*w
+x
];
2005 oct
[6] = state
->map
->map
[TE
* wh
+ (y
+1)*w
+x
];
2006 oct
[7] = state
->map
->map
[BE
* wh
+ y
*w
+x
];
2010 for (i
= 0; i
< 8; i
++) {
2011 if (oct
[i
] != oct
[0]) {
2014 else if (othercol
!= oct
[i
])
2015 break; /* three colours at this point */
2017 if (oct
[i
] != oct
[(i
+1) & 7])
2022 * Now if there are exactly two regions at
2023 * this point (not one, and not three or
2024 * more), and only two changes around the
2025 * loop, then this is a valid place to put
2028 if (i
== 8 && othercol
>= 0 && nchanges
== 2) {
2037 * If there's exactly _one_ region at this
2038 * point, on the other hand, it's a valid
2039 * place to put a region centre.
2042 ea
[en
] = eb
[en
] = oct
[0];
2050 * Now process the points we've found, one by
2053 for (i
= 0; i
< en
; i
++) {
2054 int emin
= min(ea
[i
], eb
[i
]);
2055 int emax
= max(ea
[i
], eb
[i
]);
2061 graph_edge_index(state
->map
->graph
, n
,
2062 state
->map
->ngraph
, emin
,
2066 gindex
= state
->map
->ngraph
+ emin
;
2069 assert(gindex
>= 0);
2073 * In pass 0, accumulate the values
2074 * we'll use to compute the average
2077 ax
[gindex
] += ex
[i
];
2078 ay
[gindex
] += ey
[i
];
2082 * In pass 1, work out whether this
2083 * point is closer to the average than
2084 * the last one we've seen.
2088 assert(an
[gindex
] > 0);
2089 dx
= ex
[i
] - ax
[gindex
];
2090 dy
= ey
[i
] - ay
[gindex
];
2091 d
= sqrt(dx
*dx
+ dy
*dy
);
2092 if (d
< best
[gindex
]) {
2094 bestx
[gindex
] = ex
[i
];
2095 besty
[gindex
] = ey
[i
];
2102 for (i
= 0; i
< state
->map
->ngraph
+ n
; i
++)
2110 state
->map
->edgex
= snewn(state
->map
->ngraph
, int);
2111 state
->map
->edgey
= snewn(state
->map
->ngraph
, int);
2112 memcpy(state
->map
->edgex
, bestx
, state
->map
->ngraph
* sizeof(int));
2113 memcpy(state
->map
->edgey
, besty
, state
->map
->ngraph
* sizeof(int));
2115 state
->map
->regionx
= snewn(n
, int);
2116 state
->map
->regiony
= snewn(n
, int);
2117 memcpy(state
->map
->regionx
, bestx
+ state
->map
->ngraph
, n
*sizeof(int));
2118 memcpy(state
->map
->regiony
, besty
+ state
->map
->ngraph
, n
*sizeof(int));
2120 for (i
= 0; i
< state
->map
->ngraph
; i
++)
2121 if (state
->map
->edgex
[i
] < 0) {
2122 /* Find the other representation of this edge. */
2123 int e
= state
->map
->graph
[i
];
2124 int iprime
= graph_edge_index(state
->map
->graph
, n
,
2125 state
->map
->ngraph
, e
%n
, e
/n
);
2126 assert(state
->map
->edgex
[iprime
] >= 0);
2127 state
->map
->edgex
[i
] = state
->map
->edgex
[iprime
];
2128 state
->map
->edgey
[i
] = state
->map
->edgey
[iprime
];
2142 static game_state
*dup_game(game_state
*state
)
2144 game_state
*ret
= snew(game_state
);
2147 ret
->colouring
= snewn(state
->p
.n
, int);
2148 memcpy(ret
->colouring
, state
->colouring
, state
->p
.n
* sizeof(int));
2149 ret
->pencil
= snewn(state
->p
.n
, int);
2150 memcpy(ret
->pencil
, state
->pencil
, state
->p
.n
* sizeof(int));
2151 ret
->map
= state
->map
;
2152 ret
->map
->refcount
++;
2153 ret
->completed
= state
->completed
;
2154 ret
->cheated
= state
->cheated
;
2159 static void free_game(game_state
*state
)
2161 if (--state
->map
->refcount
<= 0) {
2162 sfree(state
->map
->map
);
2163 sfree(state
->map
->graph
);
2164 sfree(state
->map
->immutable
);
2165 sfree(state
->map
->edgex
);
2166 sfree(state
->map
->edgey
);
2167 sfree(state
->map
->regionx
);
2168 sfree(state
->map
->regiony
);
2171 sfree(state
->pencil
);
2172 sfree(state
->colouring
);
2176 static char *solve_game(game_state
*state
, game_state
*currstate
,
2177 char *aux
, char **error
)
2184 struct solver_scratch
*sc
;
2188 int retlen
, retsize
;
2190 colouring
= snewn(state
->map
->n
, int);
2191 memcpy(colouring
, state
->colouring
, state
->map
->n
* sizeof(int));
2193 sc
= new_scratch(state
->map
->graph
, state
->map
->n
, state
->map
->ngraph
);
2194 sret
= map_solver(sc
, state
->map
->graph
, state
->map
->n
,
2195 state
->map
->ngraph
, colouring
, DIFFCOUNT
-1);
2201 *error
= "Puzzle is inconsistent";
2203 *error
= "Unable to find a unique solution for this puzzle";
2208 ret
= snewn(retsize
, char);
2212 for (i
= 0; i
< state
->map
->n
; i
++) {
2215 assert(colouring
[i
] >= 0);
2216 if (colouring
[i
] == currstate
->colouring
[i
])
2218 assert(!state
->map
->immutable
[i
]);
2220 len
= sprintf(buf
, ";%d:%d", colouring
[i
], i
);
2221 if (retlen
+ len
>= retsize
) {
2222 retsize
= retlen
+ len
+ 256;
2223 ret
= sresize(ret
, retsize
, char);
2225 strcpy(ret
+ retlen
, buf
);
2236 static char *game_text_format(game_state
*state
)
2245 * - -2 means no drag currently active.
2246 * - >=0 means we're dragging a solid colour.
2247 * - -1 means we're dragging a blank space, and drag_pencil
2248 * might or might not add some pencil-mark stipples to that.
2256 static game_ui
*new_ui(game_state
*state
)
2258 game_ui
*ui
= snew(game_ui
);
2259 ui
->dragx
= ui
->dragy
= -1;
2260 ui
->drag_colour
= -2;
2261 ui
->show_numbers
= FALSE
;
2265 static void free_ui(game_ui
*ui
)
2270 static char *encode_ui(game_ui
*ui
)
2275 static void decode_ui(game_ui
*ui
, char *encoding
)
2279 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
2280 game_state
*newstate
)
2284 struct game_drawstate
{
2286 unsigned long *drawn
, *todraw
;
2288 int dragx
, dragy
, drag_visible
;
2292 /* Flags in `drawn'. */
2293 #define ERR_BASE 0x00800000L
2294 #define ERR_MASK 0xFF800000L
2295 #define PENCIL_T_BASE 0x00080000L
2296 #define PENCIL_T_MASK 0x00780000L
2297 #define PENCIL_B_BASE 0x00008000L
2298 #define PENCIL_B_MASK 0x00078000L
2299 #define PENCIL_MASK 0x007F8000L
2300 #define SHOW_NUMBERS 0x00004000L
2302 #define TILESIZE (ds->tilesize)
2303 #define BORDER (TILESIZE)
2304 #define COORD(x) ( (x) * TILESIZE + BORDER )
2305 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
2307 static int region_from_coords(game_state
*state
, game_drawstate
*ds
,
2310 int w
= state
->p
.w
, h
= state
->p
.h
, wh
= w
*h
/*, n = state->p.n */;
2311 int tx
= FROMCOORD(x
), ty
= FROMCOORD(y
);
2312 int dx
= x
- COORD(tx
), dy
= y
- COORD(ty
);
2315 if (tx
< 0 || tx
>= w
|| ty
< 0 || ty
>= h
)
2316 return -1; /* border */
2318 quadrant
= 2 * (dx
> dy
) + (TILESIZE
- dx
> dy
);
2319 quadrant
= (quadrant
== 0 ? BE
:
2320 quadrant
== 1 ? LE
:
2321 quadrant
== 2 ? RE
: TE
);
2323 return state
->map
->map
[quadrant
* wh
+ ty
*w
+tx
];
2326 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
2327 int x
, int y
, int button
)
2329 char *bufp
, buf
[256];
2332 * Enable or disable numeric labels on regions.
2334 if (button
== 'l' || button
== 'L') {
2335 ui
->show_numbers
= !ui
->show_numbers
;
2339 if (button
== LEFT_BUTTON
|| button
== RIGHT_BUTTON
) {
2340 int r
= region_from_coords(state
, ds
, x
, y
);
2343 ui
->drag_colour
= state
->colouring
[r
];
2344 ui
->drag_pencil
= state
->pencil
[r
];
2345 if (ui
->drag_colour
>= 0)
2346 ui
->drag_pencil
= 0; /* should be already, but double-check */
2348 ui
->drag_colour
= -1;
2349 ui
->drag_pencil
= 0;
2356 if ((button
== LEFT_DRAG
|| button
== RIGHT_DRAG
) &&
2357 ui
->drag_colour
> -2) {
2363 if ((button
== LEFT_RELEASE
|| button
== RIGHT_RELEASE
) &&
2364 ui
->drag_colour
> -2) {
2365 int r
= region_from_coords(state
, ds
, x
, y
);
2366 int c
= ui
->drag_colour
;
2367 int p
= ui
->drag_pencil
;
2371 * Cancel the drag, whatever happens.
2373 ui
->drag_colour
= -2;
2374 ui
->dragx
= ui
->dragy
= -1;
2377 return ""; /* drag into border; do nothing else */
2379 if (state
->map
->immutable
[r
])
2380 return ""; /* can't change this region */
2382 if (state
->colouring
[r
] == c
&& state
->pencil
[r
] == p
)
2383 return ""; /* don't _need_ to change this region */
2385 if (button
== RIGHT_RELEASE
) {
2386 if (state
->colouring
[r
] >= 0) {
2387 /* Can't pencil on a coloured region */
2389 } else if (c
>= 0) {
2390 /* Right-dragging from colour to blank toggles one pencil */
2391 p
= state
->pencil
[r
] ^ (1 << c
);
2394 /* Otherwise, right-dragging from blank to blank is equivalent
2395 * to left-dragging. */
2399 oldp
= state
->pencil
[r
];
2400 if (c
!= state
->colouring
[r
]) {
2401 bufp
+= sprintf(bufp
, ";%c:%d", (int)(c
< 0 ?
'C' : '0' + c
), r
);
2407 for (i
= 0; i
< FOUR
; i
++)
2408 if ((oldp
^ p
) & (1 << i
))
2409 bufp
+= sprintf(bufp
, ";p%c:%d", (int)('0' + i
), r
);
2412 return dupstr(buf
+1); /* ignore first semicolon */
2418 static game_state
*execute_move(game_state
*state
, char *move
)
2421 game_state
*ret
= dup_game(state
);
2432 if ((c
== 'C' || (c
>= '0' && c
< '0'+FOUR
)) &&
2433 sscanf(move
+1, ":%d%n", &k
, &adv
) == 1 &&
2434 k
>= 0 && k
< state
->p
.n
) {
2437 if (ret
->colouring
[k
] >= 0) {
2444 ret
->pencil
[k
] ^= 1 << (c
- '0');
2446 ret
->colouring
[k
] = (c
== 'C' ?
-1 : c
- '0');
2449 } else if (*move
== 'S') {
2451 ret
->cheated
= TRUE
;
2457 if (*move
&& *move
!= ';') {
2466 * Check for completion.
2468 if (!ret
->completed
) {
2471 for (i
= 0; i
< n
; i
++)
2472 if (ret
->colouring
[i
] < 0) {
2478 for (i
= 0; i
< ret
->map
->ngraph
; i
++) {
2479 int j
= ret
->map
->graph
[i
] / n
;
2480 int k
= ret
->map
->graph
[i
] % n
;
2481 if (ret
->colouring
[j
] == ret
->colouring
[k
]) {
2489 ret
->completed
= TRUE
;
2495 /* ----------------------------------------------------------------------
2499 static void game_compute_size(game_params
*params
, int tilesize
,
2502 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2503 struct { int tilesize
; } ads
, *ds
= &ads
;
2504 ads
.tilesize
= tilesize
;
2506 *x
= params
->w
* TILESIZE
+ 2 * BORDER
+ 1;
2507 *y
= params
->h
* TILESIZE
+ 2 * BORDER
+ 1;
2510 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
2511 game_params
*params
, int tilesize
)
2513 ds
->tilesize
= tilesize
;
2515 assert(!ds
->bl
); /* set_size is never called twice */
2516 ds
->bl
= blitter_new(dr
, TILESIZE
+3, TILESIZE
+3);
2519 const float map_colours
[FOUR
][3] = {
2523 {0.55F
, 0.45F
, 0.35F
},
2525 const int map_hatching
[FOUR
] = {
2526 HATCH_VERT
, HATCH_SLASH
, HATCH_HORIZ
, HATCH_BACKSLASH
2529 static float *game_colours(frontend
*fe
, int *ncolours
)
2531 float *ret
= snewn(3 * NCOLOURS
, float);
2533 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
2535 ret
[COL_GRID
* 3 + 0] = 0.0F
;
2536 ret
[COL_GRID
* 3 + 1] = 0.0F
;
2537 ret
[COL_GRID
* 3 + 2] = 0.0F
;
2539 memcpy(ret
+ COL_0
* 3, map_colours
[0], 3 * sizeof(float));
2540 memcpy(ret
+ COL_1
* 3, map_colours
[1], 3 * sizeof(float));
2541 memcpy(ret
+ COL_2
* 3, map_colours
[2], 3 * sizeof(float));
2542 memcpy(ret
+ COL_3
* 3, map_colours
[3], 3 * sizeof(float));
2544 ret
[COL_ERROR
* 3 + 0] = 1.0F
;
2545 ret
[COL_ERROR
* 3 + 1] = 0.0F
;
2546 ret
[COL_ERROR
* 3 + 2] = 0.0F
;
2548 ret
[COL_ERRTEXT
* 3 + 0] = 1.0F
;
2549 ret
[COL_ERRTEXT
* 3 + 1] = 1.0F
;
2550 ret
[COL_ERRTEXT
* 3 + 2] = 1.0F
;
2552 *ncolours
= NCOLOURS
;
2556 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
2558 struct game_drawstate
*ds
= snew(struct game_drawstate
);
2562 ds
->drawn
= snewn(state
->p
.w
* state
->p
.h
, unsigned long);
2563 for (i
= 0; i
< state
->p
.w
* state
->p
.h
; i
++)
2564 ds
->drawn
[i
] = 0xFFFFL
;
2565 ds
->todraw
= snewn(state
->p
.w
* state
->p
.h
, unsigned long);
2566 ds
->started
= FALSE
;
2568 ds
->drag_visible
= FALSE
;
2569 ds
->dragx
= ds
->dragy
= -1;
2574 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
2579 blitter_free(dr
, ds
->bl
);
2583 static void draw_error(drawing
*dr
, game_drawstate
*ds
, int x
, int y
)
2591 coords
[0] = x
- TILESIZE
*2/5;
2594 coords
[3] = y
- TILESIZE
*2/5;
2595 coords
[4] = x
+ TILESIZE
*2/5;
2598 coords
[7] = y
+ TILESIZE
*2/5;
2599 draw_polygon(dr
, coords
, 4, COL_ERROR
, COL_GRID
);
2602 * Draw an exclamation mark in the diamond. This turns out to
2603 * look unpleasantly off-centre if done via draw_text, so I do
2604 * it by hand on the basis that exclamation marks aren't that
2605 * difficult to draw...
2608 yext
= TILESIZE
*2/5 - (xext
*2+2);
2609 draw_rect(dr
, x
-xext
, y
-yext
, xext
*2+1, yext
*2+1 - (xext
*3),
2611 draw_rect(dr
, x
-xext
, y
+yext
-xext
*2+1, xext
*2+1, xext
*2, COL_ERRTEXT
);
2614 static void draw_square(drawing
*dr
, game_drawstate
*ds
,
2615 game_params
*params
, struct map
*map
,
2616 int x
, int y
, unsigned long v
)
2618 int w
= params
->w
, h
= params
->h
, wh
= w
*h
;
2619 int tv
, bv
, xo
, yo
, i
, j
, oldj
;
2620 unsigned long errs
, pencil
, show_numbers
;
2622 errs
= v
& ERR_MASK
;
2624 pencil
= v
& PENCIL_MASK
;
2626 show_numbers
= v
& SHOW_NUMBERS
;
2631 clip(dr
, COORD(x
), COORD(y
), TILESIZE
, TILESIZE
);
2634 * Draw the region colour.
2636 draw_rect(dr
, COORD(x
), COORD(y
), TILESIZE
, TILESIZE
,
2637 (tv
== FOUR ? COL_BACKGROUND
: COL_0
+ tv
));
2639 * Draw the second region colour, if this is a diagonally
2642 if (map
->map
[TE
* wh
+ y
*w
+x
] != map
->map
[BE
* wh
+ y
*w
+x
]) {
2644 coords
[0] = COORD(x
)-1;
2645 coords
[1] = COORD(y
+1)+1;
2646 if (map
->map
[LE
* wh
+ y
*w
+x
] == map
->map
[TE
* wh
+ y
*w
+x
])
2647 coords
[2] = COORD(x
+1)+1;
2649 coords
[2] = COORD(x
)-1;
2650 coords
[3] = COORD(y
)-1;
2651 coords
[4] = COORD(x
+1)+1;
2652 coords
[5] = COORD(y
+1)+1;
2653 draw_polygon(dr
, coords
, 3,
2654 (bv
== FOUR ? COL_BACKGROUND
: COL_0
+ bv
), COL_GRID
);
2658 * Draw `pencil marks'. Currently we arrange these in a square
2659 * formation, which means we may be in trouble if the value of
2660 * FOUR changes later...
2663 for (yo
= 0; yo
< 4; yo
++)
2664 for (xo
= 0; xo
< 4; xo
++) {
2665 int te
= map
->map
[TE
* wh
+ y
*w
+x
];
2668 e
= (yo
< xo
&& yo
< 3-xo ? TE
:
2669 yo
> xo
&& yo
> 3-xo ? BE
:
2671 ee
= map
->map
[e
* wh
+ y
*w
+x
];
2673 if (xo
!= (yo
* 2 + 1) % 5)
2677 if (!(pencil
& ((ee
== te ? PENCIL_T_BASE
: PENCIL_B_BASE
) << c
)))
2681 (map
->map
[TE
* wh
+ y
*w
+x
] != map
->map
[LE
* wh
+ y
*w
+x
]))
2682 continue; /* avoid TL-BR diagonal line */
2684 (map
->map
[TE
* wh
+ y
*w
+x
] != map
->map
[RE
* wh
+ y
*w
+x
]))
2685 continue; /* avoid BL-TR diagonal line */
2687 draw_circle(dr
, COORD(x
) + (xo
+1)*TILESIZE
/5,
2688 COORD(y
) + (yo
+1)*TILESIZE
/5,
2689 TILESIZE
/7, COL_0
+ c
, COL_0
+ c
);
2693 * Draw the grid lines, if required.
2695 if (x
<= 0 || map
->map
[RE
*wh
+y
*w
+(x
-1)] != map
->map
[LE
*wh
+y
*w
+x
])
2696 draw_rect(dr
, COORD(x
), COORD(y
), 1, TILESIZE
, COL_GRID
);
2697 if (y
<= 0 || map
->map
[BE
*wh
+(y
-1)*w
+x
] != map
->map
[TE
*wh
+y
*w
+x
])
2698 draw_rect(dr
, COORD(x
), COORD(y
), TILESIZE
, 1, COL_GRID
);
2699 if (x
<= 0 || y
<= 0 ||
2700 map
->map
[RE
*wh
+(y
-1)*w
+(x
-1)] != map
->map
[TE
*wh
+y
*w
+x
] ||
2701 map
->map
[BE
*wh
+(y
-1)*w
+(x
-1)] != map
->map
[LE
*wh
+y
*w
+x
])
2702 draw_rect(dr
, COORD(x
), COORD(y
), 1, 1, COL_GRID
);
2705 * Draw error markers.
2707 for (yo
= 0; yo
< 3; yo
++)
2708 for (xo
= 0; xo
< 3; xo
++)
2709 if (errs
& (ERR_BASE
<< (yo
*3+xo
)))
2711 (COORD(x
)*2+TILESIZE
*xo
)/2,
2712 (COORD(y
)*2+TILESIZE
*yo
)/2);
2715 * Draw region numbers, if desired.
2719 for (i
= 0; i
< 2; i
++) {
2720 j
= map
->map
[(i?BE
:TE
)*wh
+y
*w
+x
];
2725 xo
= map
->regionx
[j
] - 2*x
;
2726 yo
= map
->regiony
[j
] - 2*y
;
2727 if (xo
>= 0 && xo
<= 2 && yo
>= 0 && yo
<= 2) {
2729 sprintf(buf
, "%d", j
);
2730 draw_text(dr
, (COORD(x
)*2+TILESIZE
*xo
)/2,
2731 (COORD(y
)*2+TILESIZE
*yo
)/2,
2732 FONT_VARIABLE
, 3*TILESIZE
/5,
2733 ALIGN_HCENTRE
|ALIGN_VCENTRE
,
2741 draw_update(dr
, COORD(x
), COORD(y
), TILESIZE
, TILESIZE
);
2744 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
2745 game_state
*state
, int dir
, game_ui
*ui
,
2746 float animtime
, float flashtime
)
2748 int w
= state
->p
.w
, h
= state
->p
.h
, wh
= w
*h
, n
= state
->p
.n
;
2752 if (ds
->drag_visible
) {
2753 blitter_load(dr
, ds
->bl
, ds
->dragx
, ds
->dragy
);
2754 draw_update(dr
, ds
->dragx
, ds
->dragy
, TILESIZE
+ 3, TILESIZE
+ 3);
2755 ds
->drag_visible
= FALSE
;
2759 * The initial contents of the window are not guaranteed and
2760 * can vary with front ends. To be on the safe side, all games
2761 * should start by drawing a big background-colour rectangle
2762 * covering the whole window.
2767 game_compute_size(&state
->p
, TILESIZE
, &ww
, &wh
);
2768 draw_rect(dr
, 0, 0, ww
, wh
, COL_BACKGROUND
);
2769 draw_rect(dr
, COORD(0), COORD(0), w
*TILESIZE
+1, h
*TILESIZE
+1,
2772 draw_update(dr
, 0, 0, ww
, wh
);
2777 if (flash_type
== 1)
2778 flash
= (int)(flashtime
* FOUR
/ flash_length
);
2780 flash
= 1 + (int)(flashtime
* THREE
/ flash_length
);
2785 * Set up the `todraw' array.
2787 for (y
= 0; y
< h
; y
++)
2788 for (x
= 0; x
< w
; x
++) {
2789 int tv
= state
->colouring
[state
->map
->map
[TE
* wh
+ y
*w
+x
]];
2790 int bv
= state
->colouring
[state
->map
->map
[BE
* wh
+ y
*w
+x
]];
2799 if (flash_type
== 1) {
2804 } else if (flash_type
== 2) {
2809 tv
= (tv
+ flash
) % FOUR
;
2811 bv
= (bv
+ flash
) % FOUR
;
2820 for (i
= 0; i
< FOUR
; i
++) {
2821 if (state
->colouring
[state
->map
->map
[TE
* wh
+ y
*w
+x
]] < 0 &&
2822 (state
->pencil
[state
->map
->map
[TE
* wh
+ y
*w
+x
]] & (1<<i
)))
2823 v
|= PENCIL_T_BASE
<< i
;
2824 if (state
->colouring
[state
->map
->map
[BE
* wh
+ y
*w
+x
]] < 0 &&
2825 (state
->pencil
[state
->map
->map
[BE
* wh
+ y
*w
+x
]] & (1<<i
)))
2826 v
|= PENCIL_B_BASE
<< i
;
2829 if (ui
->show_numbers
)
2832 ds
->todraw
[y
*w
+x
] = v
;
2836 * Add error markers to the `todraw' array.
2838 for (i
= 0; i
< state
->map
->ngraph
; i
++) {
2839 int v1
= state
->map
->graph
[i
] / n
;
2840 int v2
= state
->map
->graph
[i
] % n
;
2843 if (state
->colouring
[v1
] < 0 || state
->colouring
[v2
] < 0)
2845 if (state
->colouring
[v1
] != state
->colouring
[v2
])
2848 x
= state
->map
->edgex
[i
];
2849 y
= state
->map
->edgey
[i
];
2854 ds
->todraw
[y
*w
+x
] |= ERR_BASE
<< (yo
*3+xo
);
2857 ds
->todraw
[y
*w
+(x
-1)] |= ERR_BASE
<< (yo
*3+2);
2861 ds
->todraw
[(y
-1)*w
+x
] |= ERR_BASE
<< (2*3+xo
);
2863 if (xo
== 0 && yo
== 0) {
2864 assert(x
> 0 && y
> 0);
2865 ds
->todraw
[(y
-1)*w
+(x
-1)] |= ERR_BASE
<< (2*3+2);
2870 * Now actually draw everything.
2872 for (y
= 0; y
< h
; y
++)
2873 for (x
= 0; x
< w
; x
++) {
2874 unsigned long v
= ds
->todraw
[y
*w
+x
];
2875 if (ds
->drawn
[y
*w
+x
] != v
) {
2876 draw_square(dr
, ds
, &state
->p
, state
->map
, x
, y
, v
);
2877 ds
->drawn
[y
*w
+x
] = v
;
2882 * Draw the dragged colour blob if any.
2884 if (ui
->drag_colour
> -2) {
2885 ds
->dragx
= ui
->dragx
- TILESIZE
/2 - 2;
2886 ds
->dragy
= ui
->dragy
- TILESIZE
/2 - 2;
2887 blitter_save(dr
, ds
->bl
, ds
->dragx
, ds
->dragy
);
2888 draw_circle(dr
, ui
->dragx
, ui
->dragy
, TILESIZE
/2,
2889 (ui
->drag_colour
< 0 ? COL_BACKGROUND
:
2890 COL_0
+ ui
->drag_colour
), COL_GRID
);
2891 for (i
= 0; i
< FOUR
; i
++)
2892 if (ui
->drag_pencil
& (1 << i
))
2893 draw_circle(dr
, ui
->dragx
+ ((i
*4+2)%10-3) * TILESIZE
/10,
2894 ui
->dragy
+ (i
*2-3) * TILESIZE
/10,
2895 TILESIZE
/8, COL_0
+ i
, COL_0
+ i
);
2896 draw_update(dr
, ds
->dragx
, ds
->dragy
, TILESIZE
+ 3, TILESIZE
+ 3);
2897 ds
->drag_visible
= TRUE
;
2901 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
2902 int dir
, game_ui
*ui
)
2907 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
2908 int dir
, game_ui
*ui
)
2910 if (!oldstate
->completed
&& newstate
->completed
&&
2911 !oldstate
->cheated
&& !newstate
->cheated
) {
2912 if (flash_type
< 0) {
2913 char *env
= getenv("MAP_ALTERNATIVE_FLASH");
2915 flash_type
= atoi(env
);
2918 flash_length
= (flash_type
== 1 ?
0.50 : 0.30);
2920 return flash_length
;
2925 static int game_timing_state(game_state
*state
, game_ui
*ui
)
2930 static void game_print_size(game_params
*params
, float *x
, float *y
)
2935 * I'll use 4mm squares by default, I think. Simplest way to
2936 * compute this size is to compute the pixel puzzle size at a
2937 * given tile size and then scale.
2939 game_compute_size(params
, 400, &pw
, &ph
);
2944 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
2946 int w
= state
->p
.w
, h
= state
->p
.h
, wh
= w
*h
, n
= state
->p
.n
;
2947 int ink
, c
[FOUR
], i
;
2949 int *coords
, ncoords
, coordsize
;
2951 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2952 struct { int tilesize
; } ads
, *ds
= &ads
;
2953 /* We can't call game_set_size() here because we don't want a blitter */
2954 ads
.tilesize
= tilesize
;
2956 ink
= print_mono_colour(dr
, 0);
2957 for (i
= 0; i
< FOUR
; i
++)
2958 c
[i
] = print_rgb_colour(dr
, map_hatching
[i
], map_colours
[i
][0],
2959 map_colours
[i
][1], map_colours
[i
][2]);
2964 print_line_width(dr
, TILESIZE
/ 16);
2967 * Draw a single filled polygon around each region.
2969 for (r
= 0; r
< n
; r
++) {
2970 int octants
[8], lastdir
, d1
, d2
, ox
, oy
;
2973 * Start by finding a point on the region boundary. Any
2974 * point will do. To do this, we'll search for a square
2975 * containing the region and then decide which corner of it
2979 for (y
= 0; y
< h
; y
++) {
2980 for (x
= 0; x
< w
; x
++) {
2981 if (state
->map
->map
[wh
*0+y
*w
+x
] == r
||
2982 state
->map
->map
[wh
*1+y
*w
+x
] == r
||
2983 state
->map
->map
[wh
*2+y
*w
+x
] == r
||
2984 state
->map
->map
[wh
*3+y
*w
+x
] == r
)
2990 assert(y
< h
&& x
< w
); /* we must have found one somewhere */
2992 * This is the first square in lexicographic order which
2993 * contains part of this region. Therefore, one of the top
2994 * two corners of the square must be what we're after. The
2995 * only case in which it isn't the top left one is if the
2996 * square is diagonally divided and the region is in the
2997 * bottom right half.
2999 if (state
->map
->map
[wh
*TE
+y
*w
+x
] != r
&&
3000 state
->map
->map
[wh
*LE
+y
*w
+x
] != r
)
3001 x
++; /* could just as well have done y++ */
3004 * Now we have a point on the region boundary. Trace around
3005 * the region until we come back to this point,
3006 * accumulating coordinates for a polygon draw operation as
3016 * There are eight possible directions we could head in
3017 * from here. We identify them by octant numbers, and
3018 * we also use octant numbers to identify the spaces
3031 octants
[0] = x
<w
&& y
>0 ? state
->map
->map
[wh
*LE
+(y
-1)*w
+x
] : -1;
3032 octants
[1] = x
<w
&& y
>0 ? state
->map
->map
[wh
*BE
+(y
-1)*w
+x
] : -1;
3033 octants
[2] = x
<w
&& y
<h ? state
->map
->map
[wh
*TE
+y
*w
+x
] : -1;
3034 octants
[3] = x
<w
&& y
<h ? state
->map
->map
[wh
*LE
+y
*w
+x
] : -1;
3035 octants
[4] = x
>0 && y
<h ? state
->map
->map
[wh
*RE
+y
*w
+(x
-1)] : -1;
3036 octants
[5] = x
>0 && y
<h ? state
->map
->map
[wh
*TE
+y
*w
+(x
-1)] : -1;
3037 octants
[6] = x
>0 && y
>0 ? state
->map
->map
[wh
*BE
+(y
-1)*w
+(x
-1)] :-1;
3038 octants
[7] = x
>0 && y
>0 ? state
->map
->map
[wh
*RE
+(y
-1)*w
+(x
-1)] :-1;
3041 for (i
= 0; i
< 8; i
++)
3042 if ((octants
[i
] == r
) ^ (octants
[(i
+1)%8] == r
)) {
3050 assert(d1
!= -1 && d2
!= -1);
3055 * Now we're heading in direction d1. Save the current
3058 if (ncoords
+ 2 > coordsize
) {
3060 coords
= sresize(coords
, coordsize
, int);
3062 coords
[ncoords
++] = COORD(x
);
3063 coords
[ncoords
++] = COORD(y
);
3066 * Compute the new coordinates.
3068 x
+= (d1
% 4 == 3 ?
0 : d1
< 4 ?
+1 : -1);
3069 y
+= (d1
% 4 == 1 ?
0 : d1
> 1 && d1
< 5 ?
+1 : -1);
3070 assert(x
>= 0 && x
<= w
&& y
>= 0 && y
<= h
);
3073 } while (x
!= ox
|| y
!= oy
);
3075 draw_polygon(dr
, coords
, ncoords
/2,
3076 state
->colouring
[r
] >= 0 ?
3077 c
[state
->colouring
[r
]] : -1, ink
);
3086 const struct game thegame
= {
3087 "Map", "games.map", "map",
3094 TRUE
, game_configure
, custom_params
,
3102 FALSE
, game_text_format
,
3110 20, game_compute_size
, game_set_size
,
3113 game_free_drawstate
,
3117 TRUE
, TRUE
, game_print_size
, game_print
,
3118 FALSE
, /* wants_statusbar */
3119 FALSE
, game_timing_state
,
3123 #ifdef STANDALONE_SOLVER
3125 int main(int argc
, char **argv
)
3129 char *id
= NULL
, *desc
, *err
;
3131 int ret
, diff
, really_verbose
= FALSE
;
3132 struct solver_scratch
*sc
;
3135 while (--argc
> 0) {
3137 if (!strcmp(p
, "-v")) {
3138 really_verbose
= TRUE
;
3139 } else if (!strcmp(p
, "-g")) {
3141 } else if (*p
== '-') {
3142 fprintf(stderr
, "%s: unrecognised option `%s'\n", argv
[0], p
);
3150 fprintf(stderr
, "usage: %s [-g | -v] <game_id>\n", argv
[0]);
3154 desc
= strchr(id
, ':');
3156 fprintf(stderr
, "%s: game id expects a colon in it\n", argv
[0]);
3161 p
= default_params();
3162 decode_params(p
, id
);
3163 err
= validate_desc(p
, desc
);
3165 fprintf(stderr
, "%s: %s\n", argv
[0], err
);
3168 s
= new_game(NULL
, p
, desc
);
3170 sc
= new_scratch(s
->map
->graph
, s
->map
->n
, s
->map
->ngraph
);
3173 * When solving an Easy puzzle, we don't want to bother the
3174 * user with Hard-level deductions. For this reason, we grade
3175 * the puzzle internally before doing anything else.
3177 ret
= -1; /* placate optimiser */
3178 for (diff
= 0; diff
< DIFFCOUNT
; diff
++) {
3179 for (i
= 0; i
< s
->map
->n
; i
++)
3180 if (!s
->map
->immutable
[i
])
3181 s
->colouring
[i
] = -1;
3182 ret
= map_solver(sc
, s
->map
->graph
, s
->map
->n
, s
->map
->ngraph
,
3183 s
->colouring
, diff
);
3188 if (diff
== DIFFCOUNT
) {
3190 printf("Difficulty rating: harder than Hard, or ambiguous\n");
3192 printf("Unable to find a unique solution\n");
3196 printf("Difficulty rating: impossible (no solution exists)\n");
3198 printf("Difficulty rating: %s\n", map_diffnames
[diff
]);
3200 verbose
= really_verbose
;
3201 for (i
= 0; i
< s
->map
->n
; i
++)
3202 if (!s
->map
->immutable
[i
])
3203 s
->colouring
[i
] = -1;
3204 ret
= map_solver(sc
, s
->map
->graph
, s
->map
->n
, s
->map
->ngraph
,
3205 s
->colouring
, diff
);
3207 printf("Puzzle is inconsistent\n");
3211 for (i
= 0; i
< s
->map
->n
; i
++) {
3212 printf("%5d <- %c%c", i
, colnames
[s
->colouring
[i
]],
3213 (col
< 6 && i
+1 < s
->map
->n ?
' ' : '\n'));