From b5ba72bc4698800049947cdf7696cb44f11096bb Mon Sep 17 00:00:00 2001 From: simon Date: Mon, 11 Jan 2010 21:21:07 +0000 Subject: [PATCH] New puzzle from James Harvey: 'Singles', an implementation of Hitori. One infrastructure change in the process: latin.c has acquired a utility function to generate a latin rectangle rather than a full square. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@8828 cda61777-01e9-0310-a592-d414129be87e --- icons/Makefile | 5 +- icons/singles.sav | 45 ++ latin.c | 18 + latin.h | 3 + puzzles.but | 51 ++ singles.R | 23 + singles.c | 1963 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 2106 insertions(+), 2 deletions(-) create mode 100644 icons/singles.sav create mode 100644 singles.R create mode 100644 singles.c diff --git a/icons/Makefile b/icons/Makefile index 3cb67a4..282a60a 100644 --- a/icons/Makefile +++ b/icons/Makefile @@ -2,8 +2,8 @@ PUZZLES = blackbox bridges cube dominosa fifteen filling flip galaxies guess \ inertia keen lightup loopy map mines net netslide pattern pegs \ - rect samegame sixteen slant solo tents towers twiddle unequal \ - untangle + rect samegame singles sixteen slant solo tents towers twiddle \ + unequal untangle BASE = $(patsubst %,%-base.png,$(PUZZLES)) WEB = $(patsubst %,%-web.png,$(PUZZLES)) @@ -70,6 +70,7 @@ netslide-ibase.png : override CROP=289x289 144x144+0+0 pattern-ibase.png : override CROP=384x384 223x223+0+0 pegs-ibase.png : override CROP=263x263 147x147+116+0 rect-ibase.png : override CROP=205x205 115x115+90+0 +singles-ibase.png : override CROP=224x224 98x98+15+15 sixteen-ibase.png : override CROP=288x288 144x144+144+144 slant-ibase.png : override CROP=321x321 160x160+160+160 solo-ibase.png : override CROP=481x481 145x145+24+24 diff --git a/icons/singles.sav b/icons/singles.sav new file mode 100644 index 0000000..260fd1f --- /dev/null +++ b/icons/singles.sav @@ -0,0 +1,45 @@ +SAVEFILE:41:Simon Tatham's Portable Puzzle Collection +VERSION :1:1 +GAME :7:Singles +PARAMS :5:6x6dk +CPARAMS :5:6x6dk +SEED :15:781273601054598 +DESC :36:361566412253452144234115163346553461 +NSTATES :2:37 +STATEPOS:2:22 +MOVE :4:B1,0 +MOVE :4:C0,0 +MOVE :4:C1,1 +MOVE :4:C2,0 +MOVE :4:C0,1 +MOVE :4:B0,2 +MOVE :4:C0,3 +MOVE :4:C1,2 +MOVE :4:C4,3 +MOVE :4:B3,3 +MOVE :4:C3,2 +MOVE :4:C2,3 +MOVE :4:C3,4 +MOVE :4:B2,4 +MOVE :4:C1,4 +MOVE :4:C2,5 +MOVE :4:B1,5 +MOVE :4:C0,5 +MOVE :4:C0,4 +MOVE :4:C1,3 +MOVE :4:C3,5 +MOVE :4:B5,4 +MOVE :4:C4,4 +MOVE :4:C5,5 +MOVE :4:C5,3 +MOVE :4:C4,5 +MOVE :4:B4,0 +MOVE :4:C3,0 +MOVE :4:C4,1 +MOVE :4:C5,0 +MOVE :4:C5,1 +MOVE :4:B4,2 +MOVE :4:C5,2 +MOVE :4:C3,1 +MOVE :4:B2,1 +MOVE :4:C2,2 diff --git a/latin.c b/latin.c index 63f96a1..03d78af 100644 --- a/latin.c +++ b/latin.c @@ -1236,6 +1236,24 @@ digit *latin_generate(int o, random_state *rs) return sq; } +digit *latin_generate_rect(int w, int h, random_state *rs) +{ + int o = max(w, h), x, y; + digit *latin, *latin_rect; + + latin = latin_generate(o, rs); + latin_rect = snewn(w*h, digit); + + for (x = 0; x < w; x++) { + for (y = 0; y < h; y++) { + latin_rect[y*w + x] = latin[y*o + x]; + } + } + + sfree(latin); + return latin_rect; +} + /* -------------------------------------------------------- * Checking. */ diff --git a/latin.h b/latin.h index 5607afe..4b09f16 100644 --- a/latin.h +++ b/latin.h @@ -112,6 +112,9 @@ void latin_solver_debug(unsigned char *cube, int o); digit *latin_generate(int o, random_state *rs); +/* The order of the latin rectangle is max(w,h). */ +digit *latin_generate_rect(int w, int h, random_state *rs); + int latin_check(digit *sq, int order); /* !0 => not a latin square */ void latin_debug(digit *sq, int order); diff --git a/puzzles.but b/puzzles.but index 204aa7e..f67194f 100644 --- a/puzzles.but +++ b/puzzles.but @@ -2651,6 +2651,57 @@ level, some backtracking will be required, but the solution should still be unique. The remaining levels require increasingly complex reasoning to avoid having to backtrack. + +\C{singles} \i{Singles} + +\cfg{winhelp-topic}{games.singles} + +You have a grid of squares, all of which contain numbers. Your task +is to colour some of the squares black (removing the number) so as to satisfy +all of the following conditions: + +\b No number occurs more than once in any row or column. + +\b No black square is horizontally adjacent to any other black square. + +\b The remaining white squares must all form one contiguous region. + +Credit for this puzzle goes to \i{Nikoli} \k{nikoli-singles} who call it Hitori. + +Singles was contributed to this collection by James Harvey. + +\B{nikoli-hitori} +\W{http://www.nikoli.com/en/puzzles/hitori/index.html}\cw{http://www.nikoli.com/en/puzzles/hitori/index.html} +(beware of Flash) + +\H{singles-controls} \i{Singles controls} + +\IM{Singles controls} controls, for Singles + +Left-clicking on an empty square will colour it black; left-clicking again +will replace the number. Right-clicking will add a circle (useful for +indicating that a cell is definitely not black). + +You can also use the cursor keys to move around the grid. Pressing the +return or space keys will turn a square black or add a circle respectively, +and pressing the key again will replace the number or remove the circle. + +(All the actions described in \k{common-actions} are also available.) + +\H{singles-parameters} \I{parameters, for Singles}Singles parameters + +These parameters are available from the \q{Custom...} option on the +\q{Type} menu. + +\dt \e{Width}, \e{Height} + +\dd Size of grid in squares. + +\dt \e{Difficulty} + +\dd Controls the difficulty of the generated puzzle. + + \A{licence} \I{MIT licence}\ii{Licence} This software is \i{copyright} 2004-2010 Simon Tatham. diff --git a/singles.R b/singles.R new file mode 100644 index 0000000..3275455 --- /dev/null +++ b/singles.R @@ -0,0 +1,23 @@ +# -*- makefile -*- + +SINGLES_EXTRA = dsf latin maxflow tree234 + +singles : [X] GTK COMMON singles SINGLES_EXTRA singles-icon|no-icon +singles : [G] WINDOWS COMMON singles SINGLES_EXTRA singles.res|noicon.res + +ALL += singles[COMBINED] SINGLES_EXTRA + +singlessolver : [U] singles[STANDALONE_SOLVER] SINGLES_EXTRA STANDALONE +singlessolver : [C] singles[STANDALONE_SOLVER] SINGLES_EXTRA STANDALONE + +!begin gtk +GAMES += singles +!end + +!begin >list.c + A(singles) \ +!end + +!begin >wingames.lst +singles.exe:Singles +!end diff --git a/singles.c b/singles.c new file mode 100644 index 0000000..ec5db73 --- /dev/null +++ b/singles.c @@ -0,0 +1,1963 @@ +/* + * singles.c: implementation of Hitori ('let me alone') from Nikoli. + * + * Make single-get able to fetch a specific puzzle ID from menneske.no? + * + * www.menneske.no solving methods: + * + * Done: + * SC: if you circle a cell, any cells in same row/col with same no --> black + * -- solver_op_circle + * SB: if you make a cell black, any cells around it --> white + * -- solver_op_blacken + * ST: 3 identical cells in row, centre is white and outer two black. + * SP: 2 identical cells with single-cell gap, middle cell is white. + * -- solver_singlesep (both ST and SP) + * PI: if you have a pair of same number in row/col, any other + * cells of same number must be black. + * -- solve_doubles + * CC: if you have a black on edge one cell away from corner, cell + * on edge diag. adjacent must be white. + * CE: if you have 2 black cells of triangle on edge, third cell must + * be white. + * QM: if you have 3 black cells of diagonal square in middle, fourth + * cell must be white. + * -- solve_allblackbutone (CC, CE, and QM). + * QC: a corner with 4 identical numbers (or 2 and 2) must have the + * corner cell (and cell diagonal to that) black. + * TC: a corner with 3 identical numbers (with the L either way) + * must have the apex of L black, and other two white. + * DC: a corner with 2 identical numbers in domino can set a white + * cell along wall. + * -- solve_corners (QC, TC, DC) + * IP: pair with one-offset-pair force whites by offset pair + * -- solve_offsetpair + * MC: any cells diag. adjacent to black cells that would split board + * into separate white regions must be white. + * -- solve_removesplits + * + * Still to do: + * + * TEP: 3 pairs of dominos parallel to side, can mark 4 white cells + * alongside. + * DEP: 2 pairs of dominos parallel to side, can mark 2 white cells. + * FI: if you have two sets of double-cells packed together, singles + * in that row/col must be white (qv. PI) + * QuM: four identical cells (or 2 and 2) in middle of grid only have + * two possible solutions each. + * FDE: doubles one row/column away from edge can force a white cell. + * FDM: doubles in centre (next to bits of diag. square) can force a white cell. + * MP: two pairs with same number between force number to black. + * CnC: if circling a cell leads to impossible board, cell is black. + * MC: if we have two possiblilities, can we force a white circle? + * + */ + +#include +#include +#include +#include +#include +#include + +#include "puzzles.h" +#include "latin.h" + +#ifdef STANDALONE_SOLVER +int verbose = 0; +#endif + +#define PREFERRED_TILE_SIZE 32 +#define TILE_SIZE (ds->tilesize) +#define BORDER (TILE_SIZE / 2) + +#define CRAD ((TILE_SIZE / 2) - 1) +#define TEXTSZ ((14*CRAD/10) - 1) /* 2 * sqrt(2) of CRAD */ + +#define COORD(x) ( (x) * TILE_SIZE + BORDER ) +#define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 ) + +#define INGRID(s,x,y) ((x) >= 0 && (x) < (s)->w && (y) >= 0 && (y) < (s)->h) + +#define FLASH_TIME 0.7F + +enum { + COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT, + COL_BLACK, COL_WHITE, COL_BLACKNUM, COL_GRID, + COL_CURSOR, COL_ERROR, + NCOLOURS +}; + +struct game_params { + int w, h, diff; +}; + +#define F_BLACK 0x1 +#define F_CIRCLE 0x2 +#define F_ERROR 0x4 +#define F_SCRATCH 0x8 + +struct game_state { + int w, h, n, o; /* n = w*h; o = max(w, h) */ + int completed, used_solve, impossible; + int *nums; /* size w*h */ + unsigned int *flags; /* size w*h */ +}; + +/* top, right, bottom, left */ +static const int dxs[4] = { 0, 1, 0, -1 }; +static const int dys[4] = { -1, 0, 1, 0 }; + +/* --- Game parameters and preset functions --- */ + +#define DIFFLIST(A) \ + A(EASY,Easy,e) \ + A(TRICKY,Tricky,k) + +#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_MAX, DIFF_ANY }; +static char const *const singles_diffnames[] = { DIFFLIST(TITLE) }; +static char const singles_diffchars[] = DIFFLIST(ENCODE); +#define DIFFCOUNT lenof(singles_diffchars) +#define DIFFCONFIG DIFFLIST(CONFIG) + +static game_params *default_params(void) +{ + game_params *ret = snew(game_params); + ret->w = ret->h = 5; + ret->diff = DIFF_EASY; + + return ret; +} + +static const struct game_params singles_presets[] = { + { 5, 5, DIFF_EASY }, + { 5, 5, DIFF_TRICKY }, + { 6, 6, DIFF_EASY }, + { 6, 6, DIFF_TRICKY }, + { 8, 8, DIFF_EASY }, + { 8, 8, DIFF_TRICKY }, + { 10, 10, DIFF_EASY }, + { 10, 10, DIFF_TRICKY }, + { 12, 12, DIFF_EASY }, + { 12, 12, DIFF_TRICKY } +}; + +static int game_fetch_preset(int i, char **name, game_params **params) +{ + game_params *ret; + char buf[80]; + + if (i < 0 || i >= lenof(singles_presets)) + return FALSE; + + ret = default_params(); + *ret = singles_presets[i]; + *params = ret; + + sprintf(buf, "%dx%d %s", ret->w, ret->h, singles_diffnames[ret->diff]); + *name = dupstr(buf); + + return TRUE; +} + +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; + int i; + + ret->w = ret->h = atoi(p); + while (*p && isdigit((unsigned char)*p)) p++; + if (*p == 'x') { + p++; + ret->h = atoi(p); + while (*p && isdigit((unsigned char)*p)) p++; + } + if (*p == 'd') { + ret->diff = DIFF_MAX; /* which is invalid */ + p++; + for (i = 0; i < DIFFCOUNT; i++) { + if (*p == singles_diffchars[i]) + ret->diff = i; + } + p++; + } +} + +static char *encode_params(game_params *params, int full) +{ + char data[256]; + + if (full) + sprintf(data, "%dx%dd%c", params->w, params->h, singles_diffchars[params->diff]); + else + sprintf(data, "%dx%d", params->w, params->h); + + return dupstr(data); +} + +static config_item *game_configure(game_params *params) +{ + config_item *ret; + char buf[80]; + + ret = snewn(4, config_item); + + ret[0].name = "Width"; + ret[0].type = C_STRING; + sprintf(buf, "%d", params->w); + ret[0].sval = dupstr(buf); + ret[0].ival = 0; + + ret[1].name = "Height"; + ret[1].type = C_STRING; + sprintf(buf, "%d", params->h); + ret[1].sval = dupstr(buf); + ret[1].ival = 0; + + ret[2].name = "Difficulty"; + ret[2].type = C_CHOICES; + ret[2].sval = DIFFCONFIG; + ret[2].ival = params->diff; + + ret[3].name = NULL; + ret[3].type = C_END; + ret[3].sval = NULL; + ret[3].ival = 0; + + return ret; +} + +static game_params *custom_params(config_item *cfg) +{ + game_params *ret = snew(game_params); + + ret->w = atoi(cfg[0].sval); + ret->h = atoi(cfg[1].sval); + ret->diff = cfg[2].ival; + + return ret; +} + +static char *validate_params(game_params *params, int full) +{ + if (params->w < 2 || params->h < 2) + return "Width and neight must be at least two"; + if (params->w > 10+26+26 || params->h > 10+26+26) + return "Puzzle is too large"; + if (full) { + if (params->diff < 0 || params->diff >= DIFF_MAX) + return "Unknown difficulty rating"; + } + + return NULL; +} + +/* --- Game description string generation and unpicking --- */ + +static game_state *blank_game(int w, int h) +{ + game_state *state = snew(game_state); + + memset(state, 0, sizeof(game_state)); + state->w = w; + state->h = h; + state->n = w*h; + state->o = max(w,h); + + state->completed = state->used_solve = state->impossible = 0; + + state->nums = snewn(state->n, int); + state->flags = snewn(state->n, unsigned int); + + memset(state->nums, 0, state->n*sizeof(int)); + memset(state->flags, 0, state->n*sizeof(unsigned int)); + + return state; +} + +static game_state *dup_game(game_state *state) +{ + game_state *ret = blank_game(state->w, state->h); + + ret->completed = state->completed; + ret->used_solve = state->used_solve; + ret->impossible = state->impossible; + + memcpy(ret->nums, state->nums, state->n*sizeof(int)); + memcpy(ret->flags, state->flags, state->n*sizeof(unsigned int)); + + return ret; +} + +static void free_game(game_state *state) +{ + sfree(state->nums); + sfree(state->flags); + sfree(state); +} + +static char n2c(int num) { + if (num < 10) + return '0' + num; + else if (num < 10+26) + return 'a' + num - 10; + else + return 'A' + num - 10 - 26; + return '?'; +} + +static int c2n(char c) { + if (isdigit(c)) + return (int)(c - '0'); + else if (c >= 'a' && c <= 'z') + return (int)(c - 'a' + 10); + else if (c >= 'A' && c <= 'Z') + return (int)(c - 'A' + 10 + 26); + return -1; +} + +static void unpick_desc(game_params *params, char *desc, + game_state **sout, char **mout) +{ + game_state *state = blank_game(params->w, params->h); + char *msg = NULL; + int num = 0, i = 0; + + if (strlen(desc) != state->n) { + msg = "Game description is wrong length"; + goto done; + } + for (i = 0; i < state->n; i++) { + num = c2n(desc[i]); + if (num <= 0 || num > state->o) { + msg = "Game description contains unexpected characters"; + goto done; + } + state->nums[i] = num; + } +done: + if (msg) { /* sth went wrong. */ + if (mout) *mout = msg; + free_game(state); + } else { + if (mout) *mout = NULL; + if (sout) *sout = state; + else free_game(state); + } +} + +static char *generate_desc(game_state *state, int issolve) +{ + char *ret = snewn(state->n+1+(issolve?1:0), char); + int i, p=0; + + if (issolve) + ret[p++] = 'S'; + for (i = 0; i < state->n; i++) + ret[p++] = n2c(state->nums[i]); + ret[p] = '\0'; + return ret; +} + +/* --- Useful game functions (completion, etc.) --- */ + +static int game_can_format_as_text_now(game_params *params) +{ + return TRUE; +} + +static char *game_text_format(game_state *state) +{ + int len, x, y, i; + char *ret, *p; + + len = (state->w)*2; /* one row ... */ + len = len * (state->h*2); /* ... h rows, including gaps ... */ + len += 1; /* ... final NL */ + p = ret = snewn(len, char); + + for (y = 0; y < state->h; y++) { + for (x = 0; x < state->w; x++) { + i = y*state->w + x; + if (x > 0) *p++ = ' '; + *p++ = (state->flags[i] & F_BLACK) ? '*' : n2c(state->nums[i]); + } + *p++ = '\n'; + for (x = 0; x < state->w; x++) { + i = y*state->w + x; + if (x > 0) *p++ = ' '; + *p++ = (state->flags[i] & F_CIRCLE) ? '~' : ' '; + } + *p++ = '\n'; + } + *p++ = '\0'; + assert(p - ret == len); + + return ret; +} + +static void debug_state(const char *desc, game_state *state) { + char *dbg = game_text_format(state); + debug(("%s:\n%s", desc, dbg)); + sfree(dbg); +} + +static void connect_if_same(game_state *state, int *dsf, int i1, int i2) +{ + int c1, c2; + + if ((state->flags[i1] & F_BLACK) != (state->flags[i2] & F_BLACK)) + return; + + c1 = dsf_canonify(dsf, i1); + c2 = dsf_canonify(dsf, i2); + dsf_merge(dsf, c1, c2); +} + +static void connect_dsf(game_state *state, int *dsf) +{ + int x, y, i; + + /* Construct a dsf array for connected blocks; connections + * tracked to right and down. */ + dsf_init(dsf, state->n); + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + i = y*state->w + x; + + if (x < state->w-1) + connect_if_same(state, dsf, i, i+1); /* right */ + if (y < state->h-1) + connect_if_same(state, dsf, i, i+state->w); /* down */ + } + } +} + +static int check_rowcol(game_state *state, int starti, int di, int sz, int mark_errors) +{ + int nerr = 0, n, m, i, j; + + /* if any circled numbers have identical non-circled numbers on + * same row/column, error (non-circled) + * if any circled numbers in same column are same number, highlight them. + * if any rows/columns have >1 of same number, not complete. */ + + for (n = 0, i = starti; n < sz; n++, i += di) { + if (state->flags[i] & F_BLACK) continue; + for (m = n+1, j = i+di; m < sz; m++, j += di) { + if (state->flags[j] & F_BLACK) continue; + if (state->nums[i] != state->nums[j]) continue; + + nerr++; /* ok, we have two numbers the same in a row. */ + if (!mark_errors) continue; + + /* If we have two circles in the same row around + * two identical numbers, they are _both_ wrong. */ + if ((state->flags[i] & F_CIRCLE) && + (state->flags[j] & F_CIRCLE)) { + state->flags[i] |= F_ERROR; + state->flags[j] |= F_ERROR; + } + /* Otherwise, if we have a circle, any other identical + * numbers in that row are obviously wrong. We don't + * highlight this, however, since it makes the process + * of solving the puzzle too easy (you circle a number + * and it promptly tells you which numbers to blacken! */ +#if 0 + else if (state->flags[i] & F_CIRCLE) + state->flags[j] |= F_ERROR; + else if (state->flags[j] & F_CIRCLE) + state->flags[i] |= F_ERROR; +#endif + } + } + return nerr; +} + +static int check_complete(game_state *state, int mark_errors) +{ + int *dsf = snewn(state->n, int); + int x, y, i, error = 0, nwhite, w = state->w, h = state->h; + + if (mark_errors) { + for (i = 0; i < state->n; i++) + state->flags[i] &= ~F_ERROR; + } + connect_dsf(state, dsf); + + /* Mark any black squares in groups of >1 as errors. + * Count number of white squares. */ + nwhite = 0; + for (i = 0; i < state->n; i++) { + if (state->flags[i] & F_BLACK) { + if (dsf_size(dsf, i) > 1) { + error += 1; + if (mark_errors) + state->flags[i] |= F_ERROR; + } + } else + nwhite += 1; + } + + /* Check attributes of white squares, row- and column-wise. */ + for (x = 0; x < w; x++) /* check cols from (x,0) */ + error += check_rowcol(state, x, w, h, mark_errors); + for (y = 0; y < h; y++) /* check rows from (0,y) */ + error += check_rowcol(state, y*w, 1, w, mark_errors); + + /* mark (all) white regions as an error if there is more than one. + * may want to make this less in-your-face (by only marking + * the smallest region as an error, for example -- but what if we + * have two regions of identical size?) */ + for (i = 0; i < state->n; i++) { + if (!(state->flags[i] & F_BLACK) && + dsf_size(dsf, i) < nwhite) { + error += 1; + if (mark_errors) + state->flags[i] |= F_ERROR; + } + } + + sfree(dsf); + return (error > 0) ? 0 : 1; +} + +static char *game_state_diff(game_state *src, game_state *dst, int issolve) +{ + char *ret = NULL, buf[80], c; + int retlen = 0, x, y, i, k; + unsigned int fmask = F_BLACK | F_CIRCLE; + + assert(src->n == dst->n); + + if (issolve) { + ret = sresize(ret, 3, char); + ret[0] = 'S'; ret[1] = ';'; ret[2] = '\0'; + retlen += 2; + } + + for (x = 0; x < dst->w; x++) { + for (y = 0; y < dst->h; y++) { + i = y*dst->w + x; + if ((src->flags[i] & fmask) != (dst->flags[i] & fmask)) { + assert((dst->flags[i] & fmask) != fmask); + if (dst->flags[i] & F_BLACK) + c = 'B'; + else if (dst->flags[i] & F_CIRCLE) + c = 'C'; + else + c = 'E'; + k = sprintf(buf, "%c%d,%d;", (int)c, x, y); + ret = sresize(ret, retlen + k + 1, char); + strcpy(ret + retlen, buf); + retlen += k; + } + } + } + return ret; +} + +/* --- Solver --- */ + +enum { BLACK, CIRCLE }; + +struct solver_op { + int x, y, op; /* op one of BLACK or CIRCLE. */ + const char *desc; /* must be non-malloced. */ +}; + +struct solver_state { + struct solver_op *ops; + int n_ops, n_alloc; + int *scratch; +}; + +static struct solver_state *solver_state_new(game_state *state) +{ + struct solver_state *ss = snew(struct solver_state); + + ss->ops = NULL; + ss->n_ops = ss->n_alloc = 0; + ss->scratch = snewn(state->n, int); + + return ss; +} + +static void solver_state_free(struct solver_state *ss) +{ + sfree(ss->scratch); + if (ss->ops) sfree(ss->ops); + sfree(ss); +} + +static void solver_op_add(struct solver_state *ss, int x, int y, int op, const char *desc) +{ + struct solver_op *sop; + + if (ss->n_alloc < ss->n_ops + 1) { + ss->n_alloc = (ss->n_alloc + 1) * 2; + ss->ops = sresize(ss->ops, ss->n_alloc, struct solver_op); + } + sop = &(ss->ops[ss->n_ops++]); + sop->x = x; sop->y = y; sop->op = op; sop->desc = desc; + debug(("added solver op %s ('%s') at (%d,%d)", + op == BLACK ? "BLACK" : "CIRCLE", desc, x, y)); +} + +static void solver_op_circle(game_state *state, struct solver_state *ss, + int x, int y) +{ + int i = y*state->w + x; + + if (!INGRID(state, x, y)) return; + if (state->flags[i] & F_BLACK) { + debug(("... solver wants to add auto-circle on black (%d,%d)", x, y)); + state->impossible = 1; + return; + } + /* Only add circle op if it's not already circled. */ + if (!(state->flags[i] & F_CIRCLE)) { + solver_op_add(ss, x, y, CIRCLE, "SB - adjacent to black square"); + } +} + +static void solver_op_blacken(game_state *state, struct solver_state *ss, + int x, int y, int num) +{ + int i = y*state->w + x; + + if (!INGRID(state, x, y)) return; + if (state->nums[i] != num) return; + if (state->flags[i] & F_CIRCLE) { + debug(("... solver wants to add auto-black on circled(%d,%d)", x, y)); + state->impossible = 1; + return; + } + /* Only add black op if it's not already black. */ + if (!(state->flags[i] & F_BLACK)) { + solver_op_add(ss, x, y, BLACK, "SC - number on same row/col as circled"); + } +} + +static int solver_ops_do(game_state *state, struct solver_state *ss) +{ + int next_op = 0, i, x, y, n_ops = 0; + struct solver_op op; + + /* Care here: solver_op_* may call solver_op_add which may extend the + * ss->n_ops. */ + + while (next_op < ss->n_ops) { + op = ss->ops[next_op++]; /* copy this away, it may get reallocated. */ + i = op.y*state->w + op.x; + + if (op.op == BLACK) { + if (state->flags[i] & F_CIRCLE) { + debug(("Solver wants to blacken circled square (%d,%d)!", op.x, op.y)); + state->impossible = 1; + return n_ops; + } + if (!(state->flags[i] & F_BLACK)) { + debug(("... solver adding black at (%d,%d): %s", op.x, op.y, op.desc)); +#ifdef STANDALONE_SOLVER + if (verbose) + printf("Adding black at (%d,%d): %s\n", op.x, op.y, op.desc); +#endif + state->flags[i] |= F_BLACK; + /*debug_state("State after adding black", state);*/ + n_ops++; + solver_op_circle(state, ss, op.x-1, op.y); + solver_op_circle(state, ss, op.x+1, op.y); + solver_op_circle(state, ss, op.x, op.y-1); + solver_op_circle(state, ss, op.x, op.y+1); + } + } else { + if (state->flags[i] & F_BLACK) { + debug(("Solver wants to circle blackened square (%d,%d)!", op.x, op.y)); + state->impossible = 1; + return n_ops; + } + if (!(state->flags[i] & F_CIRCLE)) { + debug(("... solver adding circle at (%d,%d): %s", op.x, op.y, op.desc)); +#ifdef STANDALONE_SOLVER + if (verbose) + printf("Adding circle at (%d,%d): %s\n", op.x, op.y, op.desc); +#endif + state->flags[i] |= F_CIRCLE; + /*debug_state("State after adding circle", state);*/ + n_ops++; + for (x = 0; x < state->w; x++) { + if (x != op.x) + solver_op_blacken(state, ss, x, op.y, state->nums[i]); + } + for (y = 0; y < state->h; y++) { + if (y != op.y) + solver_op_blacken(state, ss, op.x, y, state->nums[i]); + } + } + } + } + ss->n_ops = 0; + return n_ops; +} + +/* If the grid has two identical numbers with one cell between them, the inner + * cell _must_ be white (and thus circled); (at least) one of the two must be + * black (since they're in the same column or row) and thus the middle cell is + * next to a black cell. */ +static int solve_singlesep(game_state *state, struct solver_state *ss) +{ + int x, y, i, ir, irr, id, idd, n_ops = ss->n_ops; + + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + i = y*state->w + x; + + /* Cell two to our right? */ + ir = i + 1; irr = ir + 1; + if (x < (state->w-2) && + state->nums[i] == state->nums[irr] && + !(state->flags[ir] & F_CIRCLE)) { + solver_op_add(ss, x+1, y, CIRCLE, "SP/ST - between identical nums"); + } + /* Cell two below us? */ + id = i + state->w; idd = id + state->w; + if (y < (state->h-2) && + state->nums[i] == state->nums[idd] && + !(state->flags[id] & F_CIRCLE)) { + solver_op_add(ss, x, y+1, CIRCLE, "SP/ST - between identical nums"); + } + } + } + return ss->n_ops - n_ops; +} + +/* If we have two identical numbers next to each other (in a row or column), + * any other identical numbers in that column must be black. */ +static int solve_doubles(game_state *state, struct solver_state *ss) +{ + int x, y, i, ii, n_ops = ss->n_ops, xy; + + for (y = 0, i = 0; y < state->h; y++) { + for (x = 0; x < state->w; x++, i++) { + assert(i == y*state->w+x); + if (state->flags[i] & F_BLACK) continue; + + ii = i+1; /* check cell to our right. */ + if (x < (state->w-1) && + !(state->flags[ii] & F_BLACK) && + state->nums[i] == state->nums[ii]) { + for (xy = 0; xy < state->w; xy++) { + if (xy == x || xy == (x+1)) continue; + if (state->nums[y*state->w + xy] == state->nums[i] && + !(state->flags[y*state->w + xy] & F_BLACK)) + solver_op_add(ss, xy, y, BLACK, "PI - same row as pair"); + } + } + + ii = i+state->w; /* check cell below us */ + if (y < (state->h-1) && + !(state->flags[ii] & F_BLACK) && + state->nums[i] == state->nums[ii]) { + for (xy = 0; xy < state->h; xy++) { + if (xy == y || xy == (y+1)) continue; + if (state->nums[xy*state->w + x] == state->nums[i] && + !(state->flags[xy*state->w + x] & F_BLACK)) + solver_op_add(ss, x, xy, BLACK, "PI - same col as pair"); + } + } + } + } + return ss->n_ops - n_ops; +} + +/* If a white square has all-but-one possible adjacent squares black, the + * one square left over must be white. */ +static int solve_allblackbutone(game_state *state, struct solver_state *ss) +{ + int x, y, i, n_ops = ss->n_ops, xd, yd, id, ifree; + int dis[4], d; + + dis[0] = -state->w; + dis[1] = 1; + dis[2] = state->w; + dis[3] = -1; + + for (y = 0, i = 0; y < state->h; y++) { + for (x = 0; x < state->w; x++, i++) { + assert(i == y*state->w+x); + if (state->flags[i] & F_BLACK) continue; + + ifree = -1; + for (d = 0; d < 4; d++) { + xd = x + dxs[d]; yd = y + dys[d]; id = i + dis[d]; + if (!INGRID(state, xd, yd)) continue; + + if (state->flags[id] & F_CIRCLE) + goto skip; /* this cell already has a way out */ + if (!(state->flags[id] & F_BLACK)) { + if (ifree != -1) + goto skip; /* this cell has >1 white cell around it. */ + ifree = id; + } + } + if (ifree != -1) + solver_op_add(ss, ifree%state->w, ifree/state->w, CIRCLE, + "CC/CE/QM: white cell with single non-black around it"); + else { + debug(("White cell with no escape at (%d,%d)", x, y)); + state->impossible = 1; + return 0; + } +skip: ; + } + } + return ss->n_ops - n_ops; +} + +/* If we have 4 numbers the same in a 2x2 corner, the far corner and the + * diagonally-adjacent square must both be black. + * If we have 3 numbers the same in a 2x2 corner, the apex of the L + * thus formed must be black. + * If we have 2 numbers the same in a 2x2 corner, the non-same cell + * one away from the corner must be white. */ +static void solve_corner(game_state *state, struct solver_state *ss, + int x, int y, int dx, int dy) +{ + int is[4], ns[4], xx, yy, w = state->w; + + for (yy = 0; yy < 2; yy++) { + for (xx = 0; xx < 2; xx++) { + is[yy*2+xx] = (y + dy*yy) * w + (x + dx*xx); + ns[yy*2+xx] = state->nums[is[yy*2+xx]]; + } + } /* order is now (corner, side 1, side 2, inner) */ + + if (ns[0] == ns[1] && ns[0] == ns[2] && ns[0] == ns[3]) { + solver_op_add(ss, is[0]%w, is[0]/w, BLACK, "QC: corner with 4 matching"); + solver_op_add(ss, is[3]%w, is[3]/w, BLACK, "QC: corner with 4 matching"); + } else if (ns[0] == ns[1] && ns[0] == ns[2]) { + /* corner and 2 sides: apex is corner. */ + solver_op_add(ss, is[0]%w, is[0]/w, BLACK, "TC: corner apex from 3 matching"); + } else if (ns[1] == ns[2] && ns[1] == ns[3]) { + /* side, side, fourth: apex is fourth. */ + solver_op_add(ss, is[3]%w, is[3]/w, BLACK, "TC: inside apex from 3 matching"); + } else if (ns[0] == ns[1] || ns[1] == ns[3]) { + /* either way here we match the non-identical side. */ + solver_op_add(ss, is[2]%w, is[2]/w, CIRCLE, "DC: corner with 2 matching"); + } else if (ns[0] == ns[2] || ns[2] == ns[3]) { + /* ditto */ + solver_op_add(ss, is[1]%w, is[1]/w, CIRCLE, "DC: corner with 2 matching"); + } +} + +static int solve_corners(game_state *state, struct solver_state *ss) +{ + int n_ops = ss->n_ops; + + solve_corner(state, ss, 0, 0, 1, 1); + solve_corner(state, ss, state->w-1, 0, -1, 1); + solve_corner(state, ss, state->w-1, state->h-1, -1, -1); + solve_corner(state, ss, 0, state->h-1, 1, -1); + + return ss->n_ops - n_ops; +} + +/* If you have the following situation: + * ... + * ...x A x x y A x... + * ...x B x x B y x... + * ... + * then both squares marked 'y' must be white. One of the left-most A or B must + * be white (since two side-by-side black cells are disallowed), which means + * that the corresponding right-most A or B must be black (since you can't + * have two of the same number on one line); thus, the adjacent squares + * to that right-most A or B must be white, which include the two marked 'y' + * in either case. + * Obviously this works in any row or column. It also works if A == B. + * It doesn't work for the degenerate case: + * ...x A A x x + * ...x B y x x + * where the square marked 'y' isn't necessarily white (consider the left-most A + * is black). + * + * */ +static void solve_offsetpair_pair(game_state *state, struct solver_state *ss, + int x1, int y1, int x2, int y2) +{ + int ox, oy, w = state->w, ax, ay, an, d, dx[2], dy[2], dn, xd, yd; + + if (x1 == x2) { /* same column */ + ox = 1; oy = 0; + } else { + assert(y1 == y2); + ox = 0; oy = 1; + } + + /* We try adjacent to (x1,y1) and the two diag. adjacent to (x2, y2). + * We expect to be called twice, once each way around. */ + ax = x1+ox; ay = y1+oy; + assert(INGRID(state, ax, ay)); + an = state->nums[ay*w + ax]; + + dx[0] = x2 + ox + oy; dx[1] = x2 + ox - oy; + dy[0] = y2 + oy + ox; dy[1] = y2 + oy - ox; + + for (d = 0; d < 2; d++) { + if (INGRID(state, dx[d], dy[d]) && (dx[d] != ax || dy[d] != ay)) { + /* The 'dx != ax || dy != ay' removes the degenerate case, + * mentioned above. */ + dn = state->nums[dy[d]*w + dx[d]]; + if (an == dn) { + /* We have a match; so (WLOG) the 'A' marked above are at + * (x1,y1) and (x2,y2), and the 'B' are at (ax,ay) and (dx,dy). */ + debug(("Found offset-pair: %d at (%d,%d) and (%d,%d)", + state->nums[y1*w + x1], x1, y1, x2, y2)); + debug((" and: %d at (%d,%d) and (%d,%d)", + an, ax, ay, dx[d], dy[d])); + + xd = dx[d] - x2; yd = dy[d] - y2; + solver_op_add(ss, x2 + xd, y2, CIRCLE, "IP: next to offset-pair"); + solver_op_add(ss, x2, y2 + yd, CIRCLE, "IP: next to offset-pair"); + } + } + } +} + +static int solve_offsetpair(game_state *state, struct solver_state *ss) +{ + int n_ops = ss->n_ops, x, xx, y, yy, n1, n2; + + for (x = 0; x < state->w-1; x++) { + for (y = 0; y < state->h; y++) { + n1 = state->nums[y*state->w + x]; + for (yy = y+1; yy < state->h; yy++) { + n2 = state->nums[yy*state->w + x]; + if (n1 == n2) { + solve_offsetpair_pair(state, ss, x, y, x, yy); + solve_offsetpair_pair(state, ss, x, yy, x, y); + } + } + } + } + for (y = 0; y < state->h-1; y++) { + for (x = 0; x < state->w; x++) { + n1 = state->nums[y*state->w + x]; + for (xx = x+1; xx < state->w; xx++) { + n2 = state->nums[y*state->w + xx]; + if (n1 == n2) { + solve_offsetpair_pair(state, ss, x, y, xx, y); + solve_offsetpair_pair(state, ss, xx, y, x, y); + } + } + } + } + return ss->n_ops - n_ops; +} + +static int solve_hassinglewhiteregion(game_state *state, struct solver_state *ss) +{ + int i, j, nwhite = 0, lwhite = -1, szwhite, start, end, next, a, d, x, y; + + for (i = 0; i < state->n; i++) { + if (!(state->flags[i] & F_BLACK)) { + nwhite++; + lwhite = i; + } + state->flags[i] &= ~F_SCRATCH; + } + if (lwhite == -1) { + debug(("solve_hassinglewhite: no white squares found!")); + state->impossible = 1; + return 0; + } + /* We don't use connect_dsf here; it's too slow, and there's a quicker + * algorithm if all we want is the size of one region. */ + /* Having written this, this algorithm is only about 5% faster than + * using a dsf. */ + memset(ss->scratch, -1, state->n * sizeof(int)); + ss->scratch[0] = lwhite; + state->flags[lwhite] |= F_SCRATCH; + start = 0; end = next = 1; + while (start < end) { + for (a = start; a < end; a++) { + i = ss->scratch[a]; assert(i != -1); + for (d = 0; d < 4; d++) { + x = (i % state->w) + dxs[d]; + y = (i / state->w) + dys[d]; + j = y*state->w + x; + if (!INGRID(state, x, y)) continue; + if (state->flags[j] & (F_BLACK | F_SCRATCH)) continue; + ss->scratch[next++] = j; + state->flags[j] |= F_SCRATCH; + } + } + start = end; end = next; + } + szwhite = next; + return (szwhite == nwhite) ? 1 : 0; +} + +static void solve_removesplits_check(game_state *state, struct solver_state *ss, + int x, int y) +{ + int i = y*state->w + x, issingle; + + if (!INGRID(state, x, y)) return; + if ((state->flags[i] & F_CIRCLE) || (state->flags[i] & F_BLACK)) + return; + + /* If putting a black square at (x,y) would make the white region + * non-contiguous, it must be circled. */ + state->flags[i] |= F_BLACK; + issingle = solve_hassinglewhiteregion(state, ss); + state->flags[i] &= ~F_BLACK; + + if (!issingle) + solver_op_add(ss, x, y, CIRCLE, "MC: black square here would split white region"); +} + +/* For all black squares, search in squares diagonally adjacent to see if + * we can rule out putting a black square there (because it would make the + * white region non-contiguous). */ +/* This function is likely to be somewhat slow. */ +static int solve_removesplits(game_state *state, struct solver_state *ss) +{ + int i, x, y, n_ops = ss->n_ops; + + if (!solve_hassinglewhiteregion(state, ss)) { + debug(("solve_removesplits: white region is not contiguous at start!")); + state->impossible = 1; + return 0; + } + + for (i = 0; i < state->n; i++) { + if (!(state->flags[i] & F_BLACK)) continue; + + x = i%state->w; y = i/state->w; + solve_removesplits_check(state, ss, x-1, y-1); + solve_removesplits_check(state, ss, x+1, y-1); + solve_removesplits_check(state, ss, x+1, y+1); + solve_removesplits_check(state, ss, x-1, y+1); + } + return ss->n_ops - n_ops; +} + +/* + * This function performs a solver step that isn't implicit in the rules + * of the game and is thus treated somewhat differently. + * + * It marks cells whose number does not exist elsewhere in its row/column + * with circles. As it happens the game generator here does mean that this + * is always correct, but it's a solving method that people should not have + * to rely upon (except in the hidden 'sneaky' difficulty setting) and so + * all grids at 'tricky' and above are checked to make sure that the grid + * is no easier if this solving step is performed beforehand. + * + * Calling with ss=NULL just returns the number of sneaky deductions that + * would have been made. + */ +static int solve_sneaky(game_state *state, struct solver_state *ss) +{ + int i, ii, x, xx, y, yy, nunique = 0; + + /* Clear SCRATCH flags. */ + for (i = 0; i < state->n; i++) state->flags[i] &= ~F_SCRATCH; + + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + i = y*state->w + x; + + /* Check for duplicate numbers on our row, mark (both) if so */ + for (xx = x; xx < state->w; xx++) { + ii = y*state->w + xx; + if (i == ii) continue; + + if (state->nums[i] == state->nums[ii]) { + state->flags[i] |= F_SCRATCH; + state->flags[ii] |= F_SCRATCH; + } + } + + /* Check for duplicate numbers on our col, mark (both) if so */ + for (yy = y; yy < state->h; yy++) { + ii = yy*state->w + x; + if (i == ii) continue; + + if (state->nums[i] == state->nums[ii]) { + state->flags[i] |= F_SCRATCH; + state->flags[ii] |= F_SCRATCH; + } + } + } + } + + /* Any cell with no marking has no duplicates on its row or column: + * set its CIRCLE. */ + for (i = 0; i < state->n; i++) { + if (!(state->flags[i] & F_SCRATCH)) { + if (ss) solver_op_add(ss, i%state->w, i/state->w, CIRCLE, + "SNEAKY: only one of its number in row and col"); + nunique += 1; + } else + state->flags[i] &= ~F_SCRATCH; + } + return nunique; +} + +static int solve_specific(game_state *state, int diff, int sneaky) +{ + struct solver_state *ss = solver_state_new(state); + + if (sneaky) solve_sneaky(state, ss); + + /* Some solver operations we only have to perform once -- + * they're only based on the numbers available, and not black + * squares or circles which may be added later. */ + + solve_singlesep(state, ss); /* never sets impossible */ + solve_doubles(state, ss); /* ditto */ + solve_corners(state, ss); /* ditto */ + + if (diff >= DIFF_TRICKY) + solve_offsetpair(state, ss); /* ditto */ + + while (1) { + if (ss->n_ops > 0) solver_ops_do(state, ss); + if (state->impossible) break; + + if (solve_allblackbutone(state, ss) > 0) continue; + if (state->impossible) break; + + if (diff >= DIFF_TRICKY) { + if (solve_removesplits(state, ss) > 0) continue; + if (state->impossible) break; + } + + break; + } + + solver_state_free(ss); + return state->impossible ? -1 : check_complete(state, 0); +} + +static char *solve_game(game_state *state, game_state *currstate, + char *aux, char **error) +{ + game_state *solved = dup_game(currstate); + char *move = NULL; + + if (solve_specific(solved, DIFF_ANY, 0)) goto solved; + free_game(solved); + + solved = dup_game(state); + if (solve_specific(solved, DIFF_ANY, 0)) goto solved; + free_game(solved); + + *error = "Unable to solve puzzle."; + return NULL; + +solved: + move = game_state_diff(currstate, solved, 1); + free_game(solved); + return move; +} + +/* --- Game generation --- */ + +/* A correctly completed Hitori board is essentially a latin square + * (no duplicated numbers in any row or column) with black squares + * added such that no black square touches another, and the white + * squares make a contiguous region. + * + * So we can generate it by: + * constructing a latin square + * adding black squares at random (minding the constraints) + * altering the numbers under the new black squares such that + the solver gets a headstart working out where they are. + */ + +static int new_game_is_good(game_params *params, + game_state *state, game_state *tosolve) +{ + int sret, sret_easy = 0; + + memcpy(tosolve->nums, state->nums, state->n * sizeof(int)); + memset(tosolve->flags, 0, state->n * sizeof(unsigned int)); + tosolve->completed = tosolve->impossible = 0; + + /* + * We try and solve it twice, once at our requested difficulty level + * (ensuring it's soluble at all) and once at the level below (if + * it exists), which we hope to fail: if you can also solve it at + * the level below then it's too easy and we have to try again. + * + * With this puzzle in particular there's an extra finesse, which is + * that we check that the generated puzzle isn't too easy _with + * an extra solver step first_, which is the 'sneaky' mode of deductions + * (asserting that any number which fulfils the latin-square rules + * on its row/column must be white). This is an artefact of the + * generation process and not implicit in the rules, so we don't want + * people to be able to use it to make the puzzle easier. + */ + + assert(params->diff < DIFF_MAX); + sret = solve_specific(tosolve, params->diff, 0); + if (params->diff > DIFF_EASY) { + memset(tosolve->flags, 0, state->n * sizeof(unsigned int)); + tosolve->completed = tosolve->impossible = 0; + + /* this is the only time the 'sneaky' flag is set to 1. */ + sret_easy = solve_specific(tosolve, params->diff-1, 1); + } + + if (sret <= 0 || sret_easy > 0) { + debug(("Generated puzzle %s at chosen difficulty %s", + sret <= 0 ? "insoluble" : "too easy", + singles_diffnames[params->diff])); + return 0; + } + return 1; +} + +#define MAXTRIES 20 + +static int best_black_col(game_state *state, random_state *rs, int *scratch, + int i, int *rownums, int *colnums) +{ + int w = state->w, x = i%w, y = i/w, j, o = state->o; + + /* Randomise the list of numbers to try. */ + for (i = 0; i < o; i++) scratch[i] = i; + shuffle(scratch, o, sizeof(int), rs); + + /* Try each number in turn, first giving preference to removing + * latin-square characteristics (i.e. those numbers which only + * occur once in a row/column). The '&&' here, although intuitively + * wrong, results in a smaller number of 'sneaky' deductions on + * solvable boards. */ + for (i = 0; i < o; i++) { + j = scratch[i] + 1; + if (rownums[y*o + j-1] == 1 && colnums[x*o + j-1] == 1) + return j; + } + + /* Then try each number in turn returning the first one that's + * not actually unique in its row/column (see comment below) */ + for (i = 0; i < o; i++) { + j = scratch[i] + 1; + if (rownums[y*o + j-1] != 0 || colnums[x*o + j-1] != 0) + return j; + } + assert(!"unable to place number under black cell."); + return 0; +} + +static char *new_game_desc(game_params *params, random_state *rs, + char **aux, int interactive) +{ + game_state *state = blank_game(params->w, params->h); + game_state *tosolve = blank_game(params->w, params->h); + int i, j, *scratch, *rownums, *colnums, x, y, ntries; + int w = state->w, h = state->h, o = state->o; + char *ret; + digit *latin; + struct solver_state *ss = solver_state_new(state); + + scratch = snewn(state->n, int); + rownums = snewn(h*o, int); + colnums = snewn(w*o, int); + +generate: + ss->n_ops = 0; + debug(("Starting game generation, size %dx%d", w, h)); + + memset(state->flags, 0, state->n*sizeof(unsigned int)); + + /* First, generate the latin rectangle. + * The order of this, o, is max(w,h). */ + latin = latin_generate_rect(w, h, rs); + for (i = 0; i < state->n; i++) + state->nums[i] = (int)latin[i]; + sfree(latin); + debug_state("State after latin square", state); + + /* Add black squares at random, using bits of solver as we go (to lay + * white squares), until we can lay no more blacks. */ + for (i = 0; i < state->n; i++) + scratch[i] = i; + shuffle(scratch, state->n, sizeof(int), rs); + for (j = 0; j < state->n; j++) { + i = scratch[j]; + if ((state->flags[i] & F_CIRCLE) || (state->flags[i] & F_BLACK)) { + debug(("generator skipping (%d,%d): %s", i%w, i/w, + (state->flags[i] & F_CIRCLE) ? "CIRCLE" : "BLACK")); + continue; /* solver knows this must be one or the other already. */ + } + + /* Add a random black cell... */ + solver_op_add(ss, i%w, i/w, BLACK, "Generator: adding random black cell"); + solver_ops_do(state, ss); + + /* ... and do as well as we know how to lay down whites that are now forced. */ + solve_allblackbutone(state, ss); + solver_ops_do(state, ss); + + solve_removesplits(state, ss); + solver_ops_do(state, ss); + + if (state->impossible) { + debug(("generator made impossible, restarting...")); + goto generate; + } + } + debug_state("State after adding blacks", state); + + /* Now we know which squares are white and which are black, we lay numbers + * under black squares at random, except that the number must appear in + * white cells at least once more in the same column or row as that [black] + * square. That's necessary to avoid multiple solutions, where blackening + * squares in the finished puzzle becomes optional. We use two arrays: + * + * rownums[ROW * o + NUM-1] is the no. of white cells containing NUM in y=ROW + * colnums[COL * o + NUM-1] is the no. of white cells containing NUM in x=COL + */ + + memset(rownums, 0, h*o * sizeof(int)); + memset(colnums, 0, w*o * sizeof(int)); + for (i = 0; i < state->n; i++) { + if (state->flags[i] & F_BLACK) continue; + j = state->nums[i]; + x = i%w; y = i/w; + rownums[y * o + j-1] += 1; + colnums[x * o + j-1] += 1; + } + + ntries = 0; +randomise: + for (i = 0; i < state->n; i++) { + if (!(state->flags[i] & F_BLACK)) continue; + state->nums[i] = best_black_col(state, rs, scratch, i, rownums, colnums); + } + debug_state("State after adding numbers", state); + + /* DIFF_ANY just returns whatever we first generated, for testing purposes. */ + if (params->diff != DIFF_ANY && + !new_game_is_good(params, state, tosolve)) { + ntries++; + if (ntries > MAXTRIES) { + debug(("Ran out of randomisation attempts, re-generating.")); + goto generate; + } + debug(("Re-randomising numbers under black squares.")); + goto randomise; + } + + ret = generate_desc(state, 0); + + free_game(tosolve); + free_game(state); + solver_state_free(ss); + sfree(scratch); + sfree(rownums); + sfree(colnums); + + return ret; +} + +static char *validate_desc(game_params *params, char *desc) +{ + char *ret = NULL; + + unpick_desc(params, desc, NULL, &ret); + return ret; +} + +static game_state *new_game(midend *me, game_params *params, char *desc) +{ + game_state *state = NULL; + + unpick_desc(params, desc, &state, NULL); + if (!state) assert(!"new_game failed to unpick"); + return state; +} + +/* --- Game UI and move routines --- */ + +struct game_ui { + int cx, cy, cshow; + int show_black_nums; +}; + +static game_ui *new_ui(game_state *state) +{ + game_ui *ui = snew(game_ui); + + ui->cx = ui->cy = ui->cshow = 0; + ui->show_black_nums = 0; + + 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) +{ + if (!oldstate->completed && newstate->completed) + ui->cshow = 0; +} + +#define DS_BLACK 0x1 +#define DS_CIRCLE 0x2 +#define DS_CURSOR 0x4 +#define DS_BLACK_NUM 0x8 +#define DS_ERROR 0x10 +#define DS_FLASH 0x20 +#define DS_IMPOSSIBLE 0x40 + +struct game_drawstate { + int tilesize, started, solved; + int w, h, n; + + unsigned int *flags; +}; + +static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, + int mx, int my, int button) +{ + char buf[80], c; + int i, x = FROMCOORD(mx), y = FROMCOORD(my); + enum { NONE, TOGGLE_BLACK, TOGGLE_CIRCLE, UI } action = NONE; + + if (IS_CURSOR_MOVE(button)) { + move_cursor(button, &ui->cx, &ui->cy, state->w, state->h, 1); + ui->cshow = 1; + action = UI; + } else if (IS_CURSOR_SELECT(button)) { + x = ui->cx; y = ui->cy; + if (!ui->cshow) { + action = UI; + ui->cshow = 1; + } + if (button == CURSOR_SELECT) { + action = TOGGLE_BLACK; + } else if (button == CURSOR_SELECT2) { + action = TOGGLE_CIRCLE; + } + } else if (IS_MOUSE_DOWN(button)) { + if (ui->cshow) { + ui->cshow = 0; + action = UI; + } + if (!INGRID(state, x, y)) { + ui->show_black_nums = 1 - ui->show_black_nums; + action = UI; /* this wants to be a per-game option. */ + } else if (button == LEFT_BUTTON) { + action = TOGGLE_BLACK; + } else if (button == RIGHT_BUTTON) { + action = TOGGLE_CIRCLE; + } + } + if (action == UI) return ""; + + if (action == TOGGLE_BLACK || action == TOGGLE_CIRCLE) { + i = y * state->w + x; + if (state->flags[i] & (F_BLACK | F_CIRCLE)) + c = 'E'; + else + c = (action == TOGGLE_BLACK) ? 'B' : 'C'; + sprintf(buf, "%c%d,%d", (int)c, x, y); + return dupstr(buf); + } + + return NULL; +} + +static game_state *execute_move(game_state *state, char *move) +{ + game_state *ret = dup_game(state); + int x, y, i, n; + + debug(("move: %s", move)); + + while (*move) { + char c = *move; + if (c == 'B' || c == 'C' || c == 'E') { + move++; + if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 || + !INGRID(state, x, y)) + goto badmove; + + i = y*ret->w + x; + ret->flags[i] &= ~(F_CIRCLE | F_BLACK); /* empty first, always. */ + if (c == 'B') + ret->flags[i] |= F_BLACK; + else if (c == 'C') + ret->flags[i] |= F_CIRCLE; + move += n; + } else if (c == 'S') { + move++; + ret->used_solve = 1; + } else + goto badmove; + + if (*move == ';') + move++; + else if (*move) + goto badmove; + } + if (check_complete(ret, 1)) ret->completed = 1; + return ret; + +badmove: + free_game(ret); + return NULL; +} + +/* ---------------------------------------------------------------------- + * Drawing routines. + */ + +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; } ads, *ds = &ads; + ads.tilesize = tilesize; + + *x = TILE_SIZE * params->w + 2 * BORDER; + *y = TILE_SIZE * params->h + 2 * BORDER; +} + +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_BLACK * 3 + i] = 0.0F; + ret[COL_BLACKNUM * 3 + i] = 0.4F; + ret[COL_WHITE * 3 + i] = 1.0F; + ret[COL_GRID * 3 + i] = ret[COL_LOWLIGHT * 3 + i]; + } + ret[COL_CURSOR * 3 + 0] = 0.2F; + ret[COL_CURSOR * 3 + 1] = 0.8F; + ret[COL_CURSOR * 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; + + *ncolours = NCOLOURS; + return ret; +} + +static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) +{ + struct game_drawstate *ds = snew(struct game_drawstate); + + ds->tilesize = ds->started = ds->solved = 0; + ds->w = state->w; + ds->h = state->h; + ds->n = state->n; + + ds->flags = snewn(state->n, unsigned int); + + memset(ds->flags, 0, state->n*sizeof(unsigned int)); + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds->flags); + sfree(ds); +} + +static void tile_redraw(drawing *dr, game_drawstate *ds, int x, int y, + int num, unsigned int f) +{ + int tcol, bg, dnum, cx, cy, tsz; + char buf[32]; + + if (f & DS_BLACK) { + bg = (f & DS_ERROR) ? COL_ERROR : COL_BLACK; + tcol = COL_BLACKNUM; + dnum = (f & DS_BLACK_NUM) ? 1 : 0; + } else { + bg = (f & DS_FLASH) ? COL_LOWLIGHT : COL_BACKGROUND; + tcol = (f & DS_ERROR) ? COL_ERROR : COL_BLACK; + dnum = 1; + } + + cx = x + TILE_SIZE/2; cy = y + TILE_SIZE/2; + + draw_rect(dr, x, y, TILE_SIZE, TILE_SIZE, bg); + draw_rect_outline(dr, x, y, TILE_SIZE, TILE_SIZE, + (f & DS_IMPOSSIBLE) ? COL_ERROR : COL_GRID); + + if (f & DS_CIRCLE) { + draw_circle(dr, cx, cy, CRAD, tcol, tcol); + draw_circle(dr, cx, cy, CRAD-1, bg, tcol); + } + + if (dnum) { + sprintf(buf, "%d", num); + if (strlen(buf) == 1) + tsz = TEXTSZ; + else + tsz = (CRAD*2 - 1) / strlen(buf); + draw_text(dr, cx, cy, FONT_VARIABLE, tsz, + ALIGN_VCENTRE | ALIGN_HCENTRE, tcol, buf); + } + + if (f & DS_CURSOR) + draw_rect_corners(dr, cx, cy, TEXTSZ/2, COL_CURSOR); + + draw_update(dr, x, y, TILE_SIZE, TILE_SIZE); +} + +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, flash; + unsigned int f; + + flash = (int)(flashtime * 5 / FLASH_TIME) % 2; + + if (!ds->started) { + int wsz = TILE_SIZE * state->w + 2 * BORDER; + int hsz = TILE_SIZE * state->h + 2 * BORDER; + draw_rect(dr, 0, 0, wsz, hsz, COL_BACKGROUND); + draw_rect_outline(dr, COORD(0)-1, COORD(0)-1, + TILE_SIZE * state->w + 2, TILE_SIZE * state->h + 2, + COL_GRID); + draw_update(dr, 0, 0, wsz, hsz); + } + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + i = y*state->w + x; + f = 0; + + if (flash) f |= DS_FLASH; + if (state->impossible) f |= DS_IMPOSSIBLE; + + if (ui->cshow && x == ui->cx && y == ui->cy) + f |= DS_CURSOR; + if (state->flags[i] & F_BLACK) { + f |= DS_BLACK; + if (ui->show_black_nums) f |= DS_BLACK_NUM; + } + if (state->flags[i] & F_CIRCLE) + f |= DS_CIRCLE; + if (state->flags[i] & F_ERROR) + f |= DS_ERROR; + + if (!ds->started || ds->flags[i] != f) { + tile_redraw(dr, ds, COORD(x), COORD(y), + state->nums[i], f); + ds->flags[i] = f; + } + } + } + ds->started = 1; +} + +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 && !newstate->used_solve) + 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; + + /* 8mm squares by default. */ + game_compute_size(params, 800, &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 paper = print_mono_colour(dr, 1); + int x, y, ox, oy, i; + char buf[32]; + + /* 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); + + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + ox = COORD(x); oy = COORD(y); + i = y*state->w+x; + + if (state->flags[i] & F_BLACK) { + draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink); + } else { + draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink); + + if (state->flags[i] & DS_CIRCLE) + draw_circle(dr, ox+TILE_SIZE/2, oy+TILE_SIZE/2, CRAD, + paper, ink); + + sprintf(buf, "%d", state->nums[i]); + draw_text(dr, ox+TILE_SIZE/2, oy+TILE_SIZE/2, FONT_VARIABLE, + TEXTSZ/strlen(buf), ALIGN_VCENTRE | ALIGN_HCENTRE, + ink, buf); + } + } + } +} + +#ifdef COMBINED +#define thegame singles +#endif + +const struct game thegame = { + "Singles", "games.singles", "singles", + 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_can_format_as_text_now, 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, + REQUIRE_RBUTTON, /* flags */ +}; + +#ifdef STANDALONE_SOLVER + +#include +#include + +static void start_soak(game_params *p, random_state *rs) +{ + time_t tt_start, tt_now, tt_last; + char *desc, *aux; + game_state *s; + int i, n = 0, ndiff[DIFF_MAX], diff, sret, nblack = 0, nsneaky = 0; + + tt_start = tt_now = time(NULL); + + printf("Soak-testing a %dx%d grid.\n", p->w, p->h); + p->diff = DIFF_ANY; + + memset(ndiff, 0, DIFF_MAX * sizeof(int)); + + while (1) { + n++; + desc = new_game_desc(p, rs, &aux, 0); + s = new_game(NULL, p, desc); + nsneaky += solve_sneaky(s, NULL); + + for (diff = 0; diff < DIFF_MAX; diff++) { + memset(s->flags, 0, s->n * sizeof(unsigned int)); + s->completed = s->impossible = 0; + sret = solve_specific(s, diff, 0); + if (sret > 0) { + ndiff[diff]++; + break; + } else if (sret < 0) + fprintf(stderr, "Impossible! %s\n", desc); + } + for (i = 0; i < s->n; i++) { + if (s->flags[i] & F_BLACK) nblack++; + } + free_game(s); + sfree(desc); + + tt_last = time(NULL); + if (tt_last > tt_now) { + tt_now = tt_last; + printf("%d total, %3.1f/s, bl/sn %3.1f%%/%3.1f%%: ", + n, (double)n / ((double)tt_now - tt_start), + ((double)nblack * 100.0) / (double)(n * p->w * p->h), + ((double)nsneaky * 100.0) / (double)(n * p->w * p->h)); + for (diff = 0; diff < DIFF_MAX; diff++) { + if (diff > 0) printf(", "); + printf("%d (%3.1f%%) %s", + ndiff[diff], (double)ndiff[diff] * 100.0 / (double)n, + singles_diffnames[diff]); + } + printf("\n"); + } + } +} + +int main(int argc, char **argv) +{ + char *id = NULL, *desc, *desc_gen = NULL, *tgame, *err, *aux; + game_state *s = NULL; + game_params *p = NULL; + int soln, soak = 0, ret = 1; + time_t seed = time(NULL); + random_state *rs = NULL; + + setvbuf(stdout, NULL, _IONBF, 0); + + while (--argc > 0) { + char *p = *++argv; + if (!strcmp(p, "-v")) { + verbose = 1; + } else if (!strcmp(p, "--soak")) { + soak = 1; + } else if (!strcmp(p, "--seed")) { + if (argc == 0) { + fprintf(stderr, "%s: --seed needs an argument", argv[0]); + goto done; + } + seed = (time_t)atoi(*++argv); + argc--; + } else if (*p == '-') { + fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); + return 1; + } else { + id = p; + } + } + + rs = random_new((void*)&seed, sizeof(time_t)); + + if (!id) { + fprintf(stderr, "usage: %s [-v] [--soak] | \n", argv[0]); + goto done; + } + desc = strchr(id, ':'); + if (desc) *desc++ = '\0'; + + p = default_params(); + decode_params(p, id); + err = validate_params(p, 1); + if (err) { + fprintf(stderr, "%s: %s", argv[0], err); + goto done; + } + + if (soak) { + if (desc) { + fprintf(stderr, "%s: --soak only needs params, not game desc.\n", argv[0]); + goto done; + } + start_soak(p, rs); + } else { + if (!desc) desc = desc_gen = new_game_desc(p, rs, &aux, 0); + + err = validate_desc(p, desc); + if (err) { + fprintf(stderr, "%s: %s\n", argv[0], err); + free_params(p); + goto done; + } + s = new_game(NULL, p, desc); + + if (verbose) { + tgame = game_text_format(s); + printf(tgame); + sfree(tgame); + } + + soln = solve_specific(s, DIFF_ANY, 0); + tgame = game_text_format(s); + printf(tgame); + sfree(tgame); + printf("Game was %s.\n\n", + soln < 0 ? "impossible" : soln > 0 ? "solved" : "not solved"); + } + ret = 0; + +done: + if (desc_gen) sfree(desc_gen); + if (p) free_params(p); + if (s) free_game(s); + if (rs) random_free(rs); + + return ret; +} + +#endif + + +/* vim: set shiftwidth=4 tabstop=8: */ -- 2.11.0