From 149255d7ed0f808783624fcaaf8c3449cf99c851 Mon Sep 17 00:00:00 2001 From: simon Date: Sat, 13 Jan 2007 14:44:50 +0000 Subject: [PATCH] Add James H's new puzzle, `Unequal' (otherwise known as the Guardian's `Futoshiki'). git-svn-id: svn://svn.tartarus.org/sgt/puzzles@7100 cda61777-01e9-0310-a592-d414129be87e --- latin.c | 1320 +++++++++++++++++++++++++++++++++++++++ latin.h | 114 ++++ puzzles.but | 69 +++ unequal.R | 23 + unequal.c | 1967 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 3493 insertions(+) create mode 100644 latin.c create mode 100644 latin.h create mode 100644 unequal.R create mode 100644 unequal.c diff --git a/latin.c b/latin.c new file mode 100644 index 0000000..fa981f2 --- /dev/null +++ b/latin.c @@ -0,0 +1,1320 @@ +#include +#include +#include + +#include "puzzles.h" +#include "tree234.h" +#include "maxflow.h" + +#ifdef STANDALONE_LATIN_TEST +#define STANDALONE_SOLVER +#endif + +#include "latin.h" + +/* -------------------------------------------------------- + * Solver. + */ + +/* + * Function called when we are certain that a particular square has + * a particular number in it. The y-coordinate passed in here is + * transformed. + */ +void latin_solver_place(struct latin_solver *solver, int x, int y, int n) +{ + int i, o = solver->o; + + assert(n <= o); + assert(cube(x,y,n)); + + /* + * Rule out all other numbers in this square. + */ + for (i = 1; i <= o; i++) + if (i != n) + cube(x,y,i) = FALSE; + + /* + * Rule out this number in all other positions in the row. + */ + for (i = 0; i < o; i++) + if (i != y) + cube(x,i,n) = FALSE; + + /* + * Rule out this number in all other positions in the column. + */ + for (i = 0; i < o; i++) + if (i != x) + cube(i,y,n) = FALSE; + + /* + * Enter the number in the result grid. + */ + solver->grid[YUNTRANS(y)*o+x] = n; + + /* + * Cross out this number from the list of numbers left to place + * in its row, its column and its block. + */ + solver->row[y*o+n-1] = solver->col[x*o+n-1] = TRUE; +} + +int latin_solver_elim(struct latin_solver *solver, int start, int step +#ifdef STANDALONE_SOLVER + , char *fmt, ... +#endif + ) +{ + int o = solver->o; + int fpos, m, i; + + /* + * Count the number of set bits within this section of the + * cube. + */ + m = 0; + fpos = -1; + for (i = 0; i < o; i++) + if (solver->cube[start+i*step]) { + fpos = start+i*step; + m++; + } + + if (m == 1) { + int x, y, n; + assert(fpos >= 0); + + n = 1 + fpos % o; + y = fpos / o; + x = y / o; + y %= o; + + if (!solver->grid[YUNTRANS(y)*o+x]) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + va_list ap; + printf("%*s", solver_recurse_depth*4, ""); + va_start(ap, fmt); + vprintf(fmt, ap); + va_end(ap); + printf(":\n%*s placing %d at (%d,%d)\n", + solver_recurse_depth*4, "", n, x, YUNTRANS(y)); + } +#endif + latin_solver_place(solver, x, y, n); + return +1; + } + } else if (m == 0) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + va_list ap; + printf("%*s", solver_recurse_depth*4, ""); + va_start(ap, fmt); + vprintf(fmt, ap); + va_end(ap); + printf(":\n%*s no possibilities available\n", + solver_recurse_depth*4, ""); + } +#endif + return -1; + } + + return 0; +} + +struct latin_solver_scratch { + unsigned char *grid, *rowidx, *colidx, *set; + int *neighbours, *bfsqueue; +#ifdef STANDALONE_SOLVER + int *bfsprev; +#endif +}; + +int latin_solver_set(struct latin_solver *solver, + struct latin_solver_scratch *scratch, + int start, int step1, int step2 +#ifdef STANDALONE_SOLVER + , char *fmt, ... +#endif + ) +{ + int o = solver->o; + int i, j, n, count; + unsigned char *grid = scratch->grid; + unsigned char *rowidx = scratch->rowidx; + unsigned char *colidx = scratch->colidx; + unsigned char *set = scratch->set; + + /* + * We are passed a o-by-o 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, o); + memset(colidx, TRUE, o); + for (i = 0; i < o; i++) { + int count = 0, first = -1; + for (j = 0; j < o; j++) + if (solver->cube[start+i*step1+j*step2]) + first = j, count++; + + if (count == 0) return -1; + 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 < o; i++) + if (rowidx[i]) + rowidx[j++] = i; + n = j; + for (i = j = 0; i < o; 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*o+j] = solver->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*o+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. + */ + if (rows > n - count) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + va_list ap; + printf("%*s", solver_recurse_depth*4, + ""); + va_start(ap, fmt); + vprintf(fmt, ap); + va_end(ap); + printf(":\n%*s contradiction reached\n", + solver_recurse_depth*4, ""); + } +#endif + return -1; + } + + 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 +1 (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*o+j]) { + ok = FALSE; + break; + } + if (!ok) { + for (j = 0; j < n; j++) + if (!set[j] && grid[i*o+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; + printf("%*s", solver_recurse_depth*4, + ""); + va_start(ap, fmt); + vprintf(fmt, ap); + va_end(ap); + printf(":\n"); + } + + pn = 1 + fpos % o; + py = fpos / o; + px = py / o; + py %= o; + + printf("%*s ruling out %d at (%d,%d)\n", + solver_recurse_depth*4, "", + pn, px, YUNTRANS(py)); + } +#endif + progress = TRUE; + solver->cube[fpos] = FALSE; + } + } + } + + if (progress) { + return +1; + } + } + } + + /* + * 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 */ + } + + return 0; +} + +/* + * Look for forcing chains. A forcing chain is a path of + * pairwise-exclusive squares (i.e. each pair of adjacent squares + * in the path are in the same row, column or block) with the + * following properties: + * + * (a) Each square on the path has precisely two possible numbers. + * + * (b) Each pair of squares which are adjacent on the path share + * at least one possible number in common. + * + * (c) Each square in the middle of the path shares _both_ of its + * numbers with at least one of its neighbours (not the same + * one with both neighbours). + * + * These together imply that at least one of the possible number + * choices at one end of the path forces _all_ the rest of the + * numbers along the path. In order to make real use of this, we + * need further properties: + * + * (c) Ruling out some number N from the square at one end + * of the path forces the square at the other end to + * take number N. + * + * (d) The two end squares are both in line with some third + * square. + * + * (e) That third square currently has N 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 number N, and that + * therefore the mutually adjacent third square does not. + * + * To find forcing chains, we're going to start a bfs at each + * suitable square, once for each of its two possible numbers. + */ +int latin_solver_forcing(struct latin_solver *solver, + struct latin_solver_scratch *scratch) +{ + int o = solver->o; + int *bfsqueue = scratch->bfsqueue; +#ifdef STANDALONE_SOLVER + int *bfsprev = scratch->bfsprev; +#endif + unsigned char *number = scratch->grid; + int *neighbours = scratch->neighbours; + int x, y; + + for (y = 0; y < o; y++) + for (x = 0; x < o; x++) { + int count, t, n; + + /* + * If this square doesn't have exactly two candidate + * numbers, don't try it. + * + * In this loop we also sum the candidate numbers, + * which is a nasty hack to allow us to quickly find + * `the other one' (since we will shortly know there + * are exactly two). + */ + for (count = t = 0, n = 1; n <= o; n++) + if (cube(x, y, n)) + count++, t += n; + if (count != 2) + continue; + + /* + * Now attempt a bfs for each candidate. + */ + for (n = 1; n <= o; n++) + if (cube(x, y, n)) { + int orign, currn, head, tail; + + /* + * Begin a bfs. + */ + orign = n; + + memset(number, o+1, o*o); + head = tail = 0; + bfsqueue[tail++] = y*o+x; +#ifdef STANDALONE_SOLVER + bfsprev[y*o+x] = -1; +#endif + number[y*o+x] = t - n; + + while (head < tail) { + int xx, yy, nneighbours, xt, yt, i; + + xx = bfsqueue[head++]; + yy = xx / o; + xx %= o; + + currn = number[yy*o+xx]; + + /* + * Find neighbours of yy,xx. + */ + nneighbours = 0; + for (yt = 0; yt < o; yt++) + neighbours[nneighbours++] = yt*o+xx; + for (xt = 0; xt < o; xt++) + neighbours[nneighbours++] = yy*o+xt; + + /* + * Try visiting each of those neighbours. + */ + for (i = 0; i < nneighbours; i++) { + int cc, tt, nn; + + xt = neighbours[i] % o; + yt = neighbours[i] / o; + + /* + * We need this square to not be + * already visited, and to include + * currn as a possible number. + */ + if (number[yt*o+xt] <= o) + continue; + if (!cube(xt, yt, currn)) + continue; + + /* + * Don't visit _this_ square a second + * time! + */ + if (xt == xx && yt == yy) + continue; + + /* + * To continue with the bfs, we need + * this square to have exactly two + * possible numbers. + */ + for (cc = tt = 0, nn = 1; nn <= o; nn++) + if (cube(xt, yt, nn)) + cc++, tt += nn; + if (cc == 2) { + bfsqueue[tail++] = yt*o+xt; +#ifdef STANDALONE_SOLVER + bfsprev[yt*o+xt] = yy*o+xx; +#endif + number[yt*o+xt] = tt - currn; + } + + /* + * One other possibility is that this + * might be the square in which we can + * make a real deduction: if it's + * adjacent to x,y, and currn is equal + * to the original number we ruled out. + */ + if (currn == orign && + (xt == x || yt == y)) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + char *sep = ""; + int xl, yl; + printf("%*sforcing chain, %d at ends of ", + solver_recurse_depth*4, "", orign); + xl = xx; + yl = yy; + while (1) { + printf("%s(%d,%d)", sep, xl, + YUNTRANS(yl)); + xl = bfsprev[yl*o+xl]; + if (xl < 0) + break; + yl = xl / o; + xl %= o; + sep = "-"; + } + printf("\n%*s ruling out %d at (%d,%d)\n", + solver_recurse_depth*4, "", + orign, xt, YUNTRANS(yt)); + } +#endif + cube(xt, yt, orign) = FALSE; + return 1; + } + } + } + } + } + + return 0; +} + +struct latin_solver_scratch *latin_solver_new_scratch(struct latin_solver *solver) +{ + struct latin_solver_scratch *scratch = snew(struct latin_solver_scratch); + int o = solver->o; + scratch->grid = snewn(o*o, unsigned char); + scratch->rowidx = snewn(o, unsigned char); + scratch->colidx = snewn(o, unsigned char); + scratch->set = snewn(o, unsigned char); + scratch->neighbours = snewn(3*o, int); + scratch->bfsqueue = snewn(o*o, int); +#ifdef STANDALONE_SOLVER + scratch->bfsprev = snewn(o*o, int); +#endif + return scratch; +} + +void latin_solver_free_scratch(struct latin_solver_scratch *scratch) +{ +#ifdef STANDALONE_SOLVER + sfree(scratch->bfsprev); +#endif + sfree(scratch->bfsqueue); + sfree(scratch->neighbours); + sfree(scratch->set); + sfree(scratch->colidx); + sfree(scratch->rowidx); + sfree(scratch->grid); + sfree(scratch); +} + +void latin_solver_alloc(struct latin_solver *solver, digit *grid, int o) +{ + int x, y; + + solver->o = o; + solver->cube = snewn(o*o*o, unsigned char); + solver->grid = grid; /* write straight back to the input */ + memset(solver->cube, TRUE, o*o*o); + + solver->row = snewn(o*o, unsigned char); + solver->col = snewn(o*o, unsigned char); + memset(solver->row, FALSE, o*o); + memset(solver->col, FALSE, o*o); + + for (x = 0; x < o; x++) + for (y = 0; y < o; y++) + if (grid[y*o+x]) + latin_solver_place(solver, x, YTRANS(y), grid[y*o+x]); +} + +void latin_solver_free(struct latin_solver *solver) +{ + sfree(solver->cube); + sfree(solver->row); + sfree(solver->col); +} + +int latin_solver_diff_simple(struct latin_solver *solver) +{ + int x, y, n, ret, o = solver->o; + /* + * Row-wise positional elimination. + */ + for (y = 0; y < o; y++) + for (n = 1; n <= o; n++) + if (!solver->row[y*o+n-1]) { + ret = latin_solver_elim(solver, cubepos(0,y,n), o*o +#ifdef STANDALONE_SOLVER + , "positional elimination," + " %d in row %d", n, YUNTRANS(y) +#endif + ); + if (ret != 0) return ret; + } + /* + * Column-wise positional elimination. + */ + for (x = 0; x < o; x++) + for (n = 1; n <= o; n++) + if (!solver->col[x*o+n-1]) { + ret = latin_solver_elim(solver, cubepos(x,0,n), o +#ifdef STANDALONE_SOLVER + , "positional elimination," + " %d in column %d", n, x +#endif + ); + if (ret != 0) return ret; + } + + /* + * Numeric elimination. + */ + for (x = 0; x < o; x++) + for (y = 0; y < o; y++) + if (!solver->grid[YUNTRANS(y)*o+x]) { + ret = latin_solver_elim(solver, cubepos(x,y,1), 1 +#ifdef STANDALONE_SOLVER + , "numeric elimination at (%d,%d)", x, + YUNTRANS(y) +#endif + ); + if (ret != 0) return ret; + } + return 0; +} + +int latin_solver_diff_set(struct latin_solver *solver, + struct latin_solver_scratch *scratch, + int *extreme) +{ + int x, y, n, ret, o = solver->o; + /* + * Row-wise set elimination. + */ + for (y = 0; y < o; y++) { + ret = latin_solver_set(solver, scratch, cubepos(0,y,1), o*o, 1 +#ifdef STANDALONE_SOLVER + , "set elimination, row %d", YUNTRANS(y) +#endif + ); + if (ret > 0) *extreme = 0; + if (ret != 0) return ret; + } + + /* + * Column-wise set elimination. + */ + for (x = 0; x < o; x++) { + ret = latin_solver_set(solver, scratch, cubepos(x,0,1), o, 1 +#ifdef STANDALONE_SOLVER + , "set elimination, column %d", x +#endif + ); + if (ret > 0) *extreme = 0; + if (ret != 0) return ret; + } + + /* + * Row-vs-column set elimination on a single number. + */ + for (n = 1; n <= o; n++) { + ret = latin_solver_set(solver, scratch, cubepos(0,0,n), o*o, o +#ifdef STANDALONE_SOLVER + , "positional set elimination, number %d", n +#endif + ); + if (ret > 0) *extreme = 1; + if (ret != 0) return ret; + } + return 0; +} + +/* This uses our own diff_* internally, but doesn't require callers + * to; this is so it can be used by games that want to rewrite + * the solver so as to use a different set of difficulties. + * + * It returns: + * 0 for 'didn't do anything' implying it was already solved. + * -1 for 'impossible' (no solution) + * 1 for 'single solution' + * >1 for 'multiple solutions' (you don't get to know how many, and + * the first such solution found will be set. + * + * and this function may well assert if given an impossible board. + */ +int latin_solver_recurse(struct latin_solver *solver, int recdiff, + latin_solver_callback cb, void *ctx) +{ + int best, bestcount; + int o = solver->o, x, y, n; + + best = -1; + bestcount = o+1; + + for (y = 0; y < o; y++) + for (x = 0; x < o; x++) + if (!solver->grid[y*o+x]) { + int count; + + /* + * An unfilled square. Count the number of + * possible digits in it. + */ + count = 0; + for (n = 1; n <= o; n++) + if (cube(x,YTRANS(y),n)) + count++; + + /* + * We should have found any impossibilities + * already, so this can safely be an assert. + */ + assert(count > 1); + + if (count < bestcount) { + bestcount = count; + best = y*o+x; + } + } + + if (best == -1) + /* we were complete already. */ + return 0; + else { + int i, j; + digit *list, *ingrid, *outgrid; + int diff = diff_impossible; /* no solution found yet */ + + /* + * Attempt recursion. + */ + y = best / o; + x = best % o; + + list = snewn(o, digit); + ingrid = snewn(o*o, digit); + outgrid = snewn(o*o, digit); + memcpy(ingrid, solver->grid, o*o); + + /* Make a list of the possible digits. */ + for (j = 0, n = 1; n <= o; n++) + if (cube(x,YTRANS(y),n)) + list[j++] = n; + +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + char *sep = ""; + printf("%*srecursing on (%d,%d) [", + solver_recurse_depth*4, "", x, y); + for (i = 0; i < j; i++) { + printf("%s%d", sep, list[i]); + sep = " or "; + } + printf("]\n"); + } +#endif + + /* + * And step along the list, recursing back into the + * main solver at every stage. + */ + for (i = 0; i < j; i++) { + int ret; + + memcpy(outgrid, ingrid, o*o); + outgrid[y*o+x] = list[i]; + +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("%*sguessing %d at (%d,%d)\n", + solver_recurse_depth*4, "", list[i], x, y); + solver_recurse_depth++; +#endif + + ret = cb(outgrid, o, recdiff, ctx); + +#ifdef STANDALONE_SOLVER + solver_recurse_depth--; + if (solver_show_working) { + printf("%*sretracting %d at (%d,%d)\n", + solver_recurse_depth*4, "", list[i], x, y); + } +#endif + /* we recurse as deep as we can, so we should never find + * find ourselves giving up on a puzzle without declaring it + * impossible. */ + assert(ret != diff_unfinished); + + /* + * If we have our first solution, copy it into the + * grid we will return. + */ + if (diff == diff_impossible && ret != diff_impossible) + memcpy(solver->grid, outgrid, o*o); + + if (ret == diff_ambiguous) + diff = diff_ambiguous; + else if (ret == diff_impossible) + /* do not change our return value */; + else { + /* the recursion turned up exactly one solution */ + if (diff == diff_impossible) + diff = recdiff; + else + diff = diff_ambiguous; + } + + /* + * As soon as we've found more than one solution, + * give up immediately. + */ + if (diff == diff_ambiguous) + break; + } + + sfree(outgrid); + sfree(ingrid); + sfree(list); + + if (diff == diff_impossible) + return -1; + else if (diff == diff_ambiguous) + return 2; + else { + assert(diff == recdiff); + return 1; + } + } +} + +enum { diff_simple = 1, diff_set, diff_extreme, diff_recursive }; + +static int latin_solver_sub(struct latin_solver *solver, int maxdiff, void *ctx) +{ + struct latin_solver_scratch *scratch = latin_solver_new_scratch(solver); + int ret, diff = diff_simple, extreme; + + assert(maxdiff <= diff_recursive); + /* + * Now loop over the grid repeatedly trying all permitted modes + * of reasoning. The loop terminates if we complete an + * iteration without making any progress; we then return + * failure or success depending on whether the grid is full or + * not. + */ + while (1) { + /* + * I'd like to write `continue;' inside each of the + * following loops, so that the solver returns here after + * making some progress. However, I can't specify that I + * want to continue an outer loop rather than the innermost + * one, so I'm apologetically resorting to a goto. + */ + cont: + latin_solver_debug(solver->cube, solver->o); + + ret = latin_solver_diff_simple(solver); + if (ret < 0) { + diff = diff_impossible; + goto got_result; + } else if (ret > 0) { + diff = max(diff, diff_simple); + goto cont; + } + + if (maxdiff <= diff_simple) + break; + + ret = latin_solver_diff_set(solver, scratch, &extreme); + if (ret < 0) { + diff = diff_impossible; + goto got_result; + } else if (ret > 0) { + diff = max(diff, extreme ? diff_extreme : diff_set); + goto cont; + } + + if (maxdiff <= diff_set) + break; + + /* + * Forcing chains. + */ + if (latin_solver_forcing(solver, scratch)) { + diff = max(diff, diff_extreme); + goto cont; + } + + /* + * If we reach here, we have made no deductions in this + * iteration, so the algorithm terminates. + */ + break; + } + + /* + * Last chance: if we haven't fully solved the puzzle yet, try + * recursing based on guesses for a particular square. We pick + * one of the most constrained empty squares we can find, which + * has the effect of pruning the search tree as much as + * possible. + */ + if (maxdiff == diff_recursive) { + int nsol = latin_solver_recurse(solver, diff_recursive, latin_solver, ctx); + if (nsol < 0) diff = diff_impossible; + else if (nsol == 1) diff = diff_recursive; + else if (nsol > 1) diff = diff_ambiguous; + /* if nsol == 0 then we were complete anyway + * (and thus don't need to change diff) */ + } else { + /* + * We're forbidden to use recursion, so we just see whether + * our grid is fully solved, and return diff_unfinished + * otherwise. + */ + int x, y, o = solver->o; + + for (y = 0; y < o; y++) + for (x = 0; x < o; x++) + if (!solver->grid[y*o+x]) + diff = diff_unfinished; + } + + got_result: + +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("%*s%s found\n", + solver_recurse_depth*4, "", + diff == diff_impossible ? "no solution (impossible)" : + diff == diff_unfinished ? "no solution (unfinished)" : + diff == diff_ambiguous ? "multiple solutions" : + "one solution"); +#endif + + latin_solver_free_scratch(scratch); + + return diff; +} + +int latin_solver(digit *grid, int o, int maxdiff, void *ctx) +{ + struct latin_solver solver; + int diff; + + latin_solver_alloc(&solver, grid, o); + diff = latin_solver_sub(&solver, maxdiff, ctx); + latin_solver_free(&solver); + return diff; +} + +void latin_solver_debug(unsigned char *cube, int o) +{ +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + struct latin_solver ls, *solver = &ls; + char *dbg; + int x, y, i, c = 0; + + ls.cube = cube; ls.o = o; /* for cube() to work */ + + dbg = snewn(3*o*o*o, unsigned char); + for (y = 0; y < o; y++) { + for (x = 0; x < o; x++) { + for (i = 1; i <= o; i++) { + if (cube(x,y,i)) + dbg[c++] = i + '0'; + else + dbg[c++] = '.'; + } + dbg[c++] = ' '; + } + dbg[c++] = '\n'; + } + dbg[c++] = '\n'; + dbg[c++] = '\0'; + + printf("%s", dbg); + sfree(dbg); + } +#endif +} + +void latin_debug(digit *sq, int o) +{ +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + int x, y; + + for (y = 0; y < o; y++) { + for (x = 0; x < o; x++) { + printf("%2d ", sq[y*o+x]); + } + printf("\n"); + } + printf("\n"); + } +#endif +} + +/* -------------------------------------------------------- + * Generation. + */ + +digit *latin_generate(int o, random_state *rs) +{ + digit *sq; + int *edges, *backedges, *capacity, *flow; + void *scratch; + int ne, scratchsize; + int i, j, k; + digit *row, *col, *numinv, *num; + + /* + * To efficiently generate a latin square in such a way that + * all possible squares are possible outputs from the function, + * we make use of a theorem which states that any r x n latin + * rectangle, with r < n, can be extended into an (r+1) x n + * latin rectangle. In other words, we can reliably generate a + * latin square row by row, by at every stage writing down any + * row at all which doesn't conflict with previous rows, and + * the theorem guarantees that we will never have to backtrack. + * + * To find a viable row at each stage, we can make use of the + * support functions in maxflow.c. + */ + + sq = snewn(o*o, digit); + + /* + * In case this method of generation introduces a really subtle + * top-to-bottom directional bias, we'll generate the rows in + * random order. + */ + row = snewn(o, digit); + col = snewn(o, digit); + numinv = snewn(o, digit); + num = snewn(o, digit); + for (i = 0; i < o; i++) + row[i] = i; + shuffle(row, i, sizeof(*row), rs); + + /* + * Set up the infrastructure for the maxflow algorithm. + */ + scratchsize = maxflow_scratch_size(o * 2 + 2); + scratch = smalloc(scratchsize); + backedges = snewn(o*o + 2*o, int); + edges = snewn((o*o + 2*o) * 2, int); + capacity = snewn(o*o + 2*o, int); + flow = snewn(o*o + 2*o, int); + /* Set up the edge array, and the initial capacities. */ + ne = 0; + for (i = 0; i < o; i++) { + /* Each LHS vertex is connected to all RHS vertices. */ + for (j = 0; j < o; j++) { + edges[ne*2] = i; + edges[ne*2+1] = j+o; + /* capacity for this edge is set later on */ + ne++; + } + } + for (i = 0; i < o; i++) { + /* Each RHS vertex is connected to the distinguished sink vertex. */ + edges[ne*2] = i+o; + edges[ne*2+1] = o*2+1; + capacity[ne] = 1; + ne++; + } + for (i = 0; i < o; i++) { + /* And the distinguished source vertex connects to each LHS vertex. */ + edges[ne*2] = o*2; + edges[ne*2+1] = i; + capacity[ne] = 1; + ne++; + } + assert(ne == o*o + 2*o); + /* Now set up backedges. */ + maxflow_setup_backedges(ne, edges, backedges); + + /* + * Now generate each row of the latin square. + */ + for (i = 0; i < o; i++) { + /* + * To prevent maxflow from behaving deterministically, we + * separately permute the columns and the digits for the + * purposes of the algorithm, differently for every row. + */ + for (j = 0; j < o; j++) + col[j] = num[j] = j; + shuffle(col, j, sizeof(*col), rs); + /* We need the num permutation in both forward and inverse forms. */ + for (j = 0; j < o; j++) + numinv[num[j]] = j; + + /* + * Set up the capacities for the maxflow run, by examining + * the existing latin square. + */ + for (j = 0; j < o*o; j++) + capacity[j] = 1; + for (j = 0; j < i; j++) + for (k = 0; k < o; k++) { + int n = num[sq[row[j]*o + col[k]] - 1]; + capacity[k*o+n] = 0; + } + + /* + * Run maxflow. + */ + j = maxflow_with_scratch(scratch, o*2+2, 2*o, 2*o+1, ne, + edges, backedges, capacity, flow, NULL); + assert(j == o); /* by the above theorem, this must have succeeded */ + + /* + * And examine the flow array to pick out the new row of + * the latin square. + */ + for (j = 0; j < o; j++) { + for (k = 0; k < o; k++) { + if (flow[j*o+k]) + break; + } + assert(k < o); + sq[row[i]*o + col[j]] = numinv[k] + 1; + } + } + + /* + * Done. Free our internal workspaces... + */ + sfree(flow); + sfree(capacity); + sfree(edges); + sfree(backedges); + sfree(scratch); + sfree(numinv); + sfree(num); + sfree(col); + sfree(row); + + /* + * ... and return our completed latin square. + */ + return sq; +} + +/* -------------------------------------------------------- + * Checking. + */ + +typedef struct lcparams { + digit elt; + int count; +} lcparams; + +static int latin_check_cmp(void *v1, void *v2) +{ + lcparams *lc1 = (lcparams *)v1; + lcparams *lc2 = (lcparams *)v2; + + if (lc1->elt < lc2->elt) return -1; + if (lc1->elt > lc2->elt) return 1; + return 0; +} + +#define ELT(sq,x,y) (sq[((y)*order)+(x)]) + +/* returns non-zero if sq is not a latin square. */ +int latin_check(digit *sq, int order) +{ + tree234 *dict = newtree234(latin_check_cmp); + int c, r; + int ret = 0; + lcparams *lcp, lc; + + /* Use a tree234 as a simple hash table, go through the square + * adding elements as we go or incrementing their counts. */ + for (c = 0; c < order; c++) { + for (r = 0; r < order; r++) { + lc.elt = ELT(sq, c, r); lc.count = 0; + lcp = find234(dict, &lc, NULL); + if (!lcp) { + lcp = snew(lcparams); + lcp->elt = ELT(sq, c, r); + lcp->count = 1; + assert(add234(dict, lcp) == lcp); + } else { + lcp->count++; + } + } + } + + /* There should be precisely 'order' letters in the alphabet, + * each occurring 'order' times (making the OxO tree) */ + if (count234(dict) != order) ret = 1; + else { + for (c = 0; (lcp = index234(dict, c)) != NULL; c++) { + if (lcp->count != order) ret = 1; + } + } + for (c = 0; (lcp = index234(dict, c)) != NULL; c++) + sfree(lcp); + freetree234(dict); + + return ret; +} + + +/* -------------------------------------------------------- + * Testing (and printing). + */ + +#ifdef STANDALONE_LATIN_TEST + +#include +#include + +const char *quis; + +static void latin_print(digit *sq, int order) +{ + int x, y; + + for (y = 0; y < order; y++) { + for (x = 0; x < order; x++) { + printf("%2u ", ELT(sq, x, y)); + } + printf("\n"); + } + printf("\n"); +} + +static void gen(int order, random_state *rs, int debug) +{ + digit *sq; + + solver_show_working = debug; + + sq = latin_generate(order, rs); + latin_print(sq, order); + if (latin_check(sq, order)) { + fprintf(stderr, "Square is not a latin square!"); + exit(1); + } + + sfree(sq); +} + +void test_soak(int order, random_state *rs) +{ + digit *sq; + int n = 0; + time_t tt_start, tt_now, tt_last; + + solver_show_working = 0; + tt_now = tt_start = time(NULL); + + while(1) { + sq = latin_generate(order, rs); + sfree(sq); + n++; + + tt_last = time(NULL); + if (tt_last > tt_now) { + tt_now = tt_last; + printf("%d total, %3.1f/s\n", n, + (double)n / (double)(tt_now - tt_start)); + } + } +} + +void usage_exit(const char *msg) +{ + if (msg) + fprintf(stderr, "%s: %s\n", quis, msg); + fprintf(stderr, "Usage: %s [--seed SEED] --soak | [game_id [game_id ...]]\n", quis); + exit(1); +} + +int main(int argc, char *argv[]) +{ + int i, soak = 0; + random_state *rs; + time_t seed = time(NULL); + + quis = argv[0]; + while (--argc > 0) { + const char *p = *++argv; + if (!strcmp(p, "--soak")) + soak = 1; + else if (!strcmp(p, "--seed")) { + if (argc == 0) + usage_exit("--seed needs an argument"); + seed = (time_t)atoi(*++argv); + argc--; + } else if (*p == '-') + usage_exit("unrecognised option"); + else + break; /* finished options */ + } + + rs = random_new((void*)&seed, sizeof(time_t)); + + if (soak == 1) { + if (argc != 1) usage_exit("only one argument for --soak"); + test_soak(atoi(*argv), rs); + } else { + if (argc > 0) { + for (i = 0; i < argc; i++) { + gen(atoi(*argv++), rs, 1); + } + } else { + while (1) { + i = random_upto(rs, 20) + 1; + gen(i, rs, 0); + } + } + } + random_free(rs); + return 0; +} + +#endif + +/* vim: set shiftwidth=4 tabstop=8: */ diff --git a/latin.h b/latin.h new file mode 100644 index 0000000..f312cf9 --- /dev/null +++ b/latin.h @@ -0,0 +1,114 @@ +#ifndef LATIN_H +#define LATIN_H + +#include "puzzles.h" + +typedef unsigned char digit; + +/* --- Solver structures, definitions --- */ + +#ifdef STANDALONE_SOLVER +int solver_show_working, solver_recurse_depth; +#endif + +struct latin_solver { + int o; /* order of latin square */ + unsigned char *cube; /* o^3, indexed by x, y, and digit: + TRUE in that position indicates a possibility */ + digit *grid; /* o^2, indexed by x and y: for final deductions */ + + unsigned char *row; /* o^2: row[y*cr+n-1] TRUE if n is in row y */ + unsigned char *col; /* o^2: col[x*cr+n-1] TRUE if n is in col x */ +}; +#define cubepos(x,y,n) (((x)*solver->o+(y))*solver->o+(n)-1) +#define cube(x,y,n) (solver->cube[cubepos(x,y,n)]) + +#define gridpos(x,y) ((y)*solver->o+(x)) +#define grid(x,y) (solver->grid[gridpos(x,y)]) + +/* A solo solver using this code would need these defined. See solo.c. */ +#ifndef YTRANS +#define YTRANS(y) (y) +#endif +#ifndef YUNTRANS +#define YUNTRANS(y) (y) +#endif + + +/* --- Solver individual strategies --- */ + +/* Place a value at a specific location. */ +void latin_solver_place(struct latin_solver *solver, int x, int y, int n); + +/* Positional elimination. */ +int latin_solver_elim(struct latin_solver *solver, int start, int step +#ifdef STANDALONE_SOLVER + , char *fmt, ... +#endif + ); + +struct latin_solver_scratch; /* private to latin.c */ +/* Set elimination */ +int latin_solver_set(struct latin_solver *solver, + struct latin_solver_scratch *scratch, + int start, int step1, int step2 +#ifdef STANDALONE_SOLVER + , char *fmt, ... +#endif + ); + +/* Forcing chains */ +int latin_solver_forcing(struct latin_solver *solver, + struct latin_solver_scratch *scratch); + + +/* --- Solver allocation --- */ + +/* Fills in (and allocates members for) a latin_solver struct. + * Will allocate members of snew, but not snew itself + * (allowing 'struct latin_solver' to be the first element in a larger + * struct, for example). */ +void latin_solver_alloc(struct latin_solver *solver, digit *grid, int o); +void latin_solver_free(struct latin_solver *solver); + +/* Allocates scratch space (for _set and _forcing) */ +struct latin_solver_scratch * + latin_solver_new_scratch(struct latin_solver *solver); +void latin_solver_free_scratch(struct latin_solver_scratch *scratch); + + +/* --- Solver guts --- */ + +/* Looped positional elimination */ +int latin_solver_diff_simple(struct latin_solver *solver); + +/* Looped set elimination; *extreme is set if it used + * the more difficult single-number elimination. */ +int latin_solver_diff_set(struct latin_solver *solver, + struct latin_solver_scratch *scratch, + int *extreme); + +typedef int (latin_solver_callback)(digit *, int, int, void*); +/* Use to provide a standard way of dealing with solvers which can recurse; + * pass in your enumeration for 'recursive diff' and your solver + * callback. Returns #solutions (0 == already solved). */ +int latin_solver_recurse(struct latin_solver *solver, int recdiff, + latin_solver_callback cb, void *ctx); + +/* Individual puzzles should use their enumerations for their + * own difficulty levels, ensuring they don't clash with these. */ +enum { diff_impossible = 10, diff_ambiguous, diff_unfinished }; +int latin_solver(digit *grid, int order, int maxdiff, void *unused); + +void latin_solver_debug(unsigned char *cube, int o); + +/* --- Generation and checking --- */ + +digit *latin_generate_quick(int o, random_state *rs); +digit *latin_generate(int o, random_state *rs); + +int latin_check(digit *sq, int order); /* !0 => not a latin square */ + +void latin_debug(digit *sq, int order); + +#endif diff --git a/puzzles.but b/puzzles.but index 154ba6e..5bee392 100644 --- a/puzzles.but +++ b/puzzles.but @@ -2073,6 +2073,75 @@ possible islands; low expansion factors can create lots of tightly-packed islands. +\C{unequal} \i{Unequal} + +\cfg{winhelp-topic}{games.unequal} + +You have a square grid; each square may contain a digit from 1 to +the size of the grid, and some squares have greater-signs between +them. Your aim is to fully populate the grid with numbers such that: + +\b Each row contains only one occurrence of each digit + +\b Each column contains only one occurrence of each digit + +\b All the greater-than signs are satisfied. + +In 'Trivial' mode, there are no greater-than signs; the puzzle is +to solve the latin square only. + +At the time of writing, this puzzle is appearing in the Guardian +weekly under the name 'Futoshiki'. + +Unequal was contributed to this collection by James Harvey. + +\H{unequal-controls} \i{Unequal controls} + +\IM{Unequal controls} controls, for Unequal + +Unequal shares much of its control system with Solo. + +To play Unequal, simply click the mouse in any empty square and then +type a digit or letter on the keyboard to fill that square. If you +make a mistake, click the mouse in the incorrect square and press +Space to clear it again (or use the Undo feature). + +If you \e{right}-click in a square and then type a number, that +number will be entered in the square as a \q{pencil mark}. You can +have pencil marks for multiple numbers in the same square. + +The game pays no attention to pencil marks, so exactly what you use +them for is up to you: you can use them as reminders that a +particular square needs to be re-examined once you know more about a +particular number, or you can use them as lists of the possible +numbers in a given square, or anything else you feel like. + +To erase a single pencil mark, right-click in the square and type +the same number again. + +All pencil marks in a square are erased when you left-click and type +a number, or when you left-click and press space. Right-clicking and +pressing space will also erase pencil marks. + +(All the actions described in \k{common-actions} are also available.) + +\H{unequal-parameters} \I{parameters, for Unequal}Unequal parameters + +These parameters are available from the \q{Custom...} option on the +\q{Type} menu. + +\dt \e{Size (s*s)} + +\dd Size of grid. + +\dt \e{Difficulty} + +\dd Controls the difficulty of the generated puzzle. At Trivial level, +there are no greater-than signs (the puzzle is to solve the latin +square only); at Tricky level, some recursion may be required (but the +solutions should always be unique). + + \A{licence} \I{MIT licence}\ii{Licence} This software is \i{copyright} 2004-2007 Simon Tatham. diff --git a/unequal.R b/unequal.R new file mode 100644 index 0000000..49d4343 --- /dev/null +++ b/unequal.R @@ -0,0 +1,23 @@ +# -*- makefile -*- + +UNEQUAL = unequal latin tree234 maxflow + +unequal : [X] GTK COMMON UNEQUAL + +unequal : [G] WINDOWS COMMON UNEQUAL + +unequalsolver : [U] unequal[STANDALONE_SOLVER] latin[STANDALONE_SOLVER] tree234 maxflow STANDALONE +unequalsolver : [C] unequal[STANDALONE_SOLVER] latin[STANDALONE_SOLVER] tree234 maxflow STANDALONE + +latincheck : [U] latin[STANDALONE_LATIN_TEST] tree234 maxflow STANDALONE +latincheck : [C] latin[STANDALONE_LATIN_TEST] tree234 maxflow STANDALONE + +ALL += UNEQUAL + +!begin gtk +GAMES += unequal +!end + +!begin >list.c + A(unequal) \ +!end diff --git a/unequal.c b/unequal.c new file mode 100644 index 0000000..74eba79 --- /dev/null +++ b/unequal.c @@ -0,0 +1,1967 @@ +/* + * unequal.c + * + * Implementation of 'Futoshiki', a puzzle featured in the Guardian. + * + * TTD: + * add multiple-links-on-same-col/row solver nous + * Optimise set solver to use bit operations instead + * + * Guardian puzzles of note: + * #1: 5:0,0L,0L,0,0,0R,0,0L,0D,0L,0R,0,2,0D,0,0,0,0,0,0,0U,0,0,0,0U, + * #2: 5:0,0,0,4L,0L,0,2LU,0L,0U,0,0,0U,0,0,0,0,0D,0,3LRUD,0,0R,3,0L,0,0, + * #3: (reprint of #2) + * #4: + * #5: 5:0,0,0,0,0,0,2,0U,3U,0U,0,0,3,0,0,0,3,0D,4,0,0,0L,0R,0,0, + * #6: 5:0D,0L,0,0R,0,0,0D,0,3,0D,0,0R,0,0R,0D,0U,0L,0,1,2,0,0,0U,0,0L, + */ + +#include +#include +#include +#include +#include +#include + +#include "puzzles.h" +#include "latin.h" /* contains typedef for digit */ + +/* ---------------------------------------------------------- + * Constant and structure definitions + */ + +#define FLASH_TIME 0.4F + +#define PREFERRED_TILE_SIZE 32 + +#define TILE_SIZE (ds->tilesize) +#define GAP_SIZE (TILE_SIZE/2) +#define SQUARE_SIZE (TILE_SIZE + GAP_SIZE) + +#define BORDER (TILE_SIZE / 2) + +#define COORD(x) ( (x) * SQUARE_SIZE + BORDER ) +#define FROMCOORD(x) ( ((x) - BORDER + SQUARE_SIZE) / SQUARE_SIZE - 1 ) + +#define GRID(p,w,x,y) ((p)->w[((y)*(p)->order)+(x)]) +#define GRID3(p,w,x,y,z) ((p)->w[ (((x)*(p)->order+(y))*(p)->order+(z)) ]) +#define HINT(p,x,y,n) GRID3(p, hints, x, y, n) + +enum { + COL_BACKGROUND, + COL_GRID, + COL_TEXT, COL_GUESS, COL_ERROR, COL_PENCIL, + COL_HIGHLIGHT, COL_LOWLIGHT, + NCOLOURS +}; + +struct game_params { + int order, diff; +}; + +#define F_IMMUTABLE 1 /* passed in as game description */ +#define F_GT_UP 2 +#define F_GT_RIGHT 4 +#define F_GT_DOWN 8 +#define F_GT_LEFT 16 +#define F_ERROR 32 +#define F_ERROR_UP 64 +#define F_ERROR_RIGHT 128 +#define F_ERROR_DOWN 256 +#define F_ERROR_LEFT 512 + +#define F_ERROR_MASK (F_ERROR|F_ERROR_UP|F_ERROR_RIGHT|F_ERROR_DOWN|F_ERROR_LEFT) + +struct game_state { + int order, completed, cheated; + digit *nums; /* actual numbers (size order^2) */ + unsigned char *hints; /* remaining possiblities (size order^3) */ + unsigned int *flags; /* flags (size order^2) */ +}; + +/* ---------------------------------------------------------- + * Game parameters and presets + */ + +/* Steal the method from map.c for difficulty levels. */ +#define DIFFLIST(A) \ + A(LATIN,Trivial,t) \ + A(EASY,Easy,e) \ + A(SET,Tricky,k) \ + A(EXTREME,Extreme,x) \ + A(RECURSIVE,Recursive,r) + +#define ENUM(upper,title,lower) DIFF_ ## upper, +#define TITLE(upper,title,lower) #title, +#define ENCODE(upper,title,lower) #lower +#define CONFIG(upper,title,lower) ":" #title +enum { DIFFLIST(ENUM) DIFF_IMPOSSIBLE = diff_impossible, DIFF_AMBIGUOUS = diff_ambiguous, DIFF_UNFINISHED = diff_unfinished }; +static char const *const unequal_diffnames[] = { DIFFLIST(TITLE) }; +static char const unequal_diffchars[] = DIFFLIST(ENCODE); +#define DIFFCOUNT lenof(unequal_diffchars) +#define DIFFCONFIG DIFFLIST(CONFIG) + +#define DEFAULT_PRESET 0 + +const static struct game_params unequal_presets[] = { + { 4, DIFF_EASY }, + { 5, DIFF_EASY }, + { 5, DIFF_SET }, + { 5, DIFF_EXTREME }, + { 6, DIFF_EASY }, + { 6, DIFF_SET }, + { 6, DIFF_EXTREME }, + { 7, DIFF_SET }, + { 7, DIFF_EXTREME }, +}; + +static int game_fetch_preset(int i, char **name, game_params **params) +{ + game_params *ret; + char buf[80]; + + if (i < 0 || i >= lenof(unequal_presets)) + return FALSE; + + ret = snew(game_params); + *ret = unequal_presets[i]; /* structure copy */ + + sprintf(buf, "%dx%d %s", ret->order, ret->order, + unequal_diffnames[ret->diff]); + + *name = dupstr(buf); + *params = ret; + return TRUE; +} + +static game_params *default_params(void) +{ + game_params *ret; + char *name; + + if (!game_fetch_preset(DEFAULT_PRESET, &name, &ret)) return NULL; + sfree(name); + return ret; +} + +static void free_params(game_params *params) +{ + sfree(params); +} + +static game_params *dup_params(game_params *params) +{ + game_params *ret = snew(game_params); + *ret = *params; /* structure copy */ + return ret; +} + +static void decode_params(game_params *ret, char const *string) +{ + char const *p = string; + + ret->order = atoi(p); + while (*p && isdigit((unsigned char)*p)) p++; + + if (*p == 'd') { + int i; + p++; + ret->diff = DIFFCOUNT+1; /* ...which is invalid */ + if (*p) { + for (i = 0; i < DIFFCOUNT; i++) { + if (*p == unequal_diffchars[i]) + ret->diff = i; + } + p++; + } + } +} + +static char *encode_params(game_params *params, int full) +{ + char ret[80]; + + sprintf(ret, "%d", params->order); + if (full) + sprintf(ret + strlen(ret), "d%c", unequal_diffchars[params->diff]); + + return dupstr(ret); +} + +static config_item *game_configure(game_params *params) +{ + config_item *ret; + char buf[80]; + + ret = snewn(3, config_item); + + ret[0].name = "Size (s*s)"; + ret[0].type = C_STRING; + sprintf(buf, "%d", params->order); + ret[0].sval = dupstr(buf); + ret[0].ival = 0; + + ret[1].name = "Difficulty"; + ret[1].type = C_CHOICES; + ret[1].sval = DIFFCONFIG; + ret[1].ival = params->diff; + + ret[2].name = NULL; + ret[2].type = C_END; + ret[2].sval = NULL; + ret[2].ival = 0; + + return ret; +} + +static game_params *custom_params(config_item *cfg) +{ + game_params *ret = snew(game_params); + + ret->order = atoi(cfg[0].sval); + ret->diff = cfg[1].ival; + + return ret; +} + +static char *validate_params(game_params *params, int full) +{ + if (params->order < 3 || params->order > 32) + return "Order must be between 3 and 32"; + if (params->diff >= DIFFCOUNT) + return "Unknown difficulty rating."; + return NULL; +} + +/* ---------------------------------------------------------- + * Various utility functions + */ + +static const struct { unsigned int f, fo, fe; int dx, dy; char c; } gtthan[] = { + { F_GT_UP, F_GT_DOWN, F_ERROR_UP, 0, -1, '^' }, + { F_GT_RIGHT, F_GT_LEFT, F_ERROR_RIGHT, 1, 0, '>' }, + { F_GT_DOWN, F_GT_UP, F_ERROR_DOWN, 0, 1, 'v' }, + { F_GT_LEFT, F_GT_RIGHT, F_ERROR_LEFT, -1, 0, '<' } +}; + +static game_state *blank_game(int order) +{ + game_state *state = snew(game_state); + int o2 = order*order, o3 = o2*order; + + state->order = order; + state->completed = state->cheated = 0; + + state->nums = snewn(o2, digit); + state->hints = snewn(o3, unsigned char); + state->flags = snewn(o2, unsigned int); + + memset(state->nums, 0, o2 * sizeof(digit)); + memset(state->hints, 0, o3); + memset(state->flags, 0, o2 * sizeof(unsigned int)); + + return state; +} + +static game_state *dup_game(game_state *state) +{ + game_state *ret = blank_game(state->order); + int o2 = state->order*state->order, o3 = o2*state->order; + + memcpy(ret->nums, state->nums, o2 * sizeof(digit)); + memcpy(ret->hints, state->hints, o3); + memcpy(ret->flags, state->flags, o2 * sizeof(unsigned int)); + + return ret; +} + +static void free_game(game_state *state) +{ + sfree(state->nums); + sfree(state->hints); + sfree(state->flags); + sfree(state); +} + +#define CHECKG(x,y) grid[(y)*o+(x)] + +/* Returns 0 if it finds an error, 1 otherwise. */ +static int check_gt(digit *grid, game_state *state, + int x, int y, int dx, int dy) +{ + int o = state->order; + int n = CHECKG(x,y), dn = CHECKG(x+dx, y+dy); + + assert(n != 0); + if (dn == 0) return 1; + + if (n <= dn) { + debug(("check_gt error (%d,%d) (%d,%d)", x, y, x+dx, y+dy)); + return 0; + } + return 1; +} + +/* Returns 0 if it finds an error, 1 otherwise. */ +static int check_num_gt(digit *grid, game_state *state, + int x, int y, int me) +{ + unsigned int f = GRID(state, flags, x, y); + int ret = 1, i; + + for (i = 0; i < 4; i++) { + if ((f & gtthan[i].f) && + !check_gt(grid, state, x, y, gtthan[i].dx, gtthan[i].dy)) { + if (me) GRID(state, flags, x, y) |= gtthan[i].fe; + ret = 0; + } + } + return ret; +} + +/* Returns 0 if it finds an error, 1 otherwise. */ +static int check_num_error(digit *grid, game_state *state, + int x, int y, int mark_errors) +{ + int o = state->order; + int xx, yy, val = CHECKG(x,y), ret = 1; + + assert(val != 0); + + /* check for dups in same column. */ + for (yy = 0; yy < state->order; yy++) { + if (yy == y) continue; + if (CHECKG(x,yy) == val) ret = 0; + } + + /* check for dups in same row. */ + for (xx = 0; xx < state->order; xx++) { + if (xx == x) continue; + if (CHECKG(xx,y) == val) ret = 0; + } + + if (!ret) { + debug(("check_num_error (%d,%d) duplicate %d", x, y, val)); + if (mark_errors) GRID(state, flags, x, y) |= F_ERROR; + } + return ret; +} + +/* Returns: -1 for 'wrong' + * 0 for 'incomplete' + * 1 for 'complete and correct' + */ +static int check_complete(digit *grid, game_state *state, int mark_errors) +{ + int x, y, ret = 1, o = state->order; + + if (mark_errors) + assert(grid == state->nums); + + for (x = 0; x < state->order; x++) { + for (y = 0; y < state->order; y++) { + if (mark_errors) + GRID(state, flags, x, y) &= ~F_ERROR_MASK; + if (grid[y*o+x] == 0) { + ret = 0; + } else { + if (!check_num_error(grid, state, x, y, mark_errors)) ret = -1; + if (!check_num_gt(grid, state, x, y, mark_errors)) ret = -1; + } + } + } + if (ret == 1 && latin_check(grid, o)) + ret = -1; + return ret; +} + +static char n2c(digit n, int order) { + if (n == 0) return ' '; + if (order < 10) { + if (n < 10) return '0' + n; + } else { + if (n < 11) return '0' + n-1; + n -= 11; + if (n <= 26) return 'A' + n; + } + return '?'; +} + +/* should be 'digit', but includes -1 for 'not a digit'. + * Includes keypresses (0 especially) for interpret_move. */ +static int c2n(int c, int order) { + if (c < 0 || c > 0xff) + return -1; + if (c == ' ' || c == '\010' || c == '\177') + return 0; + if (order < 10) { + if (c >= '1' && c <= '9') + return (int)(c - '0'); + } else { + if (c >= '0' && c <= '9') + return (int)(c - '0' + 1); + if (c >= 'A' && c <= 'Z') + return (int)(c - 'A' + 11); + if (c >= 'a' && c <= 'z') + return (int)(c - 'a' + 11); + } + return -1; +} + +static char *game_text_format(game_state *state) +{ + int x, y, len, n; + char *ret, *p; + + len = (state->order*2) * (state->order*2-1) + 1; + ret = snewn(len, char); + p = ret; + + for (y = 0; y < state->order; y++) { + for (x = 0; x < state->order; x++) { + n = GRID(state, nums, x, y); + *p++ = n > 0 ? n2c(n, state->order) : '.'; + + if (x < (state->order-1)) { + if (GRID(state, flags, x, y) & F_GT_RIGHT) + *p++ = '>'; + else if (GRID(state, flags, x+1, y) & F_GT_LEFT) + *p++ = '<'; + else + *p++ = ' '; + } + } + *p++ = '\n'; + + if (y < (state->order-1)) { + for (x = 0; x < state->order; x++) { + if (GRID(state, flags, x, y) & F_GT_DOWN) + *p++ = 'v'; + else if (GRID(state, flags, x, y+1) & F_GT_UP) + *p++ = '^'; + else + *p++ = ' '; + + if (x < state->order-1) + *p++ = ' '; + } + *p++ = '\n'; + } + } + *p++ = '\0'; + + assert(p - ret == len); + return ret; +} + +#ifdef STANDALONE_SOLVER +static void game_debug(game_state *state) +{ + char *dbg = game_text_format(state); + printf("%s", dbg); + sfree(dbg); +} +#endif + +/* ---------------------------------------------------------- + * Solver. + */ + +struct solver_link { + int len, gx, gy, lx, ly; +}; + +typedef struct game_solver { + struct latin_solver latin; /* keep first in struct! */ + + game_state *state; + + int nlinks, alinks; + struct solver_link *links; +} game_solver; + +#if 0 +static void solver_debug(game_solver *solver, int wide) +{ +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + if (!wide) + game_debug(solver->state); + else + latin_solver_debug(solver->latin.cube, solver->latin.o); + } +#endif +} +#endif + +static void solver_add_link(game_solver *solver, + int gx, int gy, int lx, int ly, int len) +{ + if (solver->alinks < solver->nlinks+1) { + solver->alinks = solver->alinks*2 + 1; + /*debug(("resizing solver->links, new size %d", solver->alinks));*/ + solver->links = sresize(solver->links, solver->alinks, struct solver_link); + } + solver->links[solver->nlinks].gx = gx; + solver->links[solver->nlinks].gy = gy; + solver->links[solver->nlinks].lx = lx; + solver->links[solver->nlinks].ly = ly; + solver->links[solver->nlinks].len = len; + solver->nlinks++; + /*debug(("Adding new link: len %d (%d,%d) < (%d,%d), nlinks now %d", + len, lx, ly, gx, gy, solver->nlinks));*/ +} + +static game_solver *new_solver(digit *grid, game_state *state) +{ + game_solver *solver = snew(game_solver); + int o = state->order; + int i, x, y; + unsigned int f; + + latin_solver_alloc(&solver->latin, grid, o); + + solver->nlinks = solver->alinks = 0; + solver->links = NULL; + + for (x = 0; x < o; x++) { + for (y = 0; y < o; y++) { + f = GRID(state, flags, x, y); + for (i = 0; i < 4; i++) { + if (f & gtthan[i].f) + solver_add_link(solver, x, y, x+gtthan[i].dx, y+gtthan[i].dy, 1); + } + } + } + + return solver; +} + +static void free_solver(game_solver *solver) +{ + if (solver->links) sfree(solver->links); + latin_solver_free(&solver->latin); + sfree(solver); +} + +static void solver_nminmax(game_solver *usolver, + int x, int y, int *min_r, int *max_r, + unsigned char **ns_r) +{ + struct latin_solver *solver = &usolver->latin; + int o = usolver->latin.o, min = o, max = 0, n; + unsigned char *ns; + + assert(x >= 0 && y >= 0 && x < o && y < o); + + ns = solver->cube + cubepos(x,y,1); + + if (grid(x,y) > 0) { + min = max = grid(x,y)-1; + } else { + for (n = 0; n < o; n++) { + if (ns[n]) { + if (n > max) max = n; + if (n < min) min = n; + } + } + } + if (min_r) *min_r = min; + if (max_r) *max_r = max; + if (ns_r) *ns_r = ns; +} + +static int solver_links(game_solver *usolver) +{ + int i, j, lmin, gmax, nchanged = 0; + unsigned char *gns, *lns; + struct solver_link *link; + struct latin_solver *solver = &usolver->latin; + + for (i = 0; i < usolver->nlinks; i++) { + link = &usolver->links[i]; + solver_nminmax(usolver, link->gx, link->gy, NULL, &gmax, &gns); + solver_nminmax(usolver, link->lx, link->ly, &lmin, NULL, &lns); + + for (j = 0; j < solver->o; j++) { + /* For the 'greater' end of the link, discount all numbers + * too small to satisfy the inequality. */ + if (gns[j]) { + if (j < (lmin+link->len)) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*slink elimination, (%d,%d) > (%d,%d):\n", + solver_recurse_depth*4, "", + link->gx, link->gy, link->lx, link->ly); + printf("%*s ruling out %d at (%d,%d)\n", + solver_recurse_depth*4, "", + j+1, link->gx, link->gy); + } +#endif + cube(link->gx, link->gy, j+1) = FALSE; + nchanged++; + } + } + /* For the 'lesser' end of the link, discount all numbers + * too large to satisfy inequality. */ + if (lns[j]) { + if (j > (gmax-link->len)) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + printf("%*slink elimination, (%d,%d) > (%d,%d):\n", + solver_recurse_depth*4, "", + link->gx, link->gy, link->lx, link->ly); + printf("%*s ruling out %d at (%d,%d)\n", + solver_recurse_depth*4, "", + j+1, link->lx, link->ly); + } +#endif + cube(link->lx, link->ly, j+1) = FALSE; + nchanged++; + } + } + } + } + return nchanged; +} + +static int solver_grid(digit *grid, int o, int maxdiff, void *ctx) +{ + game_state *state = (game_state *)ctx; + game_solver *solver; + struct latin_solver *lsolver; + struct latin_solver_scratch *scratch; + int ret, diff = DIFF_LATIN, extreme; + + assert(maxdiff <= DIFF_RECURSIVE); + + assert(state->order == o); + solver = new_solver(grid, state); + + lsolver = &solver->latin; + scratch = latin_solver_new_scratch(lsolver); + + while (1) { +cont: + ret = latin_solver_diff_simple(lsolver); + if (ret < 0) { + diff = DIFF_IMPOSSIBLE; + goto got_result; + } else if (ret > 0) { + diff = max(diff, DIFF_LATIN); + goto cont; + } + + if (maxdiff <= DIFF_LATIN) + break; + + /* This bit is unequal-specific */ + ret = solver_links(solver); + if (ret < 0) { + diff = DIFF_IMPOSSIBLE; + goto got_result; + } else if (ret > 0) { + diff = max(diff, DIFF_EASY); + goto cont; + } + + if (maxdiff <= DIFF_EASY) + break; + + ret = latin_solver_diff_set(lsolver, scratch, &extreme); + if (ret < 0) { + diff = DIFF_IMPOSSIBLE; + goto got_result; + } else if (ret > 0) { + diff = max(diff, extreme ? DIFF_EXTREME : DIFF_SET); + goto cont; + } + + if (maxdiff <= DIFF_SET) + break; + + /* + * Forcing chains. + */ + if (latin_solver_forcing(lsolver, scratch)) { + diff = max(diff, DIFF_EXTREME); + goto cont; + } + + /* + * If we reach here, we have made no deductions in this + * iteration, so the algorithm terminates. + */ + break; + } + /* + * Last chance: if we haven't fully solved the puzzle yet, try + * recursing based on guesses for a particular square. We pick + * one of the most constrained empty squares we can find, which + * has the effect of pruning the search tree as much as + * possible. + */ + if (maxdiff == DIFF_RECURSIVE) { + int nsol = latin_solver_recurse(lsolver, DIFF_RECURSIVE, solver_grid, ctx); + if (nsol < 0) diff = DIFF_IMPOSSIBLE; + else if (nsol == 1) diff = DIFF_RECURSIVE; + else if (nsol > 1) diff = DIFF_AMBIGUOUS; + /* if nsol == 0 then we were complete anyway + * (and thus don't need to change diff) */ + } else { + int cc = check_complete(grid, state, 0); + if (cc == -1) diff = DIFF_IMPOSSIBLE; + if (cc == 0) diff = DIFF_UNFINISHED; + } + +got_result: + +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("%*s%s found\n", + solver_recurse_depth*4, "", + diff == DIFF_IMPOSSIBLE ? "no solution (impossible)" : + diff == DIFF_UNFINISHED ? "no solution (unfinished)" : + diff == DIFF_AMBIGUOUS ? "multiple solutions" : + "one solution"); +#endif + + latin_solver_free_scratch(scratch); + memcpy(state->hints, solver->latin.cube, o*o*o); + free_solver(solver); + + return diff; +} + +static int solver_state(game_state *state, int maxdiff) +{ + int diff = solver_grid(state->nums, state->order, maxdiff, (void*)state); + + if (diff == DIFF_IMPOSSIBLE) + return -1; + if (diff == DIFF_UNFINISHED) + return 0; + if (diff == DIFF_AMBIGUOUS) + return 2; + return 1; +} + +static game_state *solver_hint(game_state *state, int *diff_r, int mindiff, int maxdiff) +{ + game_state *ret = dup_game(state); + int diff, r = 0; + + for (diff = mindiff; diff <= maxdiff; diff++) { + r = solver_state(ret, diff); + debug(("solver_state after %s %d", unequal_diffnames[diff], r)); + if (r != 0) goto done; + } + +done: + if (diff_r) *diff_r = (r > 0) ? diff : -1; + return ret; +} + +/* ---------------------------------------------------------- + * Game generation. + */ + +static char *latin_desc(digit *sq, size_t order) +{ + int o2 = order*order, i; + char *soln = snewn(o2+2, char); + + soln[0] = 'S'; + for (i = 0; i < o2; i++) + soln[i+1] = n2c(sq[i], order); + soln[o2+1] = '\0'; + + return soln; +} + +/* returns non-zero if it placed (or could have placed) clue. */ +static int gg_place_clue(game_state *state, int ccode, digit *latin, int checkonly) +{ + int loc = ccode / 5, which = ccode % 5; + int x = loc % state->order, y = loc / state->order; + + assert(loc < state->order*state->order); + + if (which == 4) { /* add number */ + if (state->nums[loc] != 0) { +#ifdef STANDALONE_SOLVER + if (state->nums[loc] != latin[loc]) { + printf("inconsistency for (%d,%d): state %d latin %d\n", + x, y, state->nums[loc], latin[loc]); + } +#endif + assert(state->nums[loc] == latin[loc]); + return 0; + } + if (!checkonly) { + state->nums[loc] = latin[loc]; + } + } else { /* add flag */ + int lx, ly, lloc; + + if (state->flags[loc] & gtthan[which].f) + return 0; /* already has flag. */ + + lx = x + gtthan[which].dx; + ly = y + gtthan[which].dy; + if (lx < 0 || ly < 0 || lx >= state->order || ly >= state->order) + return 0; /* flag compares to off grid */ + + lloc = loc + gtthan[which].dx + gtthan[which].dy*state->order; + if (latin[loc] <= latin[lloc]) + return 0; /* flag would be incorrect */ + + if (!checkonly) { + state->flags[loc] |= gtthan[which].f; + } + } + return 1; +} + +/* returns non-zero if it removed (or could have removed) the clue. */ +static int gg_remove_clue(game_state *state, int ccode, int checkonly) +{ + int loc = ccode / 5, which = ccode % 5; +#ifdef STANDALONE_SOLVER + int x = loc % state->order, y = loc / state->order; +#endif + + assert(loc < state->order*state->order); + + if (which == 4) { /* remove number. */ + if (state->nums[loc] == 0) return 0; + if (!checkonly) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("gg_remove_clue: removing %d at (%d,%d)", + state->nums[loc], x, y); +#endif + state->nums[loc] = 0; + } + } else { /* remove flag */ + if (!(state->flags[loc] & gtthan[which].f)) return 0; + if (!checkonly) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("gg_remove_clue: removing %c at (%d,%d)", + gtthan[which].c, x, y); +#endif + state->flags[loc] &= ~gtthan[which].f; + } + } + return 1; +} + +static int gg_best_clue(game_state *state, int *scratch, digit *latin) +{ + int ls = state->order * state->order * 5; + int maxposs = 0, minclues = 5, best = -1, i, j; + int nposs, nclues, loc, x, y; + +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + game_debug(state); + latin_solver_debug(state->hints, state->order); + } +#endif + + for (i = 0; i < ls; i++) { + if (!gg_place_clue(state, scratch[i], latin, 1)) continue; + + loc = scratch[i] / 5; + x = loc % state->order; y = loc / state->order; + for (j = nposs = 0; j < state->order; j++) { + if (state->hints[loc*state->order + j]) nposs++; + } + for (j = nclues = 0; j < 4; j++) { + if (state->flags[loc] & gtthan[j].f) nclues++; + } + if ((nposs > maxposs) || + (nposs == maxposs && nclues < minclues)) { + best = i; maxposs = nposs; minclues = nclues; +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("gg_best_clue: b%d (%d,%d) new best [%d poss, %d clues].", + best, x, y, nposs, nclues); +#endif + } + } + /* if we didn't solve, we must have 1 clue to place! */ + assert(best != -1); + return best; +} + +#ifdef STANDALONE_SOLVER +int maxtries; +#define MAXTRIES maxtries +#else +#define MAXTRIES 50 +#endif +int gg_solved; + +static int game_assemble(game_state *new, int *scratch, digit *latin, + int difficulty) +{ + game_state *copy = dup_game(new); + int best; + + if (difficulty >= DIFF_RECURSIVE) { + /* We mustn't use any solver that might guess answers; + * if it guesses wrongly but solves, gg_place_clue will + * get mighty confused. We will always trim clues down + * (making it more difficult) in game_strip, which doesn't + * have this problem. */ + difficulty = DIFF_RECURSIVE-1; + } + +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + game_debug(new); + latin_solver_debug(new->hints, new->order); + } +#endif + + while(1) { + gg_solved++; + if (solver_state(copy, difficulty) == 1) break; + + best = gg_best_clue(copy, scratch, latin); + gg_place_clue(new, scratch[best], latin, 0); + gg_place_clue(copy, scratch[best], latin, 0); + } + free_game(copy); +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + char *dbg = game_text_format(new); + printf("game_assemble: done, %d solver iterations:\n%s\n", gg_solved, dbg); + sfree(dbg); + } +#endif + return 0; +} + +static void game_strip(game_state *new, int *scratch, digit *latin, + int difficulty) +{ + int o = new->order, o2 = o*o, lscratch = o2*5, i; + game_state *copy = blank_game(new->order); + + /* For each symbol (if it exists in new), try and remove it and + * solve again; if we couldn't solve without it put it back. */ + for (i = 0; i < lscratch; i++) { + if (!gg_remove_clue(new, scratch[i], 0)) continue; + + memcpy(copy->nums, new->nums, o2 * sizeof(digit)); + memcpy(copy->flags, new->flags, o2 * sizeof(unsigned int)); + gg_solved++; + if (solver_state(copy, difficulty) != 1) { + /* put clue back, we can't solve without it. */ + assert(gg_place_clue(new, scratch[i], latin, 0) == 1); + } else { +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("game_strip: clue was redundant."); +#endif + } + } + free_game(copy); +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + char *dbg = game_text_format(new); + debug(("game_strip: done, %d solver iterations.", gg_solved)); + debug(("%s", dbg)); + sfree(dbg); + } +#endif +} + +static char *new_game_desc(game_params *params, random_state *rs, + char **aux, int interactive) +{ + digit *sq = NULL; + int i, x, y, retlen, k, nsol; + int o2 = params->order * params->order, ntries = 0; + int *scratch, lscratch = o2*5; + char *ret, buf[80]; + game_state *state = blank_game(params->order); + + /* Generate a list of 'things to strip' (randomised later) */ + scratch = snewn(lscratch, int); + for (i = 0; i < lscratch; i++) scratch[i] = i; + +generate: +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("new_game_desc: generating %s puzzle, ntries so far %d", + unequal_diffnames[params->diff], ntries); +#endif + if (sq) sfree(sq); + sq = latin_generate(params->order, rs); + latin_debug(sq, params->order); + shuffle(scratch, lscratch, sizeof(int), rs); + + memset(state->nums, 0, o2 * sizeof(digit)); + memset(state->flags, 0, o2 * sizeof(unsigned int)); + + gg_solved = 0; + if (game_assemble(state, scratch, sq, params->diff) < 0) + goto generate; + game_strip(state, scratch, sq, params->diff); + + if (params->diff > 0) { + game_state *copy = dup_game(state); + nsol = solver_state(copy, params->diff-1); + free_game(copy); + if (nsol > 0) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("game_assemble: puzzle as generated is too easy."); +#endif + if (ntries < MAXTRIES) { + ntries++; + goto generate; + } +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("Unable to generate %s %dx%d after %d attempts.", + unequal_diffnames[params->diff], + params->order, params->order, MAXTRIES); +#endif + params->diff--; + } + } +#ifdef STANDALONE_SOLVER + if (solver_show_working) + printf("new_game_desc: generated %s puzzle; %d attempts (%d solver).", + unequal_diffnames[params->diff], ntries, gg_solved); +#endif + + ret = NULL; retlen = 0; + for (y = 0; y < params->order; y++) { + for (x = 0; x < params->order; x++) { + unsigned int f = GRID(state, flags, x, y); + k = sprintf(buf, "%d%s%s%s%s,", + GRID(state, nums, x, y), + (f & F_GT_UP) ? "U" : "", + (f & F_GT_RIGHT) ? "R" : "", + (f & F_GT_DOWN) ? "D" : "", + (f & F_GT_LEFT) ? "L" : ""); + + ret = sresize(ret, retlen + k + 1, char); + strcpy(ret + retlen, buf); + retlen += k; + } + } + *aux = latin_desc(sq, params->order); + + free_game(state); + sfree(sq); + sfree(scratch); + + return ret; +} + +static game_state *load_game(game_params *params, char *desc, + char **why_r) +{ + game_state *state = blank_game(params->order); + char *p = desc; + int i = 0, n, o = params->order, x, y; + char *why = NULL; + + while (*p) { + while (*p >= 'a' && *p <= 'z') { + i += *p - 'a' + 1; + p++; + } + if (i >= o*o) { + why = "Too much data to fill grid"; goto fail; + } + + if (*p < '0' && *p > '9') { + why = "Expecting number in game description"; goto fail; + } + n = atoi(p); + if (n < 0 || n > o) { + why = "Out-of-range number in game description"; goto fail; + } + state->nums[i] = (digit)n; + while (*p >= '0' && *p <= '9') p++; /* skip number */ + + if (state->nums[i] != 0) + state->flags[i] |= F_IMMUTABLE; /* === number set by game description */ + + while (*p == 'U' || *p == 'R' || *p == 'D' || *p == 'L') { + switch (*p) { + case 'U': state->flags[i] |= F_GT_UP; break; + case 'R': state->flags[i] |= F_GT_RIGHT; break; + case 'D': state->flags[i] |= F_GT_DOWN; break; + case 'L': state->flags[i] |= F_GT_LEFT; break; + default: why = "Expecting flag URDL in game description"; goto fail; + } + p++; + } + i++; + if (i < o*o && *p != ',') { + why = "Missing separator"; goto fail; + } + if (*p == ',') p++; + } + if (i < o*o) { + why = "Not enough data to fill grid"; goto fail; + } + i = 0; + for (y = 0; y < o; y++) { + for (x = 0; x < o; x++) { + for (n = 0; n < 4; n++) { + if (GRID(state, flags, x, y) & gtthan[n].f) { + int nx = x + gtthan[n].dx; + int ny = y + gtthan[n].dy; + /* a flag must not point us off the grid. */ + if (nx < 0 || ny < 0 || nx >= o || ny >= o) { + why = "Flags go off grid"; goto fail; + } + /* if one cell is GT another, the other must not also + * be GT the first. */ + if (GRID(state, flags, nx, ny) & gtthan[n].fo) { + why = "Flags contradicting each other"; goto fail; + } + } + } + } + } + + return state; + +fail: + free_game(state); + if (why_r) *why_r = why; + return NULL; +} + +static game_state *new_game(midend *me, game_params *params, char *desc) +{ + game_state *state = load_game(params, desc, NULL); + if (!state) { + assert("Unable to load ?validated game."); + return NULL; + } + return state; +} + +static char *validate_desc(game_params *params, char *desc) +{ + char *why = NULL; + game_state *dummy = load_game(params, desc, &why); + if (dummy) { + free_game(dummy); + assert(!why); + } else + assert(why); + return why; +} + +static char *solve_game(game_state *state, game_state *currstate, + char *aux, char **error) +{ + game_state *solved; + int r; + char *ret = NULL; + + if (aux) return dupstr(aux); + + solved = dup_game(state); + for (r = 0; r < state->order*state->order; r++) { + if (!(solved->flags[r] & F_IMMUTABLE)) + solved->nums[r] = 0; + } + r = solver_state(solved, DIFFCOUNT); + if (r > 0) ret = latin_desc(solved->nums, solved->order); + free_game(solved); + return ret; +} + +/* ---------------------------------------------------------- + * Game UI input processing. + */ + +struct game_ui { + int hx, hy, hpencil; /* as for solo.c, highlight pos and type */ + int cx, cy; /* cursor position (-1,-1 for none) */ +}; + +static game_ui *new_ui(game_state *state) +{ + game_ui *ui = snew(game_ui); + + ui->hx = ui->hy = -1; + ui->hpencil = 0; + + ui->cx = ui->cy = -1; + + return ui; +} + +static void free_ui(game_ui *ui) +{ + sfree(ui); +} + +static char *encode_ui(game_ui *ui) +{ + return NULL; +} + +static void decode_ui(game_ui *ui, char *encoding) +{ +} + +static void game_changed_state(game_ui *ui, game_state *oldstate, + game_state *newstate) +{ + /* See solo.c; if we were pencil-mode highlighting and + * somehow a square has just been properly filled, cancel + * pencil mode. */ + if (ui->hx >= 0 && ui->hy >= 0 && ui->hpencil && + GRID(newstate, nums, ui->hx, ui->hy) != 0) { + ui->hx = ui->hy = -1; + } +} + +struct game_drawstate { + int tilesize, order, started; + digit *nums; /* copy of nums, o^2 */ + unsigned char *hints; /* copy of hints, o^3 */ + unsigned int *flags; /* o^2 */ + + int hx, hy, hpencil; + int cx, cy; + int hflash; +}; + +static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, + int ox, int oy, int button) +{ + int x = FROMCOORD(ox), y = FROMCOORD(oy), n; + char buf[80]; + + button &= ~MOD_MASK; + + if (x >= 0 && x < ds->order && y >= 0 && y < ds->order) { + if (button == LEFT_BUTTON) { + /* normal highlighting for non-immutable squares */ + if (GRID(state, flags, x, y) & F_IMMUTABLE) + ui->hx = ui->hy = -1; + else if (x == ui->hx && y == ui->hy && ui->hpencil == 0) + ui->hx = ui->hy = -1; + else { + ui->hx = x; ui->hy = y; ui->hpencil = 0; + } + return ""; + } + if (button == RIGHT_BUTTON) { + /* pencil highlighting for non-filled squares */ + if (GRID(state, nums, x, y) != 0) + ui->hx = ui->hy = -1; + else if (x == ui->hx && y == ui->hy && ui->hpencil) + ui->hx = ui->hy = -1; + else { + ui->hx = x; ui->hy = y; ui->hpencil = 1; + } + return ""; + } + } + if (button == 'H' || button == 'h') + return dupstr("H"); + + if (ui->hx != -1 && ui->hy != -1) { + debug(("button %d, cbutton %d", button, (int)((char)button))); + n = c2n(button, state->order); + + debug(("n %d, h (%d,%d) p %d flags 0x%x nums %d", + n, ui->hx, ui->hy, ui->hpencil, + GRID(state, flags, ui->hx, ui->hy), + GRID(state, nums, ui->hx, ui->hy))); + + if (n < 0 || n > ds->order) + return NULL; /* out of range */ + if (GRID(state, flags, ui->hx, ui->hy) & F_IMMUTABLE) + return NULL; /* can't edit immutable square (!) */ + if (ui->hpencil && GRID(state, nums, ui->hx, ui->hy) > 0) + return NULL; /* can't change hints on filled square (!) */ + + + sprintf(buf, "%c%d,%d,%d", + (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n); + + ui->hx = ui->hy = -1; + + return dupstr(buf); + } + return NULL; +} + +static game_state *execute_move(game_state *state, char *move) +{ + game_state *ret = NULL; + int x, y, n, i; + + debug(("execute_move: %s", move)); + + if ((move[0] == 'P' || move[0] == 'R') && + sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 && + x >= 0 && x < state->order && y >= 0 && y < state->order && + n >= 0 && n <= state->order) { + ret = dup_game(state); + if (move[0] == 'P' && n > 0) + HINT(ret, x, y, n-1) = !HINT(ret, x, y, n-1); + else { + GRID(ret, nums, x, y) = n; + for (i = 0; i < state->order; i++) + HINT(ret, x, y, i) = 0; + + /* real change to grid; check for completion */ + if (!ret->completed && check_complete(ret->nums, ret, 1) > 0) + ret->completed = TRUE; + } + return ret; + } else if (move[0] == 'S') { + char *p; + + ret = dup_game(state); + ret->completed = ret->cheated = TRUE; + + p = move+1; + for (i = 0; i < state->order*state->order; i++) { + n = c2n((int)*p, state->order); + if (!*p || n <= 0 || n > state->order) + goto badmove; + ret->nums[i] = n; + p++; + } + if (*p) goto badmove; + assert(check_complete(ret->nums, ret, 1) > 0); + return ret; + } else if (move[0] == 'H') { + return solver_hint(state, NULL, DIFF_EASY, DIFF_EASY); + } + +badmove: + if (ret) free_game(ret); + return NULL; +} + +/* ---------------------------------------------------------------------- + * Drawing/printing routines. + */ + +#define DRAW_SIZE (TILE_SIZE*ds->order + GAP_SIZE*(ds->order-1) + BORDER*2) + +static void game_compute_size(game_params *params, int tilesize, + int *x, int *y) +{ + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + struct { int tilesize, order; } ads, *ds = &ads; + ads.tilesize = tilesize; + ads.order = params->order; + + *x = *y = DRAW_SIZE; +} + +static void game_set_size(drawing *dr, game_drawstate *ds, + game_params *params, int tilesize) +{ + ds->tilesize = tilesize; +} + +static float *game_colours(frontend *fe, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + int i; + + game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT); + + for (i = 0; i < 3; i++) { + ret[COL_TEXT * 3 + i] = 0.0F; + ret[COL_GRID * 3 + i] = 0.5F; + } + + /* Lots of these were taken from solo.c. */ + ret[COL_GUESS * 3 + 0] = 0.0F; + ret[COL_GUESS * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1]; + ret[COL_GUESS * 3 + 2] = 0.0F; + + ret[COL_ERROR * 3 + 0] = 1.0F; + ret[COL_ERROR * 3 + 1] = 0.0F; + ret[COL_ERROR * 3 + 2] = 0.0F; + + ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0]; + ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1]; + ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2]; + + *ncolours = NCOLOURS; + return ret; +} + +static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) +{ + struct game_drawstate *ds = snew(struct game_drawstate); + int o2 = state->order*state->order, o3 = o2*state->order; + + ds->tilesize = 0; + ds->order = state->order; + + ds->nums = snewn(o2, digit); + ds->hints = snewn(o3, unsigned char); + ds->flags = snewn(o2, unsigned int); + memset(ds->nums, 0, o2*sizeof(digit)); + memset(ds->hints, 0, o3); + memset(ds->flags, 0, o2*sizeof(unsigned int)); + + ds->hx = ds->hy = ds->cx = ds->cy = -1; + ds->started = ds->hpencil = ds->hflash = 0; + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds->nums); + sfree(ds->hints); + sfree(ds->flags); + sfree(ds); +} + +static void draw_gt(drawing *dr, int ox, int oy, + int dx1, int dy1, int dx2, int dy2, int col) +{ + draw_line(dr, ox, oy, ox+dx1, oy+dy1, col); + draw_line(dr, ox+dx1, oy+dy1, ox+dx1+dx2, oy+dy1+dy2, col); +} + +static void draw_gts(drawing *dr, game_drawstate *ds, int ox, int oy, + unsigned int f, int col, int needsupdate) +{ + int g = GAP_SIZE, g2 = (g+1)/2, g4 = (g+1)/4; + + if (f & F_GT_UP) { + draw_gt(dr, ox+g2, oy-g4, g2, -g2, g2, g2, + (f & F_ERROR_UP) ? COL_ERROR : col); + if (needsupdate) draw_update(dr, ox, oy-g, TILE_SIZE, g); + } + if (f & F_GT_RIGHT) { + draw_gt(dr, ox+TILE_SIZE+g4, oy+g2, g2, g2, -g2, g2, + (f & F_ERROR_RIGHT) ? COL_ERROR : col); + if (needsupdate) draw_update(dr, ox+TILE_SIZE, oy, g, TILE_SIZE); + } + if (f & F_GT_DOWN) { + draw_gt(dr, ox+g2, oy+TILE_SIZE+g4, g2, g2, g2, -g2, + (f & F_ERROR_DOWN) ? COL_ERROR : col); + if (needsupdate) draw_update(dr, ox, oy+TILE_SIZE, TILE_SIZE, g); + } + if (f & F_GT_LEFT) { + draw_gt(dr, ox-g4, oy+g2, -g2, g2, g2, g2, + (f & F_ERROR_LEFT) ? COL_ERROR : col); + if (needsupdate) draw_update(dr, ox-g, oy, g, TILE_SIZE); + } +} + +static void draw_furniture(drawing *dr, game_drawstate *ds, game_state *state, + game_ui *ui, int x, int y, int hflash) +{ + int ox = COORD(x), oy = COORD(y), bg, hon, con; + unsigned int f = GRID(state, flags, x, y); + + bg = hflash ? COL_HIGHLIGHT : COL_BACKGROUND; + + hon = (x == ui->hx && y == ui->hy); + con = (x == ui->cx && y == ui->cy); + + /* Clear square. */ + draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, + (hon && !ui->hpencil) ? COL_HIGHLIGHT : bg); + + /* Draw the highlight (pencil or full), if we're the highlight */ + if (hon && ui->hpencil) { + int coords[6]; + coords[0] = ox; + coords[1] = oy; + coords[2] = ox + TILE_SIZE/2; + coords[3] = oy; + coords[4] = ox; + coords[5] = oy + TILE_SIZE/2; + draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT); + } + + /* Draw the square outline (which is the cursor, if we're the cursor). */ + draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, + con ? COL_GUESS : COL_GRID); + + draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE); + + /* Draw the GT signs. */ + draw_gts(dr, ds, ox, oy, f, COL_TEXT, 1); +} + +static void draw_num(drawing *dr, game_drawstate *ds, int x, int y) +{ + int ox = COORD(x), oy = COORD(y); + unsigned int f = GRID(ds,flags,x,y); + char str[2]; + + /* (can assume square has just been cleared) */ + + /* Draw number, choosing appropriate colour */ + str[0] = n2c(GRID(ds, nums, x, y), ds->order); + str[1] = '\0'; + draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2, + FONT_VARIABLE, 3*TILE_SIZE/4, ALIGN_VCENTRE | ALIGN_HCENTRE, + (f & F_IMMUTABLE) ? COL_TEXT : (f & F_ERROR) ? COL_ERROR : COL_GUESS, str); +} + +static void draw_hints(drawing *dr, game_drawstate *ds, int x, int y) +{ + int ox = COORD(x), oy = COORD(y); + int nhints, i, j, hw, hh, hmax, fontsz; + char str[2]; + + /* (can assume square has just been cleared) */ + + /* Draw hints; steal ingenious algorithm (basically) + * from solo.c:draw_number() */ + for (i = nhints = 0; i < ds->order; i++) { + if (HINT(ds, x, y, i)) nhints++; + } + + for (hw = 1; hw * hw < nhints; hw++); + if (hw < 3) hw = 3; + hh = (nhints + hw - 1) / hw; + if (hh < 2) hh = 2; + hmax = max(hw, hh); + fontsz = TILE_SIZE/(hmax*(11-hmax)/8); + + for (i = j = 0; i < ds->order; i++) { + if (HINT(ds,x,y,i)) { + int hx = j % hw, hy = j / hw; + + str[0] = n2c(i+1, ds->order); + str[1] = '\0'; + draw_text(dr, + ox + (4*hx+3) * TILE_SIZE / (4*hw+2), + oy + (4*hy+3) * TILE_SIZE / (4*hh+2), + FONT_VARIABLE, fontsz, + ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str); + j++; + } + } +} + +static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, + game_state *state, int dir, game_ui *ui, + float animtime, float flashtime) +{ + int x, y, i, hchanged = 0, cchanged = 0, stale, hflash = 0; + + debug(("highlight old (%d,%d), new (%d,%d)", ds->hx, ds->hy, ui->hx, ui->hy)); + + if (flashtime > 0 && + (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3)) + hflash = 1; + + if (!ds->started) { + draw_rect(dr, 0, 0, DRAW_SIZE, DRAW_SIZE, COL_BACKGROUND); + draw_update(dr, 0, 0, DRAW_SIZE, DRAW_SIZE); + } + if (ds->hx != ui->hx || ds->hy != ui->hy || ds->hpencil != ui->hpencil) + hchanged = 1; + if (ds->cx != ui->cx || ds->cy != ui->cy) + cchanged = 1; + + for (x = 0; x < ds->order; x++) { + for (y = 0; y < ds->order; y++) { + if (!ds->started) + stale = 1; + else if (hflash != ds->hflash) + stale = 1; + else + stale = 0; + + if (hchanged) { + if ((x == ui->hx && y == ui->hy) || + (x == ds->hx && y == ds->hy)) + stale = 1; + } + if (cchanged) { + if ((x == ui->cx && y == ui->cy) || + (x == ds->cx && y == ds->cy)) + stale = 1; + } + + if (GRID(state, nums, x, y) != GRID(ds, nums, x, y)) { + GRID(ds, nums, x, y) = GRID(state, nums, x, y); + stale = 1; + } + if (GRID(state, flags, x, y) != GRID(ds, flags, x, y)) { + GRID(ds, flags, x, y) = GRID(state, flags, x, y); + stale = 1; + } + if (GRID(ds, nums, x, y) == 0) { + /* We're not a number square (therefore we might + * display hints); do we need to update? */ + for (i = 0; i < ds->order; i++) { + if (HINT(state, x, y, i) != HINT(ds, x, y, i)) { + HINT(ds, x, y, i) = HINT(state, x, y, i); + stale = 1; + } + } + } + if (stale) { + draw_furniture(dr, ds, state, ui, x, y, hflash); + if (GRID(ds, nums, x, y) > 0) + draw_num(dr, ds, x, y); + else + draw_hints(dr, ds, x, y); + } + } + } + ds->hx = ui->hx; ds->hy = ui->hy; ds->hpencil = ui->hpencil; + ds->cx = ui->cx; ds->cy = ui->cy; + ds->started = 1; + ds->hflash = hflash; +} + +static float game_anim_length(game_state *oldstate, game_state *newstate, + int dir, game_ui *ui) +{ + return 0.0F; +} + +static float game_flash_length(game_state *oldstate, game_state *newstate, + int dir, game_ui *ui) +{ + if (!oldstate->completed && newstate->completed && + !oldstate->cheated && !newstate->cheated) + return FLASH_TIME; + return 0.0F; +} + +static int game_timing_state(game_state *state, game_ui *ui) +{ + return TRUE; +} + +static void game_print_size(game_params *params, float *x, float *y) +{ + int pw, ph; + + /* 10mm squares by default, roughly the same as Grauniad. */ + game_compute_size(params, 1000, &pw, &ph); + *x = pw / 100.0F; + *y = ph / 100.0F; +} + +static void game_print(drawing *dr, game_state *state, int tilesize) +{ + int ink = print_mono_colour(dr, 0); + int x, y, o = state->order, ox, oy, n; + char str[2]; + + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + game_drawstate ads, *ds = &ads; + game_set_size(dr, ds, NULL, tilesize); + + print_line_width(dr, 2 * TILE_SIZE / 40); + + /* Squares, numbers, gt signs */ + for (y = 0; y < o; y++) { + for (x = 0; x < o; x++) { + ox = COORD(x); oy = COORD(y); + n = GRID(state, nums, x, y); + + draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink); + + str[0] = n ? n2c(n, state->order) : ' '; + str[1] = '\0'; + draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2, + FONT_VARIABLE, TILE_SIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE, + ink, str); + + draw_gts(dr, ds, ox, oy, GRID(state, flags, x, y), ink, 1); + } + } +} + +/* ---------------------------------------------------------------------- + * Housekeeping. + */ + +#ifdef COMBINED +#define thegame unequal +#endif + +const struct game thegame = { + "Unequal", "games.unequal", "unequal", + default_params, + game_fetch_preset, + decode_params, + encode_params, + free_params, + dup_params, + TRUE, game_configure, custom_params, + validate_params, + new_game_desc, + validate_desc, + new_game, + dup_game, + free_game, + TRUE, solve_game, + TRUE, game_text_format, + new_ui, + free_ui, + encode_ui, + decode_ui, + game_changed_state, + interpret_move, + execute_move, + PREFERRED_TILE_SIZE, game_compute_size, game_set_size, + game_colours, + game_new_drawstate, + game_free_drawstate, + game_redraw, + game_anim_length, + game_flash_length, + TRUE, FALSE, game_print_size, game_print, + FALSE, /* wants_statusbar */ + FALSE, game_timing_state, + 0, /* flags */ +}; + +/* ---------------------------------------------------------------------- + * Standalone solver. + */ + +#ifdef STANDALONE_SOLVER + +#include +#include + +const char *quis = NULL; + +#if 0 /* currently unused */ + +static void debug_printf(char *fmt, ...) +{ + char buf[4096]; + va_list ap; + + va_start(ap, fmt); + vsprintf(buf, fmt, ap); + puts(buf); + va_end(ap); +} + +static void game_printf(game_state *state) +{ + char *dbg = game_text_format(state); + printf("%s", dbg); + sfree(dbg); +} + +static void game_printf_wide(game_state *state) +{ + int x, y, i, n; + + for (y = 0; y < state->order; y++) { + for (x = 0; x < state->order; x++) { + n = GRID(state, nums, x, y); + for (i = 0; i < state->order; i++) { + if (n > 0) + printf("%c", n2c(n, state->order)); + else if (HINT(state, x, y, i)) + printf("%c", n2c(i+1, state->order)); + else + printf("."); + } + printf(" "); + } + printf("\n"); + } + printf("\n"); +} + +#endif + +static void pdiff(int diff) +{ + if (diff == DIFF_IMPOSSIBLE) + printf("Game is impossible.\n"); + else if (diff == DIFF_UNFINISHED) + printf("Game has incomplete.\n"); + else if (diff == DIFF_AMBIGUOUS) + printf("Game has multiple solutions.\n"); + else + printf("Game has difficulty %s.\n", unequal_diffnames[diff]); +} + +static int solve(game_params *p, char *desc, int debug) +{ + game_state *st = new_game(NULL, p, desc); + int diff; + + solver_show_working = debug; + game_debug(st); + + diff = solver_grid(st->nums, st->order, DIFF_RECURSIVE, (void*)st); + if (debug) pdiff(diff); + + game_debug(st); + free_game(st); + return diff; +} + +static void check(game_params *p) +{ + char *msg = validate_params(p, 1); + if (msg) { + fprintf(stderr, "%s: %s", quis, msg); + exit(1); + } +} + +static int gen(game_params *p, random_state *rs, int debug) +{ + char *desc, *aux; + int diff; + + check(p); + + solver_show_working = debug; + desc = new_game_desc(p, rs, &aux, 0); + diff = solve(p, desc, debug); + sfree(aux); + sfree(desc); + + return diff; +} + +static void soak(game_params *p, random_state *rs) +{ + time_t tt_start, tt_now, tt_last; + char *aux, *desc; + game_state *st; + int n = 0, neasy = 0, realdiff = p->diff; + + check(p); + + solver_show_working = 0; + maxtries = 1; + + tt_start = tt_now = time(NULL); + + printf("Soak-generating a %dx%d grid, difficulty %s.\n", + p->order, p->order, unequal_diffnames[p->diff]); + + while (1) { + p->diff = realdiff; + desc = new_game_desc(p, rs, &aux, 0); + st = new_game(NULL, p, desc); + solver_state(st, DIFF_RECURSIVE); + free_game(st); + sfree(aux); + sfree(desc); + + n++; + if (realdiff != p->diff) neasy++; + + tt_last = time(NULL); + if (tt_last > tt_now) { + tt_now = tt_last; + printf("%d total, %3.1f/s; %d/%2.1f%% easy, %3.1f/s good.\n", + n, (double)n / ((double)tt_now - tt_start), + neasy, (double)neasy*100.0/(double)n, + (double)(n - neasy) / ((double)tt_now - tt_start)); + } + } +} + +static void usage_exit(const char *msg) +{ + if (msg) + fprintf(stderr, "%s: %s\n", quis, msg); + fprintf(stderr, "Usage: %s [--seed SEED] --soak | [game_id [game_id ...]]\n", quis); + exit(1); +} + +int main(int argc, const char *argv[]) +{ + random_state *rs; + time_t seed = time(NULL); + int do_soak = 0, diff; + + game_params *p; + + maxtries = 50; + + quis = argv[0]; + while (--argc > 0) { + const char *p = *++argv; + if (!strcmp(p, "--soak")) + do_soak = 1; + else if (!strcmp(p, "--seed")) { + if (argc == 0) + usage_exit("--seed needs an argument"); + seed = (time_t)atoi(*++argv); + argc--; + } else if (*p == '-') + usage_exit("unrecognised option"); + else + break; + } + rs = random_new((void*)&seed, sizeof(time_t)); + + if (do_soak == 1) { + if (argc != 1) usage_exit("only one argument for --soak"); + p = default_params(); + decode_params(p, *argv); + soak(p, rs); + } else if (argc > 0) { + int i; + for (i = 0; i < argc; i++) { + const char *id = *argv++; + char *desc = strchr(id, ':'), *err; + p = default_params(); + if (desc) { + *desc++ = '\0'; + decode_params(p, id); + err = validate_desc(p, desc); + if (err) { + fprintf(stderr, "%s: %s\n", quis, err); + exit(1); + } + solve(p, desc, 1); + } else { + decode_params(p, id); + diff = gen(p, rs, 1); + } + } + } else { + while(1) { + p = default_params(); + p->order = random_upto(rs, 7) + 3; + p->diff = random_upto(rs, 4); + diff = gen(p, rs, 0); + pdiff(diff); + } + } + + return 0; +} + +#endif + +/* vim: set shiftwidth=4 tabstop=8: */ -- 2.11.0