+static int solve_puzzle(const game_state *state, unsigned char *grid,
+ int w, int h,
+ unsigned char *matrix, unsigned char *workspace,
+ unsigned int *changed_h, unsigned int *changed_w,
+ int *rowdata
+#ifdef STANDALONE_SOLVER
+ , int cluewid
+#else
+ , int dummy
+#endif
+ )
+{
+ int i, j, ok, max;
+ int max_h, max_w;
+
+ assert((state!=NULL && state->common->rowdata!=NULL) ^ (grid!=NULL));
+
+ max = max(w, h);
+
+ memset(matrix, 0, w*h);
+ if (state) {
+ for (i=0; i<w*h; i++) {
+ if (state->common->immutable[i])
+ matrix[i] = state->grid[i];
+ }
+ }
+
+ /* For each column, compute how many squares can be deduced
+ * from just the row-data and initial clues.
+ * Later, changed_* will hold how many squares were changed
+ * in every row/column in the previous iteration
+ * Changed_* is used to choose the next rows / cols to re-examine
+ */
+ for (i=0; i<h; i++) {
+ int freespace, rowlen;
+ if (state && state->common->rowdata) {
+ memcpy(rowdata, state->common->rowdata + state->common->rowsize*(w+i), max*sizeof(int));
+ rowlen = state->common->rowlen[w+i];
+ } else {
+ rowlen = compute_rowdata(rowdata, grid+i*w, w, 1);
+ }
+ rowdata[rowlen] = 0;
+ if (rowlen == 0) {
+ changed_h[i] = w;
+ } else {
+ for (j=0, freespace=w+1; rowdata[j]; j++)
+ freespace -= rowdata[j] + 1;
+ for (j=0, changed_h[i]=0; rowdata[j]; j++)
+ if (rowdata[j] > freespace)
+ changed_h[i] += rowdata[j] - freespace;
+ }
+ for (j = 0; j < w; j++)
+ if (matrix[i*w+j])
+ changed_h[i]++;
+ }
+ for (i=0,max_h=0; i<h; i++)
+ if (changed_h[i] > max_h)
+ max_h = changed_h[i];
+ for (i=0; i<w; i++) {
+ int freespace, rowlen;
+ if (state && state->common->rowdata) {
+ memcpy(rowdata, state->common->rowdata + state->common->rowsize*i, max*sizeof(int));
+ rowlen = state->common->rowlen[i];
+ } else {
+ rowlen = compute_rowdata(rowdata, grid+i, h, w);
+ }
+ rowdata[rowlen] = 0;
+ if (rowlen == 0) {
+ changed_w[i] = h;
+ } else {
+ for (j=0, freespace=h+1; rowdata[j]; j++)
+ freespace -= rowdata[j] + 1;
+ for (j=0, changed_w[i]=0; rowdata[j]; j++)
+ if (rowdata[j] > freespace)
+ changed_w[i] += rowdata[j] - freespace;
+ }
+ for (j = 0; j < h; j++)
+ if (matrix[j*w+i])
+ changed_w[i]++;
+ }
+ for (i=0,max_w=0; i<w; i++)
+ if (changed_w[i] > max_w)
+ max_w = changed_w[i];
+
+ /* Solve the puzzle.
+ * Process rows/columns individually. Deductions involving more than one
+ * row and/or column at a time are not supported.
+ * Take care to only process rows/columns which have been changed since they
+ * were previously processed.
+ * Also, prioritize rows/columns which have had the most changes since their
+ * previous processing, as they promise the greatest benefit.
+ * Extremely rectangular grids (e.g. 10x20, 15x40, etc.) are not treated specially.
+ */
+ do {
+ for (; max_h && max_h >= max_w; max_h--) {
+ for (i=0; i<h; i++) {
+ if (changed_h[i] >= max_h) {
+ if (state && state->common->rowdata) {
+ memcpy(rowdata, state->common->rowdata + state->common->rowsize*(w+i), max*sizeof(int));
+ rowdata[state->common->rowlen[w+i]] = 0;
+ } else {
+ rowdata[compute_rowdata(rowdata, grid+i*w, w, 1)] = 0;
+ }
+ do_row(workspace, workspace+max, workspace+2*max,
+ workspace+3*max, workspace+4*max,
+ workspace+5*max, workspace+6*max,
+ matrix+i*w, w, 1, rowdata, changed_w
+#ifdef STANDALONE_SOLVER
+ , "row", i+1, cluewid
+#endif
+ );
+ changed_h[i] = 0;
+ }
+ }
+ for (i=0,max_w=0; i<w; i++)
+ if (changed_w[i] > max_w)
+ max_w = changed_w[i];
+ }
+ for (; max_w && max_w >= max_h; max_w--) {
+ for (i=0; i<w; i++) {
+ if (changed_w[i] >= max_w) {
+ if (state && state->common->rowdata) {
+ memcpy(rowdata, state->common->rowdata + state->common->rowsize*i, max*sizeof(int));
+ rowdata[state->common->rowlen[i]] = 0;
+ } else {
+ rowdata[compute_rowdata(rowdata, grid+i, h, w)] = 0;
+ }
+ do_row(workspace, workspace+max, workspace+2*max,
+ workspace+3*max, workspace+4*max,
+ workspace+5*max, workspace+6*max,
+ matrix+i, h, w, rowdata, changed_h
+#ifdef STANDALONE_SOLVER
+ , "col", i+1, cluewid
+#endif
+ );
+ changed_w[i] = 0;
+ }
+ }
+ for (i=0,max_h=0; i<h; i++)
+ if (changed_h[i] > max_h)
+ max_h = changed_h[i];
+ }
+ } while (max_h>0 || max_w>0);
+
+ ok = TRUE;
+ for (i=0; i<h; i++) {
+ for (j=0; j<w; j++) {
+ if (matrix[i*w+j] == UNKNOWN)
+ ok = FALSE;
+ }
+ }
+
+ return ok;
+}
+
+#ifndef STANDALONE_PICTURE_GENERATOR