/*
* 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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>
#include <math.h>
#include "puzzles.h"
#include "latin.h"
#ifdef STANDALONE_SOLVER
bool verbose = false;
#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_UNUSED1, 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) */
bool 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 bool 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(const 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(const game_params *params, bool 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(const 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].u.string.sval = dupstr(buf);
ret[1].name = "Height";
ret[1].type = C_STRING;
sprintf(buf, "%d", params->h);
ret[1].u.string.sval = dupstr(buf);
ret[2].name = "Difficulty";
ret[2].type = C_CHOICES;
ret[2].u.choices.choicenames = DIFFCONFIG;
ret[2].u.choices.selected = params->diff;
ret[3].name = NULL;
ret[3].type = C_END;
return ret;
}
static game_params *custom_params(const config_item *cfg)
{
game_params *ret = snew(game_params);
ret->w = atoi(cfg[0].u.string.sval);
ret->h = atoi(cfg[1].u.string.sval);
ret->diff = cfg[2].u.choices.selected;
return ret;
}
static const char *validate_params(const game_params *params, bool 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 = false;
state->used_solve = false;
state->impossible = false;
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(const 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((unsigned char)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(const game_params *params, const char *desc,
game_state **sout, const char **mout)
{
game_state *state = blank_game(params->w, params->h);
const 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, bool 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 bool game_can_format_as_text_now(const game_params *params)
{
return true;
}
static char *game_text_format(const 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 */
}
}
}
#define CC_MARK_ERRORS 1
#define CC_MUST_FILL 2
static int check_rowcol(game_state *state, int starti, int di, int sz, unsigned flags)
{
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 (!(flags & CC_MARK_ERRORS)) continue;
|