12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183 |
- /*
- * unruly.c: Implementation for Binary Puzzles.
- * (C) 2012 Lennard Sprong
- * Created for Simon Tatham's Portable Puzzle Collection
- * See LICENCE for licence details
- *
- * Objective of the game: Fill the grid with zeros and ones, with the
- * following rules:
- * - There can't be a run of three or more equal numbers.
- * - Each row and column contains an equal amount of zeros and ones.
- *
- * This puzzle type is known under several names, including
- * Tohu-Wa-Vohu, One and Two and Binairo.
- *
- * 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 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
- */
- /*
- * Possible future improvements:
- *
- * More solver cleverness
- *
- * - a counting-based deduction in which you find groups of squares
- * which must each contain at least one of a given colour, plus
- * other squares which are already known to be that colour, and see
- * if you have any squares left over when you've worked out where
- * they all have to be. This is a generalisation of the current
- * check_near_complete: where that only covers rows with three
- * unfilled squares, this would handle more, such as
- * 0 . . 1 0 1 . . 0 .
- * in which each of the two-square gaps must contain a 0, and there
- * are three 0s placed, and that means the rightmost square can't
- * be a 0.
- *
- * - an 'Unreasonable' difficulty level, supporting recursion and
- * backtracking.
- */
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <assert.h>
- #include <ctype.h>
- #ifdef NO_TGMATH_H
- # include <math.h>
- #else
- # include <tgmath.h>
- #endif
- #include "puzzles.h"
- #ifdef STANDALONE_SOLVER
- static bool solver_verbose = false;
- #endif
- enum {
- COL_BACKGROUND,
- COL_GRID,
- COL_EMPTY,
- /*
- * When editing this enum, maintain the invariants
- * COL_n_HIGHLIGHT = COL_n + 1
- * COL_n_LOWLIGHT = COL_n + 2
- */
- COL_0,
- COL_0_HIGHLIGHT,
- COL_0_LOWLIGHT,
- COL_1,
- COL_1_HIGHLIGHT,
- COL_1_LOWLIGHT,
- COL_CURSOR,
- COL_ERROR,
- NCOLOURS
- };
- struct game_params {
- int w2, h2; /* full grid width and height respectively */
- bool unique; /* should row and column patterns be unique? */
- int diff;
- };
- #define DIFFLIST(A) \
- A(TRIVIAL,Trivial, t) \
- A(EASY,Easy, e) \
- A(NORMAL,Normal, n) \
- #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) DIFFCOUNT };
- static char const *const unruly_diffnames[] = { DIFFLIST(TITLE) };
- static char const unruly_diffchars[] = DIFFLIST(ENCODE);
- #define DIFFCONFIG DIFFLIST(CONFIG)
- static const struct game_params unruly_presets[] = {
- { 8, 8, false, DIFF_TRIVIAL},
- { 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
- enum {
- EMPTY,
- N_ONE,
- N_ZERO,
- BOGUS
- };
- #define FE_HOR_ROW_LEFT 0x0001
- #define FE_HOR_ROW_MID 0x0003
- #define FE_HOR_ROW_RIGHT 0x0002
- #define FE_VER_ROW_TOP 0x0004
- #define FE_VER_ROW_MID 0x000C
- #define FE_VER_ROW_BOTTOM 0x0008
- #define FE_COUNT 0x0010
- #define FE_ROW_MATCH 0x0020
- #define FE_COL_MATCH 0x0040
- #define FF_ONE 0x0080
- #define FF_ZERO 0x0100
- #define FF_CURSOR 0x0200
- #define FF_FLASH1 0x0400
- #define FF_FLASH2 0x0800
- #define FF_IMMUTABLE 0x1000
- typedef struct unruly_common {
- int refcount;
- bool *immutable;
- } unruly_common;
- struct game_state {
- int w2, h2;
- bool unique;
- char *grid;
- unruly_common *common;
- bool completed, cheated;
- };
- static game_params *default_params(void)
- {
- game_params *ret = snew(game_params);
- *ret = unruly_presets[DEFAULT_PRESET]; /* structure copy */
- return ret;
- }
- static bool game_fetch_preset(int i, char **name, game_params **params)
- {
- game_params *ret;
- char buf[80];
- if (i < 0 || i >= lenof(unruly_presets))
- return false;
- ret = snew(game_params);
- *ret = unruly_presets[i]; /* structure copy */
- sprintf(buf, "%dx%d %s", ret->w2, ret->h2, unruly_diffnames[ret->diff]);
- *name = dupstr(buf);
- *params = ret;
- 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 *params, char const *string)
- {
- char const *p = string;
- params->unique = false;
- params->w2 = atoi(p);
- while (*p && isdigit((unsigned char)*p)) p++;
- if (*p == 'x') {
- p++;
- params->h2 = atoi(p);
- while (*p && isdigit((unsigned char)*p)) p++;
- } else {
- params->h2 = params->w2;
- }
- if (*p == 'u') {
- p++;
- params->unique = true;
- }
- if (*p == 'd') {
- int i;
- p++;
- params->diff = DIFFCOUNT + 1; /* ...which is invalid */
- if (*p) {
- for (i = 0; i < DIFFCOUNT; i++) {
- if (*p == unruly_diffchars[i])
- params->diff = i;
- }
- p++;
- }
- }
- }
- static char *encode_params(const game_params *params, bool 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(const game_params *params)
- {
- config_item *ret;
- char buf[80];
- ret = snewn(5, config_item);
- ret[0].name = "Width";
- ret[0].type = C_STRING;
- sprintf(buf, "%d", params->w2);
- ret[0].u.string.sval = dupstr(buf);
- ret[1].name = "Height";
- ret[1].type = C_STRING;
- sprintf(buf, "%d", params->h2);
- ret[1].u.string.sval = dupstr(buf);
- ret[2].name = "Unique rows and columns";
- ret[2].type = C_BOOLEAN;
- ret[2].u.boolean.bval = params->unique;
- ret[3].name = "Difficulty";
- ret[3].type = C_CHOICES;
- ret[3].u.choices.choicenames = DIFFCONFIG;
- ret[3].u.choices.selected = params->diff;
- ret[4].name = NULL;
- ret[4].type = C_END;
- return ret;
- }
- static game_params *custom_params(const config_item *cfg)
- {
- game_params *ret = snew(game_params);
- ret->w2 = atoi(cfg[0].u.string.sval);
- ret->h2 = atoi(cfg[1].u.string.sval);
- ret->unique = cfg[2].u.boolean.bval;
- ret->diff = cfg[3].u.choices.selected;
- return ret;
- }
- static const char *validate_params(const game_params *params, bool 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->w2 > INT_MAX / params->h2)
- return "Width times height must not be unreasonably large";
- 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 const char *validate_desc(const game_params *params, const char *desc)
- {
- int w2 = params->w2, h2 = params->h2;
- int s = w2 * h2;
- const char *p = desc;
- int pos = 0;
- while (*p) {
- if (*p >= 'a' && *p < 'z')
- pos += 1 + (*p - 'a');
- else if (*p >= 'A' && *p < 'Z')
- pos += 1 + (*p - 'A');
- else if (*p == 'Z' || *p == 'z')
- pos += 25;
- else
- return "Description contains invalid characters";
- ++p;
- }
- if (pos < s+1)
- return "Description too short";
- if (pos > s+1)
- return "Description too long";
- return NULL;
- }
- static game_state *blank_state(int w2, int h2, bool unique, bool new_common)
- {
- game_state *state = snew(game_state);
- int s = w2 * h2;
- state->w2 = w2;
- state->h2 = h2;
- state->unique = unique;
- state->grid = snewn(s, char);
- memset(state->grid, EMPTY, s);
- if (new_common) {
- state->common = snew(unruly_common);
- state->common->refcount = 1;
- state->common->immutable = snewn(s, bool);
- memset(state->common->immutable, 0, s*sizeof(bool));
- }
- state->completed = state->cheated = false;
- return state;
- }
- 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, params->unique, true);
- const char *p = desc;
- int pos = 0;
- while (*p) {
- if (*p >= 'a' && *p < 'z') {
- pos += (*p - 'a');
- if (pos < s) {
- state->grid[pos] = N_ZERO;
- state->common->immutable[pos] = true;
- }
- pos++;
- } else if (*p >= 'A' && *p < 'Z') {
- pos += (*p - 'A');
- if (pos < s) {
- state->grid[pos] = N_ONE;
- state->common->immutable[pos] = true;
- }
- pos++;
- } else if (*p == 'Z' || *p == 'z') {
- pos += 25;
- } else
- assert(!"Description contains invalid characters");
- ++p;
- }
- assert(pos == s+1);
- return 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, state->unique, false);
- memcpy(ret->grid, state->grid, s);
- ret->common = state->common;
- ret->common->refcount++;
- ret->completed = state->completed;
- ret->cheated = state->cheated;
- return ret;
- }
- static void free_game(game_state *state)
- {
- sfree(state->grid);
- if (--state->common->refcount == 0) {
- sfree(state->common->immutable);
- sfree(state->common);
- }
- sfree(state);
- }
- static bool game_can_format_as_text_now(const game_params *params)
- {
- return true;
- }
- static char *game_text_format(const game_state *state)
- {
- int w2 = state->w2, h2 = state->h2;
- int lr = w2*2 + 1;
- char *ret = snewn(lr * h2 + 1, char);
- char *p = ret;
- int x, y;
- for (y = 0; y < h2; y++) {
- for (x = 0; x < w2; x++) {
- /* Place number */
- char c = state->grid[y * w2 + x];
- *p++ = (c == N_ONE ? '1' : c == N_ZERO ? '0' : '.');
- *p++ = ' ';
- }
- /* End line */
- *p++ = '\n';
- }
- /* End with NUL */
- *p++ = '\0';
- return ret;
- }
- /* ****** *
- * Solver *
- * ****** */
- struct unruly_scratch {
- int *ones_rows;
- int *ones_cols;
- int *zeros_rows;
- int *zeros_cols;
- };
- static void unruly_solver_update_remaining(const game_state *state,
- struct unruly_scratch *scratch)
- {
- int w2 = state->w2, h2 = state->h2;
- int x, y;
- /* Reset all scratch data */
- memset(scratch->ones_rows, 0, h2 * sizeof(int));
- memset(scratch->ones_cols, 0, w2 * sizeof(int));
- memset(scratch->zeros_rows, 0, h2 * sizeof(int));
- memset(scratch->zeros_cols, 0, w2 * sizeof(int));
- for (x = 0; x < w2; x++)
- for (y = 0; y < h2; y++) {
- if (state->grid[y * w2 + x] == N_ONE) {
- scratch->ones_rows[y]++;
- scratch->ones_cols[x]++;
- } else if (state->grid[y * w2 + x] == N_ZERO) {
- scratch->zeros_rows[y]++;
- scratch->zeros_cols[x]++;
- }
- }
- }
- static struct unruly_scratch *unruly_new_scratch(const game_state *state)
- {
- int w2 = state->w2, h2 = state->h2;
- struct unruly_scratch *ret = snew(struct unruly_scratch);
- ret->ones_rows = snewn(h2, int);
- ret->ones_cols = snewn(w2, int);
- ret->zeros_rows = snewn(h2, int);
- ret->zeros_cols = snewn(w2, int);
- unruly_solver_update_remaining(state, ret);
- return ret;
- }
- static void unruly_free_scratch(struct unruly_scratch *scratch)
- {
- sfree(scratch->ones_rows);
- sfree(scratch->ones_cols);
- sfree(scratch->zeros_rows);
- sfree(scratch->zeros_cols);
- sfree(scratch);
- }
- static int unruly_solver_check_threes(game_state *state, int *rowcount,
- int *colcount, bool horizontal,
- char check, char block)
- {
- int w2 = state->w2, h2 = state->h2;
- int dx = horizontal ? 1 : 0, dy = 1 - dx;
- int sx = dx, sy = dy;
- int ex = w2 - dx, ey = h2 - dy;
- int x, y;
- int ret = 0;
- /* Check for any three squares which almost form three in a row */
- for (y = sy; y < ey; y++) {
- for (x = sx; x < ex; x++) {
- int i1 = (y-dy) * w2 + (x-dx);
- int i2 = y * w2 + x;
- int i3 = (y+dy) * w2 + (x+dx);
- if (state->grid[i1] == check && state->grid[i2] == check
- && state->grid[i3] == EMPTY) {
- ret++;
- #ifdef STANDALONE_SOLVER
- if (solver_verbose) {
- printf("Solver: %i,%i and %i,%i confirm %c at %i,%i\n",
- i1 % w2, i1 / w2, i2 % w2, i2 / w2,
- (block == N_ONE ? '1' : '0'), i3 % w2,
- i3 / w2);
- }
- #endif
- state->grid[i3] = block;
- rowcount[i3 / w2]++;
- colcount[i3 % w2]++;
- }
- if (state->grid[i1] == check && state->grid[i2] == EMPTY
- && state->grid[i3] == check) {
- ret++;
- #ifdef STANDALONE_SOLVER
- if (solver_verbose) {
- printf("Solver: %i,%i and %i,%i confirm %c at %i,%i\n",
- i1 % w2, i1 / w2, i3 % w2, i3 / w2,
- (block == N_ONE ? '1' : '0'), i2 % w2,
- i2 / w2);
- }
- #endif
- state->grid[i2] = block;
- rowcount[i2 / w2]++;
- colcount[i2 % w2]++;
- }
- if (state->grid[i1] == EMPTY && state->grid[i2] == check
- && state->grid[i3] == check) {
- ret++;
- #ifdef STANDALONE_SOLVER
- if (solver_verbose) {
- printf("Solver: %i,%i and %i,%i confirm %c at %i,%i\n",
- i2 % w2, i2 / w2, i3 % w2, i3 / w2,
- (block == N_ONE ? '1' : '0'), i1 % w2,
- i1 / w2);
- }
- #endif
- state->grid[i1] = block;
- rowcount[i1 / w2]++;
- colcount[i1 % w2]++;
- }
- }
- }
- return ret;
- }
- static int unruly_solver_check_all_threes(game_state *state,
- struct unruly_scratch *scratch)
- {
- int ret = 0;
- ret +=
- unruly_solver_check_threes(state, scratch->zeros_rows,
- scratch->zeros_cols, true, N_ONE, N_ZERO);
- ret +=
- unruly_solver_check_threes(state, scratch->ones_rows,
- scratch->ones_cols, true, N_ZERO, N_ONE);
- ret +=
- unruly_solver_check_threes(state, scratch->zeros_rows,
- scratch->zeros_cols, false, N_ONE,
- N_ZERO);
- ret +=
- unruly_solver_check_threes(state, scratch->ones_rows,
- scratch->ones_cols, false, N_ZERO, N_ONE);
- return ret;
- }
- static int unruly_solver_check_uniques(game_state *state, int *rowcount,
- bool 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, bool horizontal,
- int *rowcount, int *colcount, char fill)
- {
- int ret = 0;
- int w2 = state->w2, h2 = state->h2;
- int j;
- #ifdef STANDALONE_SOLVER
- if (solver_verbose) {
- printf("Solver: Filling %s %i with %c:",
- (horizontal ? "Row" : "Col"), i,
- (fill == N_ZERO ? '0' : '1'));
- }
- #endif
- /* Place a number in every empty square in a row/column */
- for (j = 0; j < (horizontal ? w2 : h2); j++) {
- int p = (horizontal ? i * w2 + j : j * w2 + i);
- if (state->grid[p] == EMPTY) {
- #ifdef STANDALONE_SOLVER
- if (solver_verbose) {
- printf(" (%i,%i)", (horizontal ? j : i),
- (horizontal ? i : j));
- }
- #endif
- ret++;
- state->grid[p] = fill;
- rowcount[(horizontal ? i : j)]++;
- colcount[(horizontal ? j : i)]++;
- }
- }
- #ifdef STANDALONE_SOLVER
- if (solver_verbose) {
- printf("\n");
- }
- #endif
- return ret;
- }
- static int unruly_solver_check_single_gap(game_state *state,
- int *complete, bool horizontal,
- int *rowcount, int *colcount,
- char fill)
- {
- int w2 = state->w2, h2 = state->h2;
- int count = (horizontal ? h2 : w2); /* number of rows to check */
- int target = (horizontal ? w2 : h2) / 2; /* target number of 0s/1s */
- int *other = (horizontal ? rowcount : colcount);
- int ret = 0;
- int i;
- /* Check for completed rows/cols for one number, then fill in the rest */
- for (i = 0; i < count; i++) {
- if (complete[i] == target && other[i] == target - 1) {
- #ifdef STANDALONE_SOLVER
- if (solver_verbose) {
- printf("Solver: Row %i has only one square left which must be "
- "%c\n", i, (fill == N_ZERO ? '0' : '1'));
- }
- #endif
- ret += unruly_solver_fill_row(state, i, horizontal, rowcount,
- colcount, fill);
- }
- }
- return ret;
- }
- static int unruly_solver_check_all_single_gap(game_state *state,
- struct unruly_scratch *scratch)
- {
- int ret = 0;
- ret +=
- unruly_solver_check_single_gap(state, scratch->ones_rows, true,
- scratch->zeros_rows,
- scratch->zeros_cols, N_ZERO);
- ret +=
- unruly_solver_check_single_gap(state, scratch->ones_cols, false,
- scratch->zeros_rows,
- scratch->zeros_cols, N_ZERO);
- ret +=
- unruly_solver_check_single_gap(state, scratch->zeros_rows, true,
- scratch->ones_rows,
- scratch->ones_cols, N_ONE);
- ret +=
- unruly_solver_check_single_gap(state, scratch->zeros_cols, false,
- scratch->ones_rows,
- scratch->ones_cols, N_ONE);
- return ret;
- }
- static int unruly_solver_check_complete_nums(game_state *state,
- int *complete, bool horizontal,
- int *rowcount, int *colcount,
- char fill)
- {
- int w2 = state->w2, h2 = state->h2;
- int count = (horizontal ? h2 : w2); /* number of rows to check */
- int target = (horizontal ? w2 : h2) / 2; /* target number of 0s/1s */
- int *other = (horizontal ? rowcount : colcount);
- int ret = 0;
- int i;
- /* Check for completed rows/cols for one number, then fill in the rest */
- for (i = 0; i < count; i++) {
- if (complete[i] == target && other[i] < target) {
- #ifdef STANDALONE_SOLVER
- if (solver_verbose) {
- printf("Solver: Row %i satisfied for %c\n", i,
- (fill != N_ZERO ? '0' : '1'));
- }
- #endif
- ret += unruly_solver_fill_row(state, i, horizontal, rowcount,
- colcount, fill);
- }
- }
- return ret;
- }
- static int unruly_solver_check_all_complete_nums(game_state *state,
- struct unruly_scratch *scratch)
- {
- int ret = 0;
- ret +=
- unruly_solver_check_complete_nums(state, scratch->ones_rows, true,
- scratch->zeros_rows,
- scratch->zeros_cols, N_ZERO);
- ret +=
- unruly_solver_check_complete_nums(state, scratch->ones_cols, false,
- scratch->zeros_rows,
- scratch->zeros_cols, N_ZERO);
- ret +=
- unruly_solver_check_complete_nums(state, scratch->zeros_rows, true,
- scratch->ones_rows,
- scratch->ones_cols, N_ONE);
- ret +=
- unruly_solver_check_complete_nums(state, scratch->zeros_cols, false,
- scratch->ones_rows,
- scratch->ones_cols, N_ONE);
- return ret;
- }
- static int unruly_solver_check_near_complete(game_state *state,
- int *complete, bool horizontal,
- int *rowcount, int *colcount,
- char fill)
- {
- int w2 = state->w2, h2 = state->h2;
- int w = w2/2, h = h2/2;
- int dx = horizontal ? 1 : 0, dy = 1 - dx;
- int sx = dx, sy = dy;
- int ex = w2 - dx, ey = h2 - dy;
- int x, y;
- int ret = 0;
- /*
- * This function checks for a row with one Y remaining, then looks
- * for positions that could cause the remaining squares in the row
- * to make 3 X's in a row. Example:
- *
- * Consider the following row:
- * 1 1 0 . . .
- * If the last 1 was placed in the last square, the remaining
- * squares would be 0:
- * 1 1 0 0 0 1
- * This violates the 3 in a row rule. We now know that the last 1
- * shouldn't be in the last cell.
- * 1 1 0 . . 0
- */
- /* Check for any two blank and one filled square */
- for (y = sy; y < ey; y++) {
- /* One type must have 1 remaining, the other at least 2 */
- if (horizontal && (complete[y] < w - 1 || rowcount[y] > w - 2))
- continue;
- for (x = sx; x < ex; x++) {
- int i, i1, i2, i3;
- if (!horizontal
- && (complete[x] < h - 1 || colcount[x] > h - 2))
- continue;
- i = (horizontal ? y : x);
- i1 = (y-dy) * w2 + (x-dx);
- i2 = y * w2 + x;
- i3 = (y+dy) * w2 + (x+dx);
- if (state->grid[i1] == fill && state->grid[i2] == EMPTY
- && state->grid[i3] == EMPTY) {
- /*
- * Temporarily fill the empty spaces with something else.
- * This avoids raising the counts for the row and column
- */
- state->grid[i2] = BOGUS;
- state->grid[i3] = BOGUS;
- #ifdef STANDALONE_SOLVER
- if (solver_verbose) {
- printf("Solver: Row %i nearly satisfied for %c\n", i,
- (fill != N_ZERO ? '0' : '1'));
- }
- #endif
- ret +=
- unruly_solver_fill_row(state, i, horizontal, rowcount,
- colcount, fill);
- state->grid[i2] = EMPTY;
- state->grid[i3] = EMPTY;
- }
- else if (state->grid[i1] == EMPTY && state->grid[i2] == fill
- && state->grid[i3] == EMPTY) {
- state->grid[i1] = BOGUS;
- state->grid[i3] = BOGUS;
- #ifdef STANDALONE_SOLVER
- if (solver_verbose) {
- printf("Solver: Row %i nearly satisfied for %c\n", i,
- (fill != N_ZERO ? '0' : '1'));
- }
- #endif
- ret +=
- unruly_solver_fill_row(state, i, horizontal, rowcount,
- colcount, fill);
- state->grid[i1] = EMPTY;
- state->grid[i3] = EMPTY;
- }
- else if (state->grid[i1] == EMPTY && state->grid[i2] == EMPTY
- && state->grid[i3] == fill) {
- state->grid[i1] = BOGUS;
- state->grid[i2] = BOGUS;
- #ifdef STANDALONE_SOLVER
- if (solver_verbose) {
- printf("Solver: Row %i nearly satisfied for %c\n", i,
- (fill != N_ZERO ? '0' : '1'));
- }
- #endif
- ret +=
- unruly_solver_fill_row(state, i, horizontal, rowcount,
- colcount, fill);
- state->grid[i1] = EMPTY;
- state->grid[i2] = EMPTY;
- }
- else if (state->grid[i1] == EMPTY && state->grid[i2] == EMPTY
- && state->grid[i3] == EMPTY) {
- state->grid[i1] = BOGUS;
- state->grid[i2] = BOGUS;
- state->grid[i3] = BOGUS;
- #ifdef STANDALONE_SOLVER
- if (solver_verbose) {
- printf("Solver: Row %i nearly satisfied for %c\n", i,
- (fill != N_ZERO ? '0' : '1'));
- }
- #endif
- ret +=
- unruly_solver_fill_row(state, i, horizontal, rowcount,
- colcount, fill);
- state->grid[i1] = EMPTY;
- state->grid[i2] = EMPTY;
- state->grid[i3] = EMPTY;
- }
- }
- }
- return ret;
- }
- static int unruly_solver_check_all_near_complete(game_state *state,
- struct unruly_scratch *scratch)
- {
- int ret = 0;
- ret +=
- unruly_solver_check_near_complete(state, scratch->ones_rows, true,
- scratch->zeros_rows,
- scratch->zeros_cols, N_ZERO);
- ret +=
- unruly_solver_check_near_complete(state, scratch->ones_cols, false,
- scratch->zeros_rows,
- scratch->zeros_cols, N_ZERO);
- ret +=
- unruly_solver_check_near_complete(state, scratch->zeros_rows, true,
- scratch->ones_rows,
- scratch->ones_cols, N_ONE);
- ret +=
- unruly_solver_check_near_complete(state, scratch->zeros_cols, false,
- scratch->ones_rows,
- scratch->ones_cols, N_ONE);
- return ret;
- }
- static int unruly_validate_rows(const game_state *state, bool horizontal,
- char check, int *errors)
- {
- int w2 = state->w2, h2 = state->h2;
- int dx = horizontal ? 1 : 0, dy = 1 - dx;
- int sx = dx, sy = dy;
- int ex = w2 - dx, ey = h2 - dy;
- int x, y;
- int ret = 0;
- int err1 = (horizontal ? FE_HOR_ROW_LEFT : FE_VER_ROW_TOP);
- int err2 = (horizontal ? FE_HOR_ROW_MID : FE_VER_ROW_MID);
- int err3 = (horizontal ? FE_HOR_ROW_RIGHT : FE_VER_ROW_BOTTOM);
- /* Check for any three in a row, and mark errors accordingly (if
- * required) */
- for (y = sy; y < ey; y++) {
- for (x = sx; x < ex; x++) {
- int i1 = (y-dy) * w2 + (x-dx);
- int i2 = y * w2 + x;
- int i3 = (y+dy) * w2 + (x+dx);
- if (state->grid[i1] == check && state->grid[i2] == check
- && state->grid[i3] == check) {
- ret++;
- if (errors) {
- errors[i1] |= err1;
- errors[i2] |= err2;
- errors[i3] |= err3;
- }
- }
- }
- }
- return ret;
- }
- static int unruly_validate_unique(const game_state *state, bool 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++) {
- bool 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_ONE, errors);
- errcount += unruly_validate_rows(state, false, N_ONE, errors);
- 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(const game_state *state,
- struct unruly_scratch *scratch, bool *errors)
- {
- int w2 = state->w2, h2 = state->h2;
- int w = w2/2, h = h2/2;
- bool below = false;
- bool above = false;
- int i;
- /* See if all rows/columns are satisfied. If one is exceeded,
- * mark it as an error (if required)
- */
- bool hasscratch = true;
- if (!scratch) {
- scratch = unruly_new_scratch(state);
- hasscratch = false;
- }
- for (i = 0; i < w2; i++) {
- if (scratch->ones_cols[i] < h)
- below = true;
- if (scratch->zeros_cols[i] < h)
- below = true;
- if (scratch->ones_cols[i] > h) {
- above = true;
- if (errors)
- errors[2*h2 + i] = true;
- } else if (errors)
- errors[2*h2 + i] = false;
- if (scratch->zeros_cols[i] > h) {
- above = true;
- if (errors)
- errors[2*h2 + w2 + i] = true;
- } else if (errors)
- errors[2*h2 + w2 + i] = false;
- }
- for (i = 0; i < h2; i++) {
- if (scratch->ones_rows[i] < w)
- below = true;
- if (scratch->zeros_rows[i] < w)
- below = true;
- if (scratch->ones_rows[i] > w) {
- above = true;
- if (errors)
- errors[i] = true;
- } else if (errors)
- errors[i] = false;
- if (scratch->zeros_rows[i] > w) {
- above = true;
- if (errors)
- errors[h2 + i] = true;
- } else if (errors)
- errors[h2 + i] = false;
- }
- if (!hasscratch)
- unruly_free_scratch(scratch);
- return (above ? -1 : below ? 1 : 0);
- }
- static int unruly_solve_game(game_state *state,
- struct unruly_scratch *scratch, int diff)
- {
- int done, maxdiff = -1;
- while (true) {
- done = 0;
- /* Check for impending 3's */
- done += unruly_solver_check_all_threes(state, scratch);
- /* Keep using the simpler techniques while they produce results */
- if (done) {
- if (maxdiff < DIFF_TRIVIAL)
- maxdiff = DIFF_TRIVIAL;
- continue;
- }
- /* Check for rows with only one unfilled square */
- done += unruly_solver_check_all_single_gap(state, scratch);
- if (done) {
- if (maxdiff < DIFF_TRIVIAL)
- maxdiff = DIFF_TRIVIAL;
- continue;
- }
- /* Easy techniques */
- if (diff < DIFF_EASY)
- break;
- /* Check for completed rows */
- done += unruly_solver_check_all_complete_nums(state, scratch);
- if (done) {
- if (maxdiff < DIFF_EASY)
- maxdiff = DIFF_EASY;
- 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;
- /* Check for nearly completed rows */
- done += unruly_solver_check_all_near_complete(state, scratch);
- if (done) {
- if (maxdiff < DIFF_NORMAL)
- maxdiff = DIFF_NORMAL;
- continue;
- }
- break;
- }
- return maxdiff;
- }
- static char *solve_game(const game_state *state, const game_state *currstate,
- const char *aux, const char **error)
- {
- game_state *solved = dup_game(state);
- struct unruly_scratch *scratch = unruly_new_scratch(solved);
- char *ret = NULL;
- int result;
- unruly_solve_game(solved, scratch, DIFFCOUNT);
- result = unruly_validate_counts(solved, scratch, NULL);
- if (unruly_validate_all_rows(solved, NULL) == -1)
- result = -1;
- if (result == 0) {
- int w2 = solved->w2, h2 = solved->h2;
- int s = w2 * h2;
- char *p;
- int i;
- ret = snewn(s + 2, char);
- p = ret;
- *p++ = 'S';
- for (i = 0; i < s; i++)
- *p++ = (solved->grid[i] == N_ONE ? '1' : '0');
- *p++ = '\0';
- } else if (result == 1)
- *error = "No solution found.";
- else if (result == -1)
- *error = "Puzzle is invalid.";
- free_game(solved);
- unruly_free_scratch(scratch);
- return ret;
- }
- /* ********* *
- * Generator *
- * ********* */
- static bool unruly_fill_game(game_state *state, struct unruly_scratch *scratch,
- random_state *rs)
- {
- int w2 = state->w2, h2 = state->h2;
- int s = w2 * h2;
- int i, j;
- int *spaces;
- #ifdef STANDALONE_SOLVER
- if (solver_verbose) {
- printf("Generator: Attempt to fill grid\n");
- }
- #endif
- /* Generate random array of spaces */
- spaces = snewn(s, int);
- for (i = 0; i < s; i++)
- spaces[i] = i;
- shuffle(spaces, s, sizeof(*spaces), rs);
- /*
- * Construct a valid filled grid by repeatedly picking an unfilled
- * space and fill it, then calling the solver to fill in any
- * spaces forced by the change.
- */
- for (j = 0; j < s; j++) {
- i = spaces[j];
- if (state->grid[i] != EMPTY)
- continue;
- if (random_upto(rs, 2)) {
- state->grid[i] = N_ONE;
- scratch->ones_rows[i / w2]++;
- scratch->ones_cols[i % w2]++;
- } else {
- state->grid[i] = N_ZERO;
- scratch->zeros_rows[i / w2]++;
- scratch->zeros_cols[i % w2]++;
- }
- unruly_solve_game(state, scratch, DIFFCOUNT);
- }
- sfree(spaces);
- if (unruly_validate_all_rows(state, NULL) != 0
- || unruly_validate_counts(state, scratch, NULL) != 0)
- return false;
- return true;
- }
- static char *new_game_desc(const game_params *params, random_state *rs,
- char **aux, bool interactive)
- {
- #ifdef STANDALONE_SOLVER
- char *debug;
- bool temp_verbose = false;
- #endif
- int w2 = params->w2, h2 = params->h2;
- int s = w2 * h2;
- int *spaces;
- int i, j, run;
- char *ret, *p;
- game_state *state;
- struct unruly_scratch *scratch;
- int attempts = 0;
- while (1) {
- while (true) {
- attempts++;
- state = blank_state(w2, h2, params->unique, true);
- scratch = unruly_new_scratch(state);
- if (unruly_fill_game(state, scratch, rs))
- break;
- free_game(state);
- unruly_free_scratch(scratch);
- }
- #ifdef STANDALONE_SOLVER
- if (solver_verbose) {
- printf("Puzzle generated in %i attempts\n", attempts);
- debug = game_text_format(state);
- fputs(debug, stdout);
- sfree(debug);
- temp_verbose = solver_verbose;
- solver_verbose = false;
- }
- #else
- (void)attempts;
- #endif
- unruly_free_scratch(scratch);
- /* Generate random array of spaces */
- spaces = snewn(s, int);
- for (i = 0; i < s; i++)
- spaces[i] = i;
- shuffle(spaces, s, sizeof(*spaces), rs);
- /*
- * Winnow the clues by starting from our filled grid, repeatedly
- * picking a filled space and emptying it, as long as the solver
- * reports that the puzzle can still be solved after doing so.
- */
- for (j = 0; j < s; j++) {
- char c;
- game_state *solver;
- i = spaces[j];
- c = state->grid[i];
- state->grid[i] = EMPTY;
- solver = dup_game(state);
- scratch = unruly_new_scratch(state);
- unruly_solve_game(solver, scratch, params->diff);
- if (unruly_validate_counts(solver, scratch, NULL) != 0)
- state->grid[i] = c;
- free_game(solver);
- unruly_free_scratch(scratch);
- }
- sfree(spaces);
- #ifdef STANDALONE_SOLVER
- if (temp_verbose) {
- solver_verbose = true;
- printf("Final puzzle:\n");
- debug = game_text_format(state);
- fputs(debug, stdout);
- sfree(debug);
- }
- #endif
- /*
- * See if the game has accidentally come out too easy.
- */
- if (params->diff > 0) {
- bool ok;
- game_state *solver;
- solver = dup_game(state);
- scratch = unruly_new_scratch(state);
- unruly_solve_game(solver, scratch, params->diff - 1);
- ok = unruly_validate_counts(solver, scratch, NULL) > 0;
- free_game(solver);
- unruly_free_scratch(scratch);
- if (ok)
- break;
- } else {
- /*
- * Puzzles of the easiest difficulty can't be too easy.
- */
- break;
- }
- }
- /* Encode description */
- ret = snewn(s + 1, char);
- p = ret;
- run = 0;
- for (i = 0; i < s+1; i++) {
- if (i == s || state->grid[i] == N_ZERO) {
- while (run > 24) {
- *p++ = 'z';
- run -= 25;
- }
- *p++ = 'a' + run;
- run = 0;
- } else if (state->grid[i] == N_ONE) {
- while (run > 24) {
- *p++ = 'Z';
- run -= 25;
- }
- *p++ = 'A' + run;
- run = 0;
- } else {
- run++;
- }
- }
- *p = '\0';
- free_game(state);
- return ret;
- }
- /* ************** *
- * User Interface *
- * ************** */
- struct game_ui {
- int cx, cy;
- bool cursor;
- };
- static game_ui *new_ui(const game_state *state)
- {
- game_ui *ret = snew(game_ui);
- ret->cx = ret->cy = 0;
- ret->cursor = getenv_bool("PUZZLES_SHOW_CURSOR", false);
- return ret;
- }
- static void free_ui(game_ui *ui)
- {
- sfree(ui);
- }
- static void game_changed_state(game_ui *ui, const game_state *oldstate,
- const game_state *newstate)
- {
- }
- static const char *current_key_label(const game_ui *ui,
- const game_state *state, int button)
- {
- int hx = ui->cx, hy = ui->cy;
- int w2 = state->w2;
- char i = state->grid[hy * w2 + hx];
- if (ui->cursor && IS_CURSOR_SELECT(button)) {
- if (state->common->immutable[hy * w2 + hx]) return "";
- switch (i) {
- case EMPTY:
- return button == CURSOR_SELECT ? "Black" : "White";
- case N_ONE:
- return button == CURSOR_SELECT ? "White" : "Empty";
- case N_ZERO:
- return button == CURSOR_SELECT ? "Empty" : "Black";
- }
- }
- return "";
- }
- struct game_drawstate {
- int tilesize;
- int w2, h2;
- bool started;
- int *gridfs;
- bool *rowfs;
- int *grid;
- };
- static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
- {
- struct game_drawstate *ds = snew(struct game_drawstate);
- int w2 = state->w2, h2 = state->h2;
- int s = w2 * h2;
- int i;
- ds->tilesize = 0;
- ds->w2 = w2;
- ds->h2 = h2;
- ds->started = false;
- ds->gridfs = snewn(s, int);
- ds->rowfs = snewn(2 * (w2 + h2), bool);
- ds->grid = snewn(s, int);
- for (i = 0; i < s; i++)
- ds->grid[i] = -1;
- return ds;
- }
- static void game_free_drawstate(drawing *dr, game_drawstate *ds)
- {
- sfree(ds->gridfs);
- sfree(ds->rowfs);
- sfree(ds->grid);
- sfree(ds);
- }
- #define COORD(x) ( (x) * ds->tilesize + ds->tilesize/2 )
- #define FROMCOORD(x) ( ((x)-(ds->tilesize/2)) / ds->tilesize )
- 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;
- int gx = FROMCOORD(ox);
- int gy = FROMCOORD(oy);
- int w2 = state->w2, h2 = state->h2;
- button &= ~MOD_MASK;
- /* Mouse click */
- if (button == LEFT_BUTTON || button == RIGHT_BUTTON ||
- button == MIDDLE_BUTTON) {
- if (ox >= (ds->tilesize / 2) && gx < w2
- && oy >= (ds->tilesize / 2) && gy < h2) {
- hx = gx;
- hy = gy;
- ui->cursor = false;
- } else
- return NULL;
- }
- /* Keyboard move */
- if (IS_CURSOR_MOVE(button)) {
- move_cursor(button, &ui->cx, &ui->cy, w2, h2, false);
- ui->cursor = true;
- return MOVE_UI_UPDATE;
- }
- /* Place one */
- if ((ui->cursor && (button == CURSOR_SELECT || button == CURSOR_SELECT2
- || button == '\b' || button == '0' || button == '1'
- || button == '2')) ||
- button == LEFT_BUTTON || button == RIGHT_BUTTON ||
- button == MIDDLE_BUTTON) {
- char buf[80];
- char c, i;
- if (state->common->immutable[hy * w2 + hx])
- return NULL;
- c = '-';
- i = state->grid[hy * w2 + hx];
- if (button == '0' || button == '2')
- c = '0';
- else if (button == '1')
- c = '1';
- else if (button == MIDDLE_BUTTON)
- c = '-';
- /* Cycle through options */
- else if (button == CURSOR_SELECT2 || button == RIGHT_BUTTON)
- c = (i == EMPTY ? '0' : i == N_ZERO ? '1' : '-');
- else if (button == CURSOR_SELECT || button == LEFT_BUTTON)
- c = (i == EMPTY ? '1' : i == N_ONE ? '0' : '-');
- if (state->grid[hy * w2 + hx] ==
- (c == '0' ? N_ZERO : c == '1' ? N_ONE : EMPTY))
- return NULL; /* don't put no-ops on the undo chain */
- sprintf(buf, "P%c,%d,%d", c, hx, hy);
- return dupstr(buf);
- }
- return NULL;
- }
- static game_state *execute_move(const game_state *state, const char *move)
- {
- int w2 = state->w2, h2 = state->h2;
- int s = w2 * h2;
- int x, y, i;
- char c;
- game_state *ret;
- if (move[0] == 'S') {
- const char *p;
- ret = dup_game(state);
- p = move + 1;
- for (i = 0; i < s; i++) {
- if (!*p || !(*p == '1' || *p == '0')) {
- free_game(ret);
- return NULL;
- }
- ret->grid[i] = (*p == '1' ? N_ONE : N_ZERO);
- p++;
- }
- ret->completed = ret->cheated = true;
- return ret;
- } else if (move[0] == 'P'
- && sscanf(move + 1, "%c,%d,%d", &c, &x, &y) == 3 && x >= 0
- && x < w2 && y >= 0 && y < h2 && (c == '-' || c == '0'
- || c == '1')) {
- ret = dup_game(state);
- i = y * w2 + x;
- if (state->common->immutable[i]) {
- free_game(ret);
- return NULL;
- }
- ret->grid[i] = (c == '1' ? N_ONE : c == '0' ? N_ZERO : EMPTY);
- if (!ret->completed && unruly_validate_counts(ret, NULL, NULL) == 0
- && (unruly_validate_all_rows(ret, NULL) == 0))
- ret->completed = true;
- return ret;
- }
- return NULL;
- }
- /* ----------------------------------------------------------------------
- * Drawing routines.
- */
- static void game_compute_size(const game_params *params, int tilesize,
- const game_ui *ui, int *x, int *y)
- {
- *x = tilesize * (params->w2 + 1);
- *y = tilesize * (params->h2 + 1);
- }
- static void game_set_size(drawing *dr, game_drawstate *ds,
- const game_params *params, int tilesize)
- {
- ds->tilesize = tilesize;
- }
- static float *game_colours(frontend *fe, int *ncolours)
- {
- float *ret = snewn(3 * NCOLOURS, float);
- int i;
- frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
- for (i = 0; i < 3; i++) {
- ret[COL_1 * 3 + i] = 0.2F;
- ret[COL_1_HIGHLIGHT * 3 + i] = 0.4F;
- ret[COL_1_LOWLIGHT * 3 + i] = 0.0F;
- ret[COL_0 * 3 + i] = 0.95F;
- ret[COL_0_HIGHLIGHT * 3 + i] = 1.0F;
- ret[COL_0_LOWLIGHT * 3 + i] = 0.9F;
- ret[COL_EMPTY * 3 + i] = 0.5F;
- ret[COL_GRID * 3 + i] = 0.3F;
- }
- game_mkhighlight_specific(fe, ret, COL_0, COL_0_HIGHLIGHT, COL_0_LOWLIGHT);
- game_mkhighlight_specific(fe, ret, COL_1, COL_1_HIGHLIGHT, COL_1_LOWLIGHT);
- ret[COL_ERROR * 3 + 0] = 1.0F;
- ret[COL_ERROR * 3 + 1] = 0.0F;
- ret[COL_ERROR * 3 + 2] = 0.0F;
- ret[COL_CURSOR * 3 + 0] = 0.0F;
- ret[COL_CURSOR * 3 + 1] = 0.7F;
- ret[COL_CURSOR * 3 + 2] = 0.0F;
- *ncolours = NCOLOURS;
- return ret;
- }
- static void unruly_draw_err_rectangle(drawing *dr, int x, int y, int w, int h,
- int tilesize)
- {
- double thick = tilesize / 10;
- double margin = tilesize / 20;
- draw_rect(dr, x+margin, y+margin, w-2*margin, thick, COL_ERROR);
- draw_rect(dr, x+margin, y+margin, thick, h-2*margin, COL_ERROR);
- draw_rect(dr, x+margin, y+h-margin-thick, w-2*margin, thick, COL_ERROR);
- draw_rect(dr, x+w-margin-thick, y+margin, thick, h-2*margin, COL_ERROR);
- }
- static void unruly_draw_tile(drawing *dr, int x, int y, int tilesize, int tile)
- {
- clip(dr, x, y, tilesize, tilesize);
- /* Draw the grid edge first, so the tile can overwrite it */
- draw_rect(dr, x, y, tilesize, tilesize, COL_GRID);
- /* Background of the tile */
- {
- int val = (tile & FF_ZERO ? 0 : tile & FF_ONE ? 2 : 1);
- val = (val == 0 ? COL_0 : val == 2 ? COL_1 : COL_EMPTY);
- if ((tile & (FF_FLASH1 | FF_FLASH2)) &&
- (val == COL_0 || val == COL_1)) {
- val += (tile & FF_FLASH1 ? 1 : 2);
- }
- draw_rect(dr, x, y, tilesize-1, tilesize-1, val);
- if ((val == COL_0 || val == COL_1) && (tile & FF_IMMUTABLE)) {
- draw_rect(dr, x + tilesize/6, y + tilesize/6,
- tilesize - 2*(tilesize/6) - 2, 1, val + 2);
- draw_rect(dr, x + tilesize/6, y + tilesize/6,
- 1, tilesize - 2*(tilesize/6) - 2, val + 2);
- draw_rect(dr, x + tilesize/6 + 1, y + tilesize - tilesize/6 - 2,
- tilesize - 2*(tilesize/6) - 2, 1, val + 1);
- draw_rect(dr, x + tilesize - tilesize/6 - 2, y + tilesize/6 + 1,
- 1, tilesize - 2*(tilesize/6) - 2, val + 1);
- }
- }
- /* 3-in-a-row errors */
- if (tile & (FE_HOR_ROW_LEFT | FE_HOR_ROW_RIGHT)) {
- int left = x, right = x + tilesize - 1;
- if ((tile & FE_HOR_ROW_LEFT))
- right += tilesize/2;
- if ((tile & FE_HOR_ROW_RIGHT))
- left -= tilesize/2;
- unruly_draw_err_rectangle(dr, left, y, right-left, tilesize-1, tilesize);
- }
- if (tile & (FE_VER_ROW_TOP | FE_VER_ROW_BOTTOM)) {
- int top = y, bottom = y + tilesize - 1;
- if ((tile & FE_VER_ROW_TOP))
- bottom += tilesize/2;
- if ((tile & FE_VER_ROW_BOTTOM))
- top -= tilesize/2;
- unruly_draw_err_rectangle(dr, x, top, tilesize-1, bottom-top, tilesize);
- }
- /* Count errors */
- if (tile & FE_COUNT) {
- draw_text(dr, x + tilesize/2, y + tilesize/2, FONT_VARIABLE,
- 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);
- draw_rect(dr, x, y, tilesize-1, tilesize/12, COL_CURSOR);
- draw_rect(dr, x+tilesize-1-tilesize/12, y, tilesize/12, tilesize-1,
- COL_CURSOR);
- draw_rect(dr, x, y+tilesize-1-tilesize/12, tilesize-1, tilesize/12,
- COL_CURSOR);
- }
- unclip(dr);
- draw_update(dr, x, y, tilesize, tilesize);
- }
- #define TILE_SIZE (ds->tilesize)
- #define DEFAULT_TILE_SIZE 32
- #define FLASH_FRAME 0.12F
- #define FLASH_TIME (FLASH_FRAME * 3)
- static void game_redraw(drawing *dr, game_drawstate *ds,
- 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;
- int flash;
- int x, y, i;
- if (!ds->started) {
- /* Outer edge of grid */
- draw_rect(dr, COORD(0)-TILE_SIZE/10, COORD(0)-TILE_SIZE/10,
- TILE_SIZE*w2 + 2*(TILE_SIZE/10) - 1,
- TILE_SIZE*h2 + 2*(TILE_SIZE/10) - 1, COL_GRID);
- draw_update(dr, 0, 0, TILE_SIZE * (w2+1), TILE_SIZE * (h2+1));
- ds->started = true;
- }
- flash = 0;
- if (flashtime > 0)
- flash = (int)(flashtime / FLASH_FRAME) == 1 ? FF_FLASH2 : FF_FLASH1;
- for (i = 0; i < s; i++)
- ds->gridfs[i] = 0;
- unruly_validate_all_rows(state, ds->gridfs);
- for (i = 0; i < 2 * (h2 + w2); i++)
- ds->rowfs[i] = false;
- unruly_validate_counts(state, NULL, ds->rowfs);
- for (y = 0; y < h2; y++) {
- for (x = 0; x < w2; x++) {
- int tile;
- i = y * w2 + x;
- tile = ds->gridfs[i];
- if (state->grid[i] == N_ONE) {
- tile |= FF_ONE;
- if (ds->rowfs[y] || ds->rowfs[2*h2 + x])
- tile |= FE_COUNT;
- } else if (state->grid[i] == N_ZERO) {
- tile |= FF_ZERO;
- if (ds->rowfs[h2 + y] || ds->rowfs[2*h2 + w2 + x])
- tile |= FE_COUNT;
- }
- tile |= flash;
- if (state->common->immutable[i])
- tile |= FF_IMMUTABLE;
- if (ui->cursor && ui->cx == x && ui->cy == y)
- tile |= FF_CURSOR;
- if (ds->grid[i] != tile) {
- ds->grid[i] = tile;
- unruly_draw_tile(dr, COORD(x), COORD(y), TILE_SIZE, tile);
- }
- }
- }
- }
- 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(const game_state *oldstate,
- const game_state *newstate, int dir, game_ui *ui)
- {
- if (!oldstate->completed && newstate->completed &&
- !oldstate->cheated && !newstate->cheated)
- return FLASH_TIME;
- return 0.0F;
- }
- static void game_get_cursor_location(const game_ui *ui,
- const game_drawstate *ds,
- const game_state *state,
- const game_params *params,
- int *x, int *y, int *w, int *h)
- {
- if(ui->cursor) {
- *x = COORD(ui->cx);
- *y = COORD(ui->cy);
- *w = *h = TILE_SIZE;
- }
- }
- static int game_status(const game_state *state)
- {
- return state->completed ? +1 : 0;
- }
- static void game_print_size(const game_params *params, const game_ui *ui,
- float *x, float *y)
- {
- int pw, ph;
- /* Using 7mm squares */
- game_compute_size(params, 700, ui, &pw, &ph);
- *x = pw / 100.0F;
- *y = ph / 100.0F;
- }
- static void game_print(drawing *dr, const game_state *state, const game_ui *ui,
- int tilesize)
- {
- int w2 = state->w2, h2 = state->h2;
- int x, y;
- int ink = print_mono_colour(dr, 0);
- for (y = 0; y < h2; y++)
- for (x = 0; x < w2; x++) {
- int tx = x * tilesize + (tilesize / 2);
- int ty = y * tilesize + (tilesize / 2);
- /* Draw the border */
- int coords[8];
- coords[0] = tx;
- coords[1] = ty - 1;
- coords[2] = tx + tilesize;
- coords[3] = ty - 1;
- coords[4] = tx + tilesize;
- coords[5] = ty + tilesize - 1;
- coords[6] = tx;
- coords[7] = ty + tilesize - 1;
- draw_polygon(dr, coords, 4, -1, ink);
- if (state->grid[y * w2 + x] == N_ONE)
- draw_rect(dr, tx, ty, tilesize, tilesize, ink);
- else if (state->grid[y * w2 + x] == N_ZERO)
- draw_circle(dr, tx + tilesize/2, ty + tilesize/2,
- tilesize/12, ink, ink);
- }
- }
- #ifdef COMBINED
- #define thegame unruly
- #endif
- const struct game thegame = {
- "Unruly", "games.unruly", "unruly",
- default_params,
- game_fetch_preset, NULL,
- 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,
- NULL, NULL, /* get_prefs, set_prefs */
- new_ui,
- free_ui,
- NULL, /* encode_ui */
- NULL, /* decode_ui */
- NULL, /* game_request_keys */
- game_changed_state,
- current_key_label,
- interpret_move,
- execute_move,
- DEFAULT_TILE_SIZE, game_compute_size, game_set_size,
- game_colours,
- game_new_drawstate,
- game_free_drawstate,
- game_redraw,
- game_anim_length,
- game_flash_length,
- game_get_cursor_location,
- game_status,
- true, false, game_print_size, game_print,
- false, /* wants_statusbar */
- false, NULL, /* timing_state */
- 0, /* flags */
- };
- /* ***************** *
- * Standalone solver *
- * ***************** */
- #ifdef STANDALONE_SOLVER
- #include <time.h>
- #include <stdarg.h>
- /* Most of the standalone solver code was copied from unequal.c and singles.c */
- static const char *quis;
- static void usage_exit(const char *msg)
- {
- if (msg)
- fprintf(stderr, "%s: %s\n", quis, msg);
- fprintf(stderr,
- "Usage: %s [-v] [--seed SEED] <params> | [game_id [game_id ...]]\n",
- quis);
- exit(1);
- }
- int main(int argc, char *argv[])
- {
- random_state *rs;
- time_t seed = time(NULL);
- game_params *params = NULL;
- char *id = NULL, *desc = NULL;
- const char *err;
- quis = argv[0];
- while (--argc > 0) {
- char *p = *++argv;
- if (!strcmp(p, "--seed")) {
- if (argc == 0)
- usage_exit("--seed needs an argument");
- seed = (time_t) atoi(*++argv);
- argc--;
- } else if (!strcmp(p, "-v"))
- solver_verbose = true;
- else if (*p == '-')
- usage_exit("unrecognised option");
- else
- id = p;
- }
- if (id) {
- desc = strchr(id, ':');
- if (desc)
- *desc++ = '\0';
- params = default_params();
- decode_params(params, id);
- err = validate_params(params, true);
- if (err) {
- fprintf(stderr, "Parameters are invalid\n");
- fprintf(stderr, "%s: %s", argv[0], err);
- exit(1);
- }
- }
- if (!desc) {
- char *desc_gen, *aux;
- rs = random_new((void *) &seed, sizeof(time_t));
- if (!params)
- params = default_params();
- printf("Generating puzzle with parameters %s\n",
- encode_params(params, true));
- desc_gen = new_game_desc(params, rs, &aux, false);
- if (!solver_verbose) {
- char *fmt = game_text_format(new_game(NULL, params, desc_gen));
- fputs(fmt, stdout);
- sfree(fmt);
- }
- printf("Game ID: %s\n", desc_gen);
- } else {
- game_state *input;
- struct unruly_scratch *scratch;
- int maxdiff, errcode;
- err = validate_desc(params, desc);
- if (err) {
- fprintf(stderr, "Description is invalid\n");
- fprintf(stderr, "%s", err);
- exit(1);
- }
- input = new_game(NULL, params, desc);
- scratch = unruly_new_scratch(input);
- maxdiff = unruly_solve_game(input, scratch, DIFFCOUNT);
- errcode = unruly_validate_counts(input, scratch, NULL);
- if (unruly_validate_all_rows(input, NULL) == -1)
- errcode = -1;
- if (errcode != -1) {
- char *fmt = game_text_format(input);
- fputs(fmt, stdout);
- sfree(fmt);
- if (maxdiff < 0)
- printf("Difficulty: already solved!\n");
- else
- printf("Difficulty: %s\n", unruly_diffnames[maxdiff]);
- }
- if (errcode == 1)
- printf("No solution found.\n");
- else if (errcode == -1)
- printf("Puzzle is invalid.\n");
- free_game(input);
- unruly_free_scratch(scratch);
- }
- return 0;
- }
- #endif
|