aboutsummaryrefslogtreecommitdiff
path: root/solo.c (follow)
Commit message (Collapse)AuthorAge
...
* Fix mismatch between printf format strings and arguments in someSimon Tatham2011-04-11
| | | | | | | | | | | solosolver verbose diagnostics in X mode. Also added gcc-specific prototypes with __attribute__((format)) to ensure they all get checked in future. Spotted by Arun Giridhar; segfault without this fix is reproducible by 'solosolver -v 3x3x:7_9e4_1c7d3e3d1b2_4e2c6e5_6b1d8e5d9c8_2e9_5'. [originally from svn r9151]
* Add a function to every game backend which indicates whether a gameSimon Tatham2011-04-02
| | | | | | | | | | | state is in a solved position, and a midend function wrapping it. (Or, at least, a situation in which further play is pointless. The point is, given that game state, would it be a good idea for a front end that does that sort of thing to proactively provide the option to start a fresh game?) [originally from svn r9140]
* Jonas Koelker points out that the backspace key didn't work in GTKSimon Tatham2009-12-20
| | | | | | | | | | Guess, because Guess expected ^H whereas GTK generated ^?. Other puzzles that use Backspace do it by being prepared to see either, which seems wasteful. Now the midend normalises both into ^H, so front ends can generate whichever they like while puzzles can safely just look for ^H. [originally from svn r8786]
* Memory management and other fixes from James H.Simon Tatham2009-06-17
| | | | [originally from svn r8596]
* Fix a misdesign I must have missed when I reviewed the Killer patch:Simon Tatham2009-04-30
| | | | | | | | | | | | | | | | | merge_some_cages() was written in the assumption that it would always be able to do something, in that it returned void on success and if it couldn't find anything to do it would just loop round forever trying the same things over and over again. Now it makes a methodical list of the pairs of cages which are merge candidates, goes through them in a random order until it finds a viable one, and returns a boolean indicating whether it succeeded or ran out of candidates. A test case which previously hung and now does not is "solo --generate 1 7jxkdt#12345-10". [originally from svn r8541]
* check_valid() wasn't checking that Killer cages contain at most oneSimon Tatham2009-04-29
| | | | | | | of each digit, and - perhaps more importantly - the display code wasn't highlighting violations of that rule as an error. Fix both. [originally from svn r8540]
* Patch from James H to provide 16-bit-int cleanliness in Killer Solo.Simon Tatham2009-03-02
| | | | [originally from svn r8489]
* Fix cosmetic glitch in the interaction between Killer and JigsawSimon Tatham2009-02-24
| | | | | | modes. [originally from svn r8463]
* A substantial patch to Solo from Bernd Schmidt, adding support forSimon Tatham2009-02-22
| | | | | | | | the 'Killer Sudoku' puzzle type. As a side effect I've had to increase the default tile size of Solo, so that the extra numbers drawn in the squares in Killer mode were still legible. [originally from svn r8455]
* Keyboard control patch for Solo, from James H.Simon Tatham2009-01-19
| | | | [originally from svn r8418]
* Patch from Chris Boyle to prevent Solo's inter-block dividing linesSimon Tatham2008-11-02
| | | | | | | from becoming indistinguishable from the intra-block ones at low tile sizes. [originally from svn r8259]
* New infrastructure feature. Games are now permitted to beSimon Tatham2008-09-06
| | | | | | | | | | | | | | | | | | | | | | _conditionally_ able to format the current puzzle as text to be sent to the clipboard. For instance, if a game were to support playing on a square grid and on other kinds of grid such as hexagonal, then it might reasonably feel that only the former could be sensibly rendered in ASCII art; so it can now arrange for the "Copy" menu item to be greyed out depending on the game_params. To do this I've introduced a new backend function (can_format_as_text_now()), and renamed the existing static backend field "can_format_as_text" to "can_format_as_text_ever". The latter will cause compile errors for anyone maintaining a third-party front end; if any such person is reading this, I apologise to them for the inconvenience, but I did do it deliberately so that they'd know to update their front end. As yet, no checked-in game actually uses this feature; all current games can still either copy always or copy never. [originally from svn r8161]
* Shamelessly pander to compilers whose data flow warning systemsSimon Tatham2008-04-14
| | | | | | | insist that a variable should be initialised in all branches of an if, instead of just all the non-assertion-failing ones. [originally from svn r7989]
* Having got Jigsaw mode generation working at reasonable speed, weSimon Tatham2008-04-08
| | | | | | can now productise it. [originally from svn r7979]
* Improvements to filled-grid generation. Introduced a cunning ideaSimon Tatham2008-04-08
| | | | | | | | | | | | | | | suggested by IWJ last night: grid generation can immediately choose an entire grid row randomly, since all that's doing is nailing down the names of the numbers, and that gets the whole thing started more efficiently. But the main difference is that now grid generation is given only area^2 steps to come up with a filled grid, and then cut off unceremoniously, causing grid generation to fail and be retried from scratch. This seems to prevent hangups on jigsaw layouts that admit few useful solutions, by changing layout constantly. 9j puzzles now generate at a sensible rate, and as an added bonus so do 5x5 normal puzzles, which they never used to. [originally from svn r7978]
* Revise the printing colour framework so that we can explicitlySimon Tatham2008-04-07
| | | | | | | request either of hatching or halftoning, and also choose which to supply as a fallback when printing in colour. [originally from svn r7976]
* Pedantic tweaks to allow successful compilation on Windows. (gccSimon Tatham2008-04-07
| | | | | | | | failed to point out a declaration after a statement, and gcc's linker was clever enough to optimise the call to divvy_rectangle() out of solosolver so that I didn't have to include divvy.c in that.) [originally from svn r7975]
* Substantial reworking of Solo so that it implements both Sudoku-XSimon Tatham2008-04-07
| | | | | | | | | | | | | | | | | | | | | | | | | | (require both main diagonals to have one of every digit in addition to all the usual constraints) and Jigsaw Sudoku (replace the array of rectangular sub-blocks with the sub-blocks being random polyominoes). To implement the latter, I've moved my `divvy.c' library routine out of the `unfinished' subdirectory. Jigsaw mode is currently an undocumented feature: you enable it by setting the rows parameter to 1 (and the columns parameter to your desired grid size, which unlike normal Sudoku can be anything you like including a prime number). The reason it's undocumented is because generation times are not yet reliably short: sometimes generating a jigsaw-type puzzle can hang for hours and still get nowhere. (The algorithm should terminate in principle, but not in any time you're prepared to wait.) I _think_ I know how to solve this, but have yet to try it. Until then, jigsaw mode will remain a hidden feature. Printing of X-type puzzles is also substandard at present, because the current print-colour API replaces the desired light shading of the X-cells with heavy diagonal hatching. I plan to adjust the API imminently to address this. [originally from svn r7974]
* Gary Wong observes that solo's decode_params() is overenthusiasticSimon Tatham2007-03-11
| | | | | | | | | | | about eating the letter `d' (for `diagonal') when it appears in a symmtery description: it should only be used after `m', because mirror symmetry is the only type that can be diagonal. This was causing parsing of the parameter description `3x3adu' to produce the wrong answer: the d would be swallowed, then the u ignored for being incomprehensible, and you'd get default Trivial difficulty. [originally from svn r7386]
* Gary Wong points out that solosolver's verbose output isSimon Tatham2007-03-11
| | | | | | | inconsistent in whether it numbers rows and columns from zero or from one. Standardise on one. [originally from svn r7385]
* Dariusz Olszewski's changes to support compiling for PocketPC. ThisSimon Tatham2007-02-26
| | | | | | | | | | | | is mostly done with ifdefs in windows.c; so mkfiles.pl generates a new makefile (Makefile.wce) and Recipe enables it, but it's hardly any different from Makefile.vc apart from a few definitions at the top of the files. Currently the PocketPC build is not enabled in the build script, but with any luck I'll be able to do so reasonably soon. [originally from svn r7337]
* Phil Bordelon points out an off-by-one error: since Solo doesn't useSimon Tatham2007-01-15
| | | | | | | | zero as a valid puzzle symbol, it can support at most 35 symbols, not 36. (This is largely academic since IME anything above about 25 is impractical to generate, but there we go.) [originally from svn r7115]
* HTML Help support for Puzzles, with the same kind of automaticSimon Tatham2006-12-24
| | | | | | fallback behaviour as PuTTY's support. [originally from svn r7009]
* Cleanup: it was absolutely stupid for game_wants_statusbar() to be aSimon Tatham2005-10-22
| | | | | | | | | function, since it took no parameters by which to vary its decision, and in any case it's hard to imagine a game which only _conditionally_ wants a status bar. Changed it into a boolean data field in the backend structure. [originally from svn r6417]
* Cleanup: remove the game_state parameter to game_colours(). No gameSimon Tatham2005-10-22
| | | | | | | | | | | | was actually using it, and also it wasn't being called again for different game states or different game parameters, so it would have been a mistake to depend on anything in that game state. Games are now expected to commit in advance to a single fixed list of all the colours they will ever need, which was the case in practice already and simplifies any later port to a colour-poor platform. Also this change has removed a lot of unnecessary faff from midend_colours(). [originally from svn r6416]
* Cleanup: the `mouse_priorities' field in the back end has been aSimon Tatham2005-10-22
| | | | | | | more general-purpose flags word for some time now. Rename it to `flags'. [originally from svn r6414]
* Richard Earnshaw points out that if you enter an out-of-range numberSimon Tatham2005-10-10
| | | | | | | | | in the game description, the solver will fail to notice it and overrun an array leading to assertion failure, silent wrong answers or (in extreme cases) segfaults. Hence, validate_desc() now spots them and kicks them out. [originally from svn r6383]
* Use game_set_size() to set up the temporary drawstate inSimon Tatham2005-09-23
| | | | | | | | | | | | | | | | | | game_print(), wherever feasible. This fixes a specific bug in Loopy (James H's new field ds->linewidth wasn't being set up, leading to corrupted print output), but I've made the change in all affected files because it also seems like a generally good idea to encourage it for future games, to prevent other problems of this type. There is one slight snag, which is that Map _can't_ do this because its game_set_size() also initialises a blitter. I could fix this by abstracting the common parts of Map's game_set_size() out into a subfunction called by game_set_size() and also called directly by game_print(); alternatively, I could introduce a means of determining whether a `drawing *' was for screen or printing use. Not sure which yet. [originally from svn r6340]
* I am again gormless! When I overhauled Solo's grid generator inSimon Tatham2005-09-12
| | | | | | | | | | r6160, I completely failed to ensure that generated grids were _at most_ the required difficulty. It appears to have been only random chance that prevented a request for a Trivial puzzle from producing Extreme. Here's a one-line fix. [originally from svn r6298] [r6160 == e55838bc9b0d173ca539d0cfe714495b5c12b9dd]
* Someone points out that the Solo text formatter would be a lotSimon Tatham2005-09-02
| | | | | | | better if it marked empty cells with something other than a space. So here's a three-bit change to turn it into a dot :-) [originally from svn r6261]
* James H has implemented a new `Tricky' difficulty level in Light Up:Simon Tatham2005-09-01
| | | | | | | | | | | | | | | | | | a non-recursive level above Easy, which therefore moves the recursive Hard mode further up still. Play-testing suggests that in fact Tricky is often _harder_ than the old Hard mode, since the latter had limited depth of recursion and would therefore spot complex deductions only if it happened to start a recursion on the right square; Tricky may be limited in the sophistication of its complex deductions, but it never misses one, so its puzzles tend to be hard all over. Also in this checkin, a new source file `nullfe.c', containing all the annoying stub functions required to make command-line solvers link successfully. James wrote this for (the new) lightupsolver, and I've used it to simplify the other stand-alone solvers. [originally from svn r6254]
* Implemented a couple more reasoning modes for Extreme difficultySimon Tatham2005-08-30
| | | | | | | | | | | | | | level: positional set elimination (which is so obvious I really should have thought of it myself, though it's tricky to spot) and forcing chains (which are a type of one-level proof by contradiction, findable through a simple breadth-first search without requiring recursion, but so ludicrously powerful that they are able to solve _two thirds_ of grids that the pre-Extreme Solo generated and rated as Unreasonable). Of course this makes Unreasonable mode harder still... [originally from svn r6239]
* Backspace and Delete keys now function like Space in Solo.Simon Tatham2005-08-29
| | | | [originally from svn r6237]
* Brand new difficulty level in Solo. The other day Gareth and ISimon Tatham2005-08-24
| | | | | | | | | | | | | | | | independently discovered an advanced reasoning technique in Map, and then it occurred to me that since Solo can also be considered as a graph-colouring game the same technique ought to be applicable. And it is; so here's a new difficulty level, `Extreme', which sits just above Advanced. Grids graded `Extreme' by new-Solo will of course fall into old-Solo's `Unreasonable' category (since they're not soluble using the old set of non-recursive methods). A brief and unscientific experiment suggests that about one in six Unreasonable grids generated by old-Solo are classified Extreme by the new solver; so the remaining Unreasonable mode (now containing a subset of the grids it used to) hasn't actually become much harder. [originally from svn r6209]
* Substantial infrastructure upheaval. I've separated the drawing APISimon Tatham2005-08-18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | as seen by the back ends from the one implemented by the front end, and shoved a piece of middleware (drawing.c) in between to permit interchange of multiple kinds of the latter. I've also added a number of functions to the drawing API to permit printing as well as on-screen drawing, and retired print.py in favour of integrated printing done by means of that API. The immediate visible change is that print.py is dead, and each puzzle now does its own printing: where you would previously have typed `print.py solo 2x3', you now type `solo --print 2x3' and it should work in much the same way. Advantages of the new mechanism available right now: - Map is now printable, because the new print function can make use of the output from the existing game ID decoder rather than me having to replicate all those fiddly algorithms in Python. - the new print functions can cope with non-initial game states, which means each puzzle supporting --print also supports --with-solutions. - there's also a --scale option permitting users to adjust the size of the printed puzzles. Advantages which will be available at some point: - the new API should permit me to implement native printing mechanisms on Windows and OS X. [originally from svn r6190]
* I am COMPLETELY GORMLESS. The Solo grid generator, when eliminatingSimon Tatham2005-08-04
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | clues from a filled grid, was using the algorithm - loop over the whole grid looking for a clue (or symmetry group of clues) which can be safely removed - remove it - loop over the whole grid again, and so on. This was due to my vague feeling that removing one clue might affect whether another can be removed. Of course this can happen - two clues can be alternative ways of deducing the same vital fact so that removing one makes the other necessary - but what _can't_ happen is for removing one clue to make another _become_ removable, since you can only do that by _adding_ information. In other words, after testing a clue and determining that it can't be removed, you never need to test it again. Thus, a much simpler algorithm is - loop over the possible clues (or symmetry groups) _once_, in a random order - for each clue (group), if it is removable, remove it. This still guarantees to leave the grid in a state where no further clues can be removed, but it greatly cuts down puzzle generation time and also simplifies the code. I am a fool for not having spotted this in three and a half months! [originally from svn r6160]
* Sanity-checking patch from Phil Bordelon: since Solo can't cope withSimon Tatham2005-07-16
| | | | | | | | | | more than 36 distinct symbols (it runs out of alphanumerics), check this in validate_params. I hate to do this, since I like puzzle sizes to at least be open-ended in _principle_, but in this case there's a fundamental UI limitation which won't be fixed by getting a faster CPU. [originally from svn r6098]
* Cleanups to Solo:Simon Tatham2005-07-14
| | | | | | | | | | - use the new `shuffle' utility function in a couple of places - remove the random_state parameter from solver(). It was there because I initially wanted to use the same solver for grid generation, but since I had to abandon that plan the solver now doesn't have any need for randomness at all. [originally from svn r6093]
* game_timing_state() now has access to the game_ui. This means thatSimon Tatham2005-07-10
| | | | | | | | | | | | whether the timer is currently going is no longer solely dependent on the current game_state: it can be dependent on more persistent information stored in the game_ui. In particular, Mines now freezes the timer permanently once you complete a grid for the first time, so that you can then backtrack through your solution process without destroying the information about how long it took you the first time through. [originally from svn r6088]
* Move various printf()s after declarations.Jacob Nevins2005-07-06
| | | | [originally from svn r6078]
* Unify the two solvers in Solo. nsolve has now had recursionSimon Tatham2005-07-06
| | | | | | | | | | | | | | | | | | | | | | | | | | capability added to it, to be used only when all else fails, and is simply called `solver'. This means that: - solving of 5x5 Trivial grids using the `Solve' function, which previously hung for ages because rsolve happened to take a wrong turning at the start, is now zippy - solosolver doesn't require the confusing -r and -n options - solosolver can show its working even for Unreasonable grids. Unfortunately, the new unified solver still isn't suitable for grid generation. After it proved to be so much faster at solving 5x5s, I hoped to be able to substitute it for rsolve during generation and gain additional speed in 5x5 generation too; but no luck, because it's slower _per recursion level_, and although during solving it makes up for this by needing very few levels, there is a lot of _unavoidable_ recursion during generation, especially at 5x5. A hybrid strategy which starts off with rsolve and switches to the unified solver at a critical point proved unsatisfactory as well, because the critical point changes depending on the vagaries of the recursion and can't be pinpointed easily. So rsolve is still in there, only renamed `gridgen' because that's now all it's good for. [originally from svn r6077]
* Add a `full' parameter to validate_params(), analogous to the one inJacob Nevins2005-07-05
| | | | | | | | | | | encode_params(). This is necessary for cases where generation-time parameters that are normally omitted from descriptive IDs can place restrictions on other parameters; in particular, when the default value of a relevant generation-time parameter is not the one used to generate the descriptive ID, validation could reject self-generated IDs (e.g., Net `5x2w:56182ae7c2', and some cases in `Pegs'). [originally from svn r6068]
* Enhancements to mkfiles.pl and Recipe to arrange for the auxiliarySimon Tatham2005-07-05
| | | | | | | | | | | command-line programs (solosolver, patternsolver, mineobfusc) to be built as part of the normal Makefiles. This means mkfiles.pl now has the capability to compile a source file more than once with different #defines. Also, fixes for those auxiliary programs and one fix in midend.c which the Borland compiler objected to while I was testing its makefile generation. [originally from svn r6066]
* Refactored the game_size() interface, which was getting reallySimon Tatham2005-07-05
| | | | | | | | | | | | | unpleasant and requiring lots of special cases to be taken care of by every single game. The new interface exposes an integer `tile size' or `scale' parameter to the midend and provides two much simpler routines: one which computes the pixel window size given a game_params and a tile size, and one which is given a tile size and must set up a drawstate appropriately. All the rest of the complexity is handled in the midend, mostly by binary search, so grubby special cases only have to be dealt with once. [originally from svn r6059]
* draw_polygon() and draw_circle() have always had a portabilitySimon Tatham2005-07-03
| | | | | | | | | | | | | | | | | | | constraint: because some front ends interpret `draw filled shape' to mean `including its boundary' while others interpret it to mean `not including its boundary' (and X seems to vacillate between the two opinions as it moves around the shape!), you MUST NOT draw a filled shape only. You can fill in one colour and outline in another, you can fill or outline in the same colour, or you can just outline, but just filling is a no-no. This leads to a _lot_ of double calls to these functions, so I've changed the interface. draw_circle() and draw_polygon() now each take two colour arguments, a fill colour (which can be -1 for none) and an outline colour (which must be valid). This should simplify code in the game back ends, while also reducing the possibility for coding error. [originally from svn r6047]
* General robustness patch from James Harvey:Simon Tatham2005-06-30
| | | | | | | | | | | | | - most game_size() functions now work in doubles internally and round to nearest, meaning that they have less tendency to try to alter a size they returned happily from a previous call - couple of fiddly fixes (memory leaks, precautionary casts in printf argument lists) - midend_deserialise() now constructs an appropriate drawstate, which I can't think how I overlooked myself since I _thought_ I went through the entire midend structure field by field! [originally from svn r6041]
* New {en,de}code_ui functions should be static. Oops.Simon Tatham2005-06-28
| | | | [originally from svn r6031]
* More serialisation changes: the game_aux_info structure has now beenSimon Tatham2005-06-28
| | | | | | | | | | | | retired, and replaced with a simple string. Most of the games which use it simply encode the string in the same way that the Solve move will also be encoded, i.e. solve_game() simply returns dupstr(aux_info). Again, this is a better approach than writing separate game_aux_info serialise/deserialise functions because doing it this way is self-testing (the strings are created and parsed during the course of any Solve operation at all). [originally from svn r6029]
* Another function pair required for serialisation; these ones saveSimon Tatham2005-06-28
| | | | | | | | | | | and restore anything vitally important in the game_ui. Most of the game_ui is expected to be stuff about cursor positions and currently active mouse drags, so it absolutely _doesn't_ want to be preserved over a serialisation; but one or two things would be disorienting or outright wrong to reset, such as the Net origin position and the Mines death counter. [originally from svn r6026]
* Re-architecting of the game backend interface. make_move() has beenSimon Tatham2005-06-27
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | split into two functions. The first, interpret_move(), takes all the arguments that make_move() used to get and may have the usual side effects of modifying the game_ui, but instead of returning a modified game_state it instead returns a string description of the move to be made. This string description is then passed to a second function, execute_move(), together with an input game_state, which is responsible for actually producing the new state. (solve_game() also returns a string to be passed to execute_move().) The point of this is to work towards being able to serialise the whole of a game midend into a byte stream such as a disk file, which will eventually support save and load functions in the desktop puzzles, as well as restoring half-finished games after a quit and restart in James Harvey's Palm port. Making each game supply a convert-to-string function for its game_state format would have been an unreliable way to do this, since those functions would not have been used in normal play, so they'd only have been tested when you actually tried to save and load - a recipe for latent bugs if ever I heard one. This way, you won't even be able to _make_ a move if execute_move() doesn't work properly, which means that if you can play a game at all I can have pretty high confidence that serialising it will work first time. This is only the groundwork; there will be more checkins to come on this theme. But the major upheaval should now be done, and as far as I can tell everything's still working normally. [originally from svn r6024]
generated by cgit v1.1 at 2026-04-24 22:28:09 +0000