diff options
Diffstat (limited to 'apps/plugins/puzzles/loopgen.c')
-rw-r--r-- | apps/plugins/puzzles/loopgen.c | 536 |
1 files changed, 536 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/loopgen.c b/apps/plugins/puzzles/loopgen.c new file mode 100644 index 0000000000..25b63906fa --- /dev/null +++ b/apps/plugins/puzzles/loopgen.c | |||
@@ -0,0 +1,536 @@ | |||
1 | /* | ||
2 | * loopgen.c: loop generation functions for grid.[ch]. | ||
3 | */ | ||
4 | |||
5 | #include <stdio.h> | ||
6 | #include <stdlib.h> | ||
7 | #include <stddef.h> | ||
8 | #include <string.h> | ||
9 | #include "rbassert.h" | ||
10 | #include <ctype.h> | ||
11 | #include <math.h> | ||
12 | |||
13 | #include "puzzles.h" | ||
14 | #include "tree234.h" | ||
15 | #include "grid.h" | ||
16 | #include "loopgen.h" | ||
17 | |||
18 | |||
19 | /* We're going to store lists of current candidate faces for colouring black | ||
20 | * or white. | ||
21 | * Each face gets a 'score', which tells us how adding that face right | ||
22 | * now would affect the curliness of the solution loop. We're trying to | ||
23 | * maximise that quantity so will bias our random selection of faces to | ||
24 | * colour those with high scores */ | ||
25 | struct face_score { | ||
26 | int white_score; | ||
27 | int black_score; | ||
28 | unsigned long random; | ||
29 | /* No need to store a grid_face* here. The 'face_scores' array will | ||
30 | * be a list of 'face_score' objects, one for each face of the grid, so | ||
31 | * the position (index) within the 'face_scores' array will determine | ||
32 | * which face corresponds to a particular face_score. | ||
33 | * Having a single 'face_scores' array for all faces simplifies memory | ||
34 | * management, and probably improves performance, because we don't have to | ||
35 | * malloc/free each individual face_score, and we don't have to maintain | ||
36 | * a mapping from grid_face* pointers to face_score* pointers. | ||
37 | */ | ||
38 | }; | ||
39 | |||
40 | static int generic_sort_cmpfn(void *v1, void *v2, size_t offset) | ||
41 | { | ||
42 | struct face_score *f1 = v1; | ||
43 | struct face_score *f2 = v2; | ||
44 | int r; | ||
45 | |||
46 | r = *(int *)((char *)f2 + offset) - *(int *)((char *)f1 + offset); | ||
47 | if (r) { | ||
48 | return r; | ||
49 | } | ||
50 | |||
51 | if (f1->random < f2->random) | ||
52 | return -1; | ||
53 | else if (f1->random > f2->random) | ||
54 | return 1; | ||
55 | |||
56 | /* | ||
57 | * It's _just_ possible that two faces might have been given | ||
58 | * the same random value. In that situation, fall back to | ||
59 | * comparing based on the positions within the face_scores list. | ||
60 | * This introduces a tiny directional bias, but not a significant one. | ||
61 | */ | ||
62 | return f1 - f2; | ||
63 | } | ||
64 | |||
65 | static int white_sort_cmpfn(void *v1, void *v2) | ||
66 | { | ||
67 | return generic_sort_cmpfn(v1, v2, offsetof(struct face_score,white_score)); | ||
68 | } | ||
69 | |||
70 | static int black_sort_cmpfn(void *v1, void *v2) | ||
71 | { | ||
72 | return generic_sort_cmpfn(v1, v2, offsetof(struct face_score,black_score)); | ||
73 | } | ||
74 | |||
75 | /* 'board' is an array of enum face_colour, indicating which faces are | ||
76 | * currently black/white/grey. 'colour' is FACE_WHITE or FACE_BLACK. | ||
77 | * Returns whether it's legal to colour the given face with this colour. */ | ||
78 | static int can_colour_face(grid *g, char* board, int face_index, | ||
79 | enum face_colour colour) | ||
80 | { | ||
81 | int i, j; | ||
82 | grid_face *test_face = g->faces + face_index; | ||
83 | grid_face *starting_face, *current_face; | ||
84 | grid_dot *starting_dot; | ||
85 | int transitions; | ||
86 | int current_state, s; /* booleans: equal or not-equal to 'colour' */ | ||
87 | int found_same_coloured_neighbour = FALSE; | ||
88 | assert(board[face_index] != colour); | ||
89 | |||
90 | /* Can only consider a face for colouring if it's adjacent to a face | ||
91 | * with the same colour. */ | ||
92 | for (i = 0; i < test_face->order; i++) { | ||
93 | grid_edge *e = test_face->edges[i]; | ||
94 | grid_face *f = (e->face1 == test_face) ? e->face2 : e->face1; | ||
95 | if (FACE_COLOUR(f) == colour) { | ||
96 | found_same_coloured_neighbour = TRUE; | ||
97 | break; | ||
98 | } | ||
99 | } | ||
100 | if (!found_same_coloured_neighbour) | ||
101 | return FALSE; | ||
102 | |||
103 | /* Need to avoid creating a loop of faces of this colour around some | ||
104 | * differently-coloured faces. | ||
105 | * Also need to avoid meeting a same-coloured face at a corner, with | ||
106 | * other-coloured faces in between. Here's a simple test that (I believe) | ||
107 | * takes care of both these conditions: | ||
108 | * | ||
109 | * Take the circular path formed by this face's edges, and inflate it | ||
110 | * slightly outwards. Imagine walking around this path and consider | ||
111 | * the faces that you visit in sequence. This will include all faces | ||
112 | * touching the given face, either along an edge or just at a corner. | ||
113 | * Count the number of 'colour'/not-'colour' transitions you encounter, as | ||
114 | * you walk along the complete loop. This will obviously turn out to be | ||
115 | * an even number. | ||
116 | * If 0, we're either in the middle of an "island" of this colour (should | ||
117 | * be impossible as we're not supposed to create black or white loops), | ||
118 | * or we're about to start a new island - also not allowed. | ||
119 | * If 4 or greater, there are too many separate coloured regions touching | ||
120 | * this face, and colouring it would create a loop or a corner-violation. | ||
121 | * The only allowed case is when the count is exactly 2. */ | ||
122 | |||
123 | /* i points to a dot around the test face. | ||
124 | * j points to a face around the i^th dot. | ||
125 | * The current face will always be: | ||
126 | * test_face->dots[i]->faces[j] | ||
127 | * We assume dots go clockwise around the test face, | ||
128 | * and faces go clockwise around dots. */ | ||
129 | |||
130 | /* | ||
131 | * The end condition is slightly fiddly. In sufficiently strange | ||
132 | * degenerate grids, our test face may be adjacent to the same | ||
133 | * other face multiple times (typically if it's the exterior | ||
134 | * face). Consider this, in particular: | ||
135 | * | ||
136 | * +--+ | ||
137 | * | | | ||
138 | * +--+--+ | ||
139 | * | | | | ||
140 | * +--+--+ | ||
141 | * | ||
142 | * The bottom left face there is adjacent to the exterior face | ||
143 | * twice, so we can't just terminate our iteration when we reach | ||
144 | * the same _face_ we started at. Furthermore, we can't | ||
145 | * condition on having the same (i,j) pair either, because | ||
146 | * several (i,j) pairs identify the bottom left contiguity with | ||
147 | * the exterior face! We canonicalise the (i,j) pair by taking | ||
148 | * one step around before we set the termination tracking. | ||
149 | */ | ||
150 | |||
151 | i = j = 0; | ||
152 | current_face = test_face->dots[0]->faces[0]; | ||
153 | if (current_face == test_face) { | ||
154 | j = 1; | ||
155 | current_face = test_face->dots[0]->faces[1]; | ||
156 | } | ||
157 | transitions = 0; | ||
158 | current_state = (FACE_COLOUR(current_face) == colour); | ||
159 | starting_dot = NULL; | ||
160 | starting_face = NULL; | ||
161 | while (TRUE) { | ||
162 | /* Advance to next face. | ||
163 | * Need to loop here because it might take several goes to | ||
164 | * find it. */ | ||
165 | while (TRUE) { | ||
166 | j++; | ||
167 | if (j == test_face->dots[i]->order) | ||
168 | j = 0; | ||
169 | |||
170 | if (test_face->dots[i]->faces[j] == test_face) { | ||
171 | /* Advance to next dot round test_face, then | ||
172 | * find current_face around new dot | ||
173 | * and advance to the next face clockwise */ | ||
174 | i++; | ||
175 | if (i == test_face->order) | ||
176 | i = 0; | ||
177 | for (j = 0; j < test_face->dots[i]->order; j++) { | ||
178 | if (test_face->dots[i]->faces[j] == current_face) | ||
179 | break; | ||
180 | } | ||
181 | /* Must actually find current_face around new dot, | ||
182 | * or else something's wrong with the grid. */ | ||
183 | assert(j != test_face->dots[i]->order); | ||
184 | /* Found, so advance to next face and try again */ | ||
185 | } else { | ||
186 | break; | ||
187 | } | ||
188 | } | ||
189 | /* (i,j) are now advanced to next face */ | ||
190 | current_face = test_face->dots[i]->faces[j]; | ||
191 | s = (FACE_COLOUR(current_face) == colour); | ||
192 | if (!starting_dot) { | ||
193 | starting_dot = test_face->dots[i]; | ||
194 | starting_face = current_face; | ||
195 | current_state = s; | ||
196 | } else { | ||
197 | if (s != current_state) { | ||
198 | ++transitions; | ||
199 | current_state = s; | ||
200 | if (transitions > 2) | ||
201 | break; | ||
202 | } | ||
203 | if (test_face->dots[i] == starting_dot && | ||
204 | current_face == starting_face) | ||
205 | break; | ||
206 | } | ||
207 | } | ||
208 | |||
209 | return (transitions == 2) ? TRUE : FALSE; | ||
210 | } | ||
211 | |||
212 | /* Count the number of neighbours of 'face', having colour 'colour' */ | ||
213 | static int face_num_neighbours(grid *g, char *board, grid_face *face, | ||
214 | enum face_colour colour) | ||
215 | { | ||
216 | int colour_count = 0; | ||
217 | int i; | ||
218 | grid_face *f; | ||
219 | grid_edge *e; | ||
220 | for (i = 0; i < face->order; i++) { | ||
221 | e = face->edges[i]; | ||
222 | f = (e->face1 == face) ? e->face2 : e->face1; | ||
223 | if (FACE_COLOUR(f) == colour) | ||
224 | ++colour_count; | ||
225 | } | ||
226 | return colour_count; | ||
227 | } | ||
228 | |||
229 | /* The 'score' of a face reflects its current desirability for selection | ||
230 | * as the next face to colour white or black. We want to encourage moving | ||
231 | * into grey areas and increasing loopiness, so we give scores according to | ||
232 | * how many of the face's neighbours are currently coloured the same as the | ||
233 | * proposed colour. */ | ||
234 | static int face_score(grid *g, char *board, grid_face *face, | ||
235 | enum face_colour colour) | ||
236 | { | ||
237 | /* Simple formula: score = 0 - num. same-coloured neighbours, | ||
238 | * so a higher score means fewer same-coloured neighbours. */ | ||
239 | return -face_num_neighbours(g, board, face, colour); | ||
240 | } | ||
241 | |||
242 | /* | ||
243 | * Generate a new complete random closed loop for the given grid. | ||
244 | * | ||
245 | * The method is to generate a WHITE/BLACK colouring of all the faces, | ||
246 | * such that the WHITE faces will define the inside of the path, and the | ||
247 | * BLACK faces define the outside. | ||
248 | * To do this, we initially colour all faces GREY. The infinite space outside | ||
249 | * the grid is coloured BLACK, and we choose a random face to colour WHITE. | ||
250 | * Then we gradually grow the BLACK and the WHITE regions, eliminating GREY | ||
251 | * faces, until the grid is filled with BLACK/WHITE. As we grow the regions, | ||
252 | * we avoid creating loops of a single colour, to preserve the topological | ||
253 | * shape of the WHITE and BLACK regions. | ||
254 | * We also try to make the boundary as loopy and twisty as possible, to avoid | ||
255 | * generating paths that are uninteresting. | ||
256 | * The algorithm works by choosing a BLACK/WHITE colour, then choosing a GREY | ||
257 | * face that can be coloured with that colour (without violating the | ||
258 | * topological shape of that region). It's not obvious, but I think this | ||
259 | * algorithm is guaranteed to terminate without leaving any GREY faces behind. | ||
260 | * Indeed, if there are any GREY faces at all, both the WHITE and BLACK | ||
261 | * regions can be grown. | ||
262 | * This is checked using assert()ions, and I haven't seen any failures yet. | ||
263 | * | ||
264 | * Hand-wavy proof: imagine what can go wrong... | ||
265 | * | ||
266 | * Could the white faces get completely cut off by the black faces, and still | ||
267 | * leave some grey faces remaining? | ||
268 | * No, because then the black faces would form a loop around both the white | ||
269 | * faces and the grey faces, which is disallowed because we continually | ||
270 | * maintain the correct topological shape of the black region. | ||
271 | * Similarly, the black faces can never get cut off by the white faces. That | ||
272 | * means both the WHITE and BLACK regions always have some room to grow into | ||
273 | * the GREY regions. | ||
274 | * Could it be that we can't colour some GREY face, because there are too many | ||
275 | * WHITE/BLACK transitions as we walk round the face? (see the | ||
276 | * can_colour_face() function for details) | ||
277 | * No. Imagine otherwise, and we see WHITE/BLACK/WHITE/BLACK as we walk | ||
278 | * around the face. The two WHITE faces would be connected by a WHITE path, | ||
279 | * and the BLACK faces would be connected by a BLACK path. These paths would | ||
280 | * have to cross, which is impossible. | ||
281 | * Another thing that could go wrong: perhaps we can't find any GREY face to | ||
282 | * colour WHITE, because it would create a loop-violation or a corner-violation | ||
283 | * with the other WHITE faces? | ||
284 | * This is a little bit tricky to prove impossible. Imagine you have such a | ||
285 | * GREY face (that is, if you coloured it WHITE, you would create a WHITE loop | ||
286 | * or corner violation). | ||
287 | * That would cut all the non-white area into two blobs. One of those blobs | ||
288 | * must be free of BLACK faces (because the BLACK stuff is a connected blob). | ||
289 | * So we have a connected GREY area, completely surrounded by WHITE | ||
290 | * (including the GREY face we've tentatively coloured WHITE). | ||
291 | * A well-known result in graph theory says that you can always find a GREY | ||
292 | * face whose removal leaves the remaining GREY area connected. And it says | ||
293 | * there are at least two such faces, so we can always choose the one that | ||
294 | * isn't the "tentative" GREY face. Colouring that face WHITE leaves | ||
295 | * everything nice and connected, including that "tentative" GREY face which | ||
296 | * acts as a gateway to the rest of the non-WHITE grid. | ||
297 | */ | ||
298 | void generate_loop(grid *g, char *board, random_state *rs, | ||
299 | loopgen_bias_fn_t bias, void *biasctx) | ||
300 | { | ||
301 | int i, j; | ||
302 | int num_faces = g->num_faces; | ||
303 | struct face_score *face_scores; /* Array of face_score objects */ | ||
304 | struct face_score *fs; /* Points somewhere in the above list */ | ||
305 | struct grid_face *cur_face; | ||
306 | tree234 *lightable_faces_sorted; | ||
307 | tree234 *darkable_faces_sorted; | ||
308 | int *face_list; | ||
309 | int do_random_pass; | ||
310 | |||
311 | /* Make a board */ | ||
312 | memset(board, FACE_GREY, num_faces); | ||
313 | |||
314 | /* Create and initialise the list of face_scores */ | ||
315 | face_scores = snewn(num_faces, struct face_score); | ||
316 | for (i = 0; i < num_faces; i++) { | ||
317 | face_scores[i].random = random_bits(rs, 31); | ||
318 | face_scores[i].black_score = face_scores[i].white_score = 0; | ||
319 | } | ||
320 | |||
321 | /* Colour a random, finite face white. The infinite face is implicitly | ||
322 | * coloured black. Together, they will seed the random growth process | ||
323 | * for the black and white areas. */ | ||
324 | i = random_upto(rs, num_faces); | ||
325 | board[i] = FACE_WHITE; | ||
326 | |||
327 | /* We need a way of favouring faces that will increase our loopiness. | ||
328 | * We do this by maintaining a list of all candidate faces sorted by | ||
329 | * their score and choose randomly from that with appropriate skew. | ||
330 | * In order to avoid consistently biasing towards particular faces, we | ||
331 | * need the sort order _within_ each group of scores to be completely | ||
332 | * random. But it would be abusing the hospitality of the tree234 data | ||
333 | * structure if our comparison function were nondeterministic :-). So with | ||
334 | * each face we associate a random number that does not change during a | ||
335 | * particular run of the generator, and use that as a secondary sort key. | ||
336 | * Yes, this means we will be biased towards particular random faces in | ||
337 | * any one run but that doesn't actually matter. */ | ||
338 | |||
339 | lightable_faces_sorted = newtree234(white_sort_cmpfn); | ||
340 | darkable_faces_sorted = newtree234(black_sort_cmpfn); | ||
341 | |||
342 | /* Initialise the lists of lightable and darkable faces. This is | ||
343 | * slightly different from the code inside the while-loop, because we need | ||
344 | * to check every face of the board (the grid structure does not keep a | ||
345 | * list of the infinite face's neighbours). */ | ||
346 | for (i = 0; i < num_faces; i++) { | ||
347 | grid_face *f = g->faces + i; | ||
348 | struct face_score *fs = face_scores + i; | ||
349 | if (board[i] != FACE_GREY) continue; | ||
350 | /* We need the full colourability check here, it's not enough simply | ||
351 | * to check neighbourhood. On some grids, a neighbour of the infinite | ||
352 | * face is not necessarily darkable. */ | ||
353 | if (can_colour_face(g, board, i, FACE_BLACK)) { | ||
354 | fs->black_score = face_score(g, board, f, FACE_BLACK); | ||
355 | add234(darkable_faces_sorted, fs); | ||
356 | } | ||
357 | if (can_colour_face(g, board, i, FACE_WHITE)) { | ||
358 | fs->white_score = face_score(g, board, f, FACE_WHITE); | ||
359 | add234(lightable_faces_sorted, fs); | ||
360 | } | ||
361 | } | ||
362 | |||
363 | /* Colour faces one at a time until no more faces are colourable. */ | ||
364 | while (TRUE) | ||
365 | { | ||
366 | enum face_colour colour; | ||
367 | tree234 *faces_to_pick; | ||
368 | int c_lightable = count234(lightable_faces_sorted); | ||
369 | int c_darkable = count234(darkable_faces_sorted); | ||
370 | if (c_lightable == 0 && c_darkable == 0) { | ||
371 | /* No more faces we can use at all. */ | ||
372 | break; | ||
373 | } | ||
374 | assert(c_lightable != 0 && c_darkable != 0); | ||
375 | |||
376 | /* Choose a colour, and colour the best available face | ||
377 | * with that colour. */ | ||
378 | colour = random_upto(rs, 2) ? FACE_WHITE : FACE_BLACK; | ||
379 | |||
380 | if (colour == FACE_WHITE) | ||
381 | faces_to_pick = lightable_faces_sorted; | ||
382 | else | ||
383 | faces_to_pick = darkable_faces_sorted; | ||
384 | if (bias) { | ||
385 | /* | ||
386 | * Go through all the candidate faces and pick the one the | ||
387 | * bias function likes best, breaking ties using the | ||
388 | * ordering in our tree234 (which is why we replace only | ||
389 | * if score > bestscore, not >=). | ||
390 | */ | ||
391 | int j, k; | ||
392 | struct face_score *best = NULL; | ||
393 | int score, bestscore = 0; | ||
394 | |||
395 | for (j = 0; | ||
396 | (fs = (struct face_score *)index234(faces_to_pick, j))!=NULL; | ||
397 | j++) { | ||
398 | |||
399 | assert(fs); | ||
400 | k = fs - face_scores; | ||
401 | assert(board[k] == FACE_GREY); | ||
402 | board[k] = colour; | ||
403 | score = bias(biasctx, board, k); | ||
404 | board[k] = FACE_GREY; | ||
405 | bias(biasctx, board, k); /* let bias know we put it back */ | ||
406 | |||
407 | if (!best || score > bestscore) { | ||
408 | bestscore = score; | ||
409 | best = fs; | ||
410 | } | ||
411 | } | ||
412 | fs = best; | ||
413 | } else { | ||
414 | fs = (struct face_score *)index234(faces_to_pick, 0); | ||
415 | } | ||
416 | assert(fs); | ||
417 | i = fs - face_scores; | ||
418 | assert(board[i] == FACE_GREY); | ||
419 | board[i] = colour; | ||
420 | if (bias) | ||
421 | bias(biasctx, board, i); /* notify bias function of the change */ | ||
422 | |||
423 | /* Remove this newly-coloured face from the lists. These lists should | ||
424 | * only contain grey faces. */ | ||
425 | del234(lightable_faces_sorted, fs); | ||
426 | del234(darkable_faces_sorted, fs); | ||
427 | |||
428 | /* Remember which face we've just coloured */ | ||
429 | cur_face = g->faces + i; | ||
430 | |||
431 | /* The face we've just coloured potentially affects the colourability | ||
432 | * and the scores of any neighbouring faces (touching at a corner or | ||
433 | * edge). So the search needs to be conducted around all faces | ||
434 | * touching the one we've just lit. Iterate over its corners, then | ||
435 | * over each corner's faces. For each such face, we remove it from | ||
436 | * the lists, recalculate any scores, then add it back to the lists | ||
437 | * (depending on whether it is lightable, darkable or both). */ | ||
438 | for (i = 0; i < cur_face->order; i++) { | ||
439 | grid_dot *d = cur_face->dots[i]; | ||
440 | for (j = 0; j < d->order; j++) { | ||
441 | grid_face *f = d->faces[j]; | ||
442 | int fi; /* face index of f */ | ||
443 | |||
444 | if (f == NULL) | ||
445 | continue; | ||
446 | if (f == cur_face) | ||
447 | continue; | ||
448 | |||
449 | /* If the face is already coloured, it won't be on our | ||
450 | * lightable/darkable lists anyway, so we can skip it without | ||
451 | * bothering with the removal step. */ | ||
452 | if (FACE_COLOUR(f) != FACE_GREY) continue; | ||
453 | |||
454 | /* Find the face index and face_score* corresponding to f */ | ||
455 | fi = f - g->faces; | ||
456 | fs = face_scores + fi; | ||
457 | |||
458 | /* Remove from lightable list if it's in there. We do this, | ||
459 | * even if it is still lightable, because the score might | ||
460 | * be different, and we need to remove-then-add to maintain | ||
461 | * correct sort order. */ | ||
462 | del234(lightable_faces_sorted, fs); | ||
463 | if (can_colour_face(g, board, fi, FACE_WHITE)) { | ||
464 | fs->white_score = face_score(g, board, f, FACE_WHITE); | ||
465 | add234(lightable_faces_sorted, fs); | ||
466 | } | ||
467 | /* Do the same for darkable list. */ | ||
468 | del234(darkable_faces_sorted, fs); | ||
469 | if (can_colour_face(g, board, fi, FACE_BLACK)) { | ||
470 | fs->black_score = face_score(g, board, f, FACE_BLACK); | ||
471 | add234(darkable_faces_sorted, fs); | ||
472 | } | ||
473 | } | ||
474 | } | ||
475 | } | ||
476 | |||
477 | /* Clean up */ | ||
478 | freetree234(lightable_faces_sorted); | ||
479 | freetree234(darkable_faces_sorted); | ||
480 | sfree(face_scores); | ||
481 | |||
482 | /* The next step requires a shuffled list of all faces */ | ||
483 | face_list = snewn(num_faces, int); | ||
484 | for (i = 0; i < num_faces; ++i) { | ||
485 | face_list[i] = i; | ||
486 | } | ||
487 | shuffle(face_list, num_faces, sizeof(int), rs); | ||
488 | |||
489 | /* The above loop-generation algorithm can often leave large clumps | ||
490 | * of faces of one colour. In extreme cases, the resulting path can be | ||
491 | * degenerate and not very satisfying to solve. | ||
492 | * This next step alleviates this problem: | ||
493 | * Go through the shuffled list, and flip the colour of any face we can | ||
494 | * legally flip, and which is adjacent to only one face of the opposite | ||
495 | * colour - this tends to grow 'tendrils' into any clumps. | ||
496 | * Repeat until we can find no more faces to flip. This will | ||
497 | * eventually terminate, because each flip increases the loop's | ||
498 | * perimeter, which cannot increase for ever. | ||
499 | * The resulting path will have maximal loopiness (in the sense that it | ||
500 | * cannot be improved "locally". Unfortunately, this allows a player to | ||
501 | * make some illicit deductions. To combat this (and make the path more | ||
502 | * interesting), we do one final pass making random flips. */ | ||
503 | |||
504 | /* Set to TRUE for final pass */ | ||
505 | do_random_pass = FALSE; | ||
506 | |||
507 | while (TRUE) { | ||
508 | /* Remember whether a flip occurred during this pass */ | ||
509 | int flipped = FALSE; | ||
510 | |||
511 | for (i = 0; i < num_faces; ++i) { | ||
512 | int j = face_list[i]; | ||
513 | enum face_colour opp = | ||
514 | (board[j] == FACE_WHITE) ? FACE_BLACK : FACE_WHITE; | ||
515 | if (can_colour_face(g, board, j, opp)) { | ||
516 | grid_face *face = g->faces +j; | ||
517 | if (do_random_pass) { | ||
518 | /* final random pass */ | ||
519 | if (!random_upto(rs, 10)) | ||
520 | board[j] = opp; | ||
521 | } else { | ||
522 | /* normal pass - flip when neighbour count is 1 */ | ||
523 | if (face_num_neighbours(g, board, face, opp) == 1) { | ||
524 | board[j] = opp; | ||
525 | flipped = TRUE; | ||
526 | } | ||
527 | } | ||
528 | } | ||
529 | } | ||
530 | |||
531 | if (do_random_pass) break; | ||
532 | if (!flipped) do_random_pass = TRUE; | ||
533 | } | ||
534 | |||
535 | sfree(face_list); | ||
536 | } | ||