*
* Some variants include an extra constraint, stating that no two rows or two
* columns may contain the same exact sequence of zeros and ones.
- * This rule is rarely used, so it has been discarded for this implementation.
+ * This rule is rarely used, so it is not enabled in the default presets
+ * (but it can be selected via the Custom configurer).
*
* More information:
* http://www.janko.at/Raetsel/Tohu-Wa-Vohu/index.htm
struct game_params {
int w2, h2; /* full grid width and height respectively */
+ int unique; /* should row and column patterns be unique? */
int diff;
};
#define DIFFLIST(A) \
#define DIFFCONFIG DIFFLIST(CONFIG)
const static struct game_params unruly_presets[] = {
- { 8, 8, DIFF_EASY},
- { 8, 8, DIFF_NORMAL},
- {10, 10, DIFF_EASY},
- {10, 10, DIFF_NORMAL},
- {14, 14, DIFF_EASY},
- {14, 14, DIFF_NORMAL}
+ { 8, 8, FALSE, DIFF_EASY},
+ { 8, 8, FALSE, DIFF_NORMAL},
+ {10, 10, FALSE, DIFF_EASY},
+ {10, 10, FALSE, DIFF_NORMAL},
+ {14, 14, FALSE, DIFF_EASY},
+ {14, 14, FALSE, DIFF_NORMAL}
};
#define DEFAULT_PRESET 0
BOGUS
};
-#define FE_HOR_ROW_LEFT 0x001
-#define FE_HOR_ROW_MID 0x003
-#define FE_HOR_ROW_RIGHT 0x002
+#define FE_HOR_ROW_LEFT 0x0001
+#define FE_HOR_ROW_MID 0x0003
+#define FE_HOR_ROW_RIGHT 0x0002
-#define FE_VER_ROW_TOP 0x004
-#define FE_VER_ROW_MID 0x00C
-#define FE_VER_ROW_BOTTOM 0x008
+#define FE_VER_ROW_TOP 0x0004
+#define FE_VER_ROW_MID 0x000C
+#define FE_VER_ROW_BOTTOM 0x0008
-#define FE_COUNT 0x010
+#define FE_COUNT 0x0010
-#define FF_ONE 0x020
-#define FF_ZERO 0x040
-#define FF_CURSOR 0x080
+#define FE_ROW_MATCH 0x0020
+#define FE_COL_MATCH 0x0040
-#define FF_FLASH1 0x100
-#define FF_FLASH2 0x200
-#define FF_IMMUTABLE 0x400
+#define FF_ONE 0x0080
+#define FF_ZERO 0x0100
+#define FF_CURSOR 0x0200
+
+#define FF_FLASH1 0x0400
+#define FF_FLASH2 0x0800
+#define FF_IMMUTABLE 0x1000
struct game_state {
int w2, h2;
+ int unique;
char *grid;
unsigned char *immutable;
sfree(params);
}
-static game_params *dup_params(game_params *params)
+static game_params *dup_params(const game_params *params)
{
game_params *ret = snew(game_params);
*ret = *params; /* structure copy */
{
char const *p = string;
+ params->unique = FALSE;
+
params->w2 = atoi(p);
while (*p && isdigit((unsigned char)*p)) p++;
if (*p == 'x') {
params->h2 = params->w2;
}
+ if (*p == 'u') {
+ p++;
+ params->unique = TRUE;
+ }
+
if (*p == 'd') {
int i;
p++;
}
}
-static char *encode_params(game_params *params, int full)
+static char *encode_params(const game_params *params, int full)
{
char buf[80];
sprintf(buf, "%dx%d", params->w2, params->h2);
+ if (params->unique)
+ strcat(buf, "u");
if (full)
sprintf(buf + strlen(buf), "d%c", unruly_diffchars[params->diff]);
return dupstr(buf);
}
-static config_item *game_configure(game_params *params)
+static config_item *game_configure(const game_params *params)
{
config_item *ret;
char buf[80];
- ret = snewn(4, config_item);
+ ret = snewn(5, config_item);
ret[0].name = "Width";
ret[0].type = C_STRING;
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[2].name = "Unique rows and columns";
+ ret[2].type = C_BOOLEAN;
+ ret[2].ival = params->unique;
- ret[3].name = NULL;
- ret[3].type = C_END;
- ret[3].sval = NULL;
- ret[3].ival = 0;
+ ret[3].name = "Difficulty";
+ ret[3].type = C_CHOICES;
+ ret[3].sval = DIFFCONFIG;
+ ret[3].ival = params->diff;
+
+ ret[4].name = NULL;
+ ret[4].type = C_END;
+ ret[4].sval = NULL;
+ ret[4].ival = 0;
return ret;
}
-static game_params *custom_params(config_item *cfg)
+static game_params *custom_params(const config_item *cfg)
{
game_params *ret = snew(game_params);
ret->w2 = atoi(cfg[0].sval);
ret->h2 = atoi(cfg[1].sval);
- ret->diff = cfg[2].ival;
+ ret->unique = cfg[2].ival;
+ ret->diff = cfg[3].ival;
return ret;
}
-static char *validate_params(game_params *params, int full)
+static char *validate_params(const game_params *params, int full)
{
if ((params->w2 & 1) || (params->h2 & 1))
return "Width and height must both be even";
if (params->w2 < 6 || params->h2 < 6)
return "Width and height must be at least 6";
+ if (params->unique) {
+ static const long A177790[] = {
+ /*
+ * The nth element of this array gives the number of
+ * distinct possible Unruly rows of length 2n (that is,
+ * containing exactly n 1s and n 0s and not containing
+ * three consecutive elements the same) for as long as
+ * those numbers fit in a 32-bit signed int.
+ *
+ * So in unique-rows mode, if the puzzle width is 2n, then
+ * the height must be at most (this array)[n], and vice
+ * versa.
+ *
+ * This is sequence A177790 in the Online Encyclopedia of
+ * Integer Sequences: http://oeis.org/A177790
+ */
+ 1L, 2L, 6L, 14L, 34L, 84L, 208L, 518L, 1296L, 3254L,
+ 8196L, 20700L, 52404L, 132942L, 337878L, 860142L,
+ 2192902L, 5598144L, 14308378L, 36610970L, 93770358L,
+ 240390602L, 616787116L, 1583765724L
+ };
+ if (params->w2 < 2*lenof(A177790) &&
+ params->h2 > A177790[params->w2/2]) {
+ return "Puzzle is too tall for unique-rows mode";
+ }
+ if (params->h2 < 2*lenof(A177790) &&
+ params->w2 > A177790[params->h2/2]) {
+ return "Puzzle is too long for unique-rows mode";
+ }
+ }
if (params->diff >= DIFFCOUNT)
return "Unknown difficulty rating";
return NULL;
}
-static char *validate_desc(const game_params *params, char *desc)
+static char *validate_desc(const game_params *params, const char *desc)
{
int w2 = params->w2, h2 = params->h2;
int s = w2 * h2;
- char *p = desc;
+ const char *p = desc;
int pos = 0;
while (*p) {
return NULL;
}
-static game_state *blank_state(int w2, int h2)
+static game_state *blank_state(int w2, int h2, int unique)
{
game_state *state = snew(game_state);
int s = w2 * h2;
state->w2 = w2;
state->h2 = h2;
+ state->unique = unique;
state->grid = snewn(s, char);
state->immutable = snewn(s, unsigned char);
return state;
}
-static game_state *new_game(midend *me, game_params *params, char *desc)
+static game_state *new_game(midend *me, const game_params *params,
+ const char *desc)
{
int w2 = params->w2, h2 = params->h2;
int s = w2 * h2;
- game_state *state = blank_state(w2, h2);
+ game_state *state = blank_state(w2, h2, params->unique);
- char *p = desc;
+ const char *p = desc;
int pos = 0;
while (*p) {
return state;
}
-static game_state *dup_game(game_state *state)
+static game_state *dup_game(const game_state *state)
{
int w2 = state->w2, h2 = state->h2;
int s = w2 * h2;
- game_state *ret = blank_state(w2, h2);
+ game_state *ret = blank_state(w2, h2, state->unique);
memcpy(ret->grid, state->grid, s);
memcpy(ret->immutable, state->immutable, s);
sfree(state);
}
-static int game_can_format_as_text_now(game_params *params)
+static int game_can_format_as_text_now(const game_params *params)
{
return TRUE;
}
-static char *game_text_format(game_state *state)
+static char *game_text_format(const game_state *state)
{
int w2 = state->w2, h2 = state->h2;
int lr = w2*2 + 1;
int *zeros_cols;
};
-static void unruly_solver_update_remaining(game_state *state,
+static void unruly_solver_update_remaining(const game_state *state,
struct unruly_scratch *scratch)
{
int w2 = state->w2, h2 = state->h2;
}
}
-static struct unruly_scratch *unruly_new_scratch(game_state *state)
+static struct unruly_scratch *unruly_new_scratch(const game_state *state)
{
int w2 = state->w2, h2 = state->h2;
return ret;
}
+static int unruly_solver_check_uniques(game_state *state, int *rowcount,
+ int horizontal, char check, char block,
+ struct unruly_scratch *scratch)
+{
+ int w2 = state->w2, h2 = state->h2;
+
+ int rmult = (horizontal ? w2 : 1);
+ int cmult = (horizontal ? 1 : w2);
+ int nr = (horizontal ? h2 : w2);
+ int nc = (horizontal ? w2 : h2);
+ int max = nc / 2;
+
+ int r, r2, c;
+ int ret = 0;
+
+ /*
+ * Find each row that has max entries of type 'check', and see if
+ * all those entries match those in any row with max-1 entries. If
+ * so, set the last non-matching entry of the latter row to ensure
+ * that it's different.
+ */
+ for (r = 0; r < nr; r++) {
+ if (rowcount[r] != max)
+ continue;
+ for (r2 = 0; r2 < nr; r2++) {
+ int nmatch = 0, nonmatch = -1;
+ if (rowcount[r2] != max-1)
+ continue;
+ for (c = 0; c < nc; c++) {
+ if (state->grid[r*rmult + c*cmult] == check) {
+ if (state->grid[r2*rmult + c*cmult] == check)
+ nmatch++;
+ else
+ nonmatch = c;
+ }
+ }
+ if (nmatch == max-1) {
+ int i1 = r2 * rmult + nonmatch * cmult;
+ assert(nonmatch != -1);
+ if (state->grid[i1] == block)
+ continue;
+ assert(state->grid[i1] == EMPTY);
+#ifdef STANDALONE_SOLVER
+ if (solver_verbose) {
+ printf("Solver: matching %s %i, %i gives %c at %i,%i\n",
+ horizontal ? "rows" : "cols",
+ r, r2, (block == N_ONE ? '1' : '0'), i1 % w2,
+ i1 / w2);
+ }
+#endif
+ state->grid[i1] = block;
+ if (block == N_ONE) {
+ scratch->ones_rows[i1 / w2]++;
+ scratch->ones_cols[i1 % w2]++;
+ } else {
+ scratch->zeros_rows[i1 / w2]++;
+ scratch->zeros_cols[i1 % w2]++;
+ }
+ ret++;
+ }
+ }
+ }
+ return ret;
+}
+
+static int unruly_solver_check_all_uniques(game_state *state,
+ struct unruly_scratch *scratch)
+{
+ int ret = 0;
+
+ ret += unruly_solver_check_uniques(state, scratch->ones_rows,
+ TRUE, N_ONE, N_ZERO, scratch);
+ ret += unruly_solver_check_uniques(state, scratch->zeros_rows,
+ TRUE, N_ZERO, N_ONE, scratch);
+ ret += unruly_solver_check_uniques(state, scratch->ones_cols,
+ FALSE, N_ONE, N_ZERO, scratch);
+ ret += unruly_solver_check_uniques(state, scratch->zeros_cols,
+ FALSE, N_ZERO, N_ONE, scratch);
+
+ return ret;
+}
+
static int unruly_solver_fill_row(game_state *state, int i, int horizontal,
int *rowcount, int *colcount, char fill)
{
return ret;
}
-static int unruly_validate_rows(game_state *state, int horizontal,
+static int unruly_validate_rows(const game_state *state, int horizontal,
char check, int *errors)
{
int w2 = state->w2, h2 = state->h2;
return ret;
}
-static int unruly_validate_all_rows(game_state *state, int *errors)
+static int unruly_validate_unique(const game_state *state, int horizontal,
+ int *errors)
+{
+ int w2 = state->w2, h2 = state->h2;
+
+ int rmult = (horizontal ? w2 : 1);
+ int cmult = (horizontal ? 1 : w2);
+ int nr = (horizontal ? h2 : w2);
+ int nc = (horizontal ? w2 : h2);
+ int err = (horizontal ? FE_ROW_MATCH : FE_COL_MATCH);
+
+ int r, r2, c;
+ int ret = 0;
+
+ /* Check for any two full rows matching exactly, and mark errors
+ * accordingly (if required) */
+ for (r = 0; r < nr; r++) {
+ int nfull = 0;
+ for (c = 0; c < nc; c++)
+ if (state->grid[r*rmult + c*cmult] != EMPTY)
+ nfull++;
+ if (nfull != nc)
+ continue;
+ for (r2 = r+1; r2 < nr; r2++) {
+ int match = TRUE;
+ for (c = 0; c < nc; c++)
+ if (state->grid[r*rmult + c*cmult] !=
+ state->grid[r2*rmult + c*cmult])
+ match = FALSE;
+ if (match) {
+ if (errors) {
+ for (c = 0; c < nc; c++) {
+ errors[r*rmult + c*cmult] |= err;
+ errors[r2*rmult + c*cmult] |= err;
+ }
+ }
+ ret++;
+ }
+ }
+ }
+
+ return ret;
+}
+
+static int unruly_validate_all_rows(const game_state *state, int *errors)
{
int errcount = 0;
errcount += unruly_validate_rows(state, TRUE, N_ZERO, errors);
errcount += unruly_validate_rows(state, FALSE, N_ZERO, errors);
+ if (state->unique) {
+ errcount += unruly_validate_unique(state, TRUE, errors);
+ errcount += unruly_validate_unique(state, FALSE, errors);
+ }
+
if (errcount)
return -1;
return 0;
}
-static int unruly_validate_counts(game_state *state,
+static int unruly_validate_counts(const game_state *state,
struct unruly_scratch *scratch, int *errors)
{
int w2 = state->w2, h2 = state->h2;
continue;
}
+ /* Check for impending failures of row/column uniqueness, if
+ * it's enabled in this game mode */
+ if (state->unique) {
+ done += unruly_solver_check_all_uniques(state, scratch);
+
+ if (done) {
+ if (maxdiff < DIFF_EASY)
+ maxdiff = DIFF_EASY;
+ continue;
+ }
+ }
+
/* Normal techniques */
if (diff < DIFF_NORMAL)
break;
return maxdiff;
}
-static char *solve_game(game_state *state, game_state *currstate,
- char *aux, char **error)
+static char *solve_game(const game_state *state, const game_state *currstate,
+ const char *aux, char **error)
{
game_state *solved = dup_game(state);
struct unruly_scratch *scratch = unruly_new_scratch(solved);
while (TRUE) {
attempts++;
- state = blank_state(w2, h2);
+ state = blank_state(w2, h2, params->unique);
scratch = unruly_new_scratch(state);
if (unruly_fill_game(state, scratch, rs))
break;
char cursor;
};
-static game_ui *new_ui(game_state *state)
+static game_ui *new_ui(const game_state *state)
{
game_ui *ret = snew(game_ui);
sfree(ui);
}
-static char *encode_ui(game_ui *ui)
+static char *encode_ui(const game_ui *ui)
{
return NULL;
}
-static void decode_ui(game_ui *ui, char *encoding)
+static void decode_ui(game_ui *ui, const char *encoding)
{
}
-static void game_changed_state(game_ui *ui, game_state *oldstate,
- game_state *newstate)
+static void game_changed_state(game_ui *ui, const game_state *oldstate,
+ const game_state *newstate)
{
}
int *grid;
};
-static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
+static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
{
struct game_drawstate *ds = snew(struct game_drawstate);
#define COORD(x) ( (x) * ds->tilesize + ds->tilesize/2 )
#define FROMCOORD(x) ( ((x)-(ds->tilesize/2)) / ds->tilesize )
-static char *interpret_move(game_state *state, game_ui *ui,
- const game_drawstate *ds, int ox, int oy,
- int button)
+static char *interpret_move(const game_state *state, game_ui *ui,
+ const game_drawstate *ds,
+ int ox, int oy, int button)
{
int hx = ui->cx;
int hy = ui->cy;
return NULL;
}
-static game_state *execute_move(game_state *state, char *move)
+static game_state *execute_move(const game_state *state, const char *move)
{
int w2 = state->w2, h2 = state->h2;
int s = w2 * h2;
game_state *ret;
if (move[0] == 'S') {
- char *p;
+ const char *p;
ret = dup_game(state);
p = move + 1;
* Drawing routines.
*/
-static void game_compute_size(game_params *params, int tilesize,
+static void game_compute_size(const game_params *params, int tilesize,
int *x, int *y)
{
*x = tilesize * (params->w2 + 1);
}
static void game_set_size(drawing *dr, game_drawstate *ds,
- game_params *params, int tilesize)
+ const game_params *params, int tilesize)
{
ds->tilesize = tilesize;
}
tilesize/2, ALIGN_HCENTRE | ALIGN_VCENTRE, COL_ERROR, "!");
}
+ /* Row-match errors */
+ if (tile & FE_ROW_MATCH) {
+ draw_rect(dr, x, y+tilesize/2-tilesize/12,
+ tilesize, 2*(tilesize/12), COL_ERROR);
+ }
+ if (tile & FE_COL_MATCH) {
+ draw_rect(dr, x+tilesize/2-tilesize/12, y,
+ 2*(tilesize/12), tilesize, COL_ERROR);
+ }
+
/* Cursor rectangle */
if (tile & FF_CURSOR) {
draw_rect(dr, x, y, tilesize/12, tilesize-1, COL_CURSOR);
#define FLASH_TIME (FLASH_FRAME * 3)
static void game_redraw(drawing *dr, game_drawstate *ds,
- game_state *oldstate, game_state *state, int dir,
- game_ui *ui, float animtime, float flashtime)
+ const game_state *oldstate, const game_state *state,
+ int dir, const game_ui *ui,
+ float animtime, float flashtime)
{
int w2 = state->w2, h2 = state->h2;
int s = w2 * h2;
}
}
-static float game_anim_length(game_state *oldstate, game_state *newstate,
- int dir, game_ui *ui)
+static float game_anim_length(const game_state *oldstate,
+ const 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)
+static float game_flash_length(const game_state *oldstate,
+ const game_state *newstate, int dir, game_ui *ui)
{
if (!oldstate->completed && newstate->completed &&
!oldstate->cheated && !newstate->cheated)
return 0.0F;
}
-static int game_status(game_state *state)
+static int game_status(const game_state *state)
{
return state->completed ? +1 : 0;
}
-static int game_timing_state(game_state *state, game_ui *ui)
+static int game_timing_state(const game_state *state, game_ui *ui)
{
return TRUE;
}
-static void game_print_size(game_params *params, float *x, float *y)
+static void game_print_size(const game_params *params, float *x, float *y)
{
int pw, ph;
*y = ph / 100.0F;
}
-static void game_print(drawing *dr, game_state *state, int tilesize)
+static void game_print(drawing *dr, const game_state *state, int tilesize)
{
int w2 = state->w2, h2 = state->h2;
int x, y;
~ian / sgt-puzzles.git / blobdiff