- * 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->neighbours;
- nb[1] = scratch->neighbours + 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 */
-}
-
-/*