+/*
+ * Try to find a number in the possible set of (x1,y1) which can be
+ * ruled out because it would leave no possibilities for (x2,y2).
+ */
+static int solver_mne(struct solver_usage *usage,
+ struct solver_scratch *scratch,
+ int x1, int y1, int x2, int y2)
+{
+ int c = usage->c, r = usage->r, cr = c*r;
+ int *nb[2];
+ unsigned char *set = scratch->set;
+ unsigned char *numbers = scratch->rowidx;
+ unsigned char *numbersleft = scratch->colidx;
+ int nnb, count;
+ int i, j, n, nbi;
+
+ nb[0] = scratch->mne;
+ nb[1] = scratch->mne + cr;
+
+ /*
+ * First, work out the mutual neighbour squares of the two. We
+ * can assert that they're not actually in the same block,
+ * which leaves two possibilities: they're in different block
+ * rows _and_ different block columns (thus their mutual
+ * neighbours are precisely the other two corners of the
+ * rectangle), or they're in the same row (WLOG) and different
+ * columns, in which case their mutual neighbours are the
+ * column of each block aligned with the other square.
+ *
+ * We divide the mutual neighbours into two separate subsets
+ * nb[0] and nb[1]; squares in the same subset are not only
+ * adjacent to both our key squares, but are also always
+ * adjacent to one another.
+ */
+ if (x1 / r != x2 / r && y1 % r != y2 % r) {
+ /* Corners of the rectangle. */
+ nnb = 1;
+ nb[0][0] = cubepos(x2, y1, 1);
+ nb[1][0] = cubepos(x1, y2, 1);
+ } else if (x1 / r != x2 / r) {
+ /* Same row of blocks; different blocks within that row. */
+ int x1b = x1 - (x1 % r);
+ int x2b = x2 - (x2 % r);
+
+ nnb = r;
+ for (i = 0; i < r; i++) {
+ nb[0][i] = cubepos(x2b+i, y1, 1);
+ nb[1][i] = cubepos(x1b+i, y2, 1);
+ }
+ } else {
+ /* Same column of blocks; different blocks within that column. */
+ int y1b = y1 % r;
+ int y2b = y2 % r;
+
+ assert(y1 % r != y2 % r);
+
+ nnb = c;
+ for (i = 0; i < c; i++) {
+ nb[0][i] = cubepos(x2, y1b+i*r, 1);
+ nb[1][i] = cubepos(x1, y2b+i*r, 1);
+ }
+ }
+
+ /*
+ * Right. Now loop over each possible number.
+ */
+ for (n = 1; n <= cr; n++) {
+ if (!cube(x1, y1, n))
+ continue;
+ for (j = 0; j < cr; j++)
+ numbersleft[j] = cube(x2, y2, j+1);
+
+ /*
+ * Go over every possible subset of each neighbour list,
+ * and see if its union of possible numbers minus n has the
+ * same size as the subset. If so, add the numbers in that
+ * subset to the set of things which would be ruled out
+ * from (x2,y2) if n were placed at (x1,y1).
+ */
+ memset(set, 0, nnb);
+ count = 0;
+ while (1) {
+ /*
+ * Binary increment: change the rightmost 0 to a 1, and
+ * change all 1s to the right of it to 0s.
+ */
+ i = nnb;
+ while (i > 0 && set[i-1])
+ set[--i] = 0, count--;
+ if (i > 0)
+ set[--i] = 1, count++;
+ else
+ break; /* done */
+
+ /*
+ * Examine this subset of each neighbour set.
+ */
+ for (nbi = 0; nbi < 2; nbi++) {
+ int *nbs = nb[nbi];
+
+ memset(numbers, 0, cr);
+
+ for (i = 0; i < nnb; i++)
+ if (set[i])
+ for (j = 0; j < cr; j++)
+ if (j != n-1 && usage->cube[nbs[i] + j])
+ numbers[j] = 1;
+
+ for (i = j = 0; j < cr; j++)
+ i += numbers[j];
+
+ if (i == count) {
+ /*
+ * Got one. This subset of nbs, in the absence
+ * of n, would definitely contain all the
+ * numbers listed in `numbers'. Rule them out
+ * of `numbersleft'.
+ */
+ for (j = 0; j < cr; j++)
+ if (numbers[j])
+ numbersleft[j] = 0;
+ }
+ }
+ }
+
+ /*
+ * If we've got nothing left in `numbersleft', we have a
+ * successful mutual neighbour elimination.
+ */
+ for (j = 0; j < cr; j++)
+ if (numbersleft[j])
+ break;
+
+ if (j == cr) {
+#ifdef STANDALONE_SOLVER
+ if (solver_show_working) {
+ printf("%*smutual neighbour elimination, (%d,%d) vs (%d,%d):\n",
+ solver_recurse_depth*4, "",
+ 1+x1, 1+YUNTRANS(y1), 1+x2, 1+YUNTRANS(y2));
+ printf("%*s ruling out %d at (%d,%d)\n",
+ solver_recurse_depth*4, "",
+ n, 1+x1, 1+YUNTRANS(y1));
+ }
+#endif
+ cube(x1, y1, n) = FALSE;
+ return +1;
+ }
+ }
+
+ return 0; /* nothing found */
+}
+