+static int nsolve_intersect(struct nsolve_usage *usage,
+ int start1, int step1, int start2, int step2
+#ifdef STANDALONE_SOLVER
+ , char *fmt, ...
+#endif
+ )
+{
+ int c = usage->c, r = usage->r, cr = c*r;
+ int ret, i;
+
+ /*
+ * Loop over the first domain and see if there's any set bit
+ * not also in the second.
+ */
+ for (i = 0; i < cr; i++) {
+ int p = start1+i*step1;
+ if (usage->cube[p] &&
+ !(p >= start2 && p < start2+cr*step2 &&
+ (p - start2) % step2 == 0))
+ return FALSE; /* there is, so we can't deduce */
+ }
+
+ /*
+ * We have determined that all set bits in the first domain are
+ * within its overlap with the second. So loop over the second
+ * domain and remove all set bits that aren't also in that
+ * overlap; return TRUE iff we actually _did_ anything.
+ */
+ ret = FALSE;
+ for (i = 0; i < cr; i++) {
+ int p = start2+i*step2;
+ if (usage->cube[p] &&
+ !(p >= start1 && p < start1+cr*step1 && (p - start1) % step1 == 0))
+ {
+#ifdef STANDALONE_SOLVER
+ if (solver_show_working) {
+ int px, py, pn;
+
+ if (!ret) {
+ va_list ap;
+ va_start(ap, fmt);
+ vprintf(fmt, ap);
+ va_end(ap);
+ printf(":\n");
+ }
+
+ pn = 1 + p % cr;
+ py = p / cr;
+ px = py / cr;
+ py %= cr;
+
+ printf(" ruling out %d at (%d,%d)\n",
+ pn, 1+px, 1+YUNTRANS(py));
+ }
+#endif
+ ret = TRUE; /* we did something */
+ usage->cube[p] = 0;
+ }
+ }
+
+ return ret;
+}
+
+static int nsolve_set(struct nsolve_usage *usage,
+ int start, int step1, int step2
+#ifdef STANDALONE_SOLVER
+ , char *fmt, ...
+#endif
+ )
+{
+ int c = usage->c, r = usage->r, cr = c*r;
+ int i, j, n, count;
+ unsigned char *grid = snewn(cr*cr, unsigned char);
+ unsigned char *rowidx = snewn(cr, unsigned char);
+ unsigned char *colidx = snewn(cr, unsigned char);
+ unsigned char *set = snewn(cr, unsigned char);
+
+ /*
+ * We are passed a cr-by-cr matrix of booleans. Our first job
+ * is to winnow it by finding any definite placements - i.e.
+ * any row with a solitary 1 - and discarding that row and the
+ * column containing the 1.
+ */
+ memset(rowidx, TRUE, cr);
+ memset(colidx, TRUE, cr);
+ for (i = 0; i < cr; i++) {
+ int count = 0, first = -1;
+ for (j = 0; j < cr; j++)
+ if (usage->cube[start+i*step1+j*step2])
+ first = j, count++;
+ if (count == 0) {
+ /*
+ * This condition actually marks a completely insoluble
+ * (i.e. internally inconsistent) puzzle. We return and
+ * report no progress made.
+ */
+ return FALSE;
+ }
+ if (count == 1)
+ rowidx[i] = colidx[first] = FALSE;
+ }
+
+ /*
+ * Convert each of rowidx/colidx from a list of 0s and 1s to a
+ * list of the indices of the 1s.
+ */
+ for (i = j = 0; i < cr; i++)
+ if (rowidx[i])
+ rowidx[j++] = i;
+ n = j;
+ for (i = j = 0; i < cr; i++)
+ if (colidx[i])
+ colidx[j++] = i;
+ assert(n == j);
+
+ /*
+ * And create the smaller matrix.
+ */
+ for (i = 0; i < n; i++)
+ for (j = 0; j < n; j++)
+ grid[i*cr+j] = usage->cube[start+rowidx[i]*step1+colidx[j]*step2];
+
+ /*
+ * Having done that, we now have a matrix in which every row
+ * has at least two 1s in. Now we search to see if we can find
+ * a rectangle of zeroes (in the set-theoretic sense of
+ * `rectangle', i.e. a subset of rows crossed with a subset of
+ * columns) whose width and height add up to n.
+ */
+
+ memset(set, 0, n);
+ count = 0;
+ while (1) {
+ /*
+ * We have a candidate set. If its size is <=1 or >=n-1
+ * then we move on immediately.
+ */
+ if (count > 1 && count < n-1) {
+ /*
+ * The number of rows we need is n-count. See if we can
+ * find that many rows which each have a zero in all
+ * the positions listed in `set'.
+ */
+ int rows = 0;
+ for (i = 0; i < n; i++) {
+ int ok = TRUE;
+ for (j = 0; j < n; j++)
+ if (set[j] && grid[i*cr+j]) {
+ ok = FALSE;
+ break;
+ }
+ if (ok)
+ rows++;
+ }
+
+ /*
+ * We expect never to be able to get _more_ than
+ * n-count suitable rows: this would imply that (for
+ * example) there are four numbers which between them
+ * have at most three possible positions, and hence it
+ * indicates a faulty deduction before this point or
+ * even a bogus clue.
+ */
+ assert(rows <= n - count);
+ if (rows >= n - count) {
+ int progress = FALSE;
+
+ /*
+ * We've got one! Now, for each row which _doesn't_
+ * satisfy the criterion, eliminate all its set
+ * bits in the positions _not_ listed in `set'.
+ * Return TRUE (meaning progress has been made) if
+ * we successfully eliminated anything at all.
+ *
+ * This involves referring back through
+ * rowidx/colidx in order to work out which actual
+ * positions in the cube to meddle with.
+ */
+ for (i = 0; i < n; i++) {
+ int ok = TRUE;
+ for (j = 0; j < n; j++)
+ if (set[j] && grid[i*cr+j]) {
+ ok = FALSE;
+ break;
+ }
+ if (!ok) {
+ for (j = 0; j < n; j++)
+ if (!set[j] && grid[i*cr+j]) {
+ int fpos = (start+rowidx[i]*step1+
+ colidx[j]*step2);
+#ifdef STANDALONE_SOLVER
+ if (solver_show_working) {
+ int px, py, pn;
+
+ if (!progress) {
+ va_list ap;
+ va_start(ap, fmt);
+ vprintf(fmt, ap);
+ va_end(ap);
+ printf(":\n");
+ }
+
+ pn = 1 + fpos % cr;
+ py = fpos / cr;
+ px = py / cr;
+ py %= cr;
+
+ printf(" ruling out %d at (%d,%d)\n",
+ pn, 1+px, 1+YUNTRANS(py));
+ }
+#endif
+ progress = TRUE;
+ usage->cube[fpos] = FALSE;
+ }
+ }
+ }
+
+ if (progress) {
+ sfree(set);
+ sfree(colidx);
+ sfree(rowidx);
+ sfree(grid);
+ return TRUE;
+ }
+ }
+ }
+
+ /*
+ * Binary increment: change the rightmost 0 to a 1, and
+ * change all 1s to the right of it to 0s.
+ */
+ i = n;
+ while (i > 0 && set[i-1])
+ set[--i] = 0, count--;
+ if (i > 0)
+ set[--i] = 1, count++;
+ else
+ break; /* done */
+ }
+
+ sfree(set);
+ sfree(colidx);
+ sfree(rowidx);
+ sfree(grid);
+
+ return FALSE;
+}
+
~mdw / sgt / puzzles / commitdiff