| 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 <assert.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 | } |