+ if (done_something)
+ continue;
+
+ if (difficulty < DIFF_HARD)
+ break; /* can't do anything harder */
+
+ /*
+ * Right; now we get creative. Now we're going to look for
+ * `forcing chains'. A forcing chain is a path through the
+ * graph with the following properties:
+ *
+ * (a) Each vertex on the path has precisely two possible
+ * colours.
+ *
+ * (b) Each pair of vertices which are adjacent on the
+ * path share at least one possible colour in common.
+ *
+ * (c) Each vertex in the middle of the path shares _both_
+ * of its colours with at least one of its neighbours
+ * (not the same one with both neighbours).
+ *
+ * These together imply that at least one of the possible
+ * colour choices at one end of the path forces _all_ the
+ * rest of the colours along the path. In order to make
+ * real use of this, we need further properties:
+ *
+ * (c) Ruling out some colour C from the vertex at one end
+ * of the path forces the vertex at the other end to
+ * take colour C.
+ *
+ * (d) The two end vertices are mutually adjacent to some
+ * third vertex.
+ *
+ * (e) That third vertex currently has C as a possibility.
+ *
+ * If we can find all of that lot, we can deduce that at
+ * least one of the two ends of the forcing chain has
+ * colour C, and that therefore the mutually adjacent third
+ * vertex does not.
+ *
+ * To find forcing chains, we're going to start a bfs at
+ * each suitable vertex of the graph, once for each of its
+ * two possible colours.
+ */
+ for (i = 0; i < n; i++) {
+ int c;
+
+ if (colouring[i] >= 0 || bitcount(sc->possible[i]) != 2)
+ continue;
+
+ for (c = 0; c < FOUR; c++)
+ if (sc->possible[i] & (1 << c)) {
+ int j, k, gi, origc, currc, head, tail;
+ /*
+ * Try a bfs from this vertex, ruling out
+ * colour c.
+ *
+ * Within this loop, we work in colour bitmaps
+ * rather than actual colours, because
+ * converting back and forth is a needless
+ * computational expense.
+ */
+
+ origc = 1 << c;
+
+ for (j = 0; j < n; j++) {
+ sc->bfscolour[j] = -1;
+#ifdef SOLVER_DIAGNOSTICS
+ sc->bfsprev[j] = -1;
+#endif
+ }
+ head = tail = 0;
+ sc->bfsqueue[tail++] = i;
+ sc->bfscolour[i] = sc->possible[i] &~ origc;
+
+ while (head < tail) {
+ j = sc->bfsqueue[head++];
+ currc = sc->bfscolour[j];
+
+ /*
+ * Try neighbours of j.
+ */
+ for (gi = graph_vertex_start(graph, n, ngraph, j);
+ gi < ngraph && graph[gi] < n*(j+1); gi++) {
+ k = graph[gi] - j*n;
+
+ /*
+ * To continue with the bfs in vertex
+ * k, we need k to be
+ * (a) not already visited
+ * (b) have two possible colours
+ * (c) those colours include currc.
+ */
+
+ if (sc->bfscolour[k] < 0 &&
+ colouring[k] < 0 &&
+ bitcount(sc->possible[k]) == 2 &&
+ (sc->possible[k] & currc)) {
+ sc->bfsqueue[tail++] = k;
+ sc->bfscolour[k] =
+ sc->possible[k] &~ currc;
+#ifdef SOLVER_DIAGNOSTICS
+ sc->bfsprev[k] = j;
+#endif
+ }
+
+ /*
+ * One other possibility is that k
+ * might be the region in which we can
+ * make a real deduction: if it's
+ * adjacent to i, contains currc as a
+ * possibility, and currc is equal to
+ * the original colour we ruled out.
+ */
+ if (currc == origc &&
+ graph_adjacent(graph, n, ngraph, k, i) &&
+ (sc->possible[k] & currc)) {
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose) {
+ char buf[80], *sep = "";
+ int r;
+
+ printf("%*sforcing chain, colour %s, ",
+ 2*sc->depth, "",
+ colourset(buf, origc));
+ for (r = j; r != -1; r = sc->bfsprev[r]) {
+ printf("%s%d", sep, r);
+ sep = "-";
+ }
+ printf("\n%*s ruling out %s in region"
+ " %d\n", 2*sc->depth, "",
+ colourset(buf, origc), k);
+ }
+#endif
+ sc->possible[k] &= ~origc;
+ done_something = TRUE;
+ }
+ }
+ }
+
+ assert(tail <= n);
+ }
+ }
+