2 * map.c: Game involving four-colouring a map.
9 * - better four-colouring algorithm?
10 * - can we make the pencil marks look nicer?
11 * - ability to drag a set of pencil marks?
24 * In standalone solver mode, `verbose' is a variable which can be
25 * set by command-line option; in debugging mode it's simply always
28 #if defined STANDALONE_SOLVER
29 #define SOLVER_DIAGNOSTICS
31 #elif defined SOLVER_DIAGNOSTICS
36 * I don't seriously anticipate wanting to change the number of
37 * colours used in this game, but it doesn't cost much to use a
38 * #define just in case :-)
41 #define THREE (FOUR-1)
46 * Ghastly run-time configuration option, just for Gareth (again).
48 static int flash_type
= -1;
49 static float flash_length
;
52 * Difficulty levels. I do some macro ickery here to ensure that my
53 * enum and the various forms of my name list always match up.
59 A(RECURSE,Unreasonable,u)
60 #define ENUM(upper,title,lower) DIFF_ ## upper,
61 #define TITLE(upper,title,lower) #title,
62 #define ENCODE(upper,title,lower) #lower
63 #define CONFIG(upper,title,lower) ":" #title
64 enum { DIFFLIST(ENUM
) DIFFCOUNT
};
65 static char const *const map_diffnames
[] = { DIFFLIST(TITLE
) };
66 static char const map_diffchars
[] = DIFFLIST(ENCODE
);
67 #define DIFFCONFIG DIFFLIST(CONFIG)
69 enum { TE
, BE
, LE
, RE
}; /* top/bottom/left/right edges */
74 COL_0
, COL_1
, COL_2
, COL_3
,
75 COL_ERROR
, COL_ERRTEXT
,
90 int *edgex
, *edgey
; /* position of a point on each edge */
91 int *regionx
, *regiony
; /* position of a point in each region */
97 int *colouring
, *pencil
;
98 int completed
, cheated
;
101 static game_params
*default_params(void)
103 game_params
*ret
= snew(game_params
);
108 ret
->diff
= DIFF_NORMAL
;
113 static const struct game_params map_presets
[] = {
114 {20, 15, 30, DIFF_EASY
},
115 {20, 15, 30, DIFF_NORMAL
},
116 {20, 15, 30, DIFF_HARD
},
117 {20, 15, 30, DIFF_RECURSE
},
118 {30, 25, 75, DIFF_NORMAL
},
119 {30, 25, 75, DIFF_HARD
},
122 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
127 if (i
< 0 || i
>= lenof(map_presets
))
130 ret
= snew(game_params
);
131 *ret
= map_presets
[i
];
133 sprintf(str
, "%dx%d, %d regions, %s", ret
->w
, ret
->h
, ret
->n
,
134 map_diffnames
[ret
->diff
]);
141 static void free_params(game_params
*params
)
146 static game_params
*dup_params(game_params
*params
)
148 game_params
*ret
= snew(game_params
);
149 *ret
= *params
; /* structure copy */
153 static void decode_params(game_params
*params
, char const *string
)
155 char const *p
= string
;
158 while (*p
&& isdigit((unsigned char)*p
)) p
++;
162 while (*p
&& isdigit((unsigned char)*p
)) p
++;
164 params
->h
= params
->w
;
169 while (*p
&& (*p
== '.' || isdigit((unsigned char)*p
))) p
++;
171 params
->n
= params
->w
* params
->h
/ 8;
176 for (i
= 0; i
< DIFFCOUNT
; i
++)
177 if (*p
== map_diffchars
[i
])
183 static char *encode_params(game_params
*params
, int full
)
187 sprintf(ret
, "%dx%dn%d", params
->w
, params
->h
, params
->n
);
189 sprintf(ret
+ strlen(ret
), "d%c", map_diffchars
[params
->diff
]);
194 static config_item
*game_configure(game_params
*params
)
199 ret
= snewn(5, config_item
);
201 ret
[0].name
= "Width";
202 ret
[0].type
= C_STRING
;
203 sprintf(buf
, "%d", params
->w
);
204 ret
[0].sval
= dupstr(buf
);
207 ret
[1].name
= "Height";
208 ret
[1].type
= C_STRING
;
209 sprintf(buf
, "%d", params
->h
);
210 ret
[1].sval
= dupstr(buf
);
213 ret
[2].name
= "Regions";
214 ret
[2].type
= C_STRING
;
215 sprintf(buf
, "%d", params
->n
);
216 ret
[2].sval
= dupstr(buf
);
219 ret
[3].name
= "Difficulty";
220 ret
[3].type
= C_CHOICES
;
221 ret
[3].sval
= DIFFCONFIG
;
222 ret
[3].ival
= params
->diff
;
232 static game_params
*custom_params(config_item
*cfg
)
234 game_params
*ret
= snew(game_params
);
236 ret
->w
= atoi(cfg
[0].sval
);
237 ret
->h
= atoi(cfg
[1].sval
);
238 ret
->n
= atoi(cfg
[2].sval
);
239 ret
->diff
= cfg
[3].ival
;
244 static char *validate_params(game_params
*params
, int full
)
246 if (params
->w
< 2 || params
->h
< 2)
247 return "Width and height must be at least two";
249 return "Must have at least five regions";
250 if (params
->n
> params
->w
* params
->h
)
251 return "Too many regions to fit in grid";
255 /* ----------------------------------------------------------------------
256 * Cumulative frequency table functions.
260 * Initialise a cumulative frequency table. (Hardly worth writing
261 * this function; all it does is to initialise everything in the
264 static void cf_init(int *table
, int n
)
268 for (i
= 0; i
< n
; i
++)
273 * Increment the count of symbol `sym' by `count'.
275 static void cf_add(int *table
, int n
, int sym
, int count
)
292 * Cumulative frequency lookup: return the total count of symbols
293 * with value less than `sym'.
295 static int cf_clookup(int *table
, int n
, int sym
)
297 int bit
, index
, limit
, count
;
302 assert(0 < sym
&& sym
<= n
);
304 count
= table
[0]; /* start with the whole table size */
314 * Find the least number with its lowest set bit in this
315 * position which is greater than or equal to sym.
317 index
= ((sym
+ bit
- 1) &~ (bit
* 2 - 1)) + bit
;
320 count
-= table
[index
];
331 * Single frequency lookup: return the count of symbol `sym'.
333 static int cf_slookup(int *table
, int n
, int sym
)
337 assert(0 <= sym
&& sym
< n
);
341 for (bit
= 1; sym
+bit
< n
&& !(sym
& bit
); bit
<<= 1)
342 count
-= table
[sym
+bit
];
348 * Return the largest symbol index such that the cumulative
349 * frequency up to that symbol is less than _or equal to_ count.
351 static int cf_whichsym(int *table
, int n
, int count
) {
354 assert(count
>= 0 && count
< table
[0]);
365 if (count
>= top
- table
[sym
+bit
])
368 top
-= table
[sym
+bit
];
377 /* ----------------------------------------------------------------------
380 * FIXME: this isn't entirely optimal at present, because it
381 * inherently prioritises growing the largest region since there
382 * are more squares adjacent to it. This acts as a destabilising
383 * influence leading to a few large regions and mostly small ones.
384 * It might be better to do it some other way.
387 #define WEIGHT_INCREASED 2 /* for increased perimeter */
388 #define WEIGHT_DECREASED 4 /* for decreased perimeter */
389 #define WEIGHT_UNCHANGED 3 /* for unchanged perimeter */
392 * Look at a square and decide which colours can be extended into
395 * If called with index < 0, it adds together one of
396 * WEIGHT_INCREASED, WEIGHT_DECREASED or WEIGHT_UNCHANGED for each
397 * colour that has a valid extension (according to the effect that
398 * it would have on the perimeter of the region being extended) and
399 * returns the overall total.
401 * If called with index >= 0, it returns one of the possible
402 * colours depending on the value of index, in such a way that the
403 * number of possible inputs which would give rise to a given
404 * return value correspond to the weight of that value.
406 static int extend_options(int w
, int h
, int n
, int *map
,
407 int x
, int y
, int index
)
413 if (map
[y
*w
+x
] >= 0) {
415 return 0; /* can't do this square at all */
419 * Fetch the eight neighbours of this square, in order around
422 for (dy
= -1; dy
<= +1; dy
++)
423 for (dx
= -1; dx
<= +1; dx
++) {
424 int index
= (dy
< 0 ?
6-dx
: dy
> 0 ?
2+dx
: 2*(1+dx
));
425 if (x
+dx
>= 0 && x
+dx
< w
&& y
+dy
>= 0 && y
+dy
< h
)
426 col
[index
] = map
[(y
+dy
)*w
+(x
+dx
)];
432 * Iterate over each colour that might be feasible.
434 * FIXME: this routine currently has O(n) running time. We
435 * could turn it into O(FOUR) by only bothering to iterate over
436 * the colours mentioned in the four neighbouring squares.
439 for (c
= 0; c
< n
; c
++) {
440 int count
, neighbours
, runs
;
443 * One of the even indices of col (representing the
444 * orthogonal neighbours of this square) must be equal to
445 * c, or else this square is not adjacent to region c and
446 * obviously cannot become an extension of it at this time.
449 for (i
= 0; i
< 8; i
+= 2)
456 * Now we know this square is adjacent to region c. The
457 * next question is, would extending it cause the region to
458 * become non-simply-connected? If so, we mustn't do it.
460 * We determine this by looking around col to see if we can
461 * find more than one separate run of colour c.
464 for (i
= 0; i
< 8; i
++)
465 if (col
[i
] == c
&& col
[(i
+1) & 7] != c
)
473 * This square is a possibility. Determine its effect on
474 * the region's perimeter (computed from the number of
475 * orthogonal neighbours - 1 means a perimeter increase, 3
476 * a decrease, 2 no change; 4 is impossible because the
477 * region would already not be simply connected) and we're
480 assert(neighbours
> 0 && neighbours
< 4);
481 count
= (neighbours
== 1 ? WEIGHT_INCREASED
:
482 neighbours
== 2 ? WEIGHT_UNCHANGED
: WEIGHT_DECREASED
);
485 if (index
>= 0 && index
< count
)
496 static void genmap(int w
, int h
, int n
, int *map
, random_state
*rs
)
503 tmp
= snewn(wh
, int);
506 * Clear the map, and set up `tmp' as a list of grid indices.
508 for (i
= 0; i
< wh
; i
++) {
514 * Place the region seeds by selecting n members from `tmp'.
517 for (i
= 0; i
< n
; i
++) {
518 int j
= random_upto(rs
, k
);
524 * Re-initialise `tmp' as a cumulative frequency table. This
525 * will store the number of possible region colours we can
526 * extend into each square.
531 * Go through the grid and set up the initial cumulative
534 for (y
= 0; y
< h
; y
++)
535 for (x
= 0; x
< w
; x
++)
536 cf_add(tmp
, wh
, y
*w
+x
,
537 extend_options(w
, h
, n
, map
, x
, y
, -1));
540 * Now repeatedly choose a square we can extend a region into,
544 int k
= random_upto(rs
, tmp
[0]);
549 sq
= cf_whichsym(tmp
, wh
, k
);
550 k
-= cf_clookup(tmp
, wh
, sq
);
553 colour
= extend_options(w
, h
, n
, map
, x
, y
, k
);
558 * Re-scan the nine cells around the one we've just
561 for (yy
= max(y
-1, 0); yy
< min(y
+2, h
); yy
++)
562 for (xx
= max(x
-1, 0); xx
< min(x
+2, w
); xx
++) {
563 cf_add(tmp
, wh
, yy
*w
+xx
,
564 -cf_slookup(tmp
, wh
, yy
*w
+xx
) +
565 extend_options(w
, h
, n
, map
, xx
, yy
, -1));
570 * Finally, go through and normalise the region labels into
571 * order, meaning that indistinguishable maps are actually
574 for (i
= 0; i
< n
; i
++)
577 for (i
= 0; i
< wh
; i
++) {
581 map
[i
] = tmp
[map
[i
]];
587 /* ----------------------------------------------------------------------
588 * Functions to handle graphs.
592 * Having got a map in a square grid, convert it into a graph
595 static int gengraph(int w
, int h
, int n
, int *map
, int *graph
)
600 * Start by setting the graph up as an adjacency matrix. We'll
601 * turn it into a list later.
603 for (i
= 0; i
< n
*n
; i
++)
607 * Iterate over the map looking for all adjacencies.
609 for (y
= 0; y
< h
; y
++)
610 for (x
= 0; x
< w
; x
++) {
613 if (x
+1 < w
&& (vx
= map
[y
*w
+(x
+1)]) != v
)
614 graph
[v
*n
+vx
] = graph
[vx
*n
+v
] = 1;
615 if (y
+1 < h
&& (vy
= map
[(y
+1)*w
+x
]) != v
)
616 graph
[v
*n
+vy
] = graph
[vy
*n
+v
] = 1;
620 * Turn the matrix into a list.
622 for (i
= j
= 0; i
< n
*n
; i
++)
629 static int graph_edge_index(int *graph
, int n
, int ngraph
, int i
, int j
)
636 while (top
- bot
> 1) {
637 mid
= (top
+ bot
) / 2;
640 else if (graph
[mid
] < v
)
648 #define graph_adjacent(graph, n, ngraph, i, j) \
649 (graph_edge_index((graph), (n), (ngraph), (i), (j)) >= 0)
651 static int graph_vertex_start(int *graph
, int n
, int ngraph
, int i
)
658 while (top
- bot
> 1) {
659 mid
= (top
+ bot
) / 2;
668 /* ----------------------------------------------------------------------
669 * Generate a four-colouring of a graph.
671 * FIXME: it would be nice if we could convert this recursion into
672 * pseudo-recursion using some sort of explicit stack array, for
673 * the sake of the Palm port and its limited stack.
676 static int fourcolour_recurse(int *graph
, int n
, int ngraph
,
677 int *colouring
, int *scratch
, random_state
*rs
)
679 int nfree
, nvert
, start
, i
, j
, k
, c
, ci
;
683 * Find the smallest number of free colours in any uncoloured
684 * vertex, and count the number of such vertices.
687 nfree
= FIVE
; /* start off bigger than FOUR! */
689 for (i
= 0; i
< n
; i
++)
690 if (colouring
[i
] < 0 && scratch
[i
*FIVE
+FOUR
] <= nfree
) {
691 if (nfree
> scratch
[i
*FIVE
+FOUR
]) {
692 nfree
= scratch
[i
*FIVE
+FOUR
];
699 * If there aren't any uncoloured vertices at all, we're done.
702 return TRUE
; /* we've got a colouring! */
705 * Pick a random vertex in that set.
707 j
= random_upto(rs
, nvert
);
708 for (i
= 0; i
< n
; i
++)
709 if (colouring
[i
] < 0 && scratch
[i
*FIVE
+FOUR
] == nfree
)
713 start
= graph_vertex_start(graph
, n
, ngraph
, i
);
716 * Loop over the possible colours for i, and recurse for each
720 for (c
= 0; c
< FOUR
; c
++)
721 if (scratch
[i
*FIVE
+c
] == 0)
723 shuffle(cs
, ci
, sizeof(*cs
), rs
);
729 * Fill in this colour.
734 * Update the scratch space to reflect a new neighbour
735 * of this colour for each neighbour of vertex i.
737 for (j
= start
; j
< ngraph
&& graph
[j
] < n
*(i
+1); j
++) {
739 if (scratch
[k
*FIVE
+c
] == 0)
740 scratch
[k
*FIVE
+FOUR
]--;
747 if (fourcolour_recurse(graph
, n
, ngraph
, colouring
, scratch
, rs
))
748 return TRUE
; /* got one! */
751 * If that didn't work, clean up and try again with a
754 for (j
= start
; j
< ngraph
&& graph
[j
] < n
*(i
+1); j
++) {
757 if (scratch
[k
*FIVE
+c
] == 0)
758 scratch
[k
*FIVE
+FOUR
]++;
764 * If we reach here, we were unable to find a colouring at all.
765 * (This doesn't necessarily mean the Four Colour Theorem is
766 * violated; it might just mean we've gone down a dead end and
767 * need to back up and look somewhere else. It's only an FCT
768 * violation if we get all the way back up to the top level and
774 static void fourcolour(int *graph
, int n
, int ngraph
, int *colouring
,
781 * For each vertex and each colour, we store the number of
782 * neighbours that have that colour. Also, we store the number
783 * of free colours for the vertex.
785 scratch
= snewn(n
* FIVE
, int);
786 for (i
= 0; i
< n
* FIVE
; i
++)
787 scratch
[i
] = (i
% FIVE
== FOUR ? FOUR
: 0);
790 * Clear the colouring to start with.
792 for (i
= 0; i
< n
; i
++)
795 i
= fourcolour_recurse(graph
, n
, ngraph
, colouring
, scratch
, rs
);
796 assert(i
); /* by the Four Colour Theorem :-) */
801 /* ----------------------------------------------------------------------
802 * Non-recursive solver.
805 struct solver_scratch
{
806 unsigned char *possible
; /* bitmap of colours for each region */
810 #ifdef SOLVER_DIAGNOSTICS
818 static struct solver_scratch
*new_scratch(int *graph
, int n
, int ngraph
)
820 struct solver_scratch
*sc
;
822 sc
= snew(struct solver_scratch
);
826 sc
->possible
= snewn(n
, unsigned char);
828 sc
->bfsqueue
= snewn(n
, int);
829 sc
->bfscolour
= snewn(n
, int);
830 #ifdef SOLVER_DIAGNOSTICS
831 sc
->bfsprev
= snewn(n
, int);
837 static void free_scratch(struct solver_scratch
*sc
)
841 sfree(sc
->bfscolour
);
842 #ifdef SOLVER_DIAGNOSTICS
849 * Count the bits in a word. Only needs to cope with FOUR bits.
851 static int bitcount(int word
)
853 assert(FOUR
<= 4); /* or this needs changing */
854 word
= ((word
& 0xA) >> 1) + (word
& 0x5);
855 word
= ((word
& 0xC) >> 2) + (word
& 0x3);
859 #ifdef SOLVER_DIAGNOSTICS
860 static const char colnames
[FOUR
] = { 'R', 'Y', 'G', 'B' };
863 static int place_colour(struct solver_scratch
*sc
,
864 int *colouring
, int index
, int colour
865 #ifdef SOLVER_DIAGNOSTICS
870 int *graph
= sc
->graph
, n
= sc
->n
, ngraph
= sc
->ngraph
;
873 if (!(sc
->possible
[index
] & (1 << colour
)))
874 return FALSE
; /* can't do it */
876 sc
->possible
[index
] = 1 << colour
;
877 colouring
[index
] = colour
;
879 #ifdef SOLVER_DIAGNOSTICS
881 printf("%s %c in region %d\n", verb
, colnames
[colour
], index
);
885 * Rule out this colour from all the region's neighbours.
887 for (j
= graph_vertex_start(graph
, n
, ngraph
, index
);
888 j
< ngraph
&& graph
[j
] < n
*(index
+1); j
++) {
889 k
= graph
[j
] - index
*n
;
890 #ifdef SOLVER_DIAGNOSTICS
891 if (verbose
&& (sc
->possible
[k
] & (1 << colour
)))
892 printf(" ruling out %c in region %d\n", colnames
[colour
], k
);
894 sc
->possible
[k
] &= ~(1 << colour
);
900 #ifdef SOLVER_DIAGNOSTICS
901 static char *colourset(char *buf
, int set
)
907 for (i
= 0; i
< FOUR
; i
++)
908 if (set
& (1 << i
)) {
909 p
+= sprintf(p
, "%s%c", sep
, colnames
[i
]);
918 * Returns 0 for impossible, 1 for success, 2 for failure to
919 * converge (i.e. puzzle is either ambiguous or just too
922 static int map_solver(struct solver_scratch
*sc
,
923 int *graph
, int n
, int ngraph
, int *colouring
,
929 * Initialise scratch space.
931 for (i
= 0; i
< n
; i
++)
932 sc
->possible
[i
] = (1 << FOUR
) - 1;
937 for (i
= 0; i
< n
; i
++)
938 if (colouring
[i
] >= 0) {
939 if (!place_colour(sc
, colouring
, i
, colouring
[i
]
940 #ifdef SOLVER_DIAGNOSTICS
944 return 0; /* the clues aren't even consistent! */
948 * Now repeatedly loop until we find nothing further to do.
951 int done_something
= FALSE
;
953 if (difficulty
< DIFF_EASY
)
954 break; /* can't do anything at all! */
957 * Simplest possible deduction: find a region with only one
960 for (i
= 0; i
< n
; i
++) if (colouring
[i
] < 0) {
961 int p
= sc
->possible
[i
];
964 return 0; /* puzzle is inconsistent */
966 if ((p
& (p
-1)) == 0) { /* p is a power of two */
968 for (c
= 0; c
< FOUR
; c
++)
972 if (!place_colour(sc
, colouring
, i
, c
973 #ifdef SOLVER_DIAGNOSTICS
977 return 0; /* found puzzle to be inconsistent */
978 done_something
= TRUE
;
985 if (difficulty
< DIFF_NORMAL
)
986 break; /* can't do anything harder */
989 * Failing that, go up one level. Look for pairs of regions
990 * which (a) both have the same pair of possible colours,
991 * (b) are adjacent to one another, (c) are adjacent to the
992 * same region, and (d) that region still thinks it has one
993 * or both of those possible colours.
995 * Simplest way to do this is by going through the graph
996 * edge by edge, so that we start with property (b) and
997 * then look for (a) and finally (c) and (d).
999 for (i
= 0; i
< ngraph
; i
++) {
1000 int j1
= graph
[i
] / n
, j2
= graph
[i
] % n
;
1002 #ifdef SOLVER_DIAGNOSTICS
1003 int started
= FALSE
;
1007 continue; /* done it already, other way round */
1009 if (colouring
[j1
] >= 0 || colouring
[j2
] >= 0)
1010 continue; /* they're not undecided */
1012 if (sc
->possible
[j1
] != sc
->possible
[j2
])
1013 continue; /* they don't have the same possibles */
1015 v
= sc
->possible
[j1
];
1017 * See if v contains exactly two set bits.
1019 v2
= v
& -v
; /* find lowest set bit */
1020 v2
= v
& ~v2
; /* clear it */
1021 if (v2
== 0 || (v2
& (v2
-1)) != 0) /* not power of 2 */
1025 * We've found regions j1 and j2 satisfying properties
1026 * (a) and (b): they have two possible colours between
1027 * them, and since they're adjacent to one another they
1028 * must use _both_ those colours between them.
1029 * Therefore, if they are both adjacent to any other
1030 * region then that region cannot be either colour.
1032 * Go through the neighbours of j1 and see if any are
1035 for (j
= graph_vertex_start(graph
, n
, ngraph
, j1
);
1036 j
< ngraph
&& graph
[j
] < n
*(j1
+1); j
++) {
1037 k
= graph
[j
] - j1
*n
;
1038 if (graph_adjacent(graph
, n
, ngraph
, k
, j2
) &&
1039 (sc
->possible
[k
] & v
)) {
1040 #ifdef SOLVER_DIAGNOSTICS
1044 printf("adjacent regions %d,%d share colours %s\n",
1045 j1
, j2
, colourset(buf
, v
));
1047 printf(" ruling out %s in region %d\n",
1048 colourset(buf
, sc
->possible
[k
] & v
), k
);
1051 sc
->possible
[k
] &= ~v
;
1052 done_something
= TRUE
;
1060 if (difficulty
< DIFF_HARD
)
1061 break; /* can't do anything harder */
1064 * Right; now we get creative. Now we're going to look for
1065 * `forcing chains'. A forcing chain is a path through the
1066 * graph with the following properties:
1068 * (a) Each vertex on the path has precisely two possible
1071 * (b) Each pair of vertices which are adjacent on the
1072 * path share at least one possible colour in common.
1074 * (c) Each vertex in the middle of the path shares _both_
1075 * of its colours with at least one of its neighbours
1076 * (not the same one with both neighbours).
1078 * These together imply that at least one of the possible
1079 * colour choices at one end of the path forces _all_ the
1080 * rest of the colours along the path. In order to make
1081 * real use of this, we need further properties:
1083 * (c) Ruling out some colour C from the vertex at one end
1084 * of the path forces the vertex at the other end to
1087 * (d) The two end vertices are mutually adjacent to some
1090 * (e) That third vertex currently has C as a possibility.
1092 * If we can find all of that lot, we can deduce that at
1093 * least one of the two ends of the forcing chain has
1094 * colour C, and that therefore the mutually adjacent third
1097 * To find forcing chains, we're going to start a bfs at
1098 * each suitable vertex of the graph, once for each of its
1099 * two possible colours.
1101 for (i
= 0; i
< n
; i
++) {
1104 if (colouring
[i
] >= 0 || bitcount(sc
->possible
[i
]) != 2)
1107 for (c
= 0; c
< FOUR
; c
++)
1108 if (sc
->possible
[i
] & (1 << c
)) {
1109 int j
, k
, gi
, origc
, currc
, head
, tail
;
1111 * Try a bfs from this vertex, ruling out
1114 * Within this loop, we work in colour bitmaps
1115 * rather than actual colours, because
1116 * converting back and forth is a needless
1117 * computational expense.
1122 for (j
= 0; j
< n
; j
++) {
1123 sc
->bfscolour
[j
] = -1;
1124 #ifdef SOLVER_DIAGNOSTICS
1125 sc
->bfsprev
[j
] = -1;
1129 sc
->bfsqueue
[tail
++] = i
;
1130 sc
->bfscolour
[i
] = sc
->possible
[i
] &~ origc
;
1132 while (head
< tail
) {
1133 j
= sc
->bfsqueue
[head
++];
1134 currc
= sc
->bfscolour
[j
];
1137 * Try neighbours of j.
1139 for (gi
= graph_vertex_start(graph
, n
, ngraph
, j
);
1140 gi
< ngraph
&& graph
[gi
] < n
*(j
+1); gi
++) {
1141 k
= graph
[gi
] - j
*n
;
1144 * To continue with the bfs in vertex
1145 * k, we need k to be
1146 * (a) not already visited
1147 * (b) have two possible colours
1148 * (c) those colours include currc.
1151 if (sc
->bfscolour
[k
] < 0 &&
1153 bitcount(sc
->possible
[k
]) == 2 &&
1154 (sc
->possible
[k
] & currc
)) {
1155 sc
->bfsqueue
[tail
++] = k
;
1157 sc
->possible
[k
] &~ currc
;
1158 #ifdef SOLVER_DIAGNOSTICS
1164 * One other possibility is that k
1165 * might be the region in which we can
1166 * make a real deduction: if it's
1167 * adjacent to i, contains currc as a
1168 * possibility, and currc is equal to
1169 * the original colour we ruled out.
1171 if (currc
== origc
&&
1172 graph_adjacent(graph
, n
, ngraph
, k
, i
) &&
1173 (sc
->possible
[k
] & currc
)) {
1174 #ifdef SOLVER_DIAGNOSTICS
1176 char buf
[80], *sep
= "";
1179 printf("forcing chain, colour %s, ",
1180 colourset(buf
, origc
));
1181 for (r
= j
; r
!= -1; r
= sc
->bfsprev
[r
]) {
1182 printf("%s%d", sep
, r
);
1185 printf("\n ruling out %s in region %d\n",
1186 colourset(buf
, origc
), k
);
1189 sc
->possible
[k
] &= ~origc
;
1190 done_something
= TRUE
;
1199 if (!done_something
)
1204 * See if we've got a complete solution, and return if so.
1206 for (i
= 0; i
< n
; i
++)
1207 if (colouring
[i
] < 0)
1210 return 1; /* success! */
1213 * If recursion is not permissible, we now give up.
1215 if (difficulty
< DIFF_RECURSE
)
1216 return 2; /* unable to complete */
1219 * Now we've got to do something recursive. So first hunt for a
1220 * currently-most-constrained region.
1224 struct solver_scratch
*rsc
;
1225 int *subcolouring
, *origcolouring
;
1227 int we_already_got_one
;
1232 for (i
= 0; i
< n
; i
++) if (colouring
[i
] < 0) {
1233 int p
= sc
->possible
[i
];
1234 enum { compile_time_assertion
= 1 / (FOUR
<= 4) };
1237 /* Count the set bits. */
1238 c
= (p
& 5) + ((p
>> 1) & 5);
1239 c
= (c
& 3) + ((c
>> 2) & 3);
1240 assert(c
> 1); /* or colouring[i] would be >= 0 */
1248 assert(best
>= 0); /* or we'd be solved already */
1251 * Now iterate over the possible colours for this region.
1253 rsc
= new_scratch(graph
, n
, ngraph
);
1254 rsc
->depth
= sc
->depth
+ 1;
1255 origcolouring
= snewn(n
, int);
1256 memcpy(origcolouring
, colouring
, n
* sizeof(int));
1257 subcolouring
= snewn(n
, int);
1258 we_already_got_one
= FALSE
;
1261 for (i
= 0; i
< FOUR
; i
++) {
1262 if (!(sc
->possible
[best
] & (1 << i
)))
1265 memcpy(subcolouring
, origcolouring
, n
* sizeof(int));
1266 subcolouring
[best
] = i
;
1267 subret
= map_solver(rsc
, graph
, n
, ngraph
,
1268 subcolouring
, difficulty
);
1271 * If this possibility turned up more than one valid
1272 * solution, or if it turned up one and we already had
1273 * one, we're definitely ambiguous.
1275 if (subret
== 2 || (subret
== 1 && we_already_got_one
)) {
1281 * If this possibility turned up one valid solution and
1282 * it's the first we've seen, copy it into the output.
1285 memcpy(colouring
, subcolouring
, n
* sizeof(int));
1286 we_already_got_one
= TRUE
;
1291 * Otherwise, this guess led to a contradiction, so we
1296 sfree(subcolouring
);
1303 /* ----------------------------------------------------------------------
1304 * Game generation main function.
1307 static char *new_game_desc(game_params
*params
, random_state
*rs
,
1308 char **aux
, int interactive
)
1310 struct solver_scratch
*sc
= NULL
;
1311 int *map
, *graph
, ngraph
, *colouring
, *colouring2
, *regions
;
1312 int i
, j
, w
, h
, n
, solveret
, cfreq
[FOUR
];
1315 #ifdef GENERATION_DIAGNOSTICS
1319 int retlen
, retsize
;
1328 map
= snewn(wh
, int);
1329 graph
= snewn(n
*n
, int);
1330 colouring
= snewn(n
, int);
1331 colouring2
= snewn(n
, int);
1332 regions
= snewn(n
, int);
1335 * This is the minimum difficulty below which we'll completely
1336 * reject a map design. Normally we set this to one below the
1337 * requested difficulty, ensuring that we have the right
1338 * result. However, for particularly dense maps or maps with
1339 * particularly few regions it might not be possible to get the
1340 * desired difficulty, so we will eventually drop this down to
1341 * -1 to indicate that any old map will do.
1343 mindiff
= params
->diff
;
1351 genmap(w
, h
, n
, map
, rs
);
1353 #ifdef GENERATION_DIAGNOSTICS
1354 for (y
= 0; y
< h
; y
++) {
1355 for (x
= 0; x
< w
; x
++) {
1360 putchar('a' + v
-36);
1362 putchar('A' + v
-10);
1371 * Convert the map into a graph.
1373 ngraph
= gengraph(w
, h
, n
, map
, graph
);
1375 #ifdef GENERATION_DIAGNOSTICS
1376 for (i
= 0; i
< ngraph
; i
++)
1377 printf("%d-%d\n", graph
[i
]/n
, graph
[i
]%n
);
1383 fourcolour(graph
, n
, ngraph
, colouring
, rs
);
1385 #ifdef GENERATION_DIAGNOSTICS
1386 for (i
= 0; i
< n
; i
++)
1387 printf("%d: %d\n", i
, colouring
[i
]);
1389 for (y
= 0; y
< h
; y
++) {
1390 for (x
= 0; x
< w
; x
++) {
1391 int v
= colouring
[map
[y
*w
+x
]];
1393 putchar('a' + v
-36);
1395 putchar('A' + v
-10);
1404 * Encode the solution as an aux string.
1406 if (*aux
) /* in case we've come round again */
1408 retlen
= retsize
= 0;
1410 for (i
= 0; i
< n
; i
++) {
1413 if (colouring
[i
] < 0)
1416 len
= sprintf(buf
, "%s%d:%d", i ?
";" : "S;", colouring
[i
], i
);
1417 if (retlen
+ len
>= retsize
) {
1418 retsize
= retlen
+ len
+ 256;
1419 ret
= sresize(ret
, retsize
, char);
1421 strcpy(ret
+ retlen
, buf
);
1427 * Remove the region colours one by one, keeping
1428 * solubility. Also ensure that there always remains at
1429 * least one region of every colour, so that the user can
1430 * drag from somewhere.
1432 for (i
= 0; i
< FOUR
; i
++)
1434 for (i
= 0; i
< n
; i
++) {
1436 cfreq
[colouring
[i
]]++;
1438 for (i
= 0; i
< FOUR
; i
++)
1442 shuffle(regions
, n
, sizeof(*regions
), rs
);
1444 if (sc
) free_scratch(sc
);
1445 sc
= new_scratch(graph
, n
, ngraph
);
1447 for (i
= 0; i
< n
; i
++) {
1450 if (cfreq
[colouring
[j
]] == 1)
1451 continue; /* can't remove last region of colour */
1453 memcpy(colouring2
, colouring
, n
*sizeof(int));
1455 solveret
= map_solver(sc
, graph
, n
, ngraph
, colouring2
,
1457 assert(solveret
>= 0); /* mustn't be impossible! */
1458 if (solveret
== 1) {
1459 cfreq
[colouring
[j
]]--;
1464 #ifdef GENERATION_DIAGNOSTICS
1465 for (i
= 0; i
< n
; i
++)
1466 if (colouring
[i
] >= 0) {
1470 putchar('a' + i
-36);
1472 putchar('A' + i
-10);
1475 printf(": %d\n", colouring
[i
]);
1480 * Finally, check that the puzzle is _at least_ as hard as
1481 * required, and indeed that it isn't already solved.
1482 * (Calling map_solver with negative difficulty ensures the
1483 * latter - if a solver which _does nothing_ can solve it,
1486 memcpy(colouring2
, colouring
, n
*sizeof(int));
1487 if (map_solver(sc
, graph
, n
, ngraph
, colouring2
,
1488 mindiff
- 1) == 1) {
1490 * Drop minimum difficulty if necessary.
1492 if (mindiff
> 0 && (n
< 9 || n
> 2*wh
/3)) {
1494 mindiff
= 0; /* give up and go for Easy */
1503 * Encode as a game ID. We do this by:
1505 * - first going along the horizontal edges row by row, and
1506 * then the vertical edges column by column
1507 * - encoding the lengths of runs of edges and runs of
1509 * - the decoder will reconstitute the region boundaries from
1510 * this and automatically number them the same way we did
1511 * - then we encode the initial region colours in a Slant-like
1512 * fashion (digits 0-3 interspersed with letters giving
1513 * lengths of runs of empty spaces).
1515 retlen
= retsize
= 0;
1522 * Start with a notional non-edge, so that there'll be an
1523 * explicit `a' to distinguish the case where we start with
1529 for (i
= 0; i
< w
*(h
-1) + (w
-1)*h
; i
++) {
1530 int x
, y
, dx
, dy
, v
;
1533 /* Horizontal edge. */
1539 /* Vertical edge. */
1540 x
= (i
- w
*(h
-1)) / h
;
1541 y
= (i
- w
*(h
-1)) % h
;
1546 if (retlen
+ 10 >= retsize
) {
1547 retsize
= retlen
+ 256;
1548 ret
= sresize(ret
, retsize
, char);
1551 v
= (map
[y
*w
+x
] != map
[(y
+dy
)*w
+(x
+dx
)]);
1554 ret
[retlen
++] = 'a'-1 + run
;
1559 * 'z' is a special case in this encoding. Rather
1560 * than meaning a run of 26 and a state switch, it
1561 * means a run of 25 and _no_ state switch, because
1562 * otherwise there'd be no way to encode runs of
1566 ret
[retlen
++] = 'z';
1573 ret
[retlen
++] = 'a'-1 + run
;
1574 ret
[retlen
++] = ',';
1577 for (i
= 0; i
< n
; i
++) {
1578 if (retlen
+ 10 >= retsize
) {
1579 retsize
= retlen
+ 256;
1580 ret
= sresize(ret
, retsize
, char);
1583 if (colouring
[i
] < 0) {
1585 * In _this_ encoding, 'z' is a run of 26, since
1586 * there's no implicit state switch after each run.
1587 * Confusingly different, but more compact.
1590 ret
[retlen
++] = 'z';
1596 ret
[retlen
++] = 'a'-1 + run
;
1597 ret
[retlen
++] = '0' + colouring
[i
];
1602 ret
[retlen
++] = 'a'-1 + run
;
1605 assert(retlen
< retsize
);
1618 static char *parse_edge_list(game_params
*params
, char **desc
, int *map
)
1620 int w
= params
->w
, h
= params
->h
, wh
= w
*h
, n
= params
->n
;
1621 int i
, k
, pos
, state
;
1624 for (i
= 0; i
< wh
; i
++)
1631 * Parse the game description to get the list of edges, and
1632 * build up a disjoint set forest as we go (by identifying
1633 * pairs of squares whenever the edge list shows a non-edge).
1635 while (*p
&& *p
!= ',') {
1636 if (*p
< 'a' || *p
> 'z')
1637 return "Unexpected character in edge list";
1648 } else if (pos
< w
*(h
-1)) {
1649 /* Horizontal edge. */
1654 } else if (pos
< 2*wh
-w
-h
) {
1655 /* Vertical edge. */
1656 x
= (pos
- w
*(h
-1)) / h
;
1657 y
= (pos
- w
*(h
-1)) % h
;
1661 return "Too much data in edge list";
1663 dsf_merge(map
+wh
, y
*w
+x
, (y
+dy
)*w
+(x
+dx
));
1671 assert(pos
<= 2*wh
-w
-h
);
1673 return "Too little data in edge list";
1676 * Now go through again and allocate region numbers.
1679 for (i
= 0; i
< wh
; i
++)
1681 for (i
= 0; i
< wh
; i
++) {
1682 k
= dsf_canonify(map
+wh
, i
);
1688 return "Edge list defines the wrong number of regions";
1695 static char *validate_desc(game_params
*params
, char *desc
)
1697 int w
= params
->w
, h
= params
->h
, wh
= w
*h
, n
= params
->n
;
1702 map
= snewn(2*wh
, int);
1703 ret
= parse_edge_list(params
, &desc
, map
);
1709 return "Expected comma before clue list";
1710 desc
++; /* eat comma */
1714 if (*desc
>= '0' && *desc
< '0'+FOUR
)
1716 else if (*desc
>= 'a' && *desc
<= 'z')
1717 area
+= *desc
- 'a' + 1;
1719 return "Unexpected character in clue list";
1723 return "Too little data in clue list";
1725 return "Too much data in clue list";
1730 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
1732 int w
= params
->w
, h
= params
->h
, wh
= w
*h
, n
= params
->n
;
1735 game_state
*state
= snew(game_state
);
1738 state
->colouring
= snewn(n
, int);
1739 for (i
= 0; i
< n
; i
++)
1740 state
->colouring
[i
] = -1;
1741 state
->pencil
= snewn(n
, int);
1742 for (i
= 0; i
< n
; i
++)
1743 state
->pencil
[i
] = 0;
1745 state
->completed
= state
->cheated
= FALSE
;
1747 state
->map
= snew(struct map
);
1748 state
->map
->refcount
= 1;
1749 state
->map
->map
= snewn(wh
*4, int);
1750 state
->map
->graph
= snewn(n
*n
, int);
1752 state
->map
->immutable
= snewn(n
, int);
1753 for (i
= 0; i
< n
; i
++)
1754 state
->map
->immutable
[i
] = FALSE
;
1760 ret
= parse_edge_list(params
, &p
, state
->map
->map
);
1765 * Set up the other three quadrants in `map'.
1767 for (i
= wh
; i
< 4*wh
; i
++)
1768 state
->map
->map
[i
] = state
->map
->map
[i
% wh
];
1774 * Now process the clue list.
1778 if (*p
>= '0' && *p
< '0'+FOUR
) {
1779 state
->colouring
[pos
] = *p
- '0';
1780 state
->map
->immutable
[pos
] = TRUE
;
1783 assert(*p
>= 'a' && *p
<= 'z');
1784 pos
+= *p
- 'a' + 1;
1790 state
->map
->ngraph
= gengraph(w
, h
, n
, state
->map
->map
, state
->map
->graph
);
1793 * Attempt to smooth out some of the more jagged region
1794 * outlines by the judicious use of diagonally divided squares.
1797 random_state
*rs
= random_init(desc
, strlen(desc
));
1798 int *squares
= snewn(wh
, int);
1801 for (i
= 0; i
< wh
; i
++)
1803 shuffle(squares
, wh
, sizeof(*squares
), rs
);
1806 done_something
= FALSE
;
1807 for (i
= 0; i
< wh
; i
++) {
1808 int y
= squares
[i
] / w
, x
= squares
[i
] % w
;
1809 int c
= state
->map
->map
[y
*w
+x
];
1812 if (x
== 0 || x
== w
-1 || y
== 0 || y
== h
-1)
1815 if (state
->map
->map
[TE
* wh
+ y
*w
+x
] !=
1816 state
->map
->map
[BE
* wh
+ y
*w
+x
])
1819 tc
= state
->map
->map
[BE
* wh
+ (y
-1)*w
+x
];
1820 bc
= state
->map
->map
[TE
* wh
+ (y
+1)*w
+x
];
1821 lc
= state
->map
->map
[RE
* wh
+ y
*w
+(x
-1)];
1822 rc
= state
->map
->map
[LE
* wh
+ y
*w
+(x
+1)];
1825 * If this square is adjacent on two sides to one
1826 * region and on the other two sides to the other
1827 * region, and is itself one of the two regions, we can
1828 * adjust it so that it's a diagonal.
1830 if (tc
!= bc
&& (tc
== c
|| bc
== c
)) {
1831 if ((lc
== tc
&& rc
== bc
) ||
1832 (lc
== bc
&& rc
== tc
)) {
1833 state
->map
->map
[TE
* wh
+ y
*w
+x
] = tc
;
1834 state
->map
->map
[BE
* wh
+ y
*w
+x
] = bc
;
1835 state
->map
->map
[LE
* wh
+ y
*w
+x
] = lc
;
1836 state
->map
->map
[RE
* wh
+ y
*w
+x
] = rc
;
1837 done_something
= TRUE
;
1841 } while (done_something
);
1847 * Analyse the map to find a canonical line segment
1848 * corresponding to each edge, and a canonical point
1849 * corresponding to each region. The former are where we'll
1850 * eventually put error markers; the latter are where we'll put
1851 * per-region flags such as numbers (when in diagnostic mode).
1854 int *bestx
, *besty
, *an
, pass
;
1855 float *ax
, *ay
, *best
;
1857 ax
= snewn(state
->map
->ngraph
+ n
, float);
1858 ay
= snewn(state
->map
->ngraph
+ n
, float);
1859 an
= snewn(state
->map
->ngraph
+ n
, int);
1860 bestx
= snewn(state
->map
->ngraph
+ n
, int);
1861 besty
= snewn(state
->map
->ngraph
+ n
, int);
1862 best
= snewn(state
->map
->ngraph
+ n
, float);
1864 for (i
= 0; i
< state
->map
->ngraph
+ n
; i
++) {
1865 bestx
[i
] = besty
[i
] = -1;
1866 best
[i
] = 2*(w
+h
)+1;
1867 ax
[i
] = ay
[i
] = 0.0F
;
1872 * We make two passes over the map, finding all the line
1873 * segments separating regions and all the suitable points
1874 * within regions. In the first pass, we compute the
1875 * _average_ x and y coordinate of all the points in a
1876 * given class; in the second pass, for each such average
1877 * point, we find the candidate closest to it and call that
1880 * Line segments are considered to have coordinates in
1881 * their centre. Thus, at least one coordinate for any line
1882 * segment is always something-and-a-half; so we store our
1883 * coordinates as twice their normal value.
1885 for (pass
= 0; pass
< 2; pass
++) {
1888 for (y
= 0; y
< h
; y
++)
1889 for (x
= 0; x
< w
; x
++) {
1890 int ex
[4], ey
[4], ea
[4], eb
[4], en
= 0;
1893 * Look for an edge to the right of this
1894 * square, an edge below it, and an edge in the
1895 * middle of it. Also look to see if the point
1896 * at the bottom right of this square is on an
1897 * edge (and isn't a place where more than two
1902 ea
[en
] = state
->map
->map
[RE
* wh
+ y
*w
+x
];
1903 eb
[en
] = state
->map
->map
[LE
* wh
+ y
*w
+(x
+1)];
1910 ea
[en
] = state
->map
->map
[BE
* wh
+ y
*w
+x
];
1911 eb
[en
] = state
->map
->map
[TE
* wh
+ (y
+1)*w
+x
];
1917 ea
[en
] = state
->map
->map
[TE
* wh
+ y
*w
+x
];
1918 eb
[en
] = state
->map
->map
[BE
* wh
+ y
*w
+x
];
1923 if (x
+1 < w
&& y
+1 < h
) {
1924 /* bottom right corner */
1925 int oct
[8], othercol
, nchanges
;
1926 oct
[0] = state
->map
->map
[RE
* wh
+ y
*w
+x
];
1927 oct
[1] = state
->map
->map
[LE
* wh
+ y
*w
+(x
+1)];
1928 oct
[2] = state
->map
->map
[BE
* wh
+ y
*w
+(x
+1)];
1929 oct
[3] = state
->map
->map
[TE
* wh
+ (y
+1)*w
+(x
+1)];
1930 oct
[4] = state
->map
->map
[LE
* wh
+ (y
+1)*w
+(x
+1)];
1931 oct
[5] = state
->map
->map
[RE
* wh
+ (y
+1)*w
+x
];
1932 oct
[6] = state
->map
->map
[TE
* wh
+ (y
+1)*w
+x
];
1933 oct
[7] = state
->map
->map
[BE
* wh
+ y
*w
+x
];
1937 for (i
= 0; i
< 8; i
++) {
1938 if (oct
[i
] != oct
[0]) {
1941 else if (othercol
!= oct
[i
])
1942 break; /* three colours at this point */
1944 if (oct
[i
] != oct
[(i
+1) & 7])
1949 * Now if there are exactly two regions at
1950 * this point (not one, and not three or
1951 * more), and only two changes around the
1952 * loop, then this is a valid place to put
1955 if (i
== 8 && othercol
>= 0 && nchanges
== 2) {
1964 * If there's exactly _one_ region at this
1965 * point, on the other hand, it's a valid
1966 * place to put a region centre.
1969 ea
[en
] = eb
[en
] = oct
[0];
1977 * Now process the points we've found, one by
1980 for (i
= 0; i
< en
; i
++) {
1981 int emin
= min(ea
[i
], eb
[i
]);
1982 int emax
= max(ea
[i
], eb
[i
]);
1988 graph_edge_index(state
->map
->graph
, n
,
1989 state
->map
->ngraph
, emin
,
1993 gindex
= state
->map
->ngraph
+ emin
;
1996 assert(gindex
>= 0);
2000 * In pass 0, accumulate the values
2001 * we'll use to compute the average
2004 ax
[gindex
] += ex
[i
];
2005 ay
[gindex
] += ey
[i
];
2009 * In pass 1, work out whether this
2010 * point is closer to the average than
2011 * the last one we've seen.
2015 assert(an
[gindex
] > 0);
2016 dx
= ex
[i
] - ax
[gindex
];
2017 dy
= ey
[i
] - ay
[gindex
];
2018 d
= sqrt(dx
*dx
+ dy
*dy
);
2019 if (d
< best
[gindex
]) {
2021 bestx
[gindex
] = ex
[i
];
2022 besty
[gindex
] = ey
[i
];
2029 for (i
= 0; i
< state
->map
->ngraph
+ n
; i
++)
2037 state
->map
->edgex
= snewn(state
->map
->ngraph
, int);
2038 state
->map
->edgey
= snewn(state
->map
->ngraph
, int);
2039 memcpy(state
->map
->edgex
, bestx
, state
->map
->ngraph
* sizeof(int));
2040 memcpy(state
->map
->edgey
, besty
, state
->map
->ngraph
* sizeof(int));
2042 state
->map
->regionx
= snewn(n
, int);
2043 state
->map
->regiony
= snewn(n
, int);
2044 memcpy(state
->map
->regionx
, bestx
+ state
->map
->ngraph
, n
*sizeof(int));
2045 memcpy(state
->map
->regiony
, besty
+ state
->map
->ngraph
, n
*sizeof(int));
2047 for (i
= 0; i
< state
->map
->ngraph
; i
++)
2048 if (state
->map
->edgex
[i
] < 0) {
2049 /* Find the other representation of this edge. */
2050 int e
= state
->map
->graph
[i
];
2051 int iprime
= graph_edge_index(state
->map
->graph
, n
,
2052 state
->map
->ngraph
, e
%n
, e
/n
);
2053 assert(state
->map
->edgex
[iprime
] >= 0);
2054 state
->map
->edgex
[i
] = state
->map
->edgex
[iprime
];
2055 state
->map
->edgey
[i
] = state
->map
->edgey
[iprime
];
2069 static game_state
*dup_game(game_state
*state
)
2071 game_state
*ret
= snew(game_state
);
2074 ret
->colouring
= snewn(state
->p
.n
, int);
2075 memcpy(ret
->colouring
, state
->colouring
, state
->p
.n
* sizeof(int));
2076 ret
->pencil
= snewn(state
->p
.n
, int);
2077 memcpy(ret
->pencil
, state
->pencil
, state
->p
.n
* sizeof(int));
2078 ret
->map
= state
->map
;
2079 ret
->map
->refcount
++;
2080 ret
->completed
= state
->completed
;
2081 ret
->cheated
= state
->cheated
;
2086 static void free_game(game_state
*state
)
2088 if (--state
->map
->refcount
<= 0) {
2089 sfree(state
->map
->map
);
2090 sfree(state
->map
->graph
);
2091 sfree(state
->map
->immutable
);
2092 sfree(state
->map
->edgex
);
2093 sfree(state
->map
->edgey
);
2094 sfree(state
->map
->regionx
);
2095 sfree(state
->map
->regiony
);
2098 sfree(state
->colouring
);
2102 static char *solve_game(game_state
*state
, game_state
*currstate
,
2103 char *aux
, char **error
)
2110 struct solver_scratch
*sc
;
2114 int retlen
, retsize
;
2116 colouring
= snewn(state
->map
->n
, int);
2117 memcpy(colouring
, state
->colouring
, state
->map
->n
* sizeof(int));
2119 sc
= new_scratch(state
->map
->graph
, state
->map
->n
, state
->map
->ngraph
);
2120 sret
= map_solver(sc
, state
->map
->graph
, state
->map
->n
,
2121 state
->map
->ngraph
, colouring
, DIFFCOUNT
-1);
2127 *error
= "Puzzle is inconsistent";
2129 *error
= "Unable to find a unique solution for this puzzle";
2134 ret
= snewn(retsize
, char);
2138 for (i
= 0; i
< state
->map
->n
; i
++) {
2141 assert(colouring
[i
] >= 0);
2142 if (colouring
[i
] == currstate
->colouring
[i
])
2144 assert(!state
->map
->immutable
[i
]);
2146 len
= sprintf(buf
, ";%d:%d", colouring
[i
], i
);
2147 if (retlen
+ len
>= retsize
) {
2148 retsize
= retlen
+ len
+ 256;
2149 ret
= sresize(ret
, retsize
, char);
2151 strcpy(ret
+ retlen
, buf
);
2162 static char *game_text_format(game_state
*state
)
2168 int drag_colour
; /* -1 means no drag active */
2173 static game_ui
*new_ui(game_state
*state
)
2175 game_ui
*ui
= snew(game_ui
);
2176 ui
->dragx
= ui
->dragy
= -1;
2177 ui
->drag_colour
= -2;
2178 ui
->show_numbers
= FALSE
;
2182 static void free_ui(game_ui
*ui
)
2187 static char *encode_ui(game_ui
*ui
)
2192 static void decode_ui(game_ui
*ui
, char *encoding
)
2196 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
2197 game_state
*newstate
)
2201 struct game_drawstate
{
2203 unsigned long *drawn
, *todraw
;
2205 int dragx
, dragy
, drag_visible
;
2209 /* Flags in `drawn'. */
2210 #define ERR_BASE 0x00800000L
2211 #define ERR_MASK 0xFF800000L
2212 #define PENCIL_T_BASE 0x00080000L
2213 #define PENCIL_T_MASK 0x00780000L
2214 #define PENCIL_B_BASE 0x00008000L
2215 #define PENCIL_B_MASK 0x00078000L
2216 #define PENCIL_MASK 0x007F8000L
2217 #define SHOW_NUMBERS 0x00004000L
2219 #define TILESIZE (ds->tilesize)
2220 #define BORDER (TILESIZE)
2221 #define COORD(x) ( (x) * TILESIZE + BORDER )
2222 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
2224 static int region_from_coords(game_state
*state
, game_drawstate
*ds
,
2227 int w
= state
->p
.w
, h
= state
->p
.h
, wh
= w
*h
/*, n = state->p.n */;
2228 int tx
= FROMCOORD(x
), ty
= FROMCOORD(y
);
2229 int dx
= x
- COORD(tx
), dy
= y
- COORD(ty
);
2232 if (tx
< 0 || tx
>= w
|| ty
< 0 || ty
>= h
)
2233 return -1; /* border */
2235 quadrant
= 2 * (dx
> dy
) + (TILESIZE
- dx
> dy
);
2236 quadrant
= (quadrant
== 0 ? BE
:
2237 quadrant
== 1 ? LE
:
2238 quadrant
== 2 ? RE
: TE
);
2240 return state
->map
->map
[quadrant
* wh
+ ty
*w
+tx
];
2243 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
2244 int x
, int y
, int button
)
2249 * Enable or disable numeric labels on regions.
2251 if (button
== 'l' || button
== 'L') {
2252 ui
->show_numbers
= !ui
->show_numbers
;
2256 if (button
== LEFT_BUTTON
|| button
== RIGHT_BUTTON
) {
2257 int r
= region_from_coords(state
, ds
, x
, y
);
2260 ui
->drag_colour
= state
->colouring
[r
];
2262 ui
->drag_colour
= -1;
2268 if ((button
== LEFT_DRAG
|| button
== RIGHT_DRAG
) &&
2269 ui
->drag_colour
> -2) {
2275 if ((button
== LEFT_RELEASE
|| button
== RIGHT_RELEASE
) &&
2276 ui
->drag_colour
> -2) {
2277 int r
= region_from_coords(state
, ds
, x
, y
);
2278 int c
= ui
->drag_colour
;
2281 * Cancel the drag, whatever happens.
2283 ui
->drag_colour
= -2;
2284 ui
->dragx
= ui
->dragy
= -1;
2287 return ""; /* drag into border; do nothing else */
2289 if (state
->map
->immutable
[r
])
2290 return ""; /* can't change this region */
2292 if (state
->colouring
[r
] == c
)
2293 return ""; /* don't _need_ to change this region */
2295 if (button
== RIGHT_RELEASE
&& state
->colouring
[r
] >= 0)
2296 return ""; /* can't pencil on a coloured region */
2298 sprintf(buf
, "%s%c:%d", (button
== RIGHT_RELEASE ?
"p" : ""),
2299 (int)(c
< 0 ?
'C' : '0' + c
), r
);
2306 static game_state
*execute_move(game_state
*state
, char *move
)
2309 game_state
*ret
= dup_game(state
);
2320 if ((c
== 'C' || (c
>= '0' && c
< '0'+FOUR
)) &&
2321 sscanf(move
+1, ":%d%n", &k
, &adv
) == 1 &&
2322 k
>= 0 && k
< state
->p
.n
) {
2325 if (ret
->colouring
[k
] >= 0) {
2332 ret
->pencil
[k
] ^= 1 << (c
- '0');
2334 ret
->colouring
[k
] = (c
== 'C' ?
-1 : c
- '0');
2337 } else if (*move
== 'S') {
2339 ret
->cheated
= TRUE
;
2345 if (*move
&& *move
!= ';') {
2354 * Check for completion.
2356 if (!ret
->completed
) {
2359 for (i
= 0; i
< n
; i
++)
2360 if (ret
->colouring
[i
] < 0) {
2366 for (i
= 0; i
< ret
->map
->ngraph
; i
++) {
2367 int j
= ret
->map
->graph
[i
] / n
;
2368 int k
= ret
->map
->graph
[i
] % n
;
2369 if (ret
->colouring
[j
] == ret
->colouring
[k
]) {
2377 ret
->completed
= TRUE
;
2383 /* ----------------------------------------------------------------------
2387 static void game_compute_size(game_params
*params
, int tilesize
,
2390 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2391 struct { int tilesize
; } ads
, *ds
= &ads
;
2392 ads
.tilesize
= tilesize
;
2394 *x
= params
->w
* TILESIZE
+ 2 * BORDER
+ 1;
2395 *y
= params
->h
* TILESIZE
+ 2 * BORDER
+ 1;
2398 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
2399 game_params
*params
, int tilesize
)
2401 ds
->tilesize
= tilesize
;
2404 blitter_free(dr
, ds
->bl
);
2405 ds
->bl
= blitter_new(dr
, TILESIZE
+3, TILESIZE
+3);
2408 const float map_colours
[FOUR
][3] = {
2412 {0.55F
, 0.45F
, 0.35F
},
2414 const int map_hatching
[FOUR
] = {
2415 HATCH_VERT
, HATCH_SLASH
, HATCH_HORIZ
, HATCH_BACKSLASH
2418 static float *game_colours(frontend
*fe
, game_state
*state
, int *ncolours
)
2420 float *ret
= snewn(3 * NCOLOURS
, float);
2422 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
2424 ret
[COL_GRID
* 3 + 0] = 0.0F
;
2425 ret
[COL_GRID
* 3 + 1] = 0.0F
;
2426 ret
[COL_GRID
* 3 + 2] = 0.0F
;
2428 memcpy(ret
+ COL_0
* 3, map_colours
[0], 3 * sizeof(float));
2429 memcpy(ret
+ COL_1
* 3, map_colours
[1], 3 * sizeof(float));
2430 memcpy(ret
+ COL_2
* 3, map_colours
[2], 3 * sizeof(float));
2431 memcpy(ret
+ COL_3
* 3, map_colours
[3], 3 * sizeof(float));
2433 ret
[COL_ERROR
* 3 + 0] = 1.0F
;
2434 ret
[COL_ERROR
* 3 + 1] = 0.0F
;
2435 ret
[COL_ERROR
* 3 + 2] = 0.0F
;
2437 ret
[COL_ERRTEXT
* 3 + 0] = 1.0F
;
2438 ret
[COL_ERRTEXT
* 3 + 1] = 1.0F
;
2439 ret
[COL_ERRTEXT
* 3 + 2] = 1.0F
;
2441 *ncolours
= NCOLOURS
;
2445 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
2447 struct game_drawstate
*ds
= snew(struct game_drawstate
);
2451 ds
->drawn
= snewn(state
->p
.w
* state
->p
.h
, unsigned long);
2452 for (i
= 0; i
< state
->p
.w
* state
->p
.h
; i
++)
2453 ds
->drawn
[i
] = 0xFFFFL
;
2454 ds
->todraw
= snewn(state
->p
.w
* state
->p
.h
, unsigned long);
2455 ds
->started
= FALSE
;
2457 ds
->drag_visible
= FALSE
;
2458 ds
->dragx
= ds
->dragy
= -1;
2463 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
2468 blitter_free(dr
, ds
->bl
);
2472 static void draw_error(drawing
*dr
, game_drawstate
*ds
, int x
, int y
)
2480 coords
[0] = x
- TILESIZE
*2/5;
2483 coords
[3] = y
- TILESIZE
*2/5;
2484 coords
[4] = x
+ TILESIZE
*2/5;
2487 coords
[7] = y
+ TILESIZE
*2/5;
2488 draw_polygon(dr
, coords
, 4, COL_ERROR
, COL_GRID
);
2491 * Draw an exclamation mark in the diamond. This turns out to
2492 * look unpleasantly off-centre if done via draw_text, so I do
2493 * it by hand on the basis that exclamation marks aren't that
2494 * difficult to draw...
2497 yext
= TILESIZE
*2/5 - (xext
*2+2);
2498 draw_rect(dr
, x
-xext
, y
-yext
, xext
*2+1, yext
*2+1 - (xext
*3),
2500 draw_rect(dr
, x
-xext
, y
+yext
-xext
*2+1, xext
*2+1, xext
*2, COL_ERRTEXT
);
2503 static void draw_square(drawing
*dr
, game_drawstate
*ds
,
2504 game_params
*params
, struct map
*map
,
2505 int x
, int y
, int v
)
2507 int w
= params
->w
, h
= params
->h
, wh
= w
*h
;
2508 int tv
, bv
, xo
, yo
, errs
, pencil
, i
, j
, oldj
;
2511 errs
= v
& ERR_MASK
;
2513 pencil
= v
& PENCIL_MASK
;
2515 show_numbers
= v
& SHOW_NUMBERS
;
2520 clip(dr
, COORD(x
), COORD(y
), TILESIZE
, TILESIZE
);
2523 * Draw the region colour.
2525 draw_rect(dr
, COORD(x
), COORD(y
), TILESIZE
, TILESIZE
,
2526 (tv
== FOUR ? COL_BACKGROUND
: COL_0
+ tv
));
2528 * Draw the second region colour, if this is a diagonally
2531 if (map
->map
[TE
* wh
+ y
*w
+x
] != map
->map
[BE
* wh
+ y
*w
+x
]) {
2533 coords
[0] = COORD(x
)-1;
2534 coords
[1] = COORD(y
+1)+1;
2535 if (map
->map
[LE
* wh
+ y
*w
+x
] == map
->map
[TE
* wh
+ y
*w
+x
])
2536 coords
[2] = COORD(x
+1)+1;
2538 coords
[2] = COORD(x
)-1;
2539 coords
[3] = COORD(y
)-1;
2540 coords
[4] = COORD(x
+1)+1;
2541 coords
[5] = COORD(y
+1)+1;
2542 draw_polygon(dr
, coords
, 3,
2543 (bv
== FOUR ? COL_BACKGROUND
: COL_0
+ bv
), COL_GRID
);
2547 * Draw `pencil marks'. Currently we arrange these in a square
2548 * formation, which means we may be in trouble if the value of
2549 * FOUR changes later...
2552 for (yo
= 0; yo
< 4; yo
++)
2553 for (xo
= 0; xo
< 4; xo
++) {
2554 int te
= map
->map
[TE
* wh
+ y
*w
+x
];
2557 e
= (yo
< xo
&& yo
< 3-xo ? TE
:
2558 yo
> xo
&& yo
> 3-xo ? BE
:
2560 ee
= map
->map
[e
* wh
+ y
*w
+x
];
2562 c
= (yo
& 1) * 2 + (xo
& 1);
2564 if (!(pencil
& ((ee
== te ? PENCIL_T_BASE
: PENCIL_B_BASE
) << c
)))
2568 (map
->map
[TE
* wh
+ y
*w
+x
] != map
->map
[LE
* wh
+ y
*w
+x
]))
2569 continue; /* avoid TL-BR diagonal line */
2571 (map
->map
[TE
* wh
+ y
*w
+x
] != map
->map
[RE
* wh
+ y
*w
+x
]))
2572 continue; /* avoid BL-TR diagonal line */
2574 draw_rect(dr
, COORD(x
) + (5*xo
+1)*TILESIZE
/20,
2575 COORD(y
) + (5*yo
+1)*TILESIZE
/20,
2576 4*TILESIZE
/20, 4*TILESIZE
/20, COL_0
+ c
);
2580 * Draw the grid lines, if required.
2582 if (x
<= 0 || map
->map
[RE
*wh
+y
*w
+(x
-1)] != map
->map
[LE
*wh
+y
*w
+x
])
2583 draw_rect(dr
, COORD(x
), COORD(y
), 1, TILESIZE
, COL_GRID
);
2584 if (y
<= 0 || map
->map
[BE
*wh
+(y
-1)*w
+x
] != map
->map
[TE
*wh
+y
*w
+x
])
2585 draw_rect(dr
, COORD(x
), COORD(y
), TILESIZE
, 1, COL_GRID
);
2586 if (x
<= 0 || y
<= 0 ||
2587 map
->map
[RE
*wh
+(y
-1)*w
+(x
-1)] != map
->map
[TE
*wh
+y
*w
+x
] ||
2588 map
->map
[BE
*wh
+(y
-1)*w
+(x
-1)] != map
->map
[LE
*wh
+y
*w
+x
])
2589 draw_rect(dr
, COORD(x
), COORD(y
), 1, 1, COL_GRID
);
2592 * Draw error markers.
2594 for (yo
= 0; yo
< 3; yo
++)
2595 for (xo
= 0; xo
< 3; xo
++)
2596 if (errs
& (ERR_BASE
<< (yo
*3+xo
)))
2598 (COORD(x
)*2+TILESIZE
*xo
)/2,
2599 (COORD(y
)*2+TILESIZE
*yo
)/2);
2602 * Draw region numbers, if desired.
2606 for (i
= 0; i
< 2; i
++) {
2607 j
= map
->map
[(i?BE
:TE
)*wh
+y
*w
+x
];
2612 xo
= map
->regionx
[j
] - 2*x
;
2613 yo
= map
->regiony
[j
] - 2*y
;
2614 if (xo
>= 0 && xo
<= 2 && yo
>= 0 && yo
<= 2) {
2616 sprintf(buf
, "%d", j
);
2617 draw_text(dr
, (COORD(x
)*2+TILESIZE
*xo
)/2,
2618 (COORD(y
)*2+TILESIZE
*yo
)/2,
2619 FONT_VARIABLE
, 3*TILESIZE
/5,
2620 ALIGN_HCENTRE
|ALIGN_VCENTRE
,
2628 draw_update(dr
, COORD(x
), COORD(y
), TILESIZE
, TILESIZE
);
2631 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
2632 game_state
*state
, int dir
, game_ui
*ui
,
2633 float animtime
, float flashtime
)
2635 int w
= state
->p
.w
, h
= state
->p
.h
, wh
= w
*h
, n
= state
->p
.n
;
2639 if (ds
->drag_visible
) {
2640 blitter_load(dr
, ds
->bl
, ds
->dragx
, ds
->dragy
);
2641 draw_update(dr
, ds
->dragx
, ds
->dragy
, TILESIZE
+ 3, TILESIZE
+ 3);
2642 ds
->drag_visible
= FALSE
;
2646 * The initial contents of the window are not guaranteed and
2647 * can vary with front ends. To be on the safe side, all games
2648 * should start by drawing a big background-colour rectangle
2649 * covering the whole window.
2654 game_compute_size(&state
->p
, TILESIZE
, &ww
, &wh
);
2655 draw_rect(dr
, 0, 0, ww
, wh
, COL_BACKGROUND
);
2656 draw_rect(dr
, COORD(0), COORD(0), w
*TILESIZE
+1, h
*TILESIZE
+1,
2659 draw_update(dr
, 0, 0, ww
, wh
);
2664 if (flash_type
== 1)
2665 flash
= (int)(flashtime
* FOUR
/ flash_length
);
2667 flash
= 1 + (int)(flashtime
* THREE
/ flash_length
);
2672 * Set up the `todraw' array.
2674 for (y
= 0; y
< h
; y
++)
2675 for (x
= 0; x
< w
; x
++) {
2676 int tv
= state
->colouring
[state
->map
->map
[TE
* wh
+ y
*w
+x
]];
2677 int bv
= state
->colouring
[state
->map
->map
[BE
* wh
+ y
*w
+x
]];
2686 if (flash_type
== 1) {
2691 } else if (flash_type
== 2) {
2696 tv
= (tv
+ flash
) % FOUR
;
2698 bv
= (bv
+ flash
) % FOUR
;
2707 for (i
= 0; i
< FOUR
; i
++) {
2708 if (state
->colouring
[state
->map
->map
[TE
* wh
+ y
*w
+x
]] < 0 &&
2709 (state
->pencil
[state
->map
->map
[TE
* wh
+ y
*w
+x
]] & (1<<i
)))
2710 v
|= PENCIL_T_BASE
<< i
;
2711 if (state
->colouring
[state
->map
->map
[BE
* wh
+ y
*w
+x
]] < 0 &&
2712 (state
->pencil
[state
->map
->map
[BE
* wh
+ y
*w
+x
]] & (1<<i
)))
2713 v
|= PENCIL_B_BASE
<< i
;
2716 if (ui
->show_numbers
)
2719 ds
->todraw
[y
*w
+x
] = v
;
2723 * Add error markers to the `todraw' array.
2725 for (i
= 0; i
< state
->map
->ngraph
; i
++) {
2726 int v1
= state
->map
->graph
[i
] / n
;
2727 int v2
= state
->map
->graph
[i
] % n
;
2730 if (state
->colouring
[v1
] < 0 || state
->colouring
[v2
] < 0)
2732 if (state
->colouring
[v1
] != state
->colouring
[v2
])
2735 x
= state
->map
->edgex
[i
];
2736 y
= state
->map
->edgey
[i
];
2741 ds
->todraw
[y
*w
+x
] |= ERR_BASE
<< (yo
*3+xo
);
2744 ds
->todraw
[y
*w
+(x
-1)] |= ERR_BASE
<< (yo
*3+2);
2748 ds
->todraw
[(y
-1)*w
+x
] |= ERR_BASE
<< (2*3+xo
);
2750 if (xo
== 0 && yo
== 0) {
2751 assert(x
> 0 && y
> 0);
2752 ds
->todraw
[(y
-1)*w
+(x
-1)] |= ERR_BASE
<< (2*3+2);
2757 * Now actually draw everything.
2759 for (y
= 0; y
< h
; y
++)
2760 for (x
= 0; x
< w
; x
++) {
2761 int v
= ds
->todraw
[y
*w
+x
];
2762 if (ds
->drawn
[y
*w
+x
] != v
) {
2763 draw_square(dr
, ds
, &state
->p
, state
->map
, x
, y
, v
);
2764 ds
->drawn
[y
*w
+x
] = v
;
2769 * Draw the dragged colour blob if any.
2771 if (ui
->drag_colour
> -2) {
2772 ds
->dragx
= ui
->dragx
- TILESIZE
/2 - 2;
2773 ds
->dragy
= ui
->dragy
- TILESIZE
/2 - 2;
2774 blitter_save(dr
, ds
->bl
, ds
->dragx
, ds
->dragy
);
2775 draw_circle(dr
, ui
->dragx
, ui
->dragy
, TILESIZE
/2,
2776 (ui
->drag_colour
< 0 ? COL_BACKGROUND
:
2777 COL_0
+ ui
->drag_colour
), COL_GRID
);
2778 draw_update(dr
, ds
->dragx
, ds
->dragy
, TILESIZE
+ 3, TILESIZE
+ 3);
2779 ds
->drag_visible
= TRUE
;
2783 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
2784 int dir
, game_ui
*ui
)
2789 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
2790 int dir
, game_ui
*ui
)
2792 if (!oldstate
->completed
&& newstate
->completed
&&
2793 !oldstate
->cheated
&& !newstate
->cheated
) {
2794 if (flash_type
< 0) {
2795 char *env
= getenv("MAP_ALTERNATIVE_FLASH");
2797 flash_type
= atoi(env
);
2800 flash_length
= (flash_type
== 1 ?
0.50 : 0.30);
2802 return flash_length
;
2807 static int game_wants_statusbar(void)
2812 static int game_timing_state(game_state
*state
, game_ui
*ui
)
2817 static void game_print_size(game_params
*params
, float *x
, float *y
)
2822 * I'll use 4mm squares by default, I think. Simplest way to
2823 * compute this size is to compute the pixel puzzle size at a
2824 * given tile size and then scale.
2826 game_compute_size(params
, 400, &pw
, &ph
);
2831 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
2833 int w
= state
->p
.w
, h
= state
->p
.h
, wh
= w
*h
, n
= state
->p
.n
;
2834 int ink
, c
[FOUR
], i
;
2836 int *coords
, ncoords
, coordsize
;
2838 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2839 struct { int tilesize
; } ads
, *ds
= &ads
;
2840 ads
.tilesize
= tilesize
;
2842 ink
= print_mono_colour(dr
, 0);
2843 for (i
= 0; i
< FOUR
; i
++)
2844 c
[i
] = print_rgb_colour(dr
, map_hatching
[i
], map_colours
[i
][0],
2845 map_colours
[i
][1], map_colours
[i
][2]);
2850 print_line_width(dr
, TILESIZE
/ 16);
2853 * Draw a single filled polygon around each region.
2855 for (r
= 0; r
< n
; r
++) {
2856 int octants
[8], lastdir
, d1
, d2
, ox
, oy
;
2859 * Start by finding a point on the region boundary. Any
2860 * point will do. To do this, we'll search for a square
2861 * containing the region and then decide which corner of it
2865 for (y
= 0; y
< h
; y
++) {
2866 for (x
= 0; x
< w
; x
++) {
2867 if (state
->map
->map
[wh
*0+y
*w
+x
] == r
||
2868 state
->map
->map
[wh
*1+y
*w
+x
] == r
||
2869 state
->map
->map
[wh
*2+y
*w
+x
] == r
||
2870 state
->map
->map
[wh
*3+y
*w
+x
] == r
)
2876 assert(y
< h
&& x
< w
); /* we must have found one somewhere */
2878 * This is the first square in lexicographic order which
2879 * contains part of this region. Therefore, one of the top
2880 * two corners of the square must be what we're after. The
2881 * only case in which it isn't the top left one is if the
2882 * square is diagonally divided and the region is in the
2883 * bottom right half.
2885 if (state
->map
->map
[wh
*TE
+y
*w
+x
] != r
&&
2886 state
->map
->map
[wh
*LE
+y
*w
+x
] != r
)
2887 x
++; /* could just as well have done y++ */
2890 * Now we have a point on the region boundary. Trace around
2891 * the region until we come back to this point,
2892 * accumulating coordinates for a polygon draw operation as
2902 * There are eight possible directions we could head in
2903 * from here. We identify them by octant numbers, and
2904 * we also use octant numbers to identify the spaces
2917 octants
[0] = x
<w
&& y
>0 ? state
->map
->map
[wh
*LE
+(y
-1)*w
+x
] : -1;
2918 octants
[1] = x
<w
&& y
>0 ? state
->map
->map
[wh
*BE
+(y
-1)*w
+x
] : -1;
2919 octants
[2] = x
<w
&& y
<h ? state
->map
->map
[wh
*TE
+y
*w
+x
] : -1;
2920 octants
[3] = x
<w
&& y
<h ? state
->map
->map
[wh
*LE
+y
*w
+x
] : -1;
2921 octants
[4] = x
>0 && y
<h ? state
->map
->map
[wh
*RE
+y
*w
+(x
-1)] : -1;
2922 octants
[5] = x
>0 && y
<h ? state
->map
->map
[wh
*TE
+y
*w
+(x
-1)] : -1;
2923 octants
[6] = x
>0 && y
>0 ? state
->map
->map
[wh
*BE
+(y
-1)*w
+(x
-1)] :-1;
2924 octants
[7] = x
>0 && y
>0 ? state
->map
->map
[wh
*RE
+(y
-1)*w
+(x
-1)] :-1;
2927 for (i
= 0; i
< 8; i
++)
2928 if ((octants
[i
] == r
) ^ (octants
[(i
+1)%8] == r
)) {
2936 assert(d1
!= -1 && d2
!= -1);
2941 * Now we're heading in direction d1. Save the current
2944 if (ncoords
+ 2 > coordsize
) {
2946 coords
= sresize(coords
, coordsize
, int);
2948 coords
[ncoords
++] = COORD(x
);
2949 coords
[ncoords
++] = COORD(y
);
2952 * Compute the new coordinates.
2954 x
+= (d1
% 4 == 3 ?
0 : d1
< 4 ?
+1 : -1);
2955 y
+= (d1
% 4 == 1 ?
0 : d1
> 1 && d1
< 5 ?
+1 : -1);
2956 assert(x
>= 0 && x
<= w
&& y
>= 0 && y
<= h
);
2959 } while (x
!= ox
|| y
!= oy
);
2961 draw_polygon(dr
, coords
, ncoords
/2,
2962 state
->colouring
[r
] >= 0 ?
2963 c
[state
->colouring
[r
]] : -1, ink
);
2972 const struct game thegame
= {
2980 TRUE
, game_configure
, custom_params
,
2988 FALSE
, game_text_format
,
2996 20, game_compute_size
, game_set_size
,
2999 game_free_drawstate
,
3003 TRUE
, TRUE
, game_print_size
, game_print
,
3004 game_wants_statusbar
,
3005 FALSE
, game_timing_state
,
3006 0, /* mouse_priorities */
3009 #ifdef STANDALONE_SOLVER
3013 void frontend_default_colour(frontend
*fe
, float *output
) {}
3014 void draw_text(drawing
*dr
, int x
, int y
, int fonttype
, int fontsize
,
3015 int align
, int colour
, char *text
) {}
3016 void draw_rect(drawing
*dr
, int x
, int y
, int w
, int h
, int colour
) {}
3017 void draw_line(drawing
*dr
, int x1
, int y1
, int x2
, int y2
, int colour
) {}
3018 void draw_polygon(drawing
*dr
, int *coords
, int npoints
,
3019 int fillcolour
, int outlinecolour
) {}
3020 void draw_circle(drawing
*dr
, int cx
, int cy
, int radius
,
3021 int fillcolour
, int outlinecolour
) {}
3022 void clip(drawing
*dr
, int x
, int y
, int w
, int h
) {}
3023 void unclip(drawing
*dr
) {}
3024 void start_draw(drawing
*dr
) {}
3025 void draw_update(drawing
*dr
, int x
, int y
, int w
, int h
) {}
3026 void end_draw(drawing
*dr
) {}
3027 blitter
*blitter_new(drawing
*dr
, int w
, int h
) {return NULL
;}
3028 void blitter_free(drawing
*dr
, blitter
*bl
) {}
3029 void blitter_save(drawing
*dr
, blitter
*bl
, int x
, int y
) {}
3030 void blitter_load(drawing
*dr
, blitter
*bl
, int x
, int y
) {}
3031 int print_mono_colour(drawing
*dr
, int grey
) { return 0; }
3032 int print_rgb_colour(drawing
*dr
, int hatch
, float r
, float g
, float b
)
3034 void print_line_width(drawing
*dr
, int width
) {}
3036 void fatal(char *fmt
, ...)
3040 fprintf(stderr
, "fatal error: ");
3043 vfprintf(stderr
, fmt
, ap
);
3046 fprintf(stderr
, "\n");
3050 int main(int argc
, char **argv
)
3054 char *id
= NULL
, *desc
, *err
;
3056 int ret
, diff
, really_verbose
= FALSE
;
3057 struct solver_scratch
*sc
;
3060 while (--argc
> 0) {
3062 if (!strcmp(p
, "-v")) {
3063 really_verbose
= TRUE
;
3064 } else if (!strcmp(p
, "-g")) {
3066 } else if (*p
== '-') {
3067 fprintf(stderr
, "%s: unrecognised option `%s'\n", argv
[0], p
);
3075 fprintf(stderr
, "usage: %s [-g | -v] <game_id>\n", argv
[0]);
3079 desc
= strchr(id
, ':');
3081 fprintf(stderr
, "%s: game id expects a colon in it\n", argv
[0]);
3086 p
= default_params();
3087 decode_params(p
, id
);
3088 err
= validate_desc(p
, desc
);
3090 fprintf(stderr
, "%s: %s\n", argv
[0], err
);
3093 s
= new_game(NULL
, p
, desc
);
3095 sc
= new_scratch(s
->map
->graph
, s
->map
->n
, s
->map
->ngraph
);
3098 * When solving an Easy puzzle, we don't want to bother the
3099 * user with Hard-level deductions. For this reason, we grade
3100 * the puzzle internally before doing anything else.
3102 ret
= -1; /* placate optimiser */
3103 for (diff
= 0; diff
< DIFFCOUNT
; diff
++) {
3104 for (i
= 0; i
< s
->map
->n
; i
++)
3105 if (!s
->map
->immutable
[i
])
3106 s
->colouring
[i
] = -1;
3107 ret
= map_solver(sc
, s
->map
->graph
, s
->map
->n
, s
->map
->ngraph
,
3108 s
->colouring
, diff
);
3113 if (diff
== DIFFCOUNT
) {
3115 printf("Difficulty rating: harder than Hard, or ambiguous\n");
3117 printf("Unable to find a unique solution\n");
3121 printf("Difficulty rating: impossible (no solution exists)\n");
3123 printf("Difficulty rating: %s\n", map_diffnames
[diff
]);
3125 verbose
= really_verbose
;
3126 for (i
= 0; i
< s
->map
->n
; i
++)
3127 if (!s
->map
->immutable
[i
])
3128 s
->colouring
[i
] = -1;
3129 ret
= map_solver(sc
, s
->map
->graph
, s
->map
->n
, s
->map
->ngraph
,
3130 s
->colouring
, diff
);
3132 printf("Puzzle is inconsistent\n");
3136 for (i
= 0; i
< s
->map
->n
; i
++) {
3137 printf("%5d <- %c%c", i
, colnames
[s
->colouring
[i
]],
3138 (col
< 6 && i
+1 < s
->map
->n ?
' ' : '\n'));