12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455 |
- /*
- * map.c: Game involving four-colouring a map.
- */
- /*
- * TODO:
- *
- * - clue marking
- * - better four-colouring algorithm?
- */
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <assert.h>
- #include <ctype.h>
- #include <limits.h>
- #ifdef NO_TGMATH_H
- # include <math.h>
- #else
- # include <tgmath.h>
- #endif
- #include "puzzles.h"
- /*
- * In standalone solver mode, `verbose' is a variable which can be
- * set by command-line option; in debugging mode it's simply always
- * true.
- */
- #if defined STANDALONE_SOLVER
- #define SOLVER_DIAGNOSTICS
- static bool verbose = false;
- #elif defined SOLVER_DIAGNOSTICS
- #define verbose true
- #endif
- /*
- * I don't seriously anticipate wanting to change the number of
- * colours used in this game, but it doesn't cost much to use a
- * #define just in case :-)
- */
- #define FOUR 4
- #define THREE (FOUR-1)
- #define FIVE (FOUR+1)
- #define SIX (FOUR+2)
- /*
- * Difficulty levels. I do some macro ickery here to ensure that my
- * enum and the various forms of my name list always match up.
- */
- #define DIFFLIST(A) \
- A(EASY,Easy,e) \
- A(NORMAL,Normal,n) \
- A(HARD,Hard,h) \
- A(RECURSE,Unreasonable,u)
- #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 map_diffnames[] = { DIFFLIST(TITLE) };
- static char const map_diffchars[] = DIFFLIST(ENCODE);
- #define DIFFCONFIG DIFFLIST(CONFIG)
- enum { TE, BE, LE, RE }; /* top/bottom/left/right edges */
- enum {
- COL_BACKGROUND,
- COL_GRID,
- COL_0, COL_1, COL_2, COL_3,
- COL_ERROR, COL_ERRTEXT,
- NCOLOURS
- };
- struct game_params {
- int w, h, n, diff;
- };
- struct map {
- int refcount;
- int *map;
- int *graph;
- int n;
- int ngraph;
- bool *immutable;
- int *edgex, *edgey; /* position of a point on each edge */
- int *regionx, *regiony; /* position of a point in each region */
- };
- struct game_state {
- game_params p;
- struct map *map;
- int *colouring, *pencil;
- bool completed, cheated;
- };
- static game_params *default_params(void)
- {
- game_params *ret = snew(game_params);
- #ifdef PORTRAIT_SCREEN
- ret->w = 16;
- ret->h = 18;
- #else
- ret->w = 20;
- ret->h = 15;
- #endif
- ret->n = 30;
- ret->diff = DIFF_NORMAL;
- return ret;
- }
- static const struct game_params map_presets[] = {
- #ifdef PORTRAIT_SCREEN
- {16, 18, 30, DIFF_EASY},
- {16, 18, 30, DIFF_NORMAL},
- {16, 18, 30, DIFF_HARD},
- {16, 18, 30, DIFF_RECURSE},
- {25, 30, 75, DIFF_NORMAL},
- {25, 30, 75, DIFF_HARD},
- #else
- {20, 15, 30, DIFF_EASY},
- {20, 15, 30, DIFF_NORMAL},
- {20, 15, 30, DIFF_HARD},
- {20, 15, 30, DIFF_RECURSE},
- {30, 25, 75, DIFF_NORMAL},
- {30, 25, 75, DIFF_HARD},
- #endif
- };
- static bool game_fetch_preset(int i, char **name, game_params **params)
- {
- game_params *ret;
- char str[80];
- if (i < 0 || i >= lenof(map_presets))
- return false;
- ret = snew(game_params);
- *ret = map_presets[i];
- sprintf(str, "%dx%d, %d regions, %s", ret->w, ret->h, ret->n,
- map_diffnames[ret->diff]);
- *name = dupstr(str);
- *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->w = atoi(p);
- while (*p && isdigit((unsigned char)*p)) p++;
- if (*p == 'x') {
- p++;
- params->h = atoi(p);
- while (*p && isdigit((unsigned char)*p)) p++;
- } else {
- params->h = params->w;
- }
- if (*p == 'n') {
- p++;
- params->n = atoi(p);
- while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
- } else {
- if (params->h > 0 && params->w > 0 &&
- params->w <= INT_MAX / params->h)
- params->n = params->w * params->h / 8;
- }
- if (*p == 'd') {
- int i;
- p++;
- for (i = 0; i < DIFFCOUNT; i++)
- if (*p == map_diffchars[i])
- params->diff = i;
- if (*p) p++;
- }
- }
- static char *encode_params(const game_params *params, bool full)
- {
- char ret[400];
- sprintf(ret, "%dx%dn%d", params->w, params->h, params->n);
- if (full)
- sprintf(ret + strlen(ret), "d%c", map_diffchars[params->diff]);
- return dupstr(ret);
- }
- 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->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 = "Regions";
- ret[2].type = C_STRING;
- sprintf(buf, "%d", params->n);
- ret[2].u.string.sval = dupstr(buf);
- 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->w = atoi(cfg[0].u.string.sval);
- ret->h = atoi(cfg[1].u.string.sval);
- ret->n = atoi(cfg[2].u.string.sval);
- ret->diff = cfg[3].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 height must be at least two";
- if (params->w > INT_MAX / 2 / params->h)
- return "Width times height must not be unreasonably large";
- if (params->n < 5)
- return "Must have at least five regions";
- if (params->n > params->w * params->h)
- return "Too many regions to fit in grid";
- return NULL;
- }
- /* ----------------------------------------------------------------------
- * Cumulative frequency table functions.
- */
- /*
- * Initialise a cumulative frequency table. (Hardly worth writing
- * this function; all it does is to initialise everything in the
- * array to zero.)
- */
- static void cf_init(int *table, int n)
- {
- int i;
- for (i = 0; i < n; i++)
- table[i] = 0;
- }
- /*
- * Increment the count of symbol `sym' by `count'.
- */
- static void cf_add(int *table, int n, int sym, int count)
- {
- int bit;
- bit = 1;
- while (sym != 0) {
- if (sym & bit) {
- table[sym] += count;
- sym &= ~bit;
- }
- bit <<= 1;
- }
- table[0] += count;
- }
- /*
- * Cumulative frequency lookup: return the total count of symbols
- * with value less than `sym'.
- */
- static int cf_clookup(int *table, int n, int sym)
- {
- int bit, index, limit, count;
- if (sym == 0)
- return 0;
- assert(0 < sym && sym <= n);
- count = table[0]; /* start with the whole table size */
- bit = 1;
- while (bit < n)
- bit <<= 1;
- limit = n;
- while (bit > 0) {
- /*
- * Find the least number with its lowest set bit in this
- * position which is greater than or equal to sym.
- */
- index = ((sym + bit - 1) &~ (bit * 2 - 1)) + bit;
- if (index < limit) {
- count -= table[index];
- limit = index;
- }
- bit >>= 1;
- }
- return count;
- }
- /*
- * Single frequency lookup: return the count of symbol `sym'.
- */
- static int cf_slookup(int *table, int n, int sym)
- {
- int count, bit;
- assert(0 <= sym && sym < n);
- count = table[sym];
- for (bit = 1; sym+bit < n && !(sym & bit); bit <<= 1)
- count -= table[sym+bit];
- return count;
- }
- /*
- * Return the largest symbol index such that the cumulative
- * frequency up to that symbol is less than _or equal to_ count.
- */
- static int cf_whichsym(int *table, int n, int count) {
- int bit, sym, top;
- assert(count >= 0 && count < table[0]);
- bit = 1;
- while (bit < n)
- bit <<= 1;
- sym = 0;
- top = table[0];
- while (bit > 0) {
- if (sym+bit < n) {
- if (count >= top - table[sym+bit])
- sym += bit;
- else
- top -= table[sym+bit];
- }
- bit >>= 1;
- }
- return sym;
- }
- /* ----------------------------------------------------------------------
- * Map generation.
- *
- * FIXME: this isn't entirely optimal at present, because it
- * inherently prioritises growing the largest region since there
- * are more squares adjacent to it. This acts as a destabilising
- * influence leading to a few large regions and mostly small ones.
- * It might be better to do it some other way.
- */
- #define WEIGHT_INCREASED 2 /* for increased perimeter */
- #define WEIGHT_DECREASED 4 /* for decreased perimeter */
- #define WEIGHT_UNCHANGED 3 /* for unchanged perimeter */
- /*
- * Look at a square and decide which colours can be extended into
- * it.
- *
- * If called with index < 0, it adds together one of
- * WEIGHT_INCREASED, WEIGHT_DECREASED or WEIGHT_UNCHANGED for each
- * colour that has a valid extension (according to the effect that
- * it would have on the perimeter of the region being extended) and
- * returns the overall total.
- *
- * If called with index >= 0, it returns one of the possible
- * colours depending on the value of index, in such a way that the
- * number of possible inputs which would give rise to a given
- * return value correspond to the weight of that value.
- */
- static int extend_options(int w, int h, int n, int *map,
- int x, int y, int index)
- {
- int c, i, dx, dy;
- int col[8];
- int total = 0;
- if (map[y*w+x] >= 0) {
- assert(index < 0);
- return 0; /* can't do this square at all */
- }
- /*
- * Fetch the eight neighbours of this square, in order around
- * the square.
- */
- for (dy = -1; dy <= +1; dy++)
- for (dx = -1; dx <= +1; dx++) {
- int index = (dy < 0 ? 6-dx : dy > 0 ? 2+dx : 2*(1+dx));
- if (x+dx >= 0 && x+dx < w && y+dy >= 0 && y+dy < h)
- col[index] = map[(y+dy)*w+(x+dx)];
- else
- col[index] = -1;
- }
- /*
- * Iterate over each colour that might be feasible.
- *
- * FIXME: this routine currently has O(n) running time. We
- * could turn it into O(FOUR) by only bothering to iterate over
- * the colours mentioned in the four neighbouring squares.
- */
- for (c = 0; c < n; c++) {
- int count, neighbours, runs;
- /*
- * One of the even indices of col (representing the
- * orthogonal neighbours of this square) must be equal to
- * c, or else this square is not adjacent to region c and
- * obviously cannot become an extension of it at this time.
- */
- neighbours = 0;
- for (i = 0; i < 8; i += 2)
- if (col[i] == c)
- neighbours++;
- if (!neighbours)
- continue;
- /*
- * Now we know this square is adjacent to region c. The
- * next question is, would extending it cause the region to
- * become non-simply-connected? If so, we mustn't do it.
- *
- * We determine this by looking around col to see if we can
- * find more than one separate run of colour c.
- */
- runs = 0;
- for (i = 0; i < 8; i++)
- if (col[i] == c && col[(i+1) & 7] != c)
- runs++;
- if (runs > 1)
- continue;
- assert(runs == 1);
- /*
- * This square is a possibility. Determine its effect on
- * the region's perimeter (computed from the number of
- * orthogonal neighbours - 1 means a perimeter increase, 3
- * a decrease, 2 no change; 4 is impossible because the
- * region would already not be simply connected) and we're
- * done.
- */
- assert(neighbours > 0 && neighbours < 4);
- count = (neighbours == 1 ? WEIGHT_INCREASED :
- neighbours == 2 ? WEIGHT_UNCHANGED : WEIGHT_DECREASED);
- total += count;
- if (index >= 0 && index < count)
- return c;
- else
- index -= count;
- }
- assert(index < 0);
- return total;
- }
- static void genmap(int w, int h, int n, int *map, random_state *rs)
- {
- int wh = w*h;
- int x, y, i, k;
- int *tmp;
- assert(n <= wh);
- tmp = snewn(wh, int);
- /*
- * Clear the map, and set up `tmp' as a list of grid indices.
- */
- for (i = 0; i < wh; i++) {
- map[i] = -1;
- tmp[i] = i;
- }
- /*
- * Place the region seeds by selecting n members from `tmp'.
- */
- k = wh;
- for (i = 0; i < n; i++) {
- int j = random_upto(rs, k);
- map[tmp[j]] = i;
- tmp[j] = tmp[--k];
- }
- /*
- * Re-initialise `tmp' as a cumulative frequency table. This
- * will store the number of possible region colours we can
- * extend into each square.
- */
- cf_init(tmp, wh);
- /*
- * Go through the grid and set up the initial cumulative
- * frequencies.
- */
- for (y = 0; y < h; y++)
- for (x = 0; x < w; x++)
- cf_add(tmp, wh, y*w+x,
- extend_options(w, h, n, map, x, y, -1));
- /*
- * Now repeatedly choose a square we can extend a region into,
- * and do so.
- */
- while (tmp[0] > 0) {
- int k = random_upto(rs, tmp[0]);
- int sq;
- int colour;
- int xx, yy;
- sq = cf_whichsym(tmp, wh, k);
- k -= cf_clookup(tmp, wh, sq);
- x = sq % w;
- y = sq / w;
- colour = extend_options(w, h, n, map, x, y, k);
- map[sq] = colour;
- /*
- * Re-scan the nine cells around the one we've just
- * modified.
- */
- for (yy = max(y-1, 0); yy < min(y+2, h); yy++)
- for (xx = max(x-1, 0); xx < min(x+2, w); xx++) {
- cf_add(tmp, wh, yy*w+xx,
- -cf_slookup(tmp, wh, yy*w+xx) +
- extend_options(w, h, n, map, xx, yy, -1));
- }
- }
- /*
- * Finally, go through and normalise the region labels into
- * order, meaning that indistinguishable maps are actually
- * identical.
- */
- for (i = 0; i < n; i++)
- tmp[i] = -1;
- k = 0;
- for (i = 0; i < wh; i++) {
- assert(map[i] >= 0);
- if (tmp[map[i]] < 0)
- tmp[map[i]] = k++;
- map[i] = tmp[map[i]];
- }
- sfree(tmp);
- }
- /* ----------------------------------------------------------------------
- * Functions to handle graphs.
- */
- /*
- * Having got a map in a square grid, convert it into a graph
- * representation.
- */
- static int gengraph(int w, int h, int n, int *map, int *graph)
- {
- int i, j, x, y;
- /*
- * Start by setting the graph up as an adjacency matrix. We'll
- * turn it into a list later.
- */
- for (i = 0; i < n*n; i++)
- graph[i] = 0;
- /*
- * Iterate over the map looking for all adjacencies.
- */
- for (y = 0; y < h; y++)
- for (x = 0; x < w; x++) {
- int v, vx, vy;
- v = map[y*w+x];
- if (x+1 < w && (vx = map[y*w+(x+1)]) != v)
- graph[v*n+vx] = graph[vx*n+v] = 1;
- if (y+1 < h && (vy = map[(y+1)*w+x]) != v)
- graph[v*n+vy] = graph[vy*n+v] = 1;
- }
- /*
- * Turn the matrix into a list.
- */
- for (i = j = 0; i < n*n; i++)
- if (graph[i])
- graph[j++] = i;
- return j;
- }
- static int graph_edge_index(int *graph, int n, int ngraph, int i, int j)
- {
- int v = i*n+j;
- int top, bot, mid;
- bot = -1;
- top = ngraph;
- while (top - bot > 1) {
- mid = (top + bot) / 2;
- if (graph[mid] == v)
- return mid;
- else if (graph[mid] < v)
- bot = mid;
- else
- top = mid;
- }
- return -1;
- }
- #define graph_adjacent(graph, n, ngraph, i, j) \
- (graph_edge_index((graph), (n), (ngraph), (i), (j)) >= 0)
- static int graph_vertex_start(int *graph, int n, int ngraph, int i)
- {
- int v = i*n;
- int top, bot, mid;
- bot = -1;
- top = ngraph;
- while (top - bot > 1) {
- mid = (top + bot) / 2;
- if (graph[mid] < v)
- bot = mid;
- else
- top = mid;
- }
- return top;
- }
- /* ----------------------------------------------------------------------
- * Generate a four-colouring of a graph.
- *
- * FIXME: it would be nice if we could convert this recursion into
- * pseudo-recursion using some sort of explicit stack array, for
- * the sake of the Palm port and its limited stack.
- */
- static bool fourcolour_recurse(int *graph, int n, int ngraph,
- int *colouring, int *scratch, random_state *rs)
- {
- int nfree, nvert, start, i, j, k, c, ci;
- int cs[FOUR];
- /*
- * Find the smallest number of free colours in any uncoloured
- * vertex, and count the number of such vertices.
- */
- nfree = FIVE; /* start off bigger than FOUR! */
- nvert = 0;
- for (i = 0; i < n; i++)
- if (colouring[i] < 0 && scratch[i*FIVE+FOUR] <= nfree) {
- if (nfree > scratch[i*FIVE+FOUR]) {
- nfree = scratch[i*FIVE+FOUR];
- nvert = 0;
- }
- nvert++;
- }
- /*
- * If there aren't any uncoloured vertices at all, we're done.
- */
- if (nvert == 0)
- return true; /* we've got a colouring! */
- /*
- * Pick a random vertex in that set.
- */
- j = random_upto(rs, nvert);
- for (i = 0; i < n; i++)
- if (colouring[i] < 0 && scratch[i*FIVE+FOUR] == nfree)
- if (j-- == 0)
- break;
- assert(i < n);
- start = graph_vertex_start(graph, n, ngraph, i);
- /*
- * Loop over the possible colours for i, and recurse for each
- * one.
- */
- ci = 0;
- for (c = 0; c < FOUR; c++)
- if (scratch[i*FIVE+c] == 0)
- cs[ci++] = c;
- shuffle(cs, ci, sizeof(*cs), rs);
- while (ci-- > 0) {
- c = cs[ci];
- /*
- * Fill in this colour.
- */
- colouring[i] = c;
- /*
- * Update the scratch space to reflect a new neighbour
- * of this colour for each neighbour of vertex i.
- */
- for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
- k = graph[j] - i*n;
- if (scratch[k*FIVE+c] == 0)
- scratch[k*FIVE+FOUR]--;
- scratch[k*FIVE+c]++;
- }
- /*
- * Recurse.
- */
- if (fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs))
- return true; /* got one! */
- /*
- * If that didn't work, clean up and try again with a
- * different colour.
- */
- for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
- k = graph[j] - i*n;
- scratch[k*FIVE+c]--;
- if (scratch[k*FIVE+c] == 0)
- scratch[k*FIVE+FOUR]++;
- }
- colouring[i] = -1;
- }
- /*
- * If we reach here, we were unable to find a colouring at all.
- * (This doesn't necessarily mean the Four Colour Theorem is
- * violated; it might just mean we've gone down a dead end and
- * need to back up and look somewhere else. It's only an FCT
- * violation if we get all the way back up to the top level and
- * still fail.)
- */
- return false;
- }
- static void fourcolour(int *graph, int n, int ngraph, int *colouring,
- random_state *rs)
- {
- int *scratch;
- int i;
- bool retd;
- /*
- * For each vertex and each colour, we store the number of
- * neighbours that have that colour. Also, we store the number
- * of free colours for the vertex.
- */
- scratch = snewn(n * FIVE, int);
- for (i = 0; i < n * FIVE; i++)
- scratch[i] = (i % FIVE == FOUR ? FOUR : 0);
- /*
- * Clear the colouring to start with.
- */
- for (i = 0; i < n; i++)
- colouring[i] = -1;
- retd = fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs);
- assert(retd); /* by the Four Colour Theorem :-) */
- sfree(scratch);
- }
- /* ----------------------------------------------------------------------
- * Non-recursive solver.
- */
- struct solver_scratch {
- unsigned char *possible; /* bitmap of colours for each region */
- int *graph;
- int n;
- int ngraph;
- int *bfsqueue;
- int *bfscolour;
- #ifdef SOLVER_DIAGNOSTICS
- int *bfsprev;
- #endif
- int depth;
- };
- static struct solver_scratch *new_scratch(int *graph, int n, int ngraph)
- {
- struct solver_scratch *sc;
- sc = snew(struct solver_scratch);
- sc->graph = graph;
- sc->n = n;
- sc->ngraph = ngraph;
- sc->possible = snewn(n, unsigned char);
- sc->depth = 0;
- sc->bfsqueue = snewn(n, int);
- sc->bfscolour = snewn(n, int);
- #ifdef SOLVER_DIAGNOSTICS
- sc->bfsprev = snewn(n, int);
- #endif
- return sc;
- }
- static void free_scratch(struct solver_scratch *sc)
- {
- sfree(sc->possible);
- sfree(sc->bfsqueue);
- sfree(sc->bfscolour);
- #ifdef SOLVER_DIAGNOSTICS
- sfree(sc->bfsprev);
- #endif
- sfree(sc);
- }
- /*
- * Count the bits in a word. Only needs to cope with FOUR bits.
- */
- static int bitcount(int word)
- {
- assert(FOUR <= 4); /* or this needs changing */
- word = ((word & 0xA) >> 1) + (word & 0x5);
- word = ((word & 0xC) >> 2) + (word & 0x3);
- return word;
- }
- #ifdef SOLVER_DIAGNOSTICS
- static const char colnames[FOUR] = { 'R', 'Y', 'G', 'B' };
- #endif
- static bool place_colour(struct solver_scratch *sc,
- int *colouring, int index, int colour
- #ifdef SOLVER_DIAGNOSTICS
- , const char *verb
- #endif
- )
- {
- int *graph = sc->graph, n = sc->n, ngraph = sc->ngraph;
- int j, k;
- if (!(sc->possible[index] & (1 << colour))) {
- #ifdef SOLVER_DIAGNOSTICS
- if (verbose)
- printf("%*scannot place %c in region %d\n", 2*sc->depth, "",
- colnames[colour], index);
- #endif
- return false; /* can't do it */
- }
- sc->possible[index] = 1 << colour;
- colouring[index] = colour;
- #ifdef SOLVER_DIAGNOSTICS
- if (verbose)
- printf("%*s%s %c in region %d\n", 2*sc->depth, "",
- verb, colnames[colour], index);
- #endif
- /*
- * Rule out this colour from all the region's neighbours.
- */
- for (j = graph_vertex_start(graph, n, ngraph, index);
- j < ngraph && graph[j] < n*(index+1); j++) {
- k = graph[j] - index*n;
- #ifdef SOLVER_DIAGNOSTICS
- if (verbose && (sc->possible[k] & (1 << colour)))
- printf("%*s ruling out %c in region %d\n", 2*sc->depth, "",
- colnames[colour], k);
- #endif
- sc->possible[k] &= ~(1 << colour);
- }
- return true;
- }
- #ifdef SOLVER_DIAGNOSTICS
- static char *colourset(char *buf, int set)
- {
- int i;
- char *p = buf;
- const char *sep = "";
- for (i = 0; i < FOUR; i++)
- if (set & (1 << i)) {
- p += sprintf(p, "%s%c", sep, colnames[i]);
- sep = ",";
- }
- return buf;
- }
- #endif
- /*
- * Returns 0 for impossible, 1 for success, 2 for failure to
- * converge (i.e. puzzle is either ambiguous or just too
- * difficult).
- */
- static int map_solver(struct solver_scratch *sc,
- int *graph, int n, int ngraph, int *colouring,
- int difficulty)
- {
- int i;
- if (sc->depth == 0) {
- /*
- * Initialise scratch space.
- */
- for (i = 0; i < n; i++)
- sc->possible[i] = (1 << FOUR) - 1;
- /*
- * Place clues.
- */
- for (i = 0; i < n; i++)
- if (colouring[i] >= 0) {
- if (!place_colour(sc, colouring, i, colouring[i]
- #ifdef SOLVER_DIAGNOSTICS
- , "initial clue:"
- #endif
- )) {
- #ifdef SOLVER_DIAGNOSTICS
- if (verbose)
- printf("%*sinitial clue set is inconsistent\n",
- 2*sc->depth, "");
- #endif
- return 0; /* the clues aren't even consistent! */
- }
- }
- }
- /*
- * Now repeatedly loop until we find nothing further to do.
- */
- while (1) {
- bool done_something = false;
- if (difficulty < DIFF_EASY)
- break; /* can't do anything at all! */
- /*
- * Simplest possible deduction: find a region with only one
- * possible colour.
- */
- for (i = 0; i < n; i++) if (colouring[i] < 0) {
- int p = sc->possible[i];
- if (p == 0) {
- #ifdef SOLVER_DIAGNOSTICS
- if (verbose)
- printf("%*sregion %d has no possible colours left\n",
- 2*sc->depth, "", i);
- #endif
- return 0; /* puzzle is inconsistent */
- }
- if ((p & (p-1)) == 0) { /* p is a power of two */
- int c;
- bool ret;
- for (c = 0; c < FOUR; c++)
- if (p == (1 << c))
- break;
- assert(c < FOUR);
- ret = place_colour(sc, colouring, i, c
- #ifdef SOLVER_DIAGNOSTICS
- , "placing"
- #endif
- );
- /*
- * place_colour() can only fail if colour c was not
- * even a _possibility_ for region i, and we're
- * pretty sure it was because we checked before
- * calling place_colour(). So we can safely assert
- * here rather than having to return a nice
- * friendly error code.
- */
- assert(ret);
- done_something = true;
- }
- }
- if (done_something)
- continue;
- if (difficulty < DIFF_NORMAL)
- break; /* can't do anything harder */
- /*
- * Failing that, go up one level. Look for pairs of regions
- * which (a) both have the same pair of possible colours,
- * (b) are adjacent to one another, (c) are adjacent to the
- * same region, and (d) that region still thinks it has one
- * or both of those possible colours.
- *
- * Simplest way to do this is by going through the graph
- * edge by edge, so that we start with property (b) and
- * then look for (a) and finally (c) and (d).
- */
- for (i = 0; i < ngraph; i++) {
- int j1 = graph[i] / n, j2 = graph[i] % n;
- int j, k, v, v2;
- #ifdef SOLVER_DIAGNOSTICS
- bool started = false;
- #endif
- if (j1 > j2)
- continue; /* done it already, other way round */
- if (colouring[j1] >= 0 || colouring[j2] >= 0)
- continue; /* they're not undecided */
- if (sc->possible[j1] != sc->possible[j2])
- continue; /* they don't have the same possibles */
- v = sc->possible[j1];
- /*
- * See if v contains exactly two set bits.
- */
- v2 = v & -v; /* find lowest set bit */
- v2 = v & ~v2; /* clear it */
- if (v2 == 0 || (v2 & (v2-1)) != 0) /* not power of 2 */
- continue;
- /*
- * We've found regions j1 and j2 satisfying properties
- * (a) and (b): they have two possible colours between
- * them, and since they're adjacent to one another they
- * must use _both_ those colours between them.
- * Therefore, if they are both adjacent to any other
- * region then that region cannot be either colour.
- *
- * Go through the neighbours of j1 and see if any are
- * shared with j2.
- */
- for (j = graph_vertex_start(graph, n, ngraph, j1);
- j < ngraph && graph[j] < n*(j1+1); j++) {
- k = graph[j] - j1*n;
- if (graph_adjacent(graph, n, ngraph, k, j2) &&
- (sc->possible[k] & v)) {
- #ifdef SOLVER_DIAGNOSTICS
- if (verbose) {
- char buf[80];
- if (!started)
- printf("%*sadjacent regions %d,%d share colours"
- " %s\n", 2*sc->depth, "", j1, j2,
- colourset(buf, v));
- started = true;
- printf("%*s ruling out %s in region %d\n",2*sc->depth,
- "", colourset(buf, sc->possible[k] & v), k);
- }
- #endif
- sc->possible[k] &= ~v;
- done_something = true;
- }
- }
- }
- if (done_something)
- continue;
- if (difficulty < DIFF_HARD)
- break; /* can't do anything harder */
- /*
- * Right; now we get creative. Now we're going to look for
- * `forcing chains'. A forcing chain is a path through the
- * graph with the following properties:
- *
- * (a) Each vertex on the path has precisely two possible
- * colours.
- *
- * (b) Each pair of vertices which are adjacent on the
- * path share at least one possible colour in common.
- *
- * (c) Each vertex in the middle of the path shares _both_
- * of its colours with at least one of its neighbours
- * (not the same one with both neighbours).
- *
- * These together imply that at least one of the possible
- * colour choices at one end of the path forces _all_ the
- * rest of the colours along the path. In order to make
- * real use of this, we need further properties:
- *
- * (c) Ruling out some colour C from the vertex at one end
- * of the path forces the vertex at the other end to
- * take colour C.
- *
- * (d) The two end vertices are mutually adjacent to some
- * third vertex.
- *
- * (e) That third vertex currently has C as a possibility.
- *
- * If we can find all of that lot, we can deduce that at
- * least one of the two ends of the forcing chain has
- * colour C, and that therefore the mutually adjacent third
- * vertex does not.
- *
- * To find forcing chains, we're going to start a bfs at
- * each suitable vertex of the graph, once for each of its
- * two possible colours.
- */
- for (i = 0; i < n; i++) {
- int c;
- if (colouring[i] >= 0 || bitcount(sc->possible[i]) != 2)
- continue;
- for (c = 0; c < FOUR; c++)
- if (sc->possible[i] & (1 << c)) {
- int j, k, gi, origc, currc, head, tail;
- /*
- * Try a bfs from this vertex, ruling out
- * colour c.
- *
- * Within this loop, we work in colour bitmaps
- * rather than actual colours, because
- * converting back and forth is a needless
- * computational expense.
- */
- origc = 1 << c;
- for (j = 0; j < n; j++) {
- sc->bfscolour[j] = -1;
- #ifdef SOLVER_DIAGNOSTICS
- sc->bfsprev[j] = -1;
- #endif
- }
- head = tail = 0;
- sc->bfsqueue[tail++] = i;
- sc->bfscolour[i] = sc->possible[i] &~ origc;
- while (head < tail) {
- j = sc->bfsqueue[head++];
- currc = sc->bfscolour[j];
- /*
- * Try neighbours of j.
- */
- for (gi = graph_vertex_start(graph, n, ngraph, j);
- gi < ngraph && graph[gi] < n*(j+1); gi++) {
- k = graph[gi] - j*n;
- /*
- * To continue with the bfs in vertex
- * k, we need k to be
- * (a) not already visited
- * (b) have two possible colours
- * (c) those colours include currc.
- */
- if (sc->bfscolour[k] < 0 &&
- colouring[k] < 0 &&
- bitcount(sc->possible[k]) == 2 &&
- (sc->possible[k] & currc)) {
- sc->bfsqueue[tail++] = k;
- sc->bfscolour[k] =
- sc->possible[k] &~ currc;
- #ifdef SOLVER_DIAGNOSTICS
- sc->bfsprev[k] = j;
- #endif
- }
- /*
- * One other possibility is that k
- * might be the region in which we can
- * make a real deduction: if it's
- * adjacent to i, contains currc as a
- * possibility, and currc is equal to
- * the original colour we ruled out.
- */
- if (currc == origc &&
- graph_adjacent(graph, n, ngraph, k, i) &&
- (sc->possible[k] & currc)) {
- #ifdef SOLVER_DIAGNOSTICS
- if (verbose) {
- char buf[80];
- const char *sep = "";
- int r;
- printf("%*sforcing chain, colour %s, ",
- 2*sc->depth, "",
- colourset(buf, origc));
- for (r = j; r != -1; r = sc->bfsprev[r]) {
- printf("%s%d", sep, r);
- sep = "-";
- }
- printf("\n%*s ruling out %s in region"
- " %d\n", 2*sc->depth, "",
- colourset(buf, origc), k);
- }
- #endif
- sc->possible[k] &= ~origc;
- done_something = true;
- }
- }
- }
- assert(tail <= n);
- }
- }
- if (!done_something)
- break;
- }
- /*
- * See if we've got a complete solution, and return if so.
- */
- for (i = 0; i < n; i++)
- if (colouring[i] < 0)
- break;
- if (i == n) {
- #ifdef SOLVER_DIAGNOSTICS
- if (verbose)
- printf("%*sone solution found\n", 2*sc->depth, "");
- #endif
- return 1; /* success! */
- }
- /*
- * If recursion is not permissible, we now give up.
- */
- if (difficulty < DIFF_RECURSE) {
- #ifdef SOLVER_DIAGNOSTICS
- if (verbose)
- printf("%*sunable to proceed further without recursion\n",
- 2*sc->depth, "");
- #endif
- return 2; /* unable to complete */
- }
- /*
- * Now we've got to do something recursive. So first hunt for a
- * currently-most-constrained region.
- */
- {
- int best, bestc;
- struct solver_scratch *rsc;
- int *subcolouring, *origcolouring;
- int ret, subret;
- bool we_already_got_one;
- best = -1;
- bestc = FIVE;
- for (i = 0; i < n; i++) if (colouring[i] < 0) {
- int p = sc->possible[i];
- enum { compile_time_assertion = 1 / (FOUR <= 4) };
- int c;
- /* Count the set bits. */
- c = (p & 5) + ((p >> 1) & 5);
- c = (c & 3) + ((c >> 2) & 3);
- assert(c > 1); /* or colouring[i] would be >= 0 */
- if (c < bestc) {
- best = i;
- bestc = c;
- }
- }
- assert(best >= 0); /* or we'd be solved already */
- #ifdef SOLVER_DIAGNOSTICS
- if (verbose)
- printf("%*srecursing on region %d\n", 2*sc->depth, "", best);
- #endif
- /*
- * Now iterate over the possible colours for this region.
- */
- rsc = new_scratch(graph, n, ngraph);
- rsc->depth = sc->depth + 1;
- origcolouring = snewn(n, int);
- memcpy(origcolouring, colouring, n * sizeof(int));
- subcolouring = snewn(n, int);
- we_already_got_one = false;
- ret = 0;
- for (i = 0; i < FOUR; i++) {
- if (!(sc->possible[best] & (1 << i)))
- continue;
- memcpy(rsc->possible, sc->possible, n);
- memcpy(subcolouring, origcolouring, n * sizeof(int));
- place_colour(rsc, subcolouring, best, i
- #ifdef SOLVER_DIAGNOSTICS
- , "trying"
- #endif
- );
- subret = map_solver(rsc, graph, n, ngraph,
- subcolouring, difficulty);
- #ifdef SOLVER_DIAGNOSTICS
- if (verbose) {
- printf("%*sretracting %c in region %d; found %s\n",
- 2*sc->depth, "", colnames[i], best,
- subret == 0 ? "no solutions" :
- subret == 1 ? "one solution" : "multiple solutions");
- }
- #endif
- /*
- * If this possibility turned up more than one valid
- * solution, or if it turned up one and we already had
- * one, we're definitely ambiguous.
- */
- if (subret == 2 || (subret == 1 && we_already_got_one)) {
- ret = 2;
- break;
- }
- /*
- * If this possibility turned up one valid solution and
- * it's the first we've seen, copy it into the output.
- */
- if (subret == 1) {
- memcpy(colouring, subcolouring, n * sizeof(int));
- we_already_got_one = true;
- ret = 1;
- }
- /*
- * Otherwise, this guess led to a contradiction, so we
- * do nothing.
- */
- }
- sfree(origcolouring);
- sfree(subcolouring);
- free_scratch(rsc);
- #ifdef SOLVER_DIAGNOSTICS
- if (verbose && sc->depth == 0) {
- printf("%*s%s found\n",
- 2*sc->depth, "",
- ret == 0 ? "no solutions" :
- ret == 1 ? "one solution" : "multiple solutions");
- }
- #endif
- return ret;
- }
- }
- /* ----------------------------------------------------------------------
- * Game generation main function.
- */
- static char *new_game_desc(const game_params *params, random_state *rs,
- char **aux, bool interactive)
- {
- struct solver_scratch *sc = NULL;
- int *map, *graph, ngraph, *colouring, *colouring2, *regions;
- int i, j, w, h, n, solveret, cfreq[FOUR];
- int wh;
- int mindiff, tries;
- #ifdef GENERATION_DIAGNOSTICS
- int x, y;
- #endif
- char *ret, buf[80];
- int retlen, retsize;
- w = params->w;
- h = params->h;
- n = params->n;
- wh = w*h;
- *aux = NULL;
- map = snewn(wh, int);
- graph = snewn(n*n, int);
- colouring = snewn(n, int);
- colouring2 = snewn(n, int);
- regions = snewn(n, int);
- /*
- * This is the minimum difficulty below which we'll completely
- * reject a map design. Normally we set this to one below the
- * requested difficulty, ensuring that we have the right
- * result. However, for particularly dense maps or maps with
- * particularly few regions it might not be possible to get the
- * desired difficulty, so we will eventually drop this down to
- * -1 to indicate that any old map will do.
- */
- mindiff = params->diff;
- tries = 50;
- while (1) {
- /*
- * Create the map.
- */
- genmap(w, h, n, map, rs);
- #ifdef GENERATION_DIAGNOSTICS
- for (y = 0; y < h; y++) {
- for (x = 0; x < w; x++) {
- int v = map[y*w+x];
- if (v >= 62)
- putchar('!');
- else if (v >= 36)
- putchar('a' + v-36);
- else if (v >= 10)
- putchar('A' + v-10);
- else
- putchar('0' + v);
- }
- putchar('\n');
- }
- #endif
- /*
- * Convert the map into a graph.
- */
- ngraph = gengraph(w, h, n, map, graph);
- #ifdef GENERATION_DIAGNOSTICS
- for (i = 0; i < ngraph; i++)
- printf("%d-%d\n", graph[i]/n, graph[i]%n);
- #endif
- /*
- * Colour the map.
- */
- fourcolour(graph, n, ngraph, colouring, rs);
- #ifdef GENERATION_DIAGNOSTICS
- for (i = 0; i < n; i++)
- printf("%d: %d\n", i, colouring[i]);
- for (y = 0; y < h; y++) {
- for (x = 0; x < w; x++) {
- int v = colouring[map[y*w+x]];
- if (v >= 36)
- putchar('a' + v-36);
- else if (v >= 10)
- putchar('A' + v-10);
- else
- putchar('0' + v);
- }
- putchar('\n');
- }
- #endif
- /*
- * Encode the solution as an aux string.
- */
- if (*aux) /* in case we've come round again */
- sfree(*aux);
- retlen = retsize = 0;
- ret = NULL;
- for (i = 0; i < n; i++) {
- int len;
- if (colouring[i] < 0)
- continue;
- len = sprintf(buf, "%s%d:%d", i ? ";" : "S;", colouring[i], i);
- if (retlen + len >= retsize) {
- retsize = retlen + len + 256;
- ret = sresize(ret, retsize, char);
- }
- strcpy(ret + retlen, buf);
- retlen += len;
- }
- *aux = ret;
- /*
- * Remove the region colours one by one, keeping
- * solubility. Also ensure that there always remains at
- * least one region of every colour, so that the user can
- * drag from somewhere.
- */
- for (i = 0; i < FOUR; i++)
- cfreq[i] = 0;
- for (i = 0; i < n; i++) {
- regions[i] = i;
- cfreq[colouring[i]]++;
- }
- for (i = 0; i < FOUR; i++)
- if (cfreq[i] == 0)
- continue;
- shuffle(regions, n, sizeof(*regions), rs);
- if (sc) free_scratch(sc);
- sc = new_scratch(graph, n, ngraph);
- for (i = 0; i < n; i++) {
- j = regions[i];
- if (cfreq[colouring[j]] == 1)
- continue; /* can't remove last region of colour */
- memcpy(colouring2, colouring, n*sizeof(int));
- colouring2[j] = -1;
- solveret = map_solver(sc, graph, n, ngraph, colouring2,
- params->diff);
- assert(solveret >= 0); /* mustn't be impossible! */
- if (solveret == 1) {
- cfreq[colouring[j]]--;
- colouring[j] = -1;
- }
- }
- #ifdef GENERATION_DIAGNOSTICS
- for (i = 0; i < n; i++)
- if (colouring[i] >= 0) {
- if (i >= 62)
- putchar('!');
- else if (i >= 36)
- putchar('a' + i-36);
- else if (i >= 10)
- putchar('A' + i-10);
- else
- putchar('0' + i);
- printf(": %d\n", colouring[i]);
- }
- #endif
- /*
- * Finally, check that the puzzle is _at least_ as hard as
- * required, and indeed that it isn't already solved.
- * (Calling map_solver with negative difficulty ensures the
- * latter - if a solver which _does nothing_ can solve it,
- * it's too easy!)
- */
- memcpy(colouring2, colouring, n*sizeof(int));
- if (map_solver(sc, graph, n, ngraph, colouring2,
- mindiff - 1) == 1) {
- /*
- * Drop minimum difficulty if necessary.
- */
- if (mindiff > 0 && (n < 9 || n > 2*wh/3)) {
- if (tries-- <= 0)
- mindiff = 0; /* give up and go for Easy */
- }
- continue;
- }
- break;
- }
- /*
- * Encode as a game ID. We do this by:
- *
- * - first going along the horizontal edges row by row, and
- * then the vertical edges column by column
- * - encoding the lengths of runs of edges and runs of
- * non-edges
- * - the decoder will reconstitute the region boundaries from
- * this and automatically number them the same way we did
- * - then we encode the initial region colours in a Slant-like
- * fashion (digits 0-3 interspersed with letters giving
- * lengths of runs of empty spaces).
- */
- retlen = retsize = 0;
- ret = NULL;
- {
- int run;
- bool pv;
- /*
- * Start with a notional non-edge, so that there'll be an
- * explicit `a' to distinguish the case where we start with
- * an edge.
- */
- run = 1;
- pv = false;
- for (i = 0; i < w*(h-1) + (w-1)*h; i++) {
- int x, y, dx, dy;
- bool v;
- if (i < w*(h-1)) {
- /* Horizontal edge. */
- y = i / w;
- x = i % w;
- dx = 0;
- dy = 1;
- } else {
- /* Vertical edge. */
- x = (i - w*(h-1)) / h;
- y = (i - w*(h-1)) % h;
- dx = 1;
- dy = 0;
- }
- if (retlen + 10 >= retsize) {
- retsize = retlen + 256;
- ret = sresize(ret, retsize, char);
- }
- v = (map[y*w+x] != map[(y+dy)*w+(x+dx)]);
- if (pv != v) {
- ret[retlen++] = 'a'-1 + run;
- run = 1;
- pv = v;
- } else {
- /*
- * 'z' is a special case in this encoding. Rather
- * than meaning a run of 26 and a state switch, it
- * means a run of 25 and _no_ state switch, because
- * otherwise there'd be no way to encode runs of
- * more than 26.
- */
- if (run == 25) {
- ret[retlen++] = 'z';
- run = 0;
- }
- run++;
- }
- }
- if (retlen + 10 >= retsize) {
- retsize = retlen + 256;
- ret = sresize(ret, retsize, char);
- }
- ret[retlen++] = 'a'-1 + run;
- ret[retlen++] = ',';
- run = 0;
- for (i = 0; i < n; i++) {
- if (retlen + 10 >= retsize) {
- retsize = retlen + 256;
- ret = sresize(ret, retsize, char);
- }
- if (colouring[i] < 0) {
- /*
- * In _this_ encoding, 'z' is a run of 26, since
- * there's no implicit state switch after each run.
- * Confusingly different, but more compact.
- */
- if (run == 26) {
- ret[retlen++] = 'z';
- run = 0;
- }
- run++;
- } else {
- if (run > 0)
- ret[retlen++] = 'a'-1 + run;
- ret[retlen++] = '0' + colouring[i];
- run = 0;
- }
- }
- if (run > 0)
- ret[retlen++] = 'a'-1 + run;
- ret[retlen] = '\0';
- assert(retlen < retsize);
- }
- free_scratch(sc);
- sfree(regions);
- sfree(colouring2);
- sfree(colouring);
- sfree(graph);
- sfree(map);
- return ret;
- }
- static const char *parse_edge_list(const game_params *params,
- const char **desc, int *map)
- {
- int w = params->w, h = params->h, wh = w*h, n = params->n;
- int i, k, pos;
- bool state;
- const char *p = *desc;
- const char *err = NULL;
- DSF *dsf = dsf_new(wh);
- pos = -1;
- state = false;
- /*
- * Parse the game description to get the list of edges, and
- * build up a disjoint set forest as we go (by identifying
- * pairs of squares whenever the edge list shows a non-edge).
- */
- while (*p && *p != ',') {
- if (*p < 'a' || *p > 'z') {
- err = "Unexpected character in edge list";
- goto out;
- }
- if (*p == 'z')
- k = 25;
- else
- k = *p - 'a' + 1;
- while (k-- > 0) {
- int x, y, dx, dy;
- if (pos < 0) {
- pos++;
- continue;
- } else if (pos < w*(h-1)) {
- /* Horizontal edge. */
- y = pos / w;
- x = pos % w;
- dx = 0;
- dy = 1;
- } else if (pos < 2*wh-w-h) {
- /* Vertical edge. */
- x = (pos - w*(h-1)) / h;
- y = (pos - w*(h-1)) % h;
- dx = 1;
- dy = 0;
- } else {
- err = "Too much data in edge list";
- goto out;
- }
- if (!state)
- dsf_merge(dsf, y*w+x, (y+dy)*w+(x+dx));
- pos++;
- }
- if (*p != 'z')
- state = !state;
- p++;
- }
- assert(pos <= 2*wh-w-h);
- if (pos < 2*wh-w-h) {
- err = "Too little data in edge list";
- goto out;
- }
- /*
- * Now go through again and allocate region numbers.
- */
- pos = 0;
- for (i = 0; i < wh; i++)
- map[i] = -1;
- for (i = 0; i < wh; i++) {
- k = dsf_canonify(dsf, i);
- if (map[k] < 0)
- map[k] = pos++;
- map[i] = map[k];
- }
- if (pos != n) {
- err = "Edge list defines the wrong number of regions";
- goto out;
- }
- *desc = p;
- err = NULL; /* no error */
- out:
- dsf_free(dsf);
- return err;
- }
- static const char *validate_desc(const game_params *params, const char *desc)
- {
- int w = params->w, h = params->h, wh = w*h, n = params->n;
- int area;
- int *map;
- const char *ret;
- map = snewn(wh, int);
- ret = parse_edge_list(params, &desc, map);
- sfree(map);
- if (ret)
- return ret;
- if (*desc != ',')
- return "Expected comma before clue list";
- desc++; /* eat comma */
- area = 0;
- while (*desc) {
- if (*desc >= '0' && *desc < '0'+FOUR)
- area++;
- else if (*desc >= 'a' && *desc <= 'z')
- area += *desc - 'a' + 1;
- else
- return "Unexpected character in clue list";
- desc++;
- }
- if (area < n)
- return "Too little data in clue list";
- else if (area > n)
- return "Too much data in clue list";
- return NULL;
- }
- static game_state *new_game(midend *me, const game_params *params,
- const char *desc)
- {
- int w = params->w, h = params->h, wh = w*h, n = params->n;
- int i, pos;
- const char *p;
- game_state *state = snew(game_state);
- state->p = *params;
- state->colouring = snewn(n, int);
- for (i = 0; i < n; i++)
- state->colouring[i] = -1;
- state->pencil = snewn(n, int);
- for (i = 0; i < n; i++)
- state->pencil[i] = 0;
- state->completed = false;
- state->cheated = false;
- state->map = snew(struct map);
- state->map->refcount = 1;
- state->map->map = snewn(wh*4, int);
- state->map->graph = snewn(n*n, int);
- state->map->n = n;
- state->map->immutable = snewn(n, bool);
- for (i = 0; i < n; i++)
- state->map->immutable[i] = false;
- p = desc;
- {
- const char *ret;
- ret = parse_edge_list(params, &p, state->map->map);
- assert(!ret);
- }
- /*
- * Set up the other three quadrants in `map'.
- */
- for (i = wh; i < 4*wh; i++)
- state->map->map[i] = state->map->map[i % wh];
- assert(*p == ',');
- p++;
- /*
- * Now process the clue list.
- */
- pos = 0;
- while (*p) {
- if (*p >= '0' && *p < '0'+FOUR) {
- state->colouring[pos] = *p - '0';
- state->map->immutable[pos] = true;
- pos++;
- } else {
- assert(*p >= 'a' && *p <= 'z');
- pos += *p - 'a' + 1;
- }
- p++;
- }
- assert(pos == n);
- state->map->ngraph = gengraph(w, h, n, state->map->map, state->map->graph);
- /*
- * Attempt to smooth out some of the more jagged region
- * outlines by the judicious use of diagonally divided squares.
- */
- {
- random_state *rs = random_new(desc, strlen(desc));
- int *squares = snewn(wh, int);
- bool done_something;
- for (i = 0; i < wh; i++)
- squares[i] = i;
- shuffle(squares, wh, sizeof(*squares), rs);
- do {
- done_something = false;
- for (i = 0; i < wh; i++) {
- int y = squares[i] / w, x = squares[i] % w;
- int c = state->map->map[y*w+x];
- int tc, bc, lc, rc;
- if (x == 0 || x == w-1 || y == 0 || y == h-1)
- continue;
- if (state->map->map[TE * wh + y*w+x] !=
- state->map->map[BE * wh + y*w+x])
- continue;
- tc = state->map->map[BE * wh + (y-1)*w+x];
- bc = state->map->map[TE * wh + (y+1)*w+x];
- lc = state->map->map[RE * wh + y*w+(x-1)];
- rc = state->map->map[LE * wh + y*w+(x+1)];
- /*
- * If this square is adjacent on two sides to one
- * region and on the other two sides to the other
- * region, and is itself one of the two regions, we can
- * adjust it so that it's a diagonal.
- */
- if (tc != bc && (tc == c || bc == c)) {
- if ((lc == tc && rc == bc) ||
- (lc == bc && rc == tc)) {
- state->map->map[TE * wh + y*w+x] = tc;
- state->map->map[BE * wh + y*w+x] = bc;
- state->map->map[LE * wh + y*w+x] = lc;
- state->map->map[RE * wh + y*w+x] = rc;
- done_something = true;
- }
- }
- }
- } while (done_something);
- sfree(squares);
- random_free(rs);
- }
- /*
- * Analyse the map to find a canonical line segment
- * corresponding to each edge, and a canonical point
- * corresponding to each region. The former are where we'll
- * eventually put error markers; the latter are where we'll put
- * per-region flags such as numbers (when in diagnostic mode).
- */
- {
- int *bestx, *besty, *an, pass;
- float *ax, *ay, *best;
- ax = snewn(state->map->ngraph + n, float);
- ay = snewn(state->map->ngraph + n, float);
- an = snewn(state->map->ngraph + n, int);
- bestx = snewn(state->map->ngraph + n, int);
- besty = snewn(state->map->ngraph + n, int);
- best = snewn(state->map->ngraph + n, float);
- for (i = 0; i < state->map->ngraph + n; i++) {
- bestx[i] = besty[i] = -1;
- best[i] = (float)(2*(w+h)+1);
- ax[i] = ay[i] = 0.0F;
- an[i] = 0;
- }
- /*
- * We make two passes over the map, finding all the line
- * segments separating regions and all the suitable points
- * within regions. In the first pass, we compute the
- * _average_ x and y coordinate of all the points in a
- * given class; in the second pass, for each such average
- * point, we find the candidate closest to it and call that
- * canonical.
- *
- * Line segments are considered to have coordinates in
- * their centre. Thus, at least one coordinate for any line
- * segment is always something-and-a-half; so we store our
- * coordinates as twice their normal value.
- */
- for (pass = 0; pass < 2; pass++) {
- int x, y;
- for (y = 0; y < h; y++)
- for (x = 0; x < w; x++) {
- int ex[4], ey[4], ea[4], eb[4], en = 0;
- /*
- * Look for an edge to the right of this
- * square, an edge below it, and an edge in the
- * middle of it. Also look to see if the point
- * at the bottom right of this square is on an
- * edge (and isn't a place where more than two
- * regions meet).
- */
- if (x+1 < w) {
- /* right edge */
- ea[en] = state->map->map[RE * wh + y*w+x];
- eb[en] = state->map->map[LE * wh + y*w+(x+1)];
- ex[en] = (x+1)*2;
- ey[en] = y*2+1;
- en++;
- }
- if (y+1 < h) {
- /* bottom edge */
- ea[en] = state->map->map[BE * wh + y*w+x];
- eb[en] = state->map->map[TE * wh + (y+1)*w+x];
- ex[en] = x*2+1;
- ey[en] = (y+1)*2;
- en++;
- }
- /* diagonal edge */
- ea[en] = state->map->map[TE * wh + y*w+x];
- eb[en] = state->map->map[BE * wh + y*w+x];
- ex[en] = x*2+1;
- ey[en] = y*2+1;
- en++;
- if (x+1 < w && y+1 < h) {
- /* bottom right corner */
- int oct[8], othercol, nchanges;
- oct[0] = state->map->map[RE * wh + y*w+x];
- oct[1] = state->map->map[LE * wh + y*w+(x+1)];
- oct[2] = state->map->map[BE * wh + y*w+(x+1)];
- oct[3] = state->map->map[TE * wh + (y+1)*w+(x+1)];
- oct[4] = state->map->map[LE * wh + (y+1)*w+(x+1)];
- oct[5] = state->map->map[RE * wh + (y+1)*w+x];
- oct[6] = state->map->map[TE * wh + (y+1)*w+x];
- oct[7] = state->map->map[BE * wh + y*w+x];
- othercol = -1;
- nchanges = 0;
- for (i = 0; i < 8; i++) {
- if (oct[i] != oct[0]) {
- if (othercol < 0)
- othercol = oct[i];
- else if (othercol != oct[i])
- break; /* three colours at this point */
- }
- if (oct[i] != oct[(i+1) & 7])
- nchanges++;
- }
- /*
- * Now if there are exactly two regions at
- * this point (not one, and not three or
- * more), and only two changes around the
- * loop, then this is a valid place to put
- * an error marker.
- */
- if (i == 8 && othercol >= 0 && nchanges == 2) {
- ea[en] = oct[0];
- eb[en] = othercol;
- ex[en] = (x+1)*2;
- ey[en] = (y+1)*2;
- en++;
- }
- /*
- * If there's exactly _one_ region at this
- * point, on the other hand, it's a valid
- * place to put a region centre.
- */
- if (othercol < 0) {
- ea[en] = eb[en] = oct[0];
- ex[en] = (x+1)*2;
- ey[en] = (y+1)*2;
- en++;
- }
- }
- /*
- * Now process the points we've found, one by
- * one.
- */
- for (i = 0; i < en; i++) {
- int emin = min(ea[i], eb[i]);
- int emax = max(ea[i], eb[i]);
- int gindex;
- if (emin != emax) {
- /* Graph edge */
- gindex =
- graph_edge_index(state->map->graph, n,
- state->map->ngraph, emin,
- emax);
- } else {
- /* Region number */
- gindex = state->map->ngraph + emin;
- }
- assert(gindex >= 0);
- if (pass == 0) {
- /*
- * In pass 0, accumulate the values
- * we'll use to compute the average
- * positions.
- */
- ax[gindex] += ex[i];
- ay[gindex] += ey[i];
- an[gindex] += 1;
- } else {
- /*
- * In pass 1, work out whether this
- * point is closer to the average than
- * the last one we've seen.
- */
- float dx, dy, d;
- assert(an[gindex] > 0);
- dx = ex[i] - ax[gindex];
- dy = ey[i] - ay[gindex];
- d = (float)sqrt(dx*dx + dy*dy);
- if (d < best[gindex]) {
- best[gindex] = d;
- bestx[gindex] = ex[i];
- besty[gindex] = ey[i];
- }
- }
- }
- }
- if (pass == 0) {
- for (i = 0; i < state->map->ngraph + n; i++)
- if (an[i] > 0) {
- ax[i] /= an[i];
- ay[i] /= an[i];
- }
- }
- }
- state->map->edgex = snewn(state->map->ngraph, int);
- state->map->edgey = snewn(state->map->ngraph, int);
- memcpy(state->map->edgex, bestx, state->map->ngraph * sizeof(int));
- memcpy(state->map->edgey, besty, state->map->ngraph * sizeof(int));
- state->map->regionx = snewn(n, int);
- state->map->regiony = snewn(n, int);
- memcpy(state->map->regionx, bestx + state->map->ngraph, n*sizeof(int));
- memcpy(state->map->regiony, besty + state->map->ngraph, n*sizeof(int));
- for (i = 0; i < state->map->ngraph; i++)
- if (state->map->edgex[i] < 0) {
- /* Find the other representation of this edge. */
- int e = state->map->graph[i];
- int iprime = graph_edge_index(state->map->graph, n,
- state->map->ngraph, e%n, e/n);
- assert(state->map->edgex[iprime] >= 0);
- state->map->edgex[i] = state->map->edgex[iprime];
- state->map->edgey[i] = state->map->edgey[iprime];
- }
- sfree(ax);
- sfree(ay);
- sfree(an);
- sfree(best);
- sfree(bestx);
- sfree(besty);
- }
- return state;
- }
- static game_state *dup_game(const game_state *state)
- {
- game_state *ret = snew(game_state);
- ret->p = state->p;
- ret->colouring = snewn(state->p.n, int);
- memcpy(ret->colouring, state->colouring, state->p.n * sizeof(int));
- ret->pencil = snewn(state->p.n, int);
- memcpy(ret->pencil, state->pencil, state->p.n * sizeof(int));
- ret->map = state->map;
- ret->map->refcount++;
- ret->completed = state->completed;
- ret->cheated = state->cheated;
- return ret;
- }
- static void free_game(game_state *state)
- {
- if (--state->map->refcount <= 0) {
- sfree(state->map->map);
- sfree(state->map->graph);
- sfree(state->map->immutable);
- sfree(state->map->edgex);
- sfree(state->map->edgey);
- sfree(state->map->regionx);
- sfree(state->map->regiony);
- sfree(state->map);
- }
- sfree(state->pencil);
- sfree(state->colouring);
- sfree(state);
- }
- static char *solve_game(const game_state *state, const game_state *currstate,
- const char *aux, const char **error)
- {
- if (!aux) {
- /*
- * Use the solver.
- */
- int *colouring;
- struct solver_scratch *sc;
- int sret;
- int i;
- char *ret, buf[80];
- int retlen, retsize;
- colouring = snewn(state->map->n, int);
- memcpy(colouring, state->colouring, state->map->n * sizeof(int));
- sc = new_scratch(state->map->graph, state->map->n, state->map->ngraph);
- sret = map_solver(sc, state->map->graph, state->map->n,
- state->map->ngraph, colouring, DIFFCOUNT-1);
- free_scratch(sc);
- if (sret != 1) {
- sfree(colouring);
- if (sret == 0)
- *error = "Puzzle is inconsistent";
- else
- *error = "Unable to find a unique solution for this puzzle";
- return NULL;
- }
- retsize = 64;
- ret = snewn(retsize, char);
- strcpy(ret, "S");
- retlen = 1;
- for (i = 0; i < state->map->n; i++) {
- int len;
- assert(colouring[i] >= 0);
- if (colouring[i] == currstate->colouring[i])
- continue;
- assert(!state->map->immutable[i]);
- len = sprintf(buf, ";%d:%d", colouring[i], i);
- if (retlen + len >= retsize) {
- retsize = retlen + len + 256;
- ret = sresize(ret, retsize, char);
- }
- strcpy(ret + retlen, buf);
- retlen += len;
- }
- sfree(colouring);
- return ret;
- }
- return dupstr(aux);
- }
- struct game_ui {
- /*
- * drag_colour:
- *
- * - -2 means no drag currently active.
- * - >=0 means we're dragging a solid colour.
- * - -1 means we're dragging a blank space, and drag_pencil
- * might or might not add some pencil-mark stipples to that.
- */
- int drag_colour;
- int drag_pencil;
- int dragx, dragy;
- bool show_numbers;
- int cur_x, cur_y, cur_lastmove;
- bool cur_visible, cur_moved;
- /*
- * User preference to enable alternative versions of the
- * completion flash. Some users have found the colour-cycling
- * default version to be a bit eye-twisting.
- */
- enum {
- FLASH_CYCLIC, /* cycle the four colours of the map */
- FLASH_EACH_TO_WHITE, /* turn each colour white in turn */
- FLASH_ALL_TO_WHITE /* flash the whole map to white in one go */
- } flash_type;
- };
- static void legacy_prefs_override(struct game_ui *ui_out)
- {
- static bool initialised = false;
- static int flash_type = -1;
- if (!initialised) {
- char *env;
- initialised = true;
- if ((env = getenv("MAP_ALTERNATIVE_FLASH")) != NULL)
- flash_type = FLASH_EACH_TO_WHITE;
- }
- if (flash_type != -1)
- ui_out->flash_type = flash_type;
- }
- static game_ui *new_ui(const game_state *state)
- {
- game_ui *ui = snew(game_ui);
- ui->dragx = ui->dragy = -1;
- ui->drag_colour = -2;
- ui->drag_pencil = 0;
- ui->show_numbers = false;
- ui->cur_x = ui->cur_y = 0;
- ui->cur_visible = getenv_bool("PUZZLES_SHOW_CURSOR", false);
- ui->cur_moved = false;
- ui->cur_lastmove = 0;
- ui->flash_type = FLASH_CYCLIC;
- legacy_prefs_override(ui);
- return ui;
- }
- static config_item *get_prefs(game_ui *ui)
- {
- config_item *ret;
- ret = snewn(3, config_item);
- ret[0].name = "Victory flash effect";
- ret[0].kw = "flash-type";
- ret[0].type = C_CHOICES;
- ret[0].u.choices.choicenames = ":Cyclic:Each to white:All to white";
- ret[0].u.choices.choicekws = ":cyclic:each-white:all-white";
- ret[0].u.choices.selected = ui->flash_type;
- ret[1].name = "Number regions";
- ret[1].kw = "show-numbers";
- ret[1].type = C_BOOLEAN;
- ret[1].u.boolean.bval = ui->show_numbers;
- ret[2].name = NULL;
- ret[2].type = C_END;
- return ret;
- }
- static void set_prefs(game_ui *ui, const config_item *cfg)
- {
- ui->flash_type = cfg[0].u.choices.selected;
- ui->show_numbers = cfg[1].u.boolean.bval;
- }
- 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)
- {
- }
- struct game_drawstate {
- int tilesize;
- unsigned long *drawn, *todraw;
- bool started;
- int dragx, dragy;
- bool drag_visible;
- blitter *bl;
- };
- /* Flags in `drawn'. */
- #define ERR_BASE 0x00800000L
- #define ERR_MASK 0xFF800000L
- #define PENCIL_T_BASE 0x00080000L
- #define PENCIL_T_MASK 0x00780000L
- #define PENCIL_B_BASE 0x00008000L
- #define PENCIL_B_MASK 0x00078000L
- #define PENCIL_MASK 0x007F8000L
- #define SHOW_NUMBERS 0x00004000L
- #define TILESIZE (ds->tilesize)
- #define BORDER (TILESIZE)
- #define COORD(x) ( (x) * TILESIZE + BORDER )
- #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
- /*
- * EPSILON_FOO are epsilons added to absolute cursor position by
- * cursor movement, such that in pathological cases (e.g. a very
- * small diamond-shaped area) it's relatively easy to select the
- * region you wanted.
- */
- #define EPSILON_X(button) (((button) == CURSOR_RIGHT) ? +1 : \
- ((button) == CURSOR_LEFT) ? -1 : 0)
- #define EPSILON_Y(button) (((button) == CURSOR_DOWN) ? +1 : \
- ((button) == CURSOR_UP) ? -1 : 0)
- /*
- * Return the map region containing a point in tile (tx,ty), offset by
- * (x_eps,y_eps) from the centre of the tile.
- */
- static int region_from_logical_coords(const game_state *state, int tx, int ty,
- int x_eps, int y_eps)
- {
- int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */;
- int quadrant;
- if (tx < 0 || tx >= w || ty < 0 || ty >= h)
- return -1; /* border */
- quadrant = 2 * (x_eps > y_eps) + (-x_eps > y_eps);
- quadrant = (quadrant == 0 ? BE :
- quadrant == 1 ? LE :
- quadrant == 2 ? RE : TE);
- return state->map->map[quadrant * wh + ty*w+tx];
- }
- static int region_from_coords(const game_state *state,
- const game_drawstate *ds, int x, int y)
- {
- int tx = FROMCOORD(x), ty = FROMCOORD(y);
- return region_from_logical_coords(
- state, tx, ty, x - COORD(tx) - TILESIZE/2, y - COORD(ty) - TILESIZE/2);
- }
- static int region_from_ui_cursor(const game_state *state, const game_ui *ui)
- {
- assert(ui->cur_visible);
- return region_from_logical_coords(state, ui->cur_x, ui->cur_y,
- EPSILON_X(ui->cur_lastmove),
- EPSILON_Y(ui->cur_lastmove));
- }
- static const char *current_key_label(const game_ui *ui,
- const game_state *state, int button)
- {
- int r;
- if (IS_CURSOR_SELECT(button) && ui->cur_visible) {
- if (ui->drag_colour == -2) return "Pick";
- r = region_from_ui_cursor(state, ui);
- if (state->map->immutable[r]) return "Cancel";
- if (!ui->cur_moved) return ui->drag_pencil ? "Cancel" : "Clear";
- if (button == CURSOR_SELECT2) {
- if (state->colouring[r] >= 0) return "Cancel";
- if (ui->drag_colour >= 0) return "Stipple";
- }
- if (ui->drag_pencil) return "Stipple";
- return ui->drag_colour >= 0 ? "Fill" : "Clear";
- }
- return "";
- }
- static char *interpret_move(const game_state *state, game_ui *ui,
- const game_drawstate *ds,
- int x, int y, int button)
- {
- char *bufp, buf[256];
- bool alt_button;
- int drop_region;
- /*
- * Enable or disable numeric labels on regions.
- */
- if (button == 'l' || button == 'L') {
- ui->show_numbers = !ui->show_numbers;
- return MOVE_UI_UPDATE;
- }
- if (IS_CURSOR_MOVE(button)) {
- move_cursor(button, &ui->cur_x, &ui->cur_y, state->p.w, state->p.h,
- false);
- ui->cur_visible = true;
- ui->cur_moved = true;
- ui->cur_lastmove = button;
- return MOVE_UI_UPDATE;
- }
- if (IS_CURSOR_SELECT(button)) {
- if (!ui->cur_visible) {
- ui->cur_visible = true;
- return MOVE_UI_UPDATE;
- }
- if (ui->drag_colour == -2) { /* not currently cursor-dragging, start. */
- int r = region_from_ui_cursor(state, ui);
- if (r >= 0) {
- ui->drag_colour = state->colouring[r];
- ui->drag_pencil = (ui->drag_colour >= 0) ? 0 : state->pencil[r];
- } else {
- ui->drag_colour = -1;
- ui->drag_pencil = 0;
- }
- ui->cur_moved = false;
- return MOVE_UI_UPDATE;
- } else { /* currently cursor-dragging; drop the colour in the new region. */
- alt_button = (button == CURSOR_SELECT2);
- /* Double-select removes current colour. */
- if (!ui->cur_moved) ui->drag_colour = -1;
- drop_region = region_from_ui_cursor(state, ui);
- goto drag_dropped;
- }
- }
- if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
- int r = region_from_coords(state, ds, x, y);
- if (r >= 0) {
- ui->drag_colour = state->colouring[r];
- ui->drag_pencil = state->pencil[r];
- if (ui->drag_colour >= 0)
- ui->drag_pencil = 0; /* should be already, but double-check */
- } else {
- ui->drag_colour = -1;
- ui->drag_pencil = 0;
- }
- ui->dragx = x;
- ui->dragy = y;
- ui->cur_visible = false;
- return MOVE_UI_UPDATE;
- }
- if ((button == LEFT_DRAG || button == RIGHT_DRAG) &&
- ui->drag_colour > -2) {
- ui->dragx = x;
- ui->dragy = y;
- return MOVE_UI_UPDATE;
- }
- if ((button == LEFT_RELEASE || button == RIGHT_RELEASE) &&
- ui->drag_colour > -2) {
- alt_button = (button == RIGHT_RELEASE);
- drop_region = region_from_coords(state, ds, x, y);
- goto drag_dropped;
- }
- return NULL;
- drag_dropped:
- {
- int r = drop_region;
- int c = ui->drag_colour;
- int p = ui->drag_pencil;
- int oldp;
- /*
- * Cancel the drag, whatever happens.
- */
- ui->drag_colour = -2;
- if (r < 0)
- return MOVE_UI_UPDATE; /* drag into border; do nothing else */
- if (state->map->immutable[r])
- return MOVE_UI_UPDATE; /* can't change this region */
- if (state->colouring[r] == c && state->pencil[r] == p)
- return MOVE_UI_UPDATE; /* don't _need_ to change this region */
- if (alt_button) {
- if (state->colouring[r] >= 0) {
- /* Can't pencil on a coloured region */
- return MOVE_UI_UPDATE;
- } else if (c >= 0) {
- /* Right-dragging from colour to blank toggles one pencil */
- p = state->pencil[r] ^ (1 << c);
- c = -1;
- }
- /* Otherwise, right-dragging from blank to blank is equivalent
- * to left-dragging. */
- }
- bufp = buf;
- oldp = state->pencil[r];
- if (c != state->colouring[r]) {
- bufp += sprintf(bufp, ";%c:%d", (int)(c < 0 ? 'C' : '0' + c), r);
- if (c >= 0)
- oldp = 0;
- }
- if (p != oldp) {
- int i;
- for (i = 0; i < FOUR; i++)
- if ((oldp ^ p) & (1 << i))
- bufp += sprintf(bufp, ";p%c:%d", (int)('0' + i), r);
- }
- return dupstr(buf+1); /* ignore first semicolon */
- }
- }
- static game_state *execute_move(const game_state *state, const char *move)
- {
- int n = state->p.n;
- game_state *ret = dup_game(state);
- int c, k, adv, i;
- while (*move) {
- bool pencil = false;
- c = *move;
- if (c == 'p') {
- pencil = true;
- c = *++move;
- }
- if ((c == 'C' || (c >= '0' && c < '0'+FOUR)) &&
- sscanf(move+1, ":%d%n", &k, &adv) == 1 &&
- k >= 0 && k < state->p.n) {
- move += 1 + adv;
- if (pencil) {
- if (ret->colouring[k] >= 0) {
- free_game(ret);
- return NULL;
- }
- if (c == 'C')
- ret->pencil[k] = 0;
- else
- ret->pencil[k] ^= 1 << (c - '0');
- } else {
- ret->colouring[k] = (c == 'C' ? -1 : c - '0');
- ret->pencil[k] = 0;
- }
- } else if (*move == 'S') {
- move++;
- ret->cheated = true;
- } else {
- free_game(ret);
- return NULL;
- }
- if (*move && *move != ';') {
- free_game(ret);
- return NULL;
- }
- if (*move)
- move++;
- }
- /*
- * Check for completion.
- */
- if (!ret->completed) {
- bool ok = true;
- for (i = 0; i < n; i++)
- if (ret->colouring[i] < 0) {
- ok = false;
- break;
- }
- if (ok) {
- for (i = 0; i < ret->map->ngraph; i++) {
- int j = ret->map->graph[i] / n;
- int k = ret->map->graph[i] % n;
- if (ret->colouring[j] == ret->colouring[k]) {
- ok = false;
- break;
- }
- }
- }
- if (ok)
- ret->completed = true;
- }
- return ret;
- }
- /* ----------------------------------------------------------------------
- * Drawing routines.
- */
- static void game_compute_size(const game_params *params, int tilesize,
- const game_ui *ui, int *x, int *y)
- {
- /* Ick: fake up `ds->tilesize' for macro expansion purposes */
- struct { int tilesize; } ads, *ds = &ads;
- ads.tilesize = tilesize;
- *x = params->w * TILESIZE + 2 * BORDER + 1;
- *y = params->h * TILESIZE + 2 * BORDER + 1;
- }
- static void game_set_size(drawing *dr, game_drawstate *ds,
- const game_params *params, int tilesize)
- {
- ds->tilesize = tilesize;
- assert(!ds->bl); /* set_size is never called twice */
- ds->bl = blitter_new(dr, TILESIZE+3, TILESIZE+3);
- }
- static const float map_colours[FOUR][3] = {
- #ifdef VIVID_COLOURS
- /* Use more vivid colours (e.g. on the Pocket PC) */
- {0.75F, 0.25F, 0.25F},
- {0.3F, 0.7F, 0.3F},
- {0.3F, 0.3F, 0.7F},
- {0.85F, 0.85F, 0.1F},
- #else
- {0.7F, 0.5F, 0.4F},
- {0.8F, 0.7F, 0.4F},
- {0.5F, 0.6F, 0.4F},
- {0.55F, 0.45F, 0.35F},
- #endif
- };
- static const int map_hatching[FOUR] = {
- HATCH_VERT, HATCH_SLASH, HATCH_HORIZ, HATCH_BACKSLASH
- };
- static float *game_colours(frontend *fe, int *ncolours)
- {
- float *ret = snewn(3 * NCOLOURS, float);
- frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
- ret[COL_GRID * 3 + 0] = 0.0F;
- ret[COL_GRID * 3 + 1] = 0.0F;
- ret[COL_GRID * 3 + 2] = 0.0F;
- memcpy(ret + COL_0 * 3, map_colours[0], 3 * sizeof(float));
- memcpy(ret + COL_1 * 3, map_colours[1], 3 * sizeof(float));
- memcpy(ret + COL_2 * 3, map_colours[2], 3 * sizeof(float));
- memcpy(ret + COL_3 * 3, map_colours[3], 3 * sizeof(float));
- ret[COL_ERROR * 3 + 0] = 1.0F;
- ret[COL_ERROR * 3 + 1] = 0.0F;
- ret[COL_ERROR * 3 + 2] = 0.0F;
- ret[COL_ERRTEXT * 3 + 0] = 1.0F;
- ret[COL_ERRTEXT * 3 + 1] = 1.0F;
- ret[COL_ERRTEXT * 3 + 2] = 1.0F;
- *ncolours = NCOLOURS;
- return ret;
- }
- static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
- {
- struct game_drawstate *ds = snew(struct game_drawstate);
- int i;
- ds->tilesize = 0;
- ds->drawn = snewn(state->p.w * state->p.h, unsigned long);
- for (i = 0; i < state->p.w * state->p.h; i++)
- ds->drawn[i] = 0xFFFFL;
- ds->todraw = snewn(state->p.w * state->p.h, unsigned long);
- ds->started = false;
- ds->bl = NULL;
- ds->drag_visible = false;
- ds->dragx = ds->dragy = -1;
- return ds;
- }
- static void game_free_drawstate(drawing *dr, game_drawstate *ds)
- {
- sfree(ds->drawn);
- sfree(ds->todraw);
- if (ds->bl)
- blitter_free(dr, ds->bl);
- sfree(ds);
- }
- static void draw_error(drawing *dr, game_drawstate *ds, int x, int y)
- {
- int coords[8];
- int yext, xext;
- /*
- * Draw a diamond.
- */
- coords[0] = x - TILESIZE*2/5;
- coords[1] = y;
- coords[2] = x;
- coords[3] = y - TILESIZE*2/5;
- coords[4] = x + TILESIZE*2/5;
- coords[5] = y;
- coords[6] = x;
- coords[7] = y + TILESIZE*2/5;
- draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID);
- /*
- * Draw an exclamation mark in the diamond. This turns out to
- * look unpleasantly off-centre if done via draw_text, so I do
- * it by hand on the basis that exclamation marks aren't that
- * difficult to draw...
- */
- xext = TILESIZE/16;
- yext = TILESIZE*2/5 - (xext*2+2);
- draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3),
- COL_ERRTEXT);
- draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT);
- }
- static void draw_square(drawing *dr, game_drawstate *ds,
- const game_params *params, struct map *map,
- int x, int y, unsigned long v)
- {
- int w = params->w, h = params->h, wh = w*h;
- int tv, bv, xo, yo, i, j, oldj;
- unsigned long errs, pencil, show_numbers;
- errs = v & ERR_MASK;
- v &= ~ERR_MASK;
- pencil = v & PENCIL_MASK;
- v &= ~PENCIL_MASK;
- show_numbers = v & SHOW_NUMBERS;
- v &= ~SHOW_NUMBERS;
- tv = v / FIVE;
- bv = v % FIVE;
- clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
- /*
- * Draw the region colour.
- */
- draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE,
- (tv == FOUR ? COL_BACKGROUND : COL_0 + tv));
- /*
- * Draw the second region colour, if this is a diagonally
- * divided square.
- */
- if (map->map[TE * wh + y*w+x] != map->map[BE * wh + y*w+x]) {
- int coords[6];
- coords[0] = COORD(x)-1;
- coords[1] = COORD(y+1)+1;
- if (map->map[LE * wh + y*w+x] == map->map[TE * wh + y*w+x])
- coords[2] = COORD(x+1)+1;
- else
- coords[2] = COORD(x)-1;
- coords[3] = COORD(y)-1;
- coords[4] = COORD(x+1)+1;
- coords[5] = COORD(y+1)+1;
- draw_polygon(dr, coords, 3,
- (bv == FOUR ? COL_BACKGROUND : COL_0 + bv), COL_GRID);
- }
- /*
- * Draw `pencil marks'. Currently we arrange these in a square
- * formation, which means we may be in trouble if the value of
- * FOUR changes later...
- */
- assert(FOUR == 4);
- for (yo = 0; yo < 4; yo++)
- for (xo = 0; xo < 4; xo++) {
- int te = map->map[TE * wh + y*w+x];
- int e, ee, c;
- e = (yo < xo && yo < 3-xo ? TE :
- yo > xo && yo > 3-xo ? BE :
- xo < 2 ? LE : RE);
- ee = map->map[e * wh + y*w+x];
- if (xo != (yo * 2 + 1) % 5)
- continue;
- c = yo;
- if (!(pencil & ((ee == te ? PENCIL_T_BASE : PENCIL_B_BASE) << c)))
- continue;
- if (yo == xo &&
- (map->map[TE * wh + y*w+x] != map->map[LE * wh + y*w+x]))
- continue; /* avoid TL-BR diagonal line */
- if (yo == 3-xo &&
- (map->map[TE * wh + y*w+x] != map->map[RE * wh + y*w+x]))
- continue; /* avoid BL-TR diagonal line */
- draw_circle(dr, COORD(x) + (xo+1)*TILESIZE/5,
- COORD(y) + (yo+1)*TILESIZE/5,
- TILESIZE/7, COL_0 + c, COL_0 + c);
- }
- /*
- * Draw the grid lines, if required.
- */
- if (x <= 0 || map->map[RE*wh+y*w+(x-1)] != map->map[LE*wh+y*w+x])
- draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE, COL_GRID);
- if (y <= 0 || map->map[BE*wh+(y-1)*w+x] != map->map[TE*wh+y*w+x])
- draw_rect(dr, COORD(x), COORD(y), TILESIZE, 1, COL_GRID);
- if (x <= 0 || y <= 0 ||
- map->map[RE*wh+(y-1)*w+(x-1)] != map->map[TE*wh+y*w+x] ||
- map->map[BE*wh+(y-1)*w+(x-1)] != map->map[LE*wh+y*w+x])
- draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID);
- /*
- * Draw error markers.
- */
- for (yo = 0; yo < 3; yo++)
- for (xo = 0; xo < 3; xo++)
- if (errs & (ERR_BASE << (yo*3+xo)))
- draw_error(dr, ds,
- (COORD(x)*2+TILESIZE*xo)/2,
- (COORD(y)*2+TILESIZE*yo)/2);
- /*
- * Draw region numbers, if desired.
- */
- if (show_numbers) {
- oldj = -1;
- for (i = 0; i < 2; i++) {
- j = map->map[(i?BE:TE)*wh+y*w+x];
- if (oldj == j)
- continue;
- oldj = j;
- xo = map->regionx[j] - 2*x;
- yo = map->regiony[j] - 2*y;
- if (xo >= 0 && xo <= 2 && yo >= 0 && yo <= 2) {
- char buf[80];
- sprintf(buf, "%d", j);
- draw_text(dr, (COORD(x)*2+TILESIZE*xo)/2,
- (COORD(y)*2+TILESIZE*yo)/2,
- FONT_VARIABLE, 3*TILESIZE/5,
- ALIGN_HCENTRE|ALIGN_VCENTRE,
- COL_GRID, buf);
- }
- }
- }
- unclip(dr);
- draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
- }
- static float flash_length(const game_ui *ui)
- {
- return (ui->flash_type == FLASH_EACH_TO_WHITE ? 0.50F : 0.30F);
- }
- 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 w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
- int x, y, i;
- int flash;
- if (ds->drag_visible) {
- blitter_load(dr, ds->bl, ds->dragx, ds->dragy);
- draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
- ds->drag_visible = false;
- }
- if (!ds->started) {
- draw_rect(dr, COORD(0), COORD(0), w*TILESIZE+1, h*TILESIZE+1,
- COL_GRID);
- draw_update(dr, COORD(0), COORD(0), w*TILESIZE+1, h*TILESIZE+1);
- ds->started = true;
- }
- if (flashtime) {
- if (ui->flash_type == FLASH_EACH_TO_WHITE)
- flash = (int)(flashtime * FOUR / flash_length(ui));
- else
- flash = 1 + (int)(flashtime * THREE / flash_length(ui));
- } else
- flash = -1;
- /*
- * Set up the `todraw' array.
- */
- for (y = 0; y < h; y++)
- for (x = 0; x < w; x++) {
- int tv = state->colouring[state->map->map[TE * wh + y*w+x]];
- int bv = state->colouring[state->map->map[BE * wh + y*w+x]];
- unsigned long v;
- if (tv < 0)
- tv = FOUR;
- if (bv < 0)
- bv = FOUR;
- if (flash >= 0) {
- if (ui->flash_type == FLASH_EACH_TO_WHITE) {
- if (tv == flash)
- tv = FOUR;
- if (bv == flash)
- bv = FOUR;
- } else if (ui->flash_type == FLASH_ALL_TO_WHITE) {
- if (flash % 2)
- tv = bv = FOUR;
- } else {
- if (tv != FOUR)
- tv = (tv + flash) % FOUR;
- if (bv != FOUR)
- bv = (bv + flash) % FOUR;
- }
- }
- v = tv * FIVE + bv;
- /*
- * Add pencil marks.
- */
- for (i = 0; i < FOUR; i++) {
- if (state->colouring[state->map->map[TE * wh + y*w+x]] < 0 &&
- (state->pencil[state->map->map[TE * wh + y*w+x]] & (1<<i)))
- v |= PENCIL_T_BASE << i;
- if (state->colouring[state->map->map[BE * wh + y*w+x]] < 0 &&
- (state->pencil[state->map->map[BE * wh + y*w+x]] & (1<<i)))
- v |= PENCIL_B_BASE << i;
- }
- if (ui->show_numbers)
- v |= SHOW_NUMBERS;
- ds->todraw[y*w+x] = v;
- }
- /*
- * Add error markers to the `todraw' array.
- */
- for (i = 0; i < state->map->ngraph; i++) {
- int v1 = state->map->graph[i] / n;
- int v2 = state->map->graph[i] % n;
- int xo, yo;
- if (state->colouring[v1] < 0 || state->colouring[v2] < 0)
- continue;
- if (state->colouring[v1] != state->colouring[v2])
- continue;
- x = state->map->edgex[i];
- y = state->map->edgey[i];
- xo = x % 2; x /= 2;
- yo = y % 2; y /= 2;
- ds->todraw[y*w+x] |= ERR_BASE << (yo*3+xo);
- if (xo == 0) {
- assert(x > 0);
- ds->todraw[y*w+(x-1)] |= ERR_BASE << (yo*3+2);
- }
- if (yo == 0) {
- assert(y > 0);
- ds->todraw[(y-1)*w+x] |= ERR_BASE << (2*3+xo);
- }
- if (xo == 0 && yo == 0) {
- assert(x > 0 && y > 0);
- ds->todraw[(y-1)*w+(x-1)] |= ERR_BASE << (2*3+2);
- }
- }
- /*
- * Now actually draw everything.
- */
- for (y = 0; y < h; y++)
- for (x = 0; x < w; x++) {
- unsigned long v = ds->todraw[y*w+x];
- if (ds->drawn[y*w+x] != v) {
- draw_square(dr, ds, &state->p, state->map, x, y, v);
- ds->drawn[y*w+x] = v;
- }
- }
- /*
- * Draw the dragged colour blob if any.
- */
- if ((ui->drag_colour > -2) || ui->cur_visible) {
- int bg, cursor_x, cursor_y;
- bool iscur = false;
- if (ui->drag_colour >= 0)
- bg = COL_0 + ui->drag_colour;
- else if (ui->drag_colour == -1) {
- bg = COL_BACKGROUND;
- } else {
- int r = region_from_ui_cursor(state, ui);
- int c = (r < 0) ? -1 : state->colouring[r];
- /*bg = COL_GRID;*/
- bg = (c < 0) ? COL_BACKGROUND : COL_0 + c;
- iscur = true;
- }
- if (ui->cur_visible) {
- cursor_x = COORD(ui->cur_x) + TILESIZE/2 +
- EPSILON_X(ui->cur_lastmove);
- cursor_y = COORD(ui->cur_y) + TILESIZE/2 +
- EPSILON_Y(ui->cur_lastmove);
- } else {
- cursor_x = ui->dragx;
- cursor_y = ui->dragy;
- }
- ds->dragx = cursor_x - TILESIZE/2 - 2;
- ds->dragy = cursor_y - TILESIZE/2 - 2;
- blitter_save(dr, ds->bl, ds->dragx, ds->dragy);
- draw_circle(dr, cursor_x, cursor_y,
- iscur ? TILESIZE/4 : TILESIZE/2, bg, COL_GRID);
- for (i = 0; i < FOUR; i++)
- if (ui->drag_pencil & (1 << i))
- draw_circle(dr, cursor_x + ((i*4+2)%10-3) * TILESIZE/10,
- cursor_y + (i*2-3) * TILESIZE/10,
- TILESIZE/8, COL_0 + i, COL_0 + i);
- draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
- ds->drag_visible = true;
- }
- }
- 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_length(ui);
- } else
- 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->cur_visible) {
- *x = COORD(ui->cur_x);
- *y = COORD(ui->cur_y);
- *w = *h = TILESIZE;
- }
- }
- 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;
- /*
- * I'll use 4mm squares by default, I think. Simplest way to
- * compute this size is to compute the pixel puzzle size at a
- * given tile size and then scale.
- */
- game_compute_size(params, 400, 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 w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
- int ink, c[FOUR], i;
- int x, y, r;
- int *coords, ncoords, coordsize;
- /* Ick: fake up `ds->tilesize' for macro expansion purposes */
- struct { int tilesize; } ads, *ds = &ads;
- /* We can't call game_set_size() here because we don't want a blitter */
- ads.tilesize = tilesize;
- ink = print_mono_colour(dr, 0);
- for (i = 0; i < FOUR; i++)
- c[i] = print_rgb_hatched_colour(dr, map_colours[i][0],
- map_colours[i][1], map_colours[i][2],
- map_hatching[i]);
- coordsize = 0;
- coords = NULL;
- print_line_width(dr, TILESIZE / 16);
- /*
- * Draw a single filled polygon around each region.
- */
- for (r = 0; r < n; r++) {
- int octants[8], lastdir, d1, d2, ox, oy;
- /*
- * Start by finding a point on the region boundary. Any
- * point will do. To do this, we'll search for a square
- * containing the region and then decide which corner of it
- * to use.
- */
- x = w;
- for (y = 0; y < h; y++) {
- for (x = 0; x < w; x++) {
- if (state->map->map[wh*0+y*w+x] == r ||
- state->map->map[wh*1+y*w+x] == r ||
- state->map->map[wh*2+y*w+x] == r ||
- state->map->map[wh*3+y*w+x] == r)
- break;
- }
- if (x < w)
- break;
- }
- assert(y < h && x < w); /* we must have found one somewhere */
- /*
- * This is the first square in lexicographic order which
- * contains part of this region. Therefore, one of the top
- * two corners of the square must be what we're after. The
- * only case in which it isn't the top left one is if the
- * square is diagonally divided and the region is in the
- * bottom right half.
- */
- if (state->map->map[wh*TE+y*w+x] != r &&
- state->map->map[wh*LE+y*w+x] != r)
- x++; /* could just as well have done y++ */
- /*
- * Now we have a point on the region boundary. Trace around
- * the region until we come back to this point,
- * accumulating coordinates for a polygon draw operation as
- * we go.
- */
- lastdir = -1;
- ox = x;
- oy = y;
- ncoords = 0;
- do {
- /*
- * There are eight possible directions we could head in
- * from here. We identify them by octant numbers, and
- * we also use octant numbers to identify the spaces
- * between them:
- *
- * 6 7 0
- * \ 7|0 /
- * \ | /
- * 6 \|/ 1
- * 5-----+-----1
- * 5 /|\ 2
- * / | \
- * / 4|3 \
- * 4 3 2
- */
- octants[0] = x<w && y>0 ? state->map->map[wh*LE+(y-1)*w+x] : -1;
- octants[1] = x<w && y>0 ? state->map->map[wh*BE+(y-1)*w+x] : -1;
- octants[2] = x<w && y<h ? state->map->map[wh*TE+y*w+x] : -1;
- octants[3] = x<w && y<h ? state->map->map[wh*LE+y*w+x] : -1;
- octants[4] = x>0 && y<h ? state->map->map[wh*RE+y*w+(x-1)] : -1;
- octants[5] = x>0 && y<h ? state->map->map[wh*TE+y*w+(x-1)] : -1;
- octants[6] = x>0 && y>0 ? state->map->map[wh*BE+(y-1)*w+(x-1)] :-1;
- octants[7] = x>0 && y>0 ? state->map->map[wh*RE+(y-1)*w+(x-1)] :-1;
- d1 = d2 = -1;
- for (i = 0; i < 8; i++)
- if ((octants[i] == r) ^ (octants[(i+1)%8] == r)) {
- assert(d2 == -1);
- if (d1 == -1)
- d1 = i;
- else
- d2 = i;
- }
- assert(d1 != -1 && d2 != -1);
- if (d1 == lastdir)
- d1 = d2;
- /*
- * Now we're heading in direction d1. Save the current
- * coordinates.
- */
- if (ncoords + 2 > coordsize) {
- coordsize += 128;
- coords = sresize(coords, coordsize, int);
- }
- coords[ncoords++] = COORD(x);
- coords[ncoords++] = COORD(y);
- /*
- * Compute the new coordinates.
- */
- x += (d1 % 4 == 3 ? 0 : d1 < 4 ? +1 : -1);
- y += (d1 % 4 == 1 ? 0 : d1 > 1 && d1 < 5 ? +1 : -1);
- assert(x >= 0 && x <= w && y >= 0 && y <= h);
- lastdir = d1 ^ 4;
- } while (x != ox || y != oy);
- draw_polygon(dr, coords, ncoords/2,
- state->colouring[r] >= 0 ?
- c[state->colouring[r]] : -1, ink);
- }
- sfree(coords);
- }
- #ifdef COMBINED
- #define thegame map
- #endif
- const struct game thegame = {
- "Map", "games.map", "map",
- 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,
- false, NULL, NULL, /* can_format_as_text_now, text_format */
- 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,
- 20, 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, true, game_print_size, game_print,
- false, /* wants_statusbar */
- false, NULL, /* timing_state */
- 0, /* flags */
- };
- #ifdef STANDALONE_SOLVER
- int main(int argc, char **argv)
- {
- game_params *p;
- game_state *s;
- char *id = NULL, *desc;
- const char *err;
- bool grade = false;
- int ret, diff;
- bool really_verbose = false;
- struct solver_scratch *sc;
- int i;
- while (--argc > 0) {
- char *p = *++argv;
- if (!strcmp(p, "-v")) {
- really_verbose = true;
- } else if (!strcmp(p, "-g")) {
- grade = true;
- } else if (*p == '-') {
- fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
- return 1;
- } else {
- id = p;
- }
- }
- if (!id) {
- fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]);
- return 1;
- }
- desc = strchr(id, ':');
- if (!desc) {
- fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
- return 1;
- }
- *desc++ = '\0';
- p = default_params();
- decode_params(p, id);
- err = validate_desc(p, desc);
- if (err) {
- fprintf(stderr, "%s: %s\n", argv[0], err);
- return 1;
- }
- s = new_game(NULL, p, desc);
- sc = new_scratch(s->map->graph, s->map->n, s->map->ngraph);
- /*
- * When solving an Easy puzzle, we don't want to bother the
- * user with Hard-level deductions. For this reason, we grade
- * the puzzle internally before doing anything else.
- */
- ret = -1; /* placate optimiser */
- for (diff = 0; diff < DIFFCOUNT; diff++) {
- for (i = 0; i < s->map->n; i++)
- if (!s->map->immutable[i])
- s->colouring[i] = -1;
- ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph,
- s->colouring, diff);
- if (ret < 2)
- break;
- }
- if (diff == DIFFCOUNT) {
- if (grade)
- printf("Difficulty rating: harder than Hard, or ambiguous\n");
- else
- printf("Unable to find a unique solution\n");
- } else {
- if (grade) {
- if (ret == 0)
- printf("Difficulty rating: impossible (no solution exists)\n");
- else if (ret == 1)
- printf("Difficulty rating: %s\n", map_diffnames[diff]);
- } else {
- verbose = really_verbose;
- for (i = 0; i < s->map->n; i++)
- if (!s->map->immutable[i])
- s->colouring[i] = -1;
- ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph,
- s->colouring, diff);
- if (ret == 0)
- printf("Puzzle is inconsistent\n");
- else {
- int col = 0;
- for (i = 0; i < s->map->n; i++) {
- printf("%5d <- %c%c", i, colnames[s->colouring[i]],
- (col < 6 && i+1 < s->map->n ? ' ' : '\n'));
- if (++col == 7)
- col = 0;
- }
- }
- }
- }
- return 0;
- }
- #endif
- /* vim: set shiftwidth=4 tabstop=8: */
|