« back to all changes in this revision
Viewing changes to map.c
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): Ben Hutchings
- Date: 2005-11-13 16:23:36 UTC
- Revision ID: james.westby@ubuntu.com-20051113162336-yxo6hm2m7md4pi6h
Tags: upstream-6452
Import upstream version 6452
- files added:
added
removed
map.c
1
/*
2
* map.c: Game involving four-colouring a map.
3
*/
4
5
/*
6
* TODO:
7
*
8
* - clue marking
9
* - better four-colouring algorithm?
10
*/
11
12
#include <stdio.h>
13
#include <stdlib.h>
14
#include <string.h>
15
#include <assert.h>
16
#include <ctype.h>
17
#include <math.h>
18
19
#include "puzzles.h"
20
21
/*
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
24
* true.
25
*/
26
#if defined STANDALONE_SOLVER
27
#define SOLVER_DIAGNOSTICS
28
int verbose = FALSE;
29
#elif defined SOLVER_DIAGNOSTICS
30
#define verbose TRUE
31
#endif
32
33
/*
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 :-)
37
*/
38
#define FOUR 4
39
#define THREE (FOUR-1)
40
#define FIVE (FOUR+1)
41
#define SIX (FOUR+2)
42
43
/*
44
* Ghastly run-time configuration option, just for Gareth (again).
45
*/
46
static int flash_type = -1;
47
static float flash_length;
48
49
/*
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.
52
*/
53
#define DIFFLIST(A) \
54
A(EASY,Easy,e) \
55
A(NORMAL,Normal,n) \
56
A(HARD,Hard,h) \
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)
66
67
enum { TE, BE, LE, RE }; /* top/bottom/left/right edges */
68
69
enum {
70
COL_BACKGROUND,
71
COL_GRID,
72
COL_0, COL_1, COL_2, COL_3,
73
COL_ERROR, COL_ERRTEXT,
74
NCOLOURS
75
};
76
77
struct game_params {
78
int w, h, n, diff;
79
};
80
81
struct map {
82
int refcount;
83
int *map;
84
int *graph;
85
int n;
86
int ngraph;
87
int *immutable;
88
int *edgex, *edgey; /* position of a point on each edge */
89
int *regionx, *regiony; /* position of a point in each region */
90
};
91
92
struct game_state {
93
game_params p;
94
struct map *map;
95
int *colouring, *pencil;
96
int completed, cheated;
97
};
98
99
static game_params *default_params(void)
100
{
101
game_params *ret = snew(game_params);
102
103
ret->w = 20;
104
ret->h = 15;
105
ret->n = 30;
106
ret->diff = DIFF_NORMAL;
107
108
return ret;
109
}
110
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},
118
};
119
120
static int game_fetch_preset(int i, char **name, game_params **params)
121
{
122
game_params *ret;
123
char str[80];
124
125
if (i < 0 || i >= lenof(map_presets))
126
return FALSE;
127
128
ret = snew(game_params);
129
*ret = map_presets[i];
130
131
sprintf(str, "%dx%d, %d regions, %s", ret->w, ret->h, ret->n,
132
map_diffnames[ret->diff]);
133
134
*name = dupstr(str);
135
*params = ret;
136
return TRUE;
137
}
138
139
static void free_params(game_params *params)
140
{
141
sfree(params);
142
}
143
144
static game_params *dup_params(game_params *params)
145
{
146
game_params *ret = snew(game_params);
147
*ret = *params; /* structure copy */
148
return ret;
149
}
150
151
static void decode_params(game_params *params, char const *string)
152
{
153
char const *p = string;
154
155
params->w = atoi(p);
156
while (*p && isdigit((unsigned char)*p)) p++;
157
if (*p == 'x') {
158
p++;
159
params->h = atoi(p);
160
while (*p && isdigit((unsigned char)*p)) p++;
161
} else {
162
params->h = params->w;
163
}
164
if (*p == 'n') {
165
p++;
166
params->n = atoi(p);
167
while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
168
} else {
169
params->n = params->w * params->h / 8;
170
}
171
if (*p == 'd') {
172
int i;
173
p++;
174
for (i = 0; i < DIFFCOUNT; i++)
175
if (*p == map_diffchars[i])
176
params->diff = i;
177
if (*p) p++;
178
}
179
}
180
181
static char *encode_params(game_params *params, int full)
182
{
183
char ret[400];
184
185
sprintf(ret, "%dx%dn%d", params->w, params->h, params->n);
186
if (full)
187
sprintf(ret + strlen(ret), "d%c", map_diffchars[params->diff]);
188
189
return dupstr(ret);
190
}
191
192
static config_item *game_configure(game_params *params)
193
{
194
config_item *ret;
195
char buf[80];
196
197
ret = snewn(5, config_item);
198
199
ret[0].name = "Width";
200
ret[0].type = C_STRING;
201
sprintf(buf, "%d", params->w);
202
ret[0].sval = dupstr(buf);
203
ret[0].ival = 0;
204
205
ret[1].name = "Height";
206
ret[1].type = C_STRING;
207
sprintf(buf, "%d", params->h);
208
ret[1].sval = dupstr(buf);
209
ret[1].ival = 0;
210
211
ret[2].name = "Regions";
212
ret[2].type = C_STRING;
213
sprintf(buf, "%d", params->n);
214
ret[2].sval = dupstr(buf);
215
ret[2].ival = 0;
216
217
ret[3].name = "Difficulty";
218
ret[3].type = C_CHOICES;
219
ret[3].sval = DIFFCONFIG;
220
ret[3].ival = params->diff;
221
222
ret[4].name = NULL;
223
ret[4].type = C_END;
224
ret[4].sval = NULL;
225
ret[4].ival = 0;
226
227
return ret;
228
}
229
230
static game_params *custom_params(config_item *cfg)
231
{
232
game_params *ret = snew(game_params);
233
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;
238
239
return ret;
240
}
241
242
static char *validate_params(game_params *params, int full)
243
{
244
if (params->w < 2 || params->h < 2)
245
return "Width and height must be at least two";
246
if (params->n < 5)
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";
250
return NULL;
251
}
252
253
/* ----------------------------------------------------------------------
254
* Cumulative frequency table functions.
255
*/
256
257
/*
258
* Initialise a cumulative frequency table. (Hardly worth writing
259
* this function; all it does is to initialise everything in the
260
* array to zero.)
261
*/
262
static void cf_init(int *table, int n)
263
{
264
int i;
265
266
for (i = 0; i < n; i++)
267
table[i] = 0;
268
}
269
270
/*
271
* Increment the count of symbol `sym' by `count'.
272
*/
273
static void cf_add(int *table, int n, int sym, int count)
274
{
275
int bit;
276
277
bit = 1;
278
while (sym != 0) {
279
if (sym & bit) {
280
table[sym] += count;
281
sym &= ~bit;
282
}
283
bit <<= 1;
284
}
285
286
table[0] += count;
287
}
288
289
/*
290
* Cumulative frequency lookup: return the total count of symbols
291
* with value less than `sym'.
292
*/
293
static int cf_clookup(int *table, int n, int sym)
294
{
295
int bit, index, limit, count;
296
297
if (sym == 0)
298
return 0;
299
300
assert(0 < sym && sym <= n);
301
302
count = table[0]; /* start with the whole table size */
303
304
bit = 1;
305
while (bit < n)
306
bit <<= 1;
307
308
limit = n;
309
310
while (bit > 0) {
311
/*
312
* Find the least number with its lowest set bit in this
313
* position which is greater than or equal to sym.
314
*/
315
index = ((sym + bit - 1) &~ (bit * 2 - 1)) + bit;
316
317
if (index < limit) {
318
count -= table[index];
319
limit = index;
320
}
321
322
bit >>= 1;
323
}
324
325
return count;
326
}
327
328
/*
329
* Single frequency lookup: return the count of symbol `sym'.
330
*/
331
static int cf_slookup(int *table, int n, int sym)
332
{
333
int count, bit;
334
335
assert(0 <= sym && sym < n);
336
337
count = table[sym];
338
339
for (bit = 1; sym+bit < n && !(sym & bit); bit <<= 1)
340
count -= table[sym+bit];
341
342
return count;
343
}
344
345
/*
346
* Return the largest symbol index such that the cumulative
347
* frequency up to that symbol is less than _or equal to_ count.
348
*/
349
static int cf_whichsym(int *table, int n, int count) {
350
int bit, sym, top;
351
352
assert(count >= 0 && count < table[0]);
353
354
bit = 1;
355
while (bit < n)
356
bit <<= 1;
357
358
sym = 0;
359
top = table[0];
360
361
while (bit > 0) {
362
if (sym+bit < n) {
363
if (count >= top - table[sym+bit])
364
sym += bit;
365
else
366
top -= table[sym+bit];
367
}
368
369
bit >>= 1;
370
}
371
372
return sym;
373
}
374
375
/* ----------------------------------------------------------------------
376
* Map generation.
377
*
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.
383
*/
384
385
#define WEIGHT_INCREASED 2 /* for increased perimeter */
386
#define WEIGHT_DECREASED 4 /* for decreased perimeter */
387
#define WEIGHT_UNCHANGED 3 /* for unchanged perimeter */
388
389
/*
390
* Look at a square and decide which colours can be extended into
391
* it.
392
*
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.
398
*
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.
403
*/
404
static int extend_options(int w, int h, int n, int *map,
405
int x, int y, int index)
406
{
407
int c, i, dx, dy;
408
int col[8];
409
int total = 0;
410
411
if (map[y*w+x] >= 0) {
412
assert(index < 0);
413
return 0; /* can't do this square at all */
414
}
415
416
/*
417
* Fetch the eight neighbours of this square, in order around
418
* the square.
419
*/
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)];
425
else
426
col[index] = -1;
427
}
428
429
/*
430
* Iterate over each colour that might be feasible.
431
*
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.
435
*/
436
437
for (c = 0; c < n; c++) {
438
int count, neighbours, runs;
439
440
/*
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.
445
*/
446
neighbours = 0;
447
for (i = 0; i < 8; i += 2)
448
if (col[i] == c)
449
neighbours++;
450
if (!neighbours)
451
continue;
452
453
/*
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.
457
*
458
* We determine this by looking around col to see if we can
459
* find more than one separate run of colour c.
460
*/
461
runs = 0;
462
for (i = 0; i < 8; i++)
463
if (col[i] == c && col[(i+1) & 7] != c)
464
runs++;
465
if (runs > 1)
466
continue;
467
468
assert(runs == 1);
469
470
/*
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
476
* done.
477
*/
478
assert(neighbours > 0 && neighbours < 4);
479
count = (neighbours == 1 ? WEIGHT_INCREASED :
480
neighbours == 2 ? WEIGHT_UNCHANGED : WEIGHT_DECREASED);
481
482
total += count;
483
if (index >= 0 && index < count)
484
return c;
485
else
486
index -= count;
487
}
488
489
assert(index < 0);
490
491
return total;
492
}
493
494
static void genmap(int w, int h, int n, int *map, random_state *rs)
495
{
496
int wh = w*h;
497
int x, y, i, k;
498
int *tmp;
499
500
assert(n <= wh);
501
tmp = snewn(wh, int);
502
503
/*
504
* Clear the map, and set up `tmp' as a list of grid indices.
505
*/
506
for (i = 0; i < wh; i++) {
507
map[i] = -1;
508
tmp[i] = i;
509
}
510
511
/*
512
* Place the region seeds by selecting n members from `tmp'.
513
*/
514
k = wh;
515
for (i = 0; i < n; i++) {
516
int j = random_upto(rs, k);
517
map[tmp[j]] = i;
518
tmp[j] = tmp[--k];
519
}
520
521
/*
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.
525
*/
526
cf_init(tmp, wh);
527
528
/*
529
* Go through the grid and set up the initial cumulative
530
* frequencies.
531
*/
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));
536
537
/*
538
* Now repeatedly choose a square we can extend a region into,
539
* and do so.
540
*/
541
while (tmp[0] > 0) {
542
int k = random_upto(rs, tmp[0]);
543
int sq;
544
int colour;
545
int xx, yy;
546
547
sq = cf_whichsym(tmp, wh, k);
548
k -= cf_clookup(tmp, wh, sq);
549
x = sq % w;
550
y = sq / w;
551
colour = extend_options(w, h, n, map, x, y, k);
552
553
map[sq] = colour;
554
555
/*
556
* Re-scan the nine cells around the one we've just
557
* modified.
558
*/
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));
564
}
565
}
566
567
/*
568
* Finally, go through and normalise the region labels into
569
* order, meaning that indistinguishable maps are actually
570
* identical.
571
*/
572
for (i = 0; i < n; i++)
573
tmp[i] = -1;
574
k = 0;
575
for (i = 0; i < wh; i++) {
576
assert(map[i] >= 0);
577
if (tmp[map[i]] < 0)
578
tmp[map[i]] = k++;
579
map[i] = tmp[map[i]];
580
}
581
582
sfree(tmp);
583
}
584
585
/* ----------------------------------------------------------------------
586
* Functions to handle graphs.
587
*/
588
589
/*
590
* Having got a map in a square grid, convert it into a graph
591
* representation.
592
*/
593
static int gengraph(int w, int h, int n, int *map, int *graph)
594
{
595
int i, j, x, y;
596
597
/*
598
* Start by setting the graph up as an adjacency matrix. We'll
599
* turn it into a list later.
600
*/
601
for (i = 0; i < n*n; i++)
602
graph[i] = 0;
603
604
/*
605
* Iterate over the map looking for all adjacencies.
606
*/
607
for (y = 0; y < h; y++)
608
for (x = 0; x < w; x++) {
609
int v, vx, vy;
610
v = map[y*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;
615
}
616
617
/*
618
* Turn the matrix into a list.
619
*/
620
for (i = j = 0; i < n*n; i++)
621
if (graph[i])
622
graph[j++] = i;
623
624
return j;
625
}
626
627
static int graph_edge_index(int *graph, int n, int ngraph, int i, int j)
628
{
629
int v = i*n+j;
630
int top, bot, mid;
631
632
bot = -1;
633
top = ngraph;
634
while (top - bot > 1) {
635
mid = (top + bot) / 2;
636
if (graph[mid] == v)
637
return mid;
638
else if (graph[mid] < v)
639
bot = mid;
640
else
641
top = mid;
642
}
643
return -1;
644
}
645
646
#define graph_adjacent(graph, n, ngraph, i, j) \
647
(graph_edge_index((graph), (n), (ngraph), (i), (j)) >= 0)
648
649
static int graph_vertex_start(int *graph, int n, int ngraph, int i)
650
{
651
int v = i*n;
652
int top, bot, mid;
653
654
bot = -1;
655
top = ngraph;
656
while (top - bot > 1) {
657
mid = (top + bot) / 2;
658
if (graph[mid] < v)
659
bot = mid;
660
else
661
top = mid;
662
}
663
return top;
664
}
665
666
/* ----------------------------------------------------------------------
667
* Generate a four-colouring of a graph.
668
*
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.
672
*/
673
674
static int fourcolour_recurse(int *graph, int n, int ngraph,
675
int *colouring, int *scratch, random_state *rs)
676
{
677
int nfree, nvert, start, i, j, k, c, ci;
678
int cs[FOUR];
679
680
/*
681
* Find the smallest number of free colours in any uncoloured
682
* vertex, and count the number of such vertices.
683
*/
684
685
nfree = FIVE; /* start off bigger than FOUR! */
686
nvert = 0;
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];
691
nvert = 0;
692
}
693
nvert++;
694
}
695
696
/*
697
* If there aren't any uncoloured vertices at all, we're done.
698
*/
699
if (nvert == 0)
700
return TRUE; /* we've got a colouring! */
701
702
/*
703
* Pick a random vertex in that set.
704
*/
705
j = random_upto(rs, nvert);
706
for (i = 0; i < n; i++)
707
if (colouring[i] < 0 && scratch[i*FIVE+FOUR] == nfree)
708
if (j-- == 0)
709
break;
710
assert(i < n);
711
start = graph_vertex_start(graph, n, ngraph, i);
712
713
/*
714
* Loop over the possible colours for i, and recurse for each
715
* one.
716
*/
717
ci = 0;
718
for (c = 0; c < FOUR; c++)
719
if (scratch[i*FIVE+c] == 0)
720
cs[ci++] = c;
721
shuffle(cs, ci, sizeof(*cs), rs);
722
723
while (ci-- > 0) {
724
c = cs[ci];
725
726
/*
727
* Fill in this colour.
728
*/
729
colouring[i] = c;
730
731
/*
732
* Update the scratch space to reflect a new neighbour
733
* of this colour for each neighbour of vertex i.
734
*/
735
for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
736
k = graph[j] - i*n;
737
if (scratch[k*FIVE+c] == 0)
738
scratch[k*FIVE+FOUR]--;
739
scratch[k*FIVE+c]++;
740
}
741
742
/*
743
* Recurse.
744
*/
745
if (fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs))
746
return TRUE; /* got one! */
747
748
/*
749
* If that didn't work, clean up and try again with a
750
* different colour.
751
*/
752
for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
753
k = graph[j] - i*n;
754
scratch[k*FIVE+c]--;
755
if (scratch[k*FIVE+c] == 0)
756
scratch[k*FIVE+FOUR]++;
757
}
758
colouring[i] = -1;
759
}
760
761
/*
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
767
* still fail.)
768
*/
769
return FALSE;
770
}
771
772
static void fourcolour(int *graph, int n, int ngraph, int *colouring,
773
random_state *rs)
774
{
775
int *scratch;
776
int i;
777
778
/*
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.
782
*/
783
scratch = snewn(n * FIVE, int);
784
for (i = 0; i < n * FIVE; i++)
785
scratch[i] = (i % FIVE == FOUR ? FOUR : 0);
786
787
/*
788
* Clear the colouring to start with.
789
*/
790
for (i = 0; i < n; i++)
791
colouring[i] = -1;
792
793
i = fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs);
794
assert(i); /* by the Four Colour Theorem :-) */
795
796
sfree(scratch);
797
}
798
799
/* ----------------------------------------------------------------------
800
* Non-recursive solver.
801
*/
802
803
struct solver_scratch {
804
unsigned char *possible; /* bitmap of colours for each region */
805
806
int *graph;
807
int n;
808
int ngraph;
809
810
int *bfsqueue;
811
int *bfscolour;
812
#ifdef SOLVER_DIAGNOSTICS
813
int *bfsprev;
814
#endif
815
816
int depth;
817
};
818
819
static struct solver_scratch *new_scratch(int *graph, int n, int ngraph)
820
{
821
struct solver_scratch *sc;
822
823
sc = snew(struct solver_scratch);
824
sc->graph = graph;
825
sc->n = n;
826
sc->ngraph = ngraph;
827
sc->possible = snewn(n, unsigned char);
828
sc->depth = 0;
829
sc->bfsqueue = snewn(n, int);
830
sc->bfscolour = snewn(n, int);
831
#ifdef SOLVER_DIAGNOSTICS
832
sc->bfsprev = snewn(n, int);
833
#endif
834
835
return sc;
836
}
837
838
static void free_scratch(struct solver_scratch *sc)
839
{
840
sfree(sc->possible);
841
sfree(sc->bfsqueue);
842
sfree(sc->bfscolour);
843
#ifdef SOLVER_DIAGNOSTICS
844
sfree(sc->bfsprev);
845
#endif
846
sfree(sc);
847
}
848
849
/*
850
* Count the bits in a word. Only needs to cope with FOUR bits.
851
*/
852
static int bitcount(int word)
853
{
854
assert(FOUR <= 4); /* or this needs changing */
855
word = ((word & 0xA) >> 1) + (word & 0x5);
856
word = ((word & 0xC) >> 2) + (word & 0x3);
857
return word;
858
}
859
860
#ifdef SOLVER_DIAGNOSTICS
861
static const char colnames[FOUR] = { 'R', 'Y', 'G', 'B' };
862
#endif
863
864
static int place_colour(struct solver_scratch *sc,
865
int *colouring, int index, int colour
866
#ifdef SOLVER_DIAGNOSTICS
867
, char *verb
868
#endif
869
)
870
{
871
int *graph = sc->graph, n = sc->n, ngraph = sc->ngraph;
872
int j, k;
873
874
if (!(sc->possible[index] & (1 << colour))) {
875
#ifdef SOLVER_DIAGNOSTICS
876
if (verbose)
877
printf("%*scannot place %c in region %d\n", 2*sc->depth, "",
878
colnames[colour], index);
879
#endif
880
return FALSE; /* can't do it */
881
}
882
883
sc->possible[index] = 1 << colour;
884
colouring[index] = colour;
885
886
#ifdef SOLVER_DIAGNOSTICS
887
if (verbose)
888
printf("%*s%s %c in region %d\n", 2*sc->depth, "",
889
verb, colnames[colour], index);
890
#endif
891
892
/*
893
* Rule out this colour from all the region's neighbours.
894
*/
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);
902
#endif
903
sc->possible[k] &= ~(1 << colour);
904
}
905
906
return TRUE;
907
}
908
909
#ifdef SOLVER_DIAGNOSTICS
910
static char *colourset(char *buf, int set)
911
{
912
int i;
913
char *p = buf;
914
char *sep = "";
915
916
for (i = 0; i < FOUR; i++)
917
if (set & (1 << i)) {
918
p += sprintf(p, "%s%c", sep, colnames[i]);
919
sep = ",";
920
}
921
922
return buf;
923
}
924
#endif
925
926
/*
927
* Returns 0 for impossible, 1 for success, 2 for failure to
928
* converge (i.e. puzzle is either ambiguous or just too
929
* difficult).
930
*/
931
static int map_solver(struct solver_scratch *sc,
932
int *graph, int n, int ngraph, int *colouring,
933
int difficulty)
934
{
935
int i;
936
937
if (sc->depth == 0) {
938
/*
939
* Initialise scratch space.
940
*/
941
for (i = 0; i < n; i++)
942
sc->possible[i] = (1 << FOUR) - 1;
943
944
/*
945
* Place clues.
946
*/
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
951
, "initial clue:"
952
#endif
953
)) {
954
#ifdef SOLVER_DIAGNOSTICS
955
if (verbose)
956
printf("%*sinitial clue set is inconsistent\n",
957
2*sc->depth, "");
958
#endif
959
return 0; /* the clues aren't even consistent! */
960
}
961
}
962
}
963
964
/*
965
* Now repeatedly loop until we find nothing further to do.
966
*/
967
while (1) {
968
int done_something = FALSE;
969
970
if (difficulty < DIFF_EASY)
971
break; /* can't do anything at all! */
972
973
/*
974
* Simplest possible deduction: find a region with only one
975
* possible colour.
976
*/
977
for (i = 0; i < n; i++) if (colouring[i] < 0) {
978
int p = sc->possible[i];
979
980
if (p == 0) {
981
#ifdef SOLVER_DIAGNOSTICS
982
if (verbose)
983
printf("%*sregion %d has no possible colours left\n",
984
2*sc->depth, "", i);
985
#endif
986
return 0; /* puzzle is inconsistent */
987
}
988
989
if ((p & (p-1)) == 0) { /* p is a power of two */
990
int c, ret;
991
for (c = 0; c < FOUR; c++)
992
if (p == (1 << c))
993
break;
994
assert(c < FOUR);
995
ret = place_colour(sc, colouring, i, c
996
#ifdef SOLVER_DIAGNOSTICS
997
, "placing"
998
#endif
999
);
1000
/*
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.
1007
*/
1008
assert(ret);
1009
done_something = TRUE;
1010
}
1011
}
1012
1013
if (done_something)
1014
continue;
1015
1016
if (difficulty < DIFF_NORMAL)
1017
break; /* can't do anything harder */
1018
1019
/*
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.
1025
*
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).
1029
*/
1030
for (i = 0; i < ngraph; i++) {
1031
int j1 = graph[i] / n, j2 = graph[i] % n;
1032
int j, k, v, v2;
1033
#ifdef SOLVER_DIAGNOSTICS
1034
int started = FALSE;
1035
#endif
1036
1037
if (j1 > j2)
1038
continue; /* done it already, other way round */
1039
1040
if (colouring[j1] >= 0 || colouring[j2] >= 0)
1041
continue; /* they're not undecided */
1042
1043
if (sc->possible[j1] != sc->possible[j2])
1044
continue; /* they don't have the same possibles */
1045
1046
v = sc->possible[j1];
1047
/*
1048
* See if v contains exactly two set bits.
1049
*/
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 */
1053
continue;
1054
1055
/*
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.
1062
*
1063
* Go through the neighbours of j1 and see if any are
1064
* shared with j2.
1065
*/
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
1072
if (verbose) {
1073
char buf[80];
1074
if (!started)
1075
printf("%*sadjacent regions %d,%d share colours"
1076
" %s\n", 2*sc->depth, "", j1, j2,
1077
colourset(buf, v));
1078
started = TRUE;
1079
printf("%*s ruling out %s in region %d\n",2*sc->depth,
1080
"", colourset(buf, sc->possible[k] & v), k);
1081
}
1082
#endif
1083
sc->possible[k] &= ~v;
1084
done_something = TRUE;
1085
}
1086
}
1087
}
1088
1089
if (done_something)
1090
continue;
1091
1092
if (difficulty < DIFF_HARD)
1093
break; /* can't do anything harder */
1094
1095
/*
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:
1099
*
1100
* (a) Each vertex on the path has precisely two possible
1101
* colours.
1102
*
1103
* (b) Each pair of vertices which are adjacent on the
1104
* path share at least one possible colour in common.
1105
*
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).
1109
*
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:
1114
*
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
1117
* take colour C.
1118
*
1119
* (d) The two end vertices are mutually adjacent to some
1120
* third vertex.
1121
*
1122
* (e) That third vertex currently has C as a possibility.
1123
*
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
1127
* vertex does not.
1128
*
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.
1132
*/
1133
for (i = 0; i < n; i++) {
1134
int c;
1135
1136
if (colouring[i] >= 0 || bitcount(sc->possible[i]) != 2)
1137
continue;
1138
1139
for (c = 0; c < FOUR; c++)
1140
if (sc->possible[i] & (1 << c)) {
1141
int j, k, gi, origc, currc, head, tail;
1142
/*
1143
* Try a bfs from this vertex, ruling out
1144
* colour c.
1145
*
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.
1150
*/
1151
1152
origc = 1 << c;
1153
1154
for (j = 0; j < n; j++) {
1155
sc->bfscolour[j] = -1;
1156
#ifdef SOLVER_DIAGNOSTICS
1157
sc->bfsprev[j] = -1;
1158
#endif
1159
}
1160
head = tail = 0;
1161
sc->bfsqueue[tail++] = i;
1162
sc->bfscolour[i] = sc->possible[i] &~ origc;
1163
1164
while (head < tail) {
1165
j = sc->bfsqueue[head++];
1166
currc = sc->bfscolour[j];
1167
1168
/*
1169
* Try neighbours of j.
1170
*/
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;
1174
1175
/*
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.
1181
*/
1182
1183
if (sc->bfscolour[k] < 0 &&
1184
colouring[k] < 0 &&
1185
bitcount(sc->possible[k]) == 2 &&
1186
(sc->possible[k] & currc)) {
1187
sc->bfsqueue[tail++] = k;
1188
sc->bfscolour[k] =
1189
sc->possible[k] &~ currc;
1190
#ifdef SOLVER_DIAGNOSTICS
1191
sc->bfsprev[k] = j;
1192
#endif
1193
}
1194
1195
/*
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.
1202
*/
1203
if (currc == origc &&
1204
graph_adjacent(graph, n, ngraph, k, i) &&
1205
(sc->possible[k] & currc)) {
1206
#ifdef SOLVER_DIAGNOSTICS
1207
if (verbose) {
1208
char buf[80], *sep = "";
1209
int r;
1210
1211
printf("%*sforcing chain, colour %s, ",
1212
2*sc->depth, "",
1213
colourset(buf, origc));
1214
for (r = j; r != -1; r = sc->bfsprev[r]) {
1215
printf("%s%d", sep, r);
1216
sep = "-";
1217
}
1218
printf("\n%*s ruling out %s in region"
1219
" %d\n", 2*sc->depth, "",
1220
colourset(buf, origc), k);
1221
}
1222
#endif
1223
sc->possible[k] &= ~origc;
1224
done_something = TRUE;
1225
}
1226
}
1227
}
1228
1229
assert(tail <= n);
1230
}
1231
}
1232
1233
if (!done_something)
1234
break;
1235
}
1236
1237
/*
1238
* See if we've got a complete solution, and return if so.
1239
*/
1240
for (i = 0; i < n; i++)
1241
if (colouring[i] < 0)
1242
break;
1243
if (i == n) {
1244
#ifdef SOLVER_DIAGNOSTICS
1245
if (verbose)
1246
printf("%*sone solution found\n", 2*sc->depth, "");
1247
#endif
1248
return 1; /* success! */
1249
}
1250
1251
/*
1252
* If recursion is not permissible, we now give up.
1253
*/
1254
if (difficulty < DIFF_RECURSE) {
1255
#ifdef SOLVER_DIAGNOSTICS
1256
if (verbose)
1257
printf("%*sunable to proceed further without recursion\n",
1258
2*sc->depth, "");
1259
#endif
1260
return 2; /* unable to complete */
1261
}
1262
1263
/*
1264
* Now we've got to do something recursive. So first hunt for a
1265
* currently-most-constrained region.
1266
*/
1267
{
1268
int best, bestc;
1269
struct solver_scratch *rsc;
1270
int *subcolouring, *origcolouring;
1271
int ret, subret;
1272
int we_already_got_one;
1273
1274
best = -1;
1275
bestc = FIVE;
1276
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) };
1280
int c;
1281
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 */
1286
1287
if (c < bestc) {
1288
best = i;
1289
bestc = c;
1290
}
1291
}
1292
1293
assert(best >= 0); /* or we'd be solved already */
1294
1295
#ifdef SOLVER_DIAGNOSTICS
1296
if (verbose)
1297
printf("%*srecursing on region %d\n", 2*sc->depth, "", best);
1298
#endif
1299
1300
/*
1301
* Now iterate over the possible colours for this region.
1302
*/
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;
1309
ret = 0;
1310
1311
for (i = 0; i < FOUR; i++) {
1312
if (!(sc->possible[best] & (1 << i)))
1313
continue;
1314
1315
memcpy(rsc->possible, sc->possible, n);
1316
memcpy(subcolouring, origcolouring, n * sizeof(int));
1317
1318
place_colour(rsc, subcolouring, best, i
1319
#ifdef SOLVER_DIAGNOSTICS
1320
, "trying"
1321
#endif
1322
);
1323
1324
subret = map_solver(rsc, graph, n, ngraph,
1325
subcolouring, difficulty);
1326
1327
#ifdef SOLVER_DIAGNOSTICS
1328
if (verbose) {
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");
1333
}
1334
#endif
1335
1336
/*
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.
1340
*/
1341
if (subret == 2 || (subret == 1 && we_already_got_one)) {
1342
ret = 2;
1343
break;
1344
}
1345
1346
/*
1347
* If this possibility turned up one valid solution and
1348
* it's the first we've seen, copy it into the output.
1349
*/
1350
if (subret == 1) {
1351
memcpy(colouring, subcolouring, n * sizeof(int));
1352
we_already_got_one = TRUE;
1353
ret = 1;
1354
}
1355
1356
/*
1357
* Otherwise, this guess led to a contradiction, so we
1358
* do nothing.
1359
*/
1360
}
1361
1362
sfree(subcolouring);
1363
free_scratch(rsc);
1364
1365
#ifdef SOLVER_DIAGNOSTICS
1366
if (verbose && sc->depth == 0) {
1367
printf("%*s%s found\n",
1368
2*sc->depth, "",
1369
ret == 0 ? "no solutions" :
1370
ret == 1 ? "one solution" : "multiple solutions");
1371
}
1372
#endif
1373
return ret;
1374
}
1375
}
1376
1377
/* ----------------------------------------------------------------------
1378
* Game generation main function.
1379
*/
1380
1381
static char *new_game_desc(game_params *params, random_state *rs,
1382
char **aux, int interactive)
1383
{
1384
struct solver_scratch *sc = NULL;
1385
int *map, *graph, ngraph, *colouring, *colouring2, *regions;
1386
int i, j, w, h, n, solveret, cfreq[FOUR];
1387
int wh;
1388
int mindiff, tries;
1389
#ifdef GENERATION_DIAGNOSTICS
1390
int x, y;
1391
#endif
1392
char *ret, buf[80];
1393
int retlen, retsize;
1394
1395
w = params->w;
1396
h = params->h;
1397
n = params->n;
1398
wh = w*h;
1399
1400
*aux = NULL;
1401
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);
1407
1408
/*
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.
1416
*/
1417
mindiff = params->diff;
1418
tries = 50;
1419
1420
while (1) {
1421
1422
/*
1423
* Create the map.
1424
*/
1425
genmap(w, h, n, map, rs);
1426
1427
#ifdef GENERATION_DIAGNOSTICS
1428
for (y = 0; y < h; y++) {
1429
for (x = 0; x < w; x++) {
1430
int v = map[y*w+x];
1431
if (v >= 62)
1432
putchar('!');
1433
else if (v >= 36)
1434
putchar('a' + v-36);
1435
else if (v >= 10)
1436
putchar('A' + v-10);
1437
else
1438
putchar('0' + v);
1439
}
1440
putchar('\n');
1441
}
1442
#endif
1443
1444
/*
1445
* Convert the map into a graph.
1446
*/
1447
ngraph = gengraph(w, h, n, map, graph);
1448
1449
#ifdef GENERATION_DIAGNOSTICS
1450
for (i = 0; i < ngraph; i++)
1451
printf("%d-%d\n", graph[i]/n, graph[i]%n);
1452
#endif
1453
1454
/*
1455
* Colour the map.
1456
*/
1457
fourcolour(graph, n, ngraph, colouring, rs);
1458
1459
#ifdef GENERATION_DIAGNOSTICS
1460
for (i = 0; i < n; i++)
1461
printf("%d: %d\n", i, colouring[i]);
1462
1463
for (y = 0; y < h; y++) {
1464
for (x = 0; x < w; x++) {
1465
int v = colouring[map[y*w+x]];
1466
if (v >= 36)
1467
putchar('a' + v-36);
1468
else if (v >= 10)
1469
putchar('A' + v-10);
1470
else
1471
putchar('0' + v);
1472
}
1473
putchar('\n');
1474
}
1475
#endif
1476
1477
/*
1478
* Encode the solution as an aux string.
1479
*/
1480
if (*aux) /* in case we've come round again */
1481
sfree(*aux);
1482
retlen = retsize = 0;
1483
ret = NULL;
1484
for (i = 0; i < n; i++) {
1485
int len;
1486
1487
if (colouring[i] < 0)
1488
continue;
1489
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);
1494
}
1495
strcpy(ret + retlen, buf);
1496
retlen += len;
1497
}
1498
*aux = ret;
1499
1500
/*
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.
1505
*/
1506
for (i = 0; i < FOUR; i++)
1507
cfreq[i] = 0;
1508
for (i = 0; i < n; i++) {
1509
regions[i] = i;
1510
cfreq[colouring[i]]++;
1511
}
1512
for (i = 0; i < FOUR; i++)
1513
if (cfreq[i] == 0)
1514
continue;
1515
1516
shuffle(regions, n, sizeof(*regions), rs);
1517
1518
if (sc) free_scratch(sc);
1519
sc = new_scratch(graph, n, ngraph);
1520
1521
for (i = 0; i < n; i++) {
1522
j = regions[i];
1523
1524
if (cfreq[colouring[j]] == 1)
1525
continue; /* can't remove last region of colour */
1526
1527
memcpy(colouring2, colouring, n*sizeof(int));
1528
colouring2[j] = -1;
1529
solveret = map_solver(sc, graph, n, ngraph, colouring2,
1530
params->diff);
1531
assert(solveret >= 0); /* mustn't be impossible! */
1532
if (solveret == 1) {
1533
cfreq[colouring[j]]--;
1534
colouring[j] = -1;
1535
}
1536
}
1537
1538
#ifdef GENERATION_DIAGNOSTICS
1539
for (i = 0; i < n; i++)
1540
if (colouring[i] >= 0) {
1541
if (i >= 62)
1542
putchar('!');
1543
else if (i >= 36)
1544
putchar('a' + i-36);
1545
else if (i >= 10)
1546
putchar('A' + i-10);
1547
else
1548
putchar('0' + i);
1549
printf(": %d\n", colouring[i]);
1550
}
1551
#endif
1552
1553
/*
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,
1558
* it's too easy!)
1559
*/
1560
memcpy(colouring2, colouring, n*sizeof(int));
1561
if (map_solver(sc, graph, n, ngraph, colouring2,
1562
mindiff - 1) == 1) {
1563
/*
1564
* Drop minimum difficulty if necessary.
1565
*/
1566
if (mindiff > 0 && (n < 9 || n > 2*wh/3)) {
1567
if (tries-- <= 0)
1568
mindiff = 0; /* give up and go for Easy */
1569
}
1570
continue;
1571
}
1572
1573
break;
1574
}
1575
1576
/*
1577
* Encode as a game ID. We do this by:
1578
*
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
1582
* non-edges
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).
1588
*/
1589
retlen = retsize = 0;
1590
ret = NULL;
1591
1592
{
1593
int run, pv;
1594
1595
/*
1596
* Start with a notional non-edge, so that there'll be an
1597
* explicit `a' to distinguish the case where we start with
1598
* an edge.
1599
*/
1600
run = 1;
1601
pv = 0;
1602
1603
for (i = 0; i < w*(h-1) + (w-1)*h; i++) {
1604
int x, y, dx, dy, v;
1605
1606
if (i < w*(h-1)) {
1607
/* Horizontal edge. */
1608
y = i / w;
1609
x = i % w;
1610
dx = 0;
1611
dy = 1;
1612
} else {
1613
/* Vertical edge. */
1614
x = (i - w*(h-1)) / h;
1615
y = (i - w*(h-1)) % h;
1616
dx = 1;
1617
dy = 0;
1618
}
1619
1620
if (retlen + 10 >= retsize) {
1621
retsize = retlen + 256;
1622
ret = sresize(ret, retsize, char);
1623
}
1624
1625
v = (map[y*w+x] != map[(y+dy)*w+(x+dx)]);
1626
1627
if (pv != v) {
1628
ret[retlen++] = 'a'-1 + run;
1629
run = 1;
1630
pv = v;
1631
} else {
1632
/*
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
1637
* more than 26.
1638
*/
1639
if (run == 25) {
1640
ret[retlen++] = 'z';
1641
run = 0;
1642
}
1643
run++;
1644
}
1645
}
1646
1647
ret[retlen++] = 'a'-1 + run;
1648
ret[retlen++] = ',';
1649
1650
run = 0;
1651
for (i = 0; i < n; i++) {
1652
if (retlen + 10 >= retsize) {
1653
retsize = retlen + 256;
1654
ret = sresize(ret, retsize, char);
1655
}
1656
1657
if (colouring[i] < 0) {
1658
/*
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.
1662
*/
1663
if (run == 26) {
1664
ret[retlen++] = 'z';
1665
run = 0;
1666
}
1667
run++;
1668
} else {
1669
if (run > 0)
1670
ret[retlen++] = 'a'-1 + run;
1671
ret[retlen++] = '0' + colouring[i];
1672
run = 0;
1673
}
1674
}
1675
if (run > 0)
1676
ret[retlen++] = 'a'-1 + run;
1677
ret[retlen] = '\0';
1678
1679
assert(retlen < retsize);
1680
}
1681
1682
free_scratch(sc);
1683
sfree(regions);
1684
sfree(colouring2);
1685
sfree(colouring);
1686
sfree(graph);
1687
sfree(map);
1688
1689
return ret;
1690
}
1691
1692
static char *parse_edge_list(game_params *params, char **desc, int *map)
1693
{
1694
int w = params->w, h = params->h, wh = w*h, n = params->n;
1695
int i, k, pos, state;
1696
char *p = *desc;
1697
1698
for (i = 0; i < wh; i++)
1699
map[wh+i] = i;
1700
1701
pos = -1;
1702
state = 0;
1703
1704
/*
1705
* Parse the game description to get the list of edges, and
1706
* build up a disjoint set forest as we go (by identifying
1707
* pairs of squares whenever the edge list shows a non-edge).
1708
*/
1709
while (*p && *p != ',') {
1710
if (*p < 'a' || *p > 'z')
1711
return "Unexpected character in edge list";
1712
if (*p == 'z')
1713
k = 25;
1714
else
1715
k = *p - 'a' + 1;
1716
while (k-- > 0) {
1717
int x, y, dx, dy;
1718
1719
if (pos < 0) {
1720
pos++;
1721
continue;
1722
} else if (pos < w*(h-1)) {
1723
/* Horizontal edge. */
1724
y = pos / w;
1725
x = pos % w;
1726
dx = 0;
1727
dy = 1;
1728
} else if (pos < 2*wh-w-h) {
1729
/* Vertical edge. */
1730
x = (pos - w*(h-1)) / h;
1731
y = (pos - w*(h-1)) % h;
1732
dx = 1;
1733
dy = 0;
1734
} else
1735
return "Too much data in edge list";
1736
if (!state)
1737
dsf_merge(map+wh, y*w+x, (y+dy)*w+(x+dx));
1738
1739
pos++;
1740
}
1741
if (*p != 'z')
1742
state = !state;
1743
p++;
1744
}
1745
assert(pos <= 2*wh-w-h);
1746
if (pos < 2*wh-w-h)
1747
return "Too little data in edge list";
1748
1749
/*
1750
* Now go through again and allocate region numbers.
1751
*/
1752
pos = 0;
1753
for (i = 0; i < wh; i++)
1754
map[i] = -1;
1755
for (i = 0; i < wh; i++) {
1756
k = dsf_canonify(map+wh, i);
1757
if (map[k] < 0)
1758
map[k] = pos++;
1759
map[i] = map[k];
1760
}
1761
if (pos != n)
1762
return "Edge list defines the wrong number of regions";
1763
1764
*desc = p;
1765
1766
return NULL;
1767
}
1768
1769
static char *validate_desc(game_params *params, char *desc)
1770
{
1771
int w = params->w, h = params->h, wh = w*h, n = params->n;
1772
int area;
1773
int *map;
1774
char *ret;
1775
1776
map = snewn(2*wh, int);
1777
ret = parse_edge_list(params, &desc, map);
1778
if (ret)
1779
return ret;
1780
sfree(map);
1781
1782
if (*desc != ',')
1783
return "Expected comma before clue list";
1784
desc++; /* eat comma */
1785
1786
area = 0;
1787
while (*desc) {
1788
if (*desc >= '0' && *desc < '0'+FOUR)
1789
area++;
1790
else if (*desc >= 'a' && *desc <= 'z')
1791
area += *desc - 'a' + 1;
1792
else
1793
return "Unexpected character in clue list";
1794
desc++;
1795
}
1796
if (area < n)
1797
return "Too little data in clue list";
1798
else if (area > n)
1799
return "Too much data in clue list";
1800
1801
return NULL;
1802
}
1803
1804
static game_state *new_game(midend *me, game_params *params, char *desc)
1805
{
1806
int w = params->w, h = params->h, wh = w*h, n = params->n;
1807
int i, pos;
1808
char *p;
1809
game_state *state = snew(game_state);
1810
1811
state->p = *params;
1812
state->colouring = snewn(n, int);
1813
for (i = 0; i < n; i++)
1814
state->colouring[i] = -1;
1815
state->pencil = snewn(n, int);
1816
for (i = 0; i < n; i++)
1817
state->pencil[i] = 0;
1818
1819
state->completed = state->cheated = FALSE;
1820
1821
state->map = snew(struct map);
1822
state->map->refcount = 1;
1823
state->map->map = snewn(wh*4, int);
1824
state->map->graph = snewn(n*n, int);
1825
state->map->n = n;
1826
state->map->immutable = snewn(n, int);
1827
for (i = 0; i < n; i++)
1828
state->map->immutable[i] = FALSE;
1829
1830
p = desc;
1831
1832
{
1833
char *ret;
1834
ret = parse_edge_list(params, &p, state->map->map);
1835
assert(!ret);
1836
}
1837
1838
/*
1839
* Set up the other three quadrants in `map'.
1840
*/
1841
for (i = wh; i < 4*wh; i++)
1842
state->map->map[i] = state->map->map[i % wh];
1843
1844
assert(*p == ',');
1845
p++;
1846
1847
/*
1848
* Now process the clue list.
1849
*/
1850
pos = 0;
1851
while (*p) {
1852
if (*p >= '0' && *p < '0'+FOUR) {
1853
state->colouring[pos] = *p - '0';
1854
state->map->immutable[pos] = TRUE;
1855
pos++;
1856
} else {
1857
assert(*p >= 'a' && *p <= 'z');
1858
pos += *p - 'a' + 1;
1859
}
1860
p++;
1861
}
1862
assert(pos == n);
1863
1864
state->map->ngraph = gengraph(w, h, n, state->map->map, state->map->graph);
1865
1866
/*
1867
* Attempt to smooth out some of the more jagged region
1868
* outlines by the judicious use of diagonally divided squares.
1869
*/
1870
{
1871
random_state *rs = random_new(desc, strlen(desc));
1872
int *squares = snewn(wh, int);
1873
int done_something;
1874
1875
for (i = 0; i < wh; i++)
1876
squares[i] = i;
1877
shuffle(squares, wh, sizeof(*squares), rs);
1878
1879
do {
1880
done_something = FALSE;
1881
for (i = 0; i < wh; i++) {
1882
int y = squares[i] / w, x = squares[i] % w;
1883
int c = state->map->map[y*w+x];
1884
int tc, bc, lc, rc;
1885
1886
if (x == 0 || x == w-1 || y == 0 || y == h-1)
1887
continue;
1888
1889
if (state->map->map[TE * wh + y*w+x] !=
1890
state->map->map[BE * wh + y*w+x])
1891
continue;
1892
1893
tc = state->map->map[BE * wh + (y-1)*w+x];
1894
bc = state->map->map[TE * wh + (y+1)*w+x];
1895
lc = state->map->map[RE * wh + y*w+(x-1)];
1896
rc = state->map->map[LE * wh + y*w+(x+1)];
1897
1898
/*
1899
* If this square is adjacent on two sides to one
1900
* region and on the other two sides to the other
1901
* region, and is itself one of the two regions, we can
1902
* adjust it so that it's a diagonal.
1903
*/
1904
if (tc != bc && (tc == c || bc == c)) {
1905
if ((lc == tc && rc == bc) ||
1906
(lc == bc && rc == tc)) {
1907
state->map->map[TE * wh + y*w+x] = tc;
1908
state->map->map[BE * wh + y*w+x] = bc;
1909
state->map->map[LE * wh + y*w+x] = lc;
1910
state->map->map[RE * wh + y*w+x] = rc;
1911
done_something = TRUE;
1912
}
1913
}
1914
}
1915
} while (done_something);
1916
sfree(squares);
1917
random_free(rs);
1918
}
1919
1920
/*
1921
* Analyse the map to find a canonical line segment
1922
* corresponding to each edge, and a canonical point
1923
* corresponding to each region. The former are where we'll
1924
* eventually put error markers; the latter are where we'll put
1925
* per-region flags such as numbers (when in diagnostic mode).
1926
*/
1927
{
1928
int *bestx, *besty, *an, pass;
1929
float *ax, *ay, *best;
1930
1931
ax = snewn(state->map->ngraph + n, float);
1932
ay = snewn(state->map->ngraph + n, float);
1933
an = snewn(state->map->ngraph + n, int);
1934
bestx = snewn(state->map->ngraph + n, int);
1935
besty = snewn(state->map->ngraph + n, int);
1936
best = snewn(state->map->ngraph + n, float);
1937
1938
for (i = 0; i < state->map->ngraph + n; i++) {
1939
bestx[i] = besty[i] = -1;
1940
best[i] = 2*(w+h)+1;
1941
ax[i] = ay[i] = 0.0F;
1942
an[i] = 0;
1943
}
1944
1945
/*
1946
* We make two passes over the map, finding all the line
1947
* segments separating regions and all the suitable points
1948
* within regions. In the first pass, we compute the
1949
* _average_ x and y coordinate of all the points in a
1950
* given class; in the second pass, for each such average
1951
* point, we find the candidate closest to it and call that
1952
* canonical.
1953
*
1954
* Line segments are considered to have coordinates in
1955
* their centre. Thus, at least one coordinate for any line
1956
* segment is always something-and-a-half; so we store our
1957
* coordinates as twice their normal value.
1958
*/
1959
for (pass = 0; pass < 2; pass++) {
1960
int x, y;
1961
1962
for (y = 0; y < h; y++)
1963
for (x = 0; x < w; x++) {
1964
int ex[4], ey[4], ea[4], eb[4], en = 0;
1965
1966
/*
1967
* Look for an edge to the right of this
1968
* square, an edge below it, and an edge in the
1969
* middle of it. Also look to see if the point
1970
* at the bottom right of this square is on an
1971
* edge (and isn't a place where more than two
1972
* regions meet).
1973
*/
1974
if (x+1 < w) {
1975
/* right edge */
1976
ea[en] = state->map->map[RE * wh + y*w+x];
1977
eb[en] = state->map->map[LE * wh + y*w+(x+1)];
1978
ex[en] = (x+1)*2;
1979
ey[en] = y*2+1;
1980
en++;
1981
}
1982
if (y+1 < h) {
1983
/* bottom edge */
1984
ea[en] = state->map->map[BE * wh + y*w+x];
1985
eb[en] = state->map->map[TE * wh + (y+1)*w+x];
1986
ex[en] = x*2+1;
1987
ey[en] = (y+1)*2;
1988
en++;
1989
}
1990
/* diagonal edge */
1991
ea[en] = state->map->map[TE * wh + y*w+x];
1992
eb[en] = state->map->map[BE * wh + y*w+x];
1993
ex[en] = x*2+1;
1994
ey[en] = y*2+1;
1995
en++;
1996
1997
if (x+1 < w && y+1 < h) {
1998
/* bottom right corner */
1999
int oct[8], othercol, nchanges;
2000
oct[0] = state->map->map[RE * wh + y*w+x];
2001
oct[1] = state->map->map[LE * wh + y*w+(x+1)];
2002
oct[2] = state->map->map[BE * wh + y*w+(x+1)];
2003
oct[3] = state->map->map[TE * wh + (y+1)*w+(x+1)];
2004
oct[4] = state->map->map[LE * wh + (y+1)*w+(x+1)];
2005
oct[5] = state->map->map[RE * wh + (y+1)*w+x];
2006
oct[6] = state->map->map[TE * wh + (y+1)*w+x];
2007
oct[7] = state->map->map[BE * wh + y*w+x];
2008
2009
othercol = -1;
2010
nchanges = 0;
2011
for (i = 0; i < 8; i++) {
2012
if (oct[i] != oct[0]) {
2013
if (othercol < 0)
2014
othercol = oct[i];
2015
else if (othercol != oct[i])
2016
break; /* three colours at this point */
2017
}
2018
if (oct[i] != oct[(i+1) & 7])
2019
nchanges++;
2020
}
2021
2022
/*
2023
* Now if there are exactly two regions at
2024
* this point (not one, and not three or
2025
* more), and only two changes around the
2026
* loop, then this is a valid place to put
2027
* an error marker.
2028
*/
2029
if (i == 8 && othercol >= 0 && nchanges == 2) {
2030
ea[en] = oct[0];
2031
eb[en] = othercol;
2032
ex[en] = (x+1)*2;
2033
ey[en] = (y+1)*2;
2034
en++;
2035
}
2036
2037
/*
2038
* If there's exactly _one_ region at this
2039
* point, on the other hand, it's a valid
2040
* place to put a region centre.
2041
*/
2042
if (othercol < 0) {
2043
ea[en] = eb[en] = oct[0];
2044
ex[en] = (x+1)*2;
2045
ey[en] = (y+1)*2;
2046
en++;
2047
}
2048
}
2049
2050
/*
2051
* Now process the points we've found, one by
2052
* one.
2053
*/
2054
for (i = 0; i < en; i++) {
2055
int emin = min(ea[i], eb[i]);
2056
int emax = max(ea[i], eb[i]);
2057
int gindex;
2058
2059
if (emin != emax) {
2060
/* Graph edge */
2061
gindex =
2062
graph_edge_index(state->map->graph, n,
2063
state->map->ngraph, emin,
2064
emax);
2065
} else {
2066
/* Region number */
2067
gindex = state->map->ngraph + emin;
2068
}
2069
2070
assert(gindex >= 0);
2071
2072
if (pass == 0) {
2073
/*
2074
* In pass 0, accumulate the values
2075
* we'll use to compute the average
2076
* positions.
2077
*/
2078
ax[gindex] += ex[i];
2079
ay[gindex] += ey[i];
2080
an[gindex] += 1.0F;
2081
} else {
2082
/*
2083
* In pass 1, work out whether this
2084
* point is closer to the average than
2085
* the last one we've seen.
2086
*/
2087
float dx, dy, d;
2088
2089
assert(an[gindex] > 0);
2090
dx = ex[i] - ax[gindex];
2091
dy = ey[i] - ay[gindex];
2092
d = sqrt(dx*dx + dy*dy);
2093
if (d < best[gindex]) {
2094
best[gindex] = d;
2095
bestx[gindex] = ex[i];
2096
besty[gindex] = ey[i];
2097
}
2098
}
2099
}
2100
}
2101
2102
if (pass == 0) {
2103
for (i = 0; i < state->map->ngraph + n; i++)
2104
if (an[i] > 0) {
2105
ax[i] /= an[i];
2106
ay[i] /= an[i];
2107
}
2108
}
2109
}
2110
2111
state->map->edgex = snewn(state->map->ngraph, int);
2112
state->map->edgey = snewn(state->map->ngraph, int);
2113
memcpy(state->map->edgex, bestx, state->map->ngraph * sizeof(int));
2114
memcpy(state->map->edgey, besty, state->map->ngraph * sizeof(int));
2115
2116
state->map->regionx = snewn(n, int);
2117
state->map->regiony = snewn(n, int);
2118
memcpy(state->map->regionx, bestx + state->map->ngraph, n*sizeof(int));
2119
memcpy(state->map->regiony, besty + state->map->ngraph, n*sizeof(int));
2120
2121
for (i = 0; i < state->map->ngraph; i++)
2122
if (state->map->edgex[i] < 0) {
2123
/* Find the other representation of this edge. */
2124
int e = state->map->graph[i];
2125
int iprime = graph_edge_index(state->map->graph, n,
2126
state->map->ngraph, e%n, e/n);
2127
assert(state->map->edgex[iprime] >= 0);
2128
state->map->edgex[i] = state->map->edgex[iprime];
2129
state->map->edgey[i] = state->map->edgey[iprime];
2130
}
2131
2132
sfree(ax);
2133
sfree(ay);
2134
sfree(an);
2135
sfree(best);
2136
sfree(bestx);
2137
sfree(besty);
2138
}
2139
2140
return state;
2141
}
2142
2143
static game_state *dup_game(game_state *state)
2144
{
2145
game_state *ret = snew(game_state);
2146
2147
ret->p = state->p;
2148
ret->colouring = snewn(state->p.n, int);
2149
memcpy(ret->colouring, state->colouring, state->p.n * sizeof(int));
2150
ret->pencil = snewn(state->p.n, int);
2151
memcpy(ret->pencil, state->pencil, state->p.n * sizeof(int));
2152
ret->map = state->map;
2153
ret->map->refcount++;
2154
ret->completed = state->completed;
2155
ret->cheated = state->cheated;
2156
2157
return ret;
2158
}
2159
2160
static void free_game(game_state *state)
2161
{
2162
if (--state->map->refcount <= 0) {
2163
sfree(state->map->map);
2164
sfree(state->map->graph);
2165
sfree(state->map->immutable);
2166
sfree(state->map->edgex);
2167
sfree(state->map->edgey);
2168
sfree(state->map->regionx);
2169
sfree(state->map->regiony);
2170
sfree(state->map);
2171
}
2172
sfree(state->pencil);
2173
sfree(state->colouring);
2174
sfree(state);
2175
}
2176
2177
static char *solve_game(game_state *state, game_state *currstate,
2178
char *aux, char **error)
2179
{
2180
if (!aux) {
2181
/*
2182
* Use the solver.
2183
*/
2184
int *colouring;
2185
struct solver_scratch *sc;
2186
int sret;
2187
int i;
2188
char *ret, buf[80];
2189
int retlen, retsize;
2190
2191
colouring = snewn(state->map->n, int);
2192
memcpy(colouring, state->colouring, state->map->n * sizeof(int));
2193
2194
sc = new_scratch(state->map->graph, state->map->n, state->map->ngraph);
2195
sret = map_solver(sc, state->map->graph, state->map->n,
2196
state->map->ngraph, colouring, DIFFCOUNT-1);
2197
free_scratch(sc);
2198
2199
if (sret != 1) {
2200
sfree(colouring);
2201
if (sret == 0)
2202
*error = "Puzzle is inconsistent";
2203
else
2204
*error = "Unable to find a unique solution for this puzzle";
2205
return NULL;
2206
}
2207
2208
retsize = 64;
2209
ret = snewn(retsize, char);
2210
strcpy(ret, "S");
2211
retlen = 1;
2212
2213
for (i = 0; i < state->map->n; i++) {
2214
int len;
2215
2216
assert(colouring[i] >= 0);
2217
if (colouring[i] == currstate->colouring[i])
2218
continue;
2219
assert(!state->map->immutable[i]);
2220
2221
len = sprintf(buf, ";%d:%d", colouring[i], i);
2222
if (retlen + len >= retsize) {
2223
retsize = retlen + len + 256;
2224
ret = sresize(ret, retsize, char);
2225
}
2226
strcpy(ret + retlen, buf);
2227
retlen += len;
2228
}
2229
2230
sfree(colouring);
2231
2232
return ret;
2233
}
2234
return dupstr(aux);
2235
}
2236
2237
static char *game_text_format(game_state *state)
2238
{
2239
return NULL;
2240
}
2241
2242
struct game_ui {
2243
/*
2244
* drag_colour:
2245
*
2246
* - -2 means no drag currently active.
2247
* - >=0 means we're dragging a solid colour.
2248
* - -1 means we're dragging a blank space, and drag_pencil
2249
* might or might not add some pencil-mark stipples to that.
2250
*/
2251
int drag_colour;
2252
int drag_pencil;
2253
int dragx, dragy;
2254
int show_numbers;
2255
};
2256
2257
static game_ui *new_ui(game_state *state)
2258
{
2259
game_ui *ui = snew(game_ui);
2260
ui->dragx = ui->dragy = -1;
2261
ui->drag_colour = -2;
2262
ui->show_numbers = FALSE;
2263
return ui;
2264
}
2265
2266
static void free_ui(game_ui *ui)
2267
{
2268
sfree(ui);
2269
}
2270
2271
static char *encode_ui(game_ui *ui)
2272
{
2273
return NULL;
2274
}
2275
2276
static void decode_ui(game_ui *ui, char *encoding)
2277
{
2278
}
2279
2280
static void game_changed_state(game_ui *ui, game_state *oldstate,
2281
game_state *newstate)
2282
{
2283
}
2284
2285
struct game_drawstate {
2286
int tilesize;
2287
unsigned long *drawn, *todraw;
2288
int started;
2289
int dragx, dragy, drag_visible;
2290
blitter *bl;
2291
};
2292
2293
/* Flags in `drawn'. */
2294
#define ERR_BASE 0x00800000L
2295
#define ERR_MASK 0xFF800000L
2296
#define PENCIL_T_BASE 0x00080000L
2297
#define PENCIL_T_MASK 0x00780000L
2298
#define PENCIL_B_BASE 0x00008000L
2299
#define PENCIL_B_MASK 0x00078000L
2300
#define PENCIL_MASK 0x007F8000L
2301
#define SHOW_NUMBERS 0x00004000L
2302
2303
#define TILESIZE (ds->tilesize)
2304
#define BORDER (TILESIZE)
2305
#define COORD(x) ( (x) * TILESIZE + BORDER )
2306
#define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
2307
2308
static int region_from_coords(game_state *state, game_drawstate *ds,
2309
int x, int y)
2310
{
2311
int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */;
2312
int tx = FROMCOORD(x), ty = FROMCOORD(y);
2313
int dx = x - COORD(tx), dy = y - COORD(ty);
2314
int quadrant;
2315
2316
if (tx < 0 || tx >= w || ty < 0 || ty >= h)
2317
return -1; /* border */
2318
2319
quadrant = 2 * (dx > dy) + (TILESIZE - dx > dy);
2320
quadrant = (quadrant == 0 ? BE :
2321
quadrant == 1 ? LE :
2322
quadrant == 2 ? RE : TE);
2323
2324
return state->map->map[quadrant * wh + ty*w+tx];
2325
}
2326
2327
static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
2328
int x, int y, int button)
2329
{
2330
char *bufp, buf[256];
2331
2332
/*
2333
* Enable or disable numeric labels on regions.
2334
*/
2335
if (button == 'l' || button == 'L') {
2336
ui->show_numbers = !ui->show_numbers;
2337
return "";
2338
}
2339
2340
if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
2341
int r = region_from_coords(state, ds, x, y);
2342
2343
if (r >= 0) {
2344
ui->drag_colour = state->colouring[r];
2345
ui->drag_pencil = state->pencil[r];
2346
if (ui->drag_colour >= 0)
2347
ui->drag_pencil = 0; /* should be already, but double-check */
2348
} else {
2349
ui->drag_colour = -1;
2350
ui->drag_pencil = 0;
2351
}
2352
ui->dragx = x;
2353
ui->dragy = y;
2354
return "";
2355
}
2356
2357
if ((button == LEFT_DRAG || button == RIGHT_DRAG) &&
2358
ui->drag_colour > -2) {
2359
ui->dragx = x;
2360
ui->dragy = y;
2361
return "";
2362
}
2363
2364
if ((button == LEFT_RELEASE || button == RIGHT_RELEASE) &&
2365
ui->drag_colour > -2) {
2366
int r = region_from_coords(state, ds, x, y);
2367
int c = ui->drag_colour;
2368
int p = ui->drag_pencil;
2369
int oldp;
2370
2371
/*
2372
* Cancel the drag, whatever happens.
2373
*/
2374
ui->drag_colour = -2;
2375
ui->dragx = ui->dragy = -1;
2376
2377
if (r < 0)
2378
return ""; /* drag into border; do nothing else */
2379
2380
if (state->map->immutable[r])
2381
return ""; /* can't change this region */
2382
2383
if (state->colouring[r] == c && state->pencil[r] == p)
2384
return ""; /* don't _need_ to change this region */
2385
2386
if (button == RIGHT_RELEASE) {
2387
if (state->colouring[r] >= 0) {
2388
/* Can't pencil on a coloured region */
2389
return "";
2390
} else if (c >= 0) {
2391
/* Right-dragging from colour to blank toggles one pencil */
2392
p = state->pencil[r] ^ (1 << c);
2393
c = -1;
2394
}
2395
/* Otherwise, right-dragging from blank to blank is equivalent
2396
* to left-dragging. */
2397
}
2398
2399
bufp = buf;
2400
oldp = state->pencil[r];
2401
if (c != state->colouring[r]) {
2402
bufp += sprintf(bufp, ";%c:%d", (int)(c < 0 ? 'C' : '0' + c), r);
2403
if (c >= 0)
2404
oldp = 0;
2405
}
2406
if (p != oldp) {
2407
int i;
2408
for (i = 0; i < FOUR; i++)
2409
if ((oldp ^ p) & (1 << i))
2410
bufp += sprintf(bufp, ";p%c:%d", (int)('0' + i), r);
2411
}
2412
2413
return dupstr(buf+1); /* ignore first semicolon */
2414
}
2415
2416
return NULL;
2417
}
2418
2419
static game_state *execute_move(game_state *state, char *move)
2420
{
2421
int n = state->p.n;
2422
game_state *ret = dup_game(state);
2423
int c, k, adv, i;
2424
2425
while (*move) {
2426
int pencil = FALSE;
2427
2428
c = *move;
2429
if (c == 'p') {
2430
pencil = TRUE;
2431
c = *++move;
2432
}
2433
if ((c == 'C' || (c >= '0' && c < '0'+FOUR)) &&
2434
sscanf(move+1, ":%d%n", &k, &adv) == 1 &&
2435
k >= 0 && k < state->p.n) {
2436
move += 1 + adv;
2437
if (pencil) {
2438
if (ret->colouring[k] >= 0) {
2439
free_game(ret);
2440
return NULL;
2441
}
2442
if (c == 'C')
2443
ret->pencil[k] = 0;
2444
else
2445
ret->pencil[k] ^= 1 << (c - '0');
2446
} else {
2447
ret->colouring[k] = (c == 'C' ? -1 : c - '0');
2448
ret->pencil[k] = 0;
2449
}
2450
} else if (*move == 'S') {
2451
move++;
2452
ret->cheated = TRUE;
2453
} else {
2454
free_game(ret);
2455
return NULL;
2456
}
2457
2458
if (*move && *move != ';') {
2459
free_game(ret);
2460
return NULL;
2461
}
2462
if (*move)
2463
move++;
2464
}
2465
2466
/*
2467
* Check for completion.
2468
*/
2469
if (!ret->completed) {
2470
int ok = TRUE;
2471
2472
for (i = 0; i < n; i++)
2473
if (ret->colouring[i] < 0) {
2474
ok = FALSE;
2475
break;
2476
}
2477
2478
if (ok) {
2479
for (i = 0; i < ret->map->ngraph; i++) {
2480
int j = ret->map->graph[i] / n;
2481
int k = ret->map->graph[i] % n;
2482
if (ret->colouring[j] == ret->colouring[k]) {
2483
ok = FALSE;
2484
break;
2485
}
2486
}
2487
}
2488
2489
if (ok)
2490
ret->completed = TRUE;
2491
}
2492
2493
return ret;
2494
}
2495
2496
/* ----------------------------------------------------------------------
2497
* Drawing routines.
2498
*/
2499
2500
static void game_compute_size(game_params *params, int tilesize,
2501
int *x, int *y)
2502
{
2503
/* Ick: fake up `ds->tilesize' for macro expansion purposes */
2504
struct { int tilesize; } ads, *ds = &ads;
2505
ads.tilesize = tilesize;
2506
2507
*x = params->w * TILESIZE + 2 * BORDER + 1;
2508
*y = params->h * TILESIZE + 2 * BORDER + 1;
2509
}
2510
2511
static void game_set_size(drawing *dr, game_drawstate *ds,
2512
game_params *params, int tilesize)
2513
{
2514
ds->tilesize = tilesize;
2515
2516
assert(!ds->bl); /* set_size is never called twice */
2517
ds->bl = blitter_new(dr, TILESIZE+3, TILESIZE+3);
2518
}
2519
2520
const float map_colours[FOUR][3] = {
2521
{0.7F, 0.5F, 0.4F},
2522
{0.8F, 0.7F, 0.4F},
2523
{0.5F, 0.6F, 0.4F},
2524
{0.55F, 0.45F, 0.35F},
2525
};
2526
const int map_hatching[FOUR] = {
2527
HATCH_VERT, HATCH_SLASH, HATCH_HORIZ, HATCH_BACKSLASH
2528
};
2529
2530
static float *game_colours(frontend *fe, int *ncolours)
2531
{
2532
float *ret = snewn(3 * NCOLOURS, float);
2533
2534
frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
2535
2536
ret[COL_GRID * 3 + 0] = 0.0F;
2537
ret[COL_GRID * 3 + 1] = 0.0F;
2538
ret[COL_GRID * 3 + 2] = 0.0F;
2539
2540
memcpy(ret + COL_0 * 3, map_colours[0], 3 * sizeof(float));
2541
memcpy(ret + COL_1 * 3, map_colours[1], 3 * sizeof(float));
2542
memcpy(ret + COL_2 * 3, map_colours[2], 3 * sizeof(float));
2543
memcpy(ret + COL_3 * 3, map_colours[3], 3 * sizeof(float));
2544
2545
ret[COL_ERROR * 3 + 0] = 1.0F;
2546
ret[COL_ERROR * 3 + 1] = 0.0F;
2547
ret[COL_ERROR * 3 + 2] = 0.0F;
2548
2549
ret[COL_ERRTEXT * 3 + 0] = 1.0F;
2550
ret[COL_ERRTEXT * 3 + 1] = 1.0F;
2551
ret[COL_ERRTEXT * 3 + 2] = 1.0F;
2552
2553
*ncolours = NCOLOURS;
2554
return ret;
2555
}
2556
2557
static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
2558
{
2559
struct game_drawstate *ds = snew(struct game_drawstate);
2560
int i;
2561
2562
ds->tilesize = 0;
2563
ds->drawn = snewn(state->p.w * state->p.h, unsigned long);
2564
for (i = 0; i < state->p.w * state->p.h; i++)
2565
ds->drawn[i] = 0xFFFFL;
2566
ds->todraw = snewn(state->p.w * state->p.h, unsigned long);
2567
ds->started = FALSE;
2568
ds->bl = NULL;
2569
ds->drag_visible = FALSE;
2570
ds->dragx = ds->dragy = -1;
2571
2572
return ds;
2573
}
2574
2575
static void game_free_drawstate(drawing *dr, game_drawstate *ds)
2576
{
2577
sfree(ds->drawn);
2578
sfree(ds->todraw);
2579
if (ds->bl)
2580
blitter_free(dr, ds->bl);
2581
sfree(ds);
2582
}
2583
2584
static void draw_error(drawing *dr, game_drawstate *ds, int x, int y)
2585
{
2586
int coords[8];
2587
int yext, xext;
2588
2589
/*
2590
* Draw a diamond.
2591
*/
2592
coords[0] = x - TILESIZE*2/5;
2593
coords[1] = y;
2594
coords[2] = x;
2595
coords[3] = y - TILESIZE*2/5;
2596
coords[4] = x + TILESIZE*2/5;
2597
coords[5] = y;
2598
coords[6] = x;
2599
coords[7] = y + TILESIZE*2/5;
2600
draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID);
2601
2602
/*
2603
* Draw an exclamation mark in the diamond. This turns out to
2604
* look unpleasantly off-centre if done via draw_text, so I do
2605
* it by hand on the basis that exclamation marks aren't that
2606
* difficult to draw...
2607
*/
2608
xext = TILESIZE/16;
2609
yext = TILESIZE*2/5 - (xext*2+2);
2610
draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3),
2611
COL_ERRTEXT);
2612
draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT);
2613
}
2614
2615
static void draw_square(drawing *dr, game_drawstate *ds,
2616
game_params *params, struct map *map,
2617
int x, int y, unsigned long v)
2618
{
2619
int w = params->w, h = params->h, wh = w*h;
2620
int tv, bv, xo, yo, i, j, oldj;
2621
unsigned long errs, pencil, show_numbers;
2622
2623
errs = v & ERR_MASK;
2624
v &= ~ERR_MASK;
2625
pencil = v & PENCIL_MASK;
2626
v &= ~PENCIL_MASK;
2627
show_numbers = v & SHOW_NUMBERS;
2628
v &= ~SHOW_NUMBERS;
2629
tv = v / FIVE;
2630
bv = v % FIVE;
2631
2632
clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
2633
2634
/*
2635
* Draw the region colour.
2636
*/
2637
draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE,
2638
(tv == FOUR ? COL_BACKGROUND : COL_0 + tv));
2639
/*
2640
* Draw the second region colour, if this is a diagonally
2641
* divided square.
2642
*/
2643
if (map->map[TE * wh + y*w+x] != map->map[BE * wh + y*w+x]) {
2644
int coords[6];
2645
coords[0] = COORD(x)-1;
2646
coords[1] = COORD(y+1)+1;
2647
if (map->map[LE * wh + y*w+x] == map->map[TE * wh + y*w+x])
2648
coords[2] = COORD(x+1)+1;
2649
else
2650
coords[2] = COORD(x)-1;
2651
coords[3] = COORD(y)-1;
2652
coords[4] = COORD(x+1)+1;
2653
coords[5] = COORD(y+1)+1;
2654
draw_polygon(dr, coords, 3,
2655
(bv == FOUR ? COL_BACKGROUND : COL_0 + bv), COL_GRID);
2656
}
2657
2658
/*
2659
* Draw `pencil marks'. Currently we arrange these in a square
2660
* formation, which means we may be in trouble if the value of
2661
* FOUR changes later...
2662
*/
2663
assert(FOUR == 4);
2664
for (yo = 0; yo < 4; yo++)
2665
for (xo = 0; xo < 4; xo++) {
2666
int te = map->map[TE * wh + y*w+x];
2667
int e, ee, c;
2668
2669
e = (yo < xo && yo < 3-xo ? TE :
2670
yo > xo && yo > 3-xo ? BE :
2671
xo < 2 ? LE : RE);
2672
ee = map->map[e * wh + y*w+x];
2673
2674
if (xo != (yo * 2 + 1) % 5)
2675
continue;
2676
c = yo;
2677
2678
if (!(pencil & ((ee == te ? PENCIL_T_BASE : PENCIL_B_BASE) << c)))
2679
continue;
2680
2681
if (yo == xo &&
2682
(map->map[TE * wh + y*w+x] != map->map[LE * wh + y*w+x]))
2683
continue; /* avoid TL-BR diagonal line */
2684
if (yo == 3-xo &&
2685
(map->map[TE * wh + y*w+x] != map->map[RE * wh + y*w+x]))
2686
continue; /* avoid BL-TR diagonal line */
2687
2688
draw_circle(dr, COORD(x) + (xo+1)*TILESIZE/5,
2689
COORD(y) + (yo+1)*TILESIZE/5,
2690
TILESIZE/7, COL_0 + c, COL_0 + c);
2691
}
2692
2693
/*
2694
* Draw the grid lines, if required.
2695
*/
2696
if (x <= 0 || map->map[RE*wh+y*w+(x-1)] != map->map[LE*wh+y*w+x])
2697
draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE, COL_GRID);
2698
if (y <= 0 || map->map[BE*wh+(y-1)*w+x] != map->map[TE*wh+y*w+x])
2699
draw_rect(dr, COORD(x), COORD(y), TILESIZE, 1, COL_GRID);
2700
if (x <= 0 || y <= 0 ||
2701
map->map[RE*wh+(y-1)*w+(x-1)] != map->map[TE*wh+y*w+x] ||
2702
map->map[BE*wh+(y-1)*w+(x-1)] != map->map[LE*wh+y*w+x])
2703
draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID);
2704
2705
/*
2706
* Draw error markers.
2707
*/
2708
for (yo = 0; yo < 3; yo++)
2709
for (xo = 0; xo < 3; xo++)
2710
if (errs & (ERR_BASE << (yo*3+xo)))
2711
draw_error(dr, ds,
2712
(COORD(x)*2+TILESIZE*xo)/2,
2713
(COORD(y)*2+TILESIZE*yo)/2);
2714
2715
/*
2716
* Draw region numbers, if desired.
2717
*/
2718
if (show_numbers) {
2719
oldj = -1;
2720
for (i = 0; i < 2; i++) {
2721
j = map->map[(i?BE:TE)*wh+y*w+x];
2722
if (oldj == j)
2723
continue;
2724
oldj = j;
2725
2726
xo = map->regionx[j] - 2*x;
2727
yo = map->regiony[j] - 2*y;
2728
if (xo >= 0 && xo <= 2 && yo >= 0 && yo <= 2) {
2729
char buf[80];
2730
sprintf(buf, "%d", j);
2731
draw_text(dr, (COORD(x)*2+TILESIZE*xo)/2,
2732
(COORD(y)*2+TILESIZE*yo)/2,
2733
FONT_VARIABLE, 3*TILESIZE/5,
2734
ALIGN_HCENTRE|ALIGN_VCENTRE,
2735
COL_GRID, buf);
2736
}
2737
}
2738
}
2739
2740
unclip(dr);
2741
2742
draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
2743
}
2744
2745
static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
2746
game_state *state, int dir, game_ui *ui,
2747
float animtime, float flashtime)
2748
{
2749
int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
2750
int x, y, i;
2751
int flash;
2752
2753
if (ds->drag_visible) {
2754
blitter_load(dr, ds->bl, ds->dragx, ds->dragy);
2755
draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
2756
ds->drag_visible = FALSE;
2757
}
2758
2759
/*
2760
* The initial contents of the window are not guaranteed and
2761
* can vary with front ends. To be on the safe side, all games
2762
* should start by drawing a big background-colour rectangle
2763
* covering the whole window.
2764
*/
2765
if (!ds->started) {
2766
int ww, wh;
2767
2768
game_compute_size(&state->p, TILESIZE, &ww, &wh);
2769
draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND);
2770
draw_rect(dr, COORD(0), COORD(0), w*TILESIZE+1, h*TILESIZE+1,
2771
COL_GRID);
2772
2773
draw_update(dr, 0, 0, ww, wh);
2774
ds->started = TRUE;
2775
}
2776
2777
if (flashtime) {
2778
if (flash_type == 1)
2779
flash = (int)(flashtime * FOUR / flash_length);
2780
else
2781
flash = 1 + (int)(flashtime * THREE / flash_length);
2782
} else
2783
flash = -1;
2784
2785
/*
2786
* Set up the `todraw' array.
2787
*/
2788
for (y = 0; y < h; y++)
2789
for (x = 0; x < w; x++) {
2790
int tv = state->colouring[state->map->map[TE * wh + y*w+x]];
2791
int bv = state->colouring[state->map->map[BE * wh + y*w+x]];
2792
unsigned long v;
2793
2794
if (tv < 0)
2795
tv = FOUR;
2796
if (bv < 0)
2797
bv = FOUR;
2798
2799
if (flash >= 0) {
2800
if (flash_type == 1) {
2801
if (tv == flash)
2802
tv = FOUR;
2803
if (bv == flash)
2804
bv = FOUR;
2805
} else if (flash_type == 2) {
2806
if (flash % 2)
2807
tv = bv = FOUR;
2808
} else {
2809
if (tv != FOUR)
2810
tv = (tv + flash) % FOUR;
2811
if (bv != FOUR)
2812
bv = (bv + flash) % FOUR;
2813
}
2814
}
2815
2816
v = tv * FIVE + bv;
2817
2818
/*
2819
* Add pencil marks.
2820
*/
2821
for (i = 0; i < FOUR; i++) {
2822
if (state->colouring[state->map->map[TE * wh + y*w+x]] < 0 &&
2823
(state->pencil[state->map->map[TE * wh + y*w+x]] & (1<<i)))
2824
v |= PENCIL_T_BASE << i;
2825
if (state->colouring[state->map->map[BE * wh + y*w+x]] < 0 &&
2826
(state->pencil[state->map->map[BE * wh + y*w+x]] & (1<<i)))
2827
v |= PENCIL_B_BASE << i;
2828
}
2829
2830
if (ui->show_numbers)
2831
v |= SHOW_NUMBERS;
2832
2833
ds->todraw[y*w+x] = v;
2834
}
2835
2836
/*
2837
* Add error markers to the `todraw' array.
2838
*/
2839
for (i = 0; i < state->map->ngraph; i++) {
2840
int v1 = state->map->graph[i] / n;
2841
int v2 = state->map->graph[i] % n;
2842
int xo, yo;
2843
2844
if (state->colouring[v1] < 0 || state->colouring[v2] < 0)
2845
continue;
2846
if (state->colouring[v1] != state->colouring[v2])
2847
continue;
2848
2849
x = state->map->edgex[i];
2850
y = state->map->edgey[i];
2851
2852
xo = x % 2; x /= 2;
2853
yo = y % 2; y /= 2;
2854
2855
ds->todraw[y*w+x] |= ERR_BASE << (yo*3+xo);
2856
if (xo == 0) {
2857
assert(x > 0);
2858
ds->todraw[y*w+(x-1)] |= ERR_BASE << (yo*3+2);
2859
}
2860
if (yo == 0) {
2861
assert(y > 0);
2862
ds->todraw[(y-1)*w+x] |= ERR_BASE << (2*3+xo);
2863
}
2864
if (xo == 0 && yo == 0) {
2865
assert(x > 0 && y > 0);
2866
ds->todraw[(y-1)*w+(x-1)] |= ERR_BASE << (2*3+2);
2867
}
2868
}
2869
2870
/*
2871
* Now actually draw everything.
2872
*/
2873
for (y = 0; y < h; y++)
2874
for (x = 0; x < w; x++) {
2875
unsigned long v = ds->todraw[y*w+x];
2876
if (ds->drawn[y*w+x] != v) {
2877
draw_square(dr, ds, &state->p, state->map, x, y, v);
2878
ds->drawn[y*w+x] = v;
2879
}
2880
}
2881
2882
/*
2883
* Draw the dragged colour blob if any.
2884
*/
2885
if (ui->drag_colour > -2) {
2886
ds->dragx = ui->dragx - TILESIZE/2 - 2;
2887
ds->dragy = ui->dragy - TILESIZE/2 - 2;
2888
blitter_save(dr, ds->bl, ds->dragx, ds->dragy);
2889
draw_circle(dr, ui->dragx, ui->dragy, TILESIZE/2,
2890
(ui->drag_colour < 0 ? COL_BACKGROUND :
2891
COL_0 + ui->drag_colour), COL_GRID);
2892
for (i = 0; i < FOUR; i++)
2893
if (ui->drag_pencil & (1 << i))
2894
draw_circle(dr, ui->dragx + ((i*4+2)%10-3) * TILESIZE/10,
2895
ui->dragy + (i*2-3) * TILESIZE/10,
2896
TILESIZE/8, COL_0 + i, COL_0 + i);
2897
draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
2898
ds->drag_visible = TRUE;
2899
}
2900
}
2901
2902
static float game_anim_length(game_state *oldstate, game_state *newstate,
2903
int dir, game_ui *ui)
2904
{
2905
return 0.0F;
2906
}
2907
2908
static float game_flash_length(game_state *oldstate, game_state *newstate,
2909
int dir, game_ui *ui)
2910
{
2911
if (!oldstate->completed && newstate->completed &&
2912
!oldstate->cheated && !newstate->cheated) {
2913
if (flash_type < 0) {
2914
char *env = getenv("MAP_ALTERNATIVE_FLASH");
2915
if (env)
2916
flash_type = atoi(env);
2917
else
2918
flash_type = 0;
2919
flash_length = (flash_type == 1 ? 0.50 : 0.30);
2920
}
2921
return flash_length;
2922
} else
2923
return 0.0F;
2924
}
2925
2926
static int game_timing_state(game_state *state, game_ui *ui)
2927
{
2928
return TRUE;
2929
}
2930
2931
static void game_print_size(game_params *params, float *x, float *y)
2932
{
2933
int pw, ph;
2934
2935
/*
2936
* I'll use 4mm squares by default, I think. Simplest way to
2937
* compute this size is to compute the pixel puzzle size at a
2938
* given tile size and then scale.
2939
*/
2940
game_compute_size(params, 400, &pw, &ph);
2941
*x = pw / 100.0;
2942
*y = ph / 100.0;
2943
}
2944
2945
static void game_print(drawing *dr, game_state *state, int tilesize)
2946
{
2947
int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
2948
int ink, c[FOUR], i;
2949
int x, y, r;
2950
int *coords, ncoords, coordsize;
2951
2952
/* Ick: fake up `ds->tilesize' for macro expansion purposes */
2953
struct { int tilesize; } ads, *ds = &ads;
2954
/* We can't call game_set_size() here because we don't want a blitter */
2955
ads.tilesize = tilesize;
2956
2957
ink = print_mono_colour(dr, 0);
2958
for (i = 0; i < FOUR; i++)
2959
c[i] = print_rgb_colour(dr, map_hatching[i], map_colours[i][0],
2960
map_colours[i][1], map_colours[i][2]);
2961
2962
coordsize = 0;
2963
coords = NULL;
2964
2965
print_line_width(dr, TILESIZE / 16);
2966
2967
/*
2968
* Draw a single filled polygon around each region.
2969
*/
2970
for (r = 0; r < n; r++) {
2971
int octants[8], lastdir, d1, d2, ox, oy;
2972
2973
/*
2974
* Start by finding a point on the region boundary. Any
2975
* point will do. To do this, we'll search for a square
2976
* containing the region and then decide which corner of it
2977
* to use.
2978
*/
2979
x = w;
2980
for (y = 0; y < h; y++) {
2981
for (x = 0; x < w; x++) {
2982
if (state->map->map[wh*0+y*w+x] == r ||
2983
state->map->map[wh*1+y*w+x] == r ||
2984
state->map->map[wh*2+y*w+x] == r ||
2985
state->map->map[wh*3+y*w+x] == r)
2986
break;
2987
}
2988
if (x < w)
2989
break;
2990
}
2991
assert(y < h && x < w); /* we must have found one somewhere */
2992
/*
2993
* This is the first square in lexicographic order which
2994
* contains part of this region. Therefore, one of the top
2995
* two corners of the square must be what we're after. The
2996
* only case in which it isn't the top left one is if the
2997
* square is diagonally divided and the region is in the
2998
* bottom right half.
2999
*/
3000
if (state->map->map[wh*TE+y*w+x] != r &&
3001
state->map->map[wh*LE+y*w+x] != r)
3002
x++; /* could just as well have done y++ */
3003
3004
/*
3005
* Now we have a point on the region boundary. Trace around
3006
* the region until we come back to this point,
3007
* accumulating coordinates for a polygon draw operation as
3008
* we go.
3009
*/
3010
lastdir = -1;
3011
ox = x;
3012
oy = y;
3013
ncoords = 0;
3014
3015
do {
3016
/*
3017
* There are eight possible directions we could head in
3018
* from here. We identify them by octant numbers, and
3019
* we also use octant numbers to identify the spaces
3020
* between them:
3021
*
3022
* 6 7 0
3023
* \ 7|0 /
3024
* \ | /
3025
* 6 \|/ 1
3026
* 5-----+-----1
3027
* 5 /|\ 2
3028
* / | \
3029
* / 4|3 \
3030
* 4 3 2
3031
*/
3032
octants[0] = x<w && y>0 ? state->map->map[wh*LE+(y-1)*w+x] : -1;
3033
octants[1] = x<w && y>0 ? state->map->map[wh*BE+(y-1)*w+x] : -1;
3034
octants[2] = x<w && y<h ? state->map->map[wh*TE+y*w+x] : -1;
3035
octants[3] = x<w && y<h ? state->map->map[wh*LE+y*w+x] : -1;
3036
octants[4] = x>0 && y<h ? state->map->map[wh*RE+y*w+(x-1)] : -1;
3037
octants[5] = x>0 && y<h ? state->map->map[wh*TE+y*w+(x-1)] : -1;
3038
octants[6] = x>0 && y>0 ? state->map->map[wh*BE+(y-1)*w+(x-1)] :-1;
3039
octants[7] = x>0 && y>0 ? state->map->map[wh*RE+(y-1)*w+(x-1)] :-1;
3040
3041
d1 = d2 = -1;
3042
for (i = 0; i < 8; i++)
3043
if ((octants[i] == r) ^ (octants[(i+1)%8] == r)) {
3044
assert(d2 == -1);
3045
if (d1 == -1)
3046
d1 = i;
3047
else
3048
d2 = i;
3049
}
3050
3051
assert(d1 != -1 && d2 != -1);
3052
if (d1 == lastdir)
3053
d1 = d2;
3054
3055
/*
3056
* Now we're heading in direction d1. Save the current
3057
* coordinates.
3058
*/
3059
if (ncoords + 2 > coordsize) {
3060
coordsize += 128;
3061
coords = sresize(coords, coordsize, int);
3062
}
3063
coords[ncoords++] = COORD(x);
3064
coords[ncoords++] = COORD(y);
3065
3066
/*
3067
* Compute the new coordinates.
3068
*/
3069
x += (d1 % 4 == 3 ? 0 : d1 < 4 ? +1 : -1);
3070
y += (d1 % 4 == 1 ? 0 : d1 > 1 && d1 < 5 ? +1 : -1);
3071
assert(x >= 0 && x <= w && y >= 0 && y <= h);
3072
3073
lastdir = d1 ^ 4;
3074
} while (x != ox || y != oy);
3075
3076
draw_polygon(dr, coords, ncoords/2,
3077
state->colouring[r] >= 0 ?
3078
c[state->colouring[r]] : -1, ink);
3079
}
3080
sfree(coords);
3081
}
3082
3083
#ifdef COMBINED
3084
#define thegame map
3085
#endif
3086
3087
const struct game thegame = {
3088
"Map", "games.map",
3089
default_params,
3090
game_fetch_preset,
3091
decode_params,
3092
encode_params,
3093
free_params,
3094
dup_params,
3095
TRUE, game_configure, custom_params,
3096
validate_params,
3097
new_game_desc,
3098
validate_desc,
3099
new_game,
3100
dup_game,
3101
free_game,
3102
TRUE, solve_game,
3103
FALSE, game_text_format,
3104
new_ui,
3105
free_ui,
3106
encode_ui,
3107
decode_ui,
3108
game_changed_state,
3109
interpret_move,
3110
execute_move,
3111
20, game_compute_size, game_set_size,
3112
game_colours,
3113
game_new_drawstate,
3114
game_free_drawstate,
3115
game_redraw,
3116
game_anim_length,
3117
game_flash_length,
3118
TRUE, TRUE, game_print_size, game_print,
3119
FALSE, /* wants_statusbar */
3120
FALSE, game_timing_state,
3121
0, /* flags */
3122
};
3123
3124
#ifdef STANDALONE_SOLVER
3125
3126
int main(int argc, char **argv)
3127
{
3128
game_params *p;
3129
game_state *s;
3130
char *id = NULL, *desc, *err;
3131
int grade = FALSE;
3132
int ret, diff, really_verbose = FALSE;
3133
struct solver_scratch *sc;
3134
int i;
3135
3136
while (--argc > 0) {
3137
char *p = *++argv;
3138
if (!strcmp(p, "-v")) {
3139
really_verbose = TRUE;
3140
} else if (!strcmp(p, "-g")) {
3141
grade = TRUE;
3142
} else if (*p == '-') {
3143
fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
3144
return 1;
3145
} else {
3146
id = p;
3147
}
3148
}
3149
3150
if (!id) {
3151
fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
3152
return 1;
3153
}
3154
3155
desc = strchr(id, ':');
3156
if (!desc) {
3157
fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
3158
return 1;
3159
}
3160
*desc++ = '\0';
3161
3162
p = default_params();
3163
decode_params(p, id);
3164
err = validate_desc(p, desc);
3165
if (err) {
3166
fprintf(stderr, "%s: %s\n", argv[0], err);
3167
return 1;
3168
}
3169
s = new_game(NULL, p, desc);
3170
3171
sc = new_scratch(s->map->graph, s->map->n, s->map->ngraph);
3172
3173
/*
3174
* When solving an Easy puzzle, we don't want to bother the
3175
* user with Hard-level deductions. For this reason, we grade
3176
* the puzzle internally before doing anything else.
3177
*/
3178
ret = -1; /* placate optimiser */
3179
for (diff = 0; diff < DIFFCOUNT; diff++) {
3180
for (i = 0; i < s->map->n; i++)
3181
if (!s->map->immutable[i])
3182
s->colouring[i] = -1;
3183
ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph,
3184
s->colouring, diff);
3185
if (ret < 2)
3186
break;
3187
}
3188
3189
if (diff == DIFFCOUNT) {
3190
if (grade)
3191
printf("Difficulty rating: harder than Hard, or ambiguous\n");
3192
else
3193
printf("Unable to find a unique solution\n");
3194
} else {
3195
if (grade) {
3196
if (ret == 0)
3197
printf("Difficulty rating: impossible (no solution exists)\n");
3198
else if (ret == 1)
3199
printf("Difficulty rating: %s\n", map_diffnames[diff]);
3200
} else {
3201
verbose = really_verbose;
3202
for (i = 0; i < s->map->n; i++)
3203
if (!s->map->immutable[i])
3204
s->colouring[i] = -1;
3205
ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph,
3206
s->colouring, diff);
3207
if (ret == 0)
3208
printf("Puzzle is inconsistent\n");
3209
else {
3210
int col = 0;
3211
3212
for (i = 0; i < s->map->n; i++) {
3213
printf("%5d <- %c%c", i, colnames[s->colouring[i]],
3214
(col < 6 && i+1 < s->map->n ? ' ' : '\n'));
3215
if (++col == 7)
3216
col = 0;
3217
}
3218
}
3219
}
3220
}
3221
3222
return 0;
3223
}
3224
3225
#endif
Loggerhead is a web-based interface for Breezy
Version: 2.0.1