Improve speed of grid generation: I've found something simple I can

[sgt/puzzles] / puzzles.but

\title Simon Tatham's Portable Puzzle Collection

\cfg{winhelp-filename}{puzzles.hlp}
\cfg{winhelp-contents-titlepage}{Contents}

\cfg{text-filename}{puzzles.txt}

\cfg{html-contents-filename}{index.html}
\cfg{html-template-filename}{%k.html}
\cfg{html-index-filename}{docindex.html}
\cfg{html-leaf-level}{1}
\cfg{html-contents-depth-0}{1}
\cfg{html-contents-depth-1}{2}
\cfg{html-leaf-contains-contents}{true}

\cfg{info-filename}{puzzles.info}

\cfg{ps-filename}{puzzles.ps}
\cfg{pdf-filename}{puzzles.pdf}

\define{by} \u00D7{x}

This is a collection of small one-player puzzle games.

\copyright This manual is copyright 2004-5 Simon Tatham. All rights
reserved. You may distribute this documentation under the MIT licence.
See \k{licence} for the licence text in full.

\cfg{html-local-head}{<meta name="AppleTitle" content="Puzzles Help">}

\versionid $Id$

\C{intro} Introduction

I wrote this collection because I thought there should be more small
desktop toys available: little games you can pop up in a window and
play for two or three minutes while you take a break from whatever
else you were doing. And I was also annoyed that every time I found
a good game on (say) \i{Unix}, it wasn't available the next time I
was sitting at a \i{Windows} machine, or vice versa; so I arranged
that everything in my personal puzzle collection will happily run on
both, and have more recently done a port to Mac OS X as well. When I
find (or perhaps invent) further puzzle games that I like, they'll
be added to this collection and will immediately be available on
both platforms. And if anyone feels like writing any other front
ends - PocketPC, Mac OS pre-10, or whatever it might be - then all
the games in this framework will immediately become available on
another platform as well.

The actual games in this collection were mostly not my invention; I
saw them elsewhere, and rewrote them in a form that was more
convenient for me. I do not claim credit, in general, for inventing
the rules of any of these puzzles; all I claim is authorship of the
code (or at least those parts of the code that weren't contributed
by other people!).

This collection is distributed under the \i{MIT licence} (see
\k{licence}). This means that you can do pretty much anything you like
with the game binaries or the code, except pretending you wrote them
yourself, or suing me if anything goes wrong. 

The most recent versions, and \i{source code}, can be found at
\I{website}\W{http://www.chiark.greenend.org.uk/~sgtatham/puzzles/}\cw{http://www.chiark.greenend.org.uk/~sgtatham/puzzles/}.

Please report \I{feedback}\i{bugs} to
\W{mailto:anakin@pobox.com}\cw{anakin@pobox.com}.
You might find it helpful to read this article before reporting a bug:

\W{http://www.chiark.greenend.org.uk/~sgtatham/bugs.html}\cw{http://www.chiark.greenend.org.uk/~sgtatham/bugs.html}

\ii{Patches} are welcome. Especially if they provide a new front end
(to make all these games run on another platform), or a new game.


\C{common} \ii{Common features}

This chapter describes features that are common to all the games.

\H{common-actions} \I{controls}Common actions

These actions are all available from the \I{Game menu}\q{Game} menu
and via \I{keys}keyboard shortcuts, in addition to any game-specific
actions.

(On Mac OS X, to conform with local user interface standards, these
actions are situated on the \I{File menu}\q{File} and \I{Edit
menu}\q{Edit} menus instead.)

\dt \ii\e{New game} (\q{N}, Ctrl+\q{N})

\dd Starts a new game, with a random initial state.

\dt \ii\e{Restart game}

\dd Resets the current game to its initial state. (This can be undone.)

\dt \ii\e{Load}

\dd Loads a saved game from a file on disk.

\dt \ii\e{Save}

\dd Saves the current state of your game to a file on disk.

\lcont{

The Load and Save operations should preserve your entire game
history (so you can save, reload, and still Undo and Redo things you
had done before saving).

}

\dt \ii\e{Undo} (\q{U}, Ctrl+\q{Z}, Ctrl+\q{_})

\dd Undoes a single move. (You can undo moves back to the start of the
session.)

\dt \ii\e{Redo} (\q{R}, Ctrl+\q{R})

\dd Redoes a previously undone move.

\dt \ii\e{Copy}

\dd Copies the current state of your game to the clipboard in text
format, so that you can paste it into (say) an e-mail client or a
web message board if you're discussing the game with someone else.
(Not all games support this feature.)

\dt \ii\e{Solve}

\dd Transforms the puzzle instantly into its solved state. For some
games (Cube) this feature is not supported at all because it is of
no particular use. For other games (such as Pattern), the solved
state can be used to give you information, if you can't see how a
solution can exist at all or you want to know where you made a
mistake. For still other games (such as Sixteen), automatic solution
tells you nothing about how to \e{get} to the solution, but it does
provide a useful way to get there quickly so that you can experiment
with set-piece moves and transformations.

\lcont{

Some games (such as Solo) are capable of solving a game ID you have
typed in from elsewhere. Other games (such as Rectangles) cannot
solve a game ID they didn't invent themself, but when they did
invent the game ID they know what the solution is already. Still
other games (Pattern) can solve \e{some} external game IDs, but only
if they aren't too difficult.

The \q{Solve} command adds the solved state to the end of the undo
chain for the puzzle. In other words, if you want to go back to
solving it yourself after seeing the answer, you can just press Undo.

}

\dt \I{exit}\ii\e{Quit} (\q{Q}, Ctrl+\q{Q})

\dd Closes the application entirely.

\H{common-id} Specifying games with the \ii{game ID}

There are two ways to save a game specification out of a puzzle and
recreate it later, or recreate it in somebody else's copy of the
same puzzle.

The \q{\i{Specific}} and \q{\i{Random Seed}} options from the
\I{Game menu}\q{Game} menu (or the \q{File} menu, on Mac OS X) each
show a piece of text (a \q{game ID}) which is sufficient to
reconstruct precisely the same game at a later date.

You can enter either of these pieces of text back into the program
(via the same \q{Specific} or \q{Random Seed} menu options) at a
later point, and it will recreate the same game. You can also use
either one as a \i{command line} argument (on Windows or Unix); see
\k{common-cmdline} for more detail.

The difference between the two forms is that a descriptive game ID
is a literal \e{description} of the \i{initial state} of the game,
whereas a random seed is just a piece of arbitrary text which was
provided as input to the random number generator used to create the
puzzle. This means that:

\b Descriptive game IDs tend to be longer in many puzzles (although
some, such as Cube (\k{cube}), only need very short descriptions).
So a random seed is often a \e{quicker} way to note down the puzzle
you're currently playing, or to tell it to somebody else so they can
play the same one as you.

\b Any text at all is a valid random seed. The automatically
generated ones are fifteen-digit numbers, but anything will do; you
can type in your full name, or a word you just made up, and a valid
puzzle will be generated from it. This provides a way for two or
more people to race to complete the same puzzle: you think of a
random seed, then everybody types it in at the same time, and nobody
has an advantage due to having seen the generated puzzle before
anybody else.

\b It is often possible to convert puzzles from other sources (such
as \q{nonograms} or \q{sudoku} from newspapers) into descriptive
game IDs suitable for use with these programs.

\b Random seeds are not guaranteed to produce the same result if you
use them with a different \i\e{version} of the puzzle program. This
is because the generation algorithm might have been improved or
modified in later versions of the code, and will therefore produce a
different result when given the same sequence of random numbers. Use
a descriptive game ID if you aren't sure that it will be used on the
same version of the program as yours.

\lcont{(Use the \q{About} menu option to find out the version number
of the program. Programs with the same version number running on
different platforms should still be random-seed compatible.)}

\I{ID format}A descriptive game ID starts with a piece of text which
encodes the \i\e{parameters} of the current game (such as grid
size). Then there is a colon, and after that is the description of
the game's initial state. A random seed starts with a similar string
of parameters, but then it contains a hash sign followed by
arbitrary data.

If you enter a descriptive game ID, the program will not be able to
show you the random seed which generated it, since it wasn't
generated \e{from} a random seed. If you \e{enter} a random seed,
however, the program will be able to show you the descriptive game
ID derived from that random seed.

Note that the game parameter strings are not always identical
between the two forms. For some games, there will be parameter data
provided with the random seed which is not included in the
descriptive game ID. This is because that parameter information is
only relevant when \e{generating} puzzle grids, and is not important
when playing them. Thus, for example, the difficulty level in Solo
(\k{solo}) is not mentioned in the descriptive game ID.

These additional parameters are also not set permanently if you type
in a game ID. For example, suppose you have Solo set to \q{Advanced}
difficulty level, and then a friend wants your help with a
\q{Trivial} puzzle; so the friend reads out a random seed specifying
\q{Trivial} difficulty, and you type it in. The program will
generate you the same \q{Trivial} grid which your friend was having
trouble with, but once you have finished playing it, when you ask
for a new game it will automatically go back to the \q{Advanced}
difficulty which it was previously set on.

\H{common-type} The \q{Type} menu

The \I{Type menu}\q{Type} menu, if present, may contain a list of
\i{preset} game settings. Selecting one of these will start a new
random game with the parameters specified.

The \q{Type} menu may also contain a \q{\i{Custom}} option which
allows you to fine-tune game \i{parameters}. The parameters
available are specific to each game and are described in the
following sections.

\H{common-cmdline} Specifying game parameters on the \i{command line}

(This section does not apply to the Mac OS X version.)

The games in this collection deliberately do not ever save
information on to the computer they run on: they have no high score
tables and no saved preferences. (This is because I expect at least
some people to play them at work, and those people will probably
appreciate leaving as little evidence as possible!)

However, if you do want to arrange for one of these games to default
to a particular set of parameters, you can specify them on the
command line.

The easiest way to do this is to set up the parameters you want
using the \q{Type} menu (see \k{common-type}), and then to select
\q{Random Seed} from the \q{Game} or \q{File} menu (see
\k{common-id}). The text in the \q{Game ID} box will be composed of
two parts, separated by a hash. The first of these parts represents
the game parameters (the size of the playing area, for example, and
anything else you set using the \q{Type} menu).

If you run the game with just that parameter text on the command
line, it will start up with the settings you specified.

For example: if you run Cube (see \k{cube}), select \q{Octahedron}
from the \q{Type} menu, and then go to the game ID selection, you
will see a string of the form \cq{o2x2#338686542711620}. Take only
the part before the hash (\cq{o2x2}), and start Cube with that text
on the command line: \cq{cube o2x2}.

If you copy the \e{entire} game ID on to the command line, the game
will start up in the specific game that was described. This is
occasionally a more convenient way to start a particular game ID
than by pasting it into the game ID selection box.

(You could also retrieve the encoded game parameters using the
\q{Specific} menu option instead of \q{Random Seed}, but if you do
then some options, such as the difficulty level in Solo, will be
missing. See \k{common-id} for more details on this.)

\C{net} \i{Net}

\cfg{winhelp-topic}{games.net}

(\e{Note:} the \i{Windows} version of this game is called
\i\cw{NETGAME.EXE} to avoid clashing with Windows's own \cw{NET.EXE}.)

I originally saw this in the form of a Flash game called \i{FreeNet}
\k{FreeNet}, written by Pavils Jurjans; there are several other
implementations under the name \i{NetWalk}. The computer prepares a
network by connecting up the centres of squares in a grid, and then
shuffles the network by rotating every tile randomly. Your job is to
rotate it all back into place. The successful solution will be an
entirely connected network, with no closed loops. \#{The latter
clause means that there are no closed paths within the network.
Could this be clearer? "No closed paths"?} As a visual aid,
all tiles which are connected to the one in the middle are
highlighted. 

\B{FreeNet} \W{http://www.jurjans.lv/stuff/net/FreeNet.htm}\cw{http://www.jurjans.lv/stuff/net/FreeNet.htm}

\H{net-controls} \i{Net controls}

\IM{Net controls} controls, for Net
\IM{Net controls} keys, for Net
\IM{Net controls} shortcuts (keyboard), for Net

This game can be played with either the keyboard or the mouse. The
controls are:

\dt \e{Select tile}: mouse pointer, arrow keys

\dt \e{Rotate tile anticlockwise}: left mouse button, \q{A} key

\dt \e{Rotate tile clockwise}: right mouse button, \q{D} key

\dt \e{Rotate tile by 180 degrees}: \q{F} key

\dt \e{Lock (or unlock) tile}: middle mouse button, shift-click, \q{S} key

\dd You can lock a tile once you're sure of its orientation. You can
also unlock it again, but while it's locked you can't accidentally
turn it.

The following controls are not necessary to complete the game, but may
be useful:

\dt \e{Shift grid}: Shift + arrow keys

\dd On grids that wrap, you can move the origin of the grid, so that
tiles that were on opposite sides of the grid can be seen together.

\dt \e{Move centre}: Ctrl + arrow keys

\dd You can change which tile is used as the source of highlighting.
(It doesn't ultimately matter which tile this is, as every tile will
be connected to every other tile in a correct solution, but it may be
helpful in the intermediate stages of solving the puzzle.)

\dt \e{Jumble tiles}: \q{J} key

\dd This key turns all tiles that are not locked to random
orientations.

(All the actions described in \k{common-actions} are also available.)

\H{net-params} \I{parameters, for Net}Net parameters

These parameters are available from the \q{Custom...} option on the
\q{Type} menu.

\dt \e{Width}, \e{Height}

\dd Size of grid in tiles.

\dt \e{Walls wrap around}

\dd If checked, flow can pass from the left edge to the right edge,
and from top to bottom, and vice versa.

\dt \e{Barrier probability}

\dd A number between 0.0 and 1.0 controlling whether an immovable
barrier is placed between two tiles to prevent flow between them (a
higher number gives more barriers). Since barriers are immovable, they
act as constraints on the solution (i.e., hints).

\lcont{

The grid generation in Net has been carefully arranged so that the
barriers are independent of the rest of the grid. This means that if
you note down the random seed used to generate the current puzzle
(see \k{common-id}), change the \e{Barrier probability} parameter,
and then re-enter the same random seed, you should see exactly the
same starting grid, with the only change being the number of
barriers. So if you're stuck on a particular grid and need a hint,
you could start up another instance of Net, set up the same
parameters but a higher barrier probability, and enter the game seed
from the original Net window.

}

\dt \e{Ensure unique solution}

\dd Normally, Net will make sure that the puzzles it presents have
only one solution. Puzzles with ambiguous sections can be more
difficult and more subtle, so if you like you can turn off this
feature and risk having ambiguous puzzles. (Also, finding \e{all}
the possible solutions can be an additional challenge for an
advanced player.)

\C{cube} \i{Cube}

\cfg{winhelp-topic}{games.cube}

This is another one I originally saw as a web game. This one was a
Java game \k{cube-java-game}, by Paul Scott. You have a grid of 16
squares, six of which are blue; on one square rests a cube. Your move
is to use the arrow keys to roll the cube through 90 degrees so that
it moves to an adjacent square. If you roll the cube on to a blue
square, the blue square is picked up on one face of the cube; if you
roll a blue face of the cube on to a non-blue square, the blueness is
put down again. (In general, whenever you roll the cube, the two faces
that come into contact swap colours.) Your job is to get all six blue
squares on to the six faces of the cube at the same time. Count your
moves and try to do it in as few as possible. 

Unlike the original Java game, my version has an additional feature:
once you've mastered the game with a cube rolling on a square grid,
you can change to a triangular grid and roll any of a tetrahedron, an
octahedron or an icosahedron. 

\B{cube-java-game} \W{http://www3.sympatico.ca/paulscott/cube/cube.htm}\cw{http://www3.sympatico.ca/paulscott/cube/cube.htm}

\H{cube-controls} \i{Cube controls}

\IM{Cube controls} controls, for Cube
\IM{Cube controls} keys, for Cube
\IM{Cube controls} shortcuts (keyboard), for Cube

This game can be played with either the keyboard or the mouse.

Left-clicking anywhere on the window will move the cube (or other
solid) towards the mouse pointer.

The arrow keys can also used to roll the cube on its square grid in
the four cardinal directions.
On the triangular grids, the mapping of arrow keys to directions is
more approximate. Vertical movement is disallowed where it doesn't
make sense. The four keys surrounding the arrow keys on the numeric
keypad (\q{7}, \q{9}, \q{1}, \q{3}) can be used for diagonal movement.

(All the actions described in \k{common-actions} are also available.)

\H{cube-params} \I{parameters, for Cube}Cube parameters

These parameters are available from the \q{Custom...} option on the
\q{Type} menu.

\dt \e{Type of solid}

\dd Selects the solid to roll (and hence the shape of the grid):
tetrahedron, cube, octahedron, or icosahedron.

\dt \e{Width / top}, \e{Height / bottom}

\dd On a square grid, horizontal and vertical dimensions. On a
triangular grid, the number of triangles on the top and bottom rows
respectively.


\C{fifteen} \i{Fifteen}

\cfg{winhelp-topic}{games.fifteen}

The old ones are the best: this is the good old \q{\i{15-puzzle}}
with sliding tiles. You have a 4\by\.4 square grid; 15 squares
contain numbered tiles, and the sixteenth is empty. Your move is to
choose a tile next to the empty space, and slide it into the space.
The aim is to end up with the tiles in numerical order, with the
space in the bottom right (so that the top row reads 1,2,3,4 and the
bottom row reads 13,14,15,\e{space}).

\H{fifteen-controls} \i{Fifteen controls}

\IM{Fifteen controls} controls, for Fifteen
\IM{Fifteen controls} keys, for Fifteen
\IM{Fifteen controls} shortcuts (keyboard), for Fifteen

This game can be controlled with the mouse or the keyboard.

A left-click with the mouse in the row or column containing the empty
space will move as many tiles as necessary to move the space to the
mouse pointer.

The arrow keys will move a tile adjacent to the space in the direction
indicated (moving the space in the \e{opposite} direction).

(All the actions described in \k{common-actions} are also available.)

\H{fifteen-params} \I{parameters, for Fifteen}Fifteen parameters

The only options available from the \q{Custom...} option on the \q{Type}
menu are \e{Width} and \e{Height}, which are self-explanatory. (Once
you've changed these, it's not a \q{15-puzzle} any more, of course!)


\C{sixteen} \i{Sixteen}

\cfg{winhelp-topic}{games.sixteen}

Another sliding tile puzzle, visually similar to Fifteen (see
\k{fifteen}) but with a different type of move. This time, there is no
hole: all 16 squares on the grid contain numbered squares. Your move
is to shift an entire row left or right, or shift an entire column up
or down; every time you do that, the tile you shift off the grid
re-appears at the other end of the same row, in the space you just
vacated. To win, arrange the tiles into numerical order (1,2,3,4 on
the top row, 13,14,15,16 on the bottom). When you've done that, try
playing on different sizes of grid. 

I \e{might} have invented this game myself, though only by accident if
so (and I'm sure other people have independently invented it). I
thought I was imitating a screensaver I'd seen, but I have a feeling
that the screensaver might actually have been a Fifteen-type puzzle
rather than this slightly different kind. So this might be the one
thing in my puzzle collection which represents creativity on my part
rather than just engineering.

\H{sixteen-controls} \I{controls, for Sixteen}Sixteen controls

This game is played with the mouse. Left-clicking on an arrow will
move the appropriate row or column in the direction indicated.
Right-clicking will move it in the opposite direction.

(All the actions described in \k{common-actions} are also available.)

\H{sixteen-params} \I{parameters, for Sixteen}Sixteen parameters

The parameters available from the \q{Custom...} option on the
\q{Type} menu are:

\b \e{Width} and \e{Height}, which are self-explanatory.

\b You can ask for a limited shuffling operation to be performed on
the grid. By default, Sixteen will shuffle the grid in such a way
that any arrangement is about as probable as any other. You can
override this by requesting a precise number of shuffling moves to
be performed. Typically your aim is then to determine the precise
set of shuffling moves and invert them exactly, so that you answer
(say) a four-move shuffle with a four-move solution. Note that the
more moves you ask for, the more likely it is that solutions shorter
than the target length will turn out to be possible.


\C{twiddle} \i{Twiddle}

\cfg{winhelp-topic}{games.twiddle}

Twiddle is a tile-rearrangement puzzle, visually similar to Sixteen
(see \k{sixteen}): you are given a grid of square tiles, each
containing a number, and your aim is to arrange the numbers into
ascending order.

In basic Twiddle, your move is to rotate a square group of four
tiles about their common centre. (Orientation is not significant in
the basic puzzle, although you can select it.) On more advanced
settings, you can rotate a larger square group of tiles.

I first saw this type of puzzle in the GameCube game \q{Metroid
Prime 2}. In the Main Gyro Chamber in that game, there is a puzzle
you solve to unlock a door, which is a special case of Twiddle. I
developed this game as a generalisation of that puzzle.

\H{twiddle-controls} \I{controls, for Twiddle}Twiddle controls

To play Twiddle, click the mouse in the centre of the square group
you wish to rotate. In the basic mode, you rotate a 2\by\.2 square,
which means you have to click at a corner point where four tiles
meet.

In more advanced modes you might be rotating 3\by\.3 or even more at
a time; if the size of the square is odd then you simply click in
the centre tile of the square you want to rotate.

Clicking with the left mouse button rotates the group anticlockwise.
Clicking with the right button rotates it clockwise.

(All the actions described in \k{common-actions} are also available.)

\H{twiddle-parameters} \I{parameters, for Twiddle}Twiddle parameters

Twiddle provides several configuration options via the \q{Custom}
option on the \q{Type} menu:

\b You can configure the width and height of the puzzle grid.

\b You can configure the size of square block that rotates at a time.

\b You can ask for every square in the grid to be distinguishable
(the default), or you can ask for a simplified puzzle in which there
are groups of identical numbers. In the simplified puzzle your aim
is just to arrange all the 1s into the first row, all the 2s into
the second row, and so on.

\b You can configure whether the orientation of tiles matters. If
you ask for an orientable puzzle, each tile will have a triangle
drawn in it. All the triangles must be pointing upwards to complete
the puzzle.

\b You can ask for a limited shuffling operation to be performed on
the grid. By default, Twiddle will shuffle the grid so much that any
arrangement is about as probable as any other. You can override this
by requesting a precise number of shuffling moves to be performed.
Typically your aim is then to determine the precise set of shuffling
moves and invert them exactly, so that you answer (say) a four-move
shuffle with a four-move solution. Note that the more moves you ask
for, the more likely it is that solutions shorter than the target
length will turn out to be possible.


\C{rectangles} \i{Rectangles}

\cfg{winhelp-topic}{games.rectangles}

You have a grid of squares, with numbers written in some (but not all)
of the squares. Your task is to subdivide the grid into rectangles of
various sizes, such that (a) every rectangle contains exactly one
numbered square, and (b) the area of each rectangle is equal to the
number written in its numbered square.

Credit for this game goes to the Japanese puzzle magazine \i{Nikoli}
\k{nikoli-rect}; I've also seen a Palm implementation at \i{Puzzle
Palace} \k{puzzle-palace-rect}. Unlike Puzzle Palace's
implementation, my version automatically generates random grids of
any size you like. The quality of puzzle design is therefore not
quite as good as hand-crafted puzzles would be, but on the plus side
you get an inexhaustible supply of puzzles tailored to your own
specification.

\B{nikoli-rect} \W{http://www.nikoli.co.jp/puzzles/7/index_text-e.htm}\cw{http://www.nikoli.co.jp/puzzles/7/index_text-e.htm}

\B{puzzle-palace-rect} \W{http://www.puzzle.gr.jp/puzzle/sikaku/palm/index.html.en}\cw{http://www.puzzle.gr.jp/puzzle/sikaku/palm/index.html.en}

\H{rectangles-controls} \I{controls, for Rectangles}Rectangles controls

This game is played with the mouse.

Left-click any edge to toggle it on or off, or click and drag to draw
an entire rectangle (or line) on the grid in one go (removing any
existing edges within that rectangle).

When a rectangle of the correct size is completed, it will be shaded.

(All the actions described in \k{common-actions} are also available.)

\H{rectangles-params} \I{parameters, for Rectangles}Rectangles parameters

These parameters are available from the \q{Custom...} option on the
\q{Type} menu.

\dt \e{Width}, \e{Height}

\dd Size of grid, in squares.

\dt \e{Expansion factor}

\dd This is a mechanism for changing the type of grids generated by
the program. Some people prefer a grid containing a few large
rectangles to one containing many small ones. So you can ask
Rectangles to essentially generate a \e{smaller} grid than the size
you specified, and then to expand it by adding rows and columns.

\lcont{

The default expansion factor of zero means that Rectangles will
simply generate a grid of the size you ask for, and do nothing
further. If you set an expansion factor of (say) 0.5, it means that
each dimension of the grid will be expanded to half again as big
after generation. In other words, the initial grid will be 2/3 the
size in each dimension, and will be expanded to its full size
without adding any more rectangles.

Setting an expansion factor of around 0.5 tends to make the game
more difficult, and also (in my experience) rewards a less deductive
and more intuitive playing style. If you set it \e{too} high,
though, the game simply cannot generate more than a few rectangles
to cover the entire grid, and the game becomes trivial.

}

\dt \e{Ensure unique solution}

\dd Normally, Rectangles will make sure that the puzzles it presents
have only one solution. Puzzles with ambiguous sections can be more
difficult and more subtle, so if you like you can turn off this
feature and risk having ambiguous puzzles. Also, finding \e{all} the
possible solutions can be an additional challenge for an advanced
player. Turning off this option can also speed up puzzle generation.


\C{netslide} \i{Netslide}

\cfg{winhelp-topic}{games.netslide}

This game combines the grid generation of Net (see \k{net}) with the
movement of Sixteen (see \k{sixteen}): you have a Net grid, but
instead of rotating tiles back into place you have to slide them
into place by moving a whole row at a time. 

As in Sixteen, \I{controls, for Netslide}control is with the mouse.
See \k{sixteen-controls}.

\I{parameters, for Netslide}The available game parameters have similar
meanings to those in Net (see \k{net-params}) and Sixteen (see
\k{sixteen-params}).

Netslide was contributed to this collection by Richard Boulton.

\C{pattern} \i{Pattern}

\cfg{winhelp-topic}{games.pattern}

You have a grid of squares, which must all be filled in either black
or white. Beside each row of the grid are listed the lengths of the
runs of black squares on that row; above each column are listed the
lengths of the runs of black squares in that column. Your aim is to
fill in the entire grid black or white.

I first saw this puzzle form around 1995, under the name
\q{\i{nonograms}}. I've seen it in various places since then, under
different names.

Normally, puzzles of this type turn out to be a meaningful picture
of something once you've solved them. However, since this version
generates the puzzles automatically, they will just look like random
groupings of squares. (One user has suggested that this is actually
a \e{good} thing, since it prevents you from guessing the colour of
squares based on the picture, and forces you to use logic instead.)
The advantage, though, is that you never run out of them.

\H{pattern-controls} \I{controls, for Pattern}Pattern controls

This game is played with the mouse.

Left-click in a square to colour it black. Right-click to colour it
white. If you make a mistake, you can middle-click, or hold down
Shift while clicking with any button, to colour the square in the
default grey (meaning \q{undecided}) again.

You can click and drag with the left or right mouse button to colour
a vertical or horizontal line of squares black or white at a time
(respectively). If you click and drag with the middle button, or
with Shift held down, you can colour a whole rectangle of squares
grey.

(All the actions described in \k{common-actions} are also available.)

\H{pattern-parameters} \I{parameters, for Pattern}Pattern parameters

The only options available from the \q{Custom...} option on the \q{Type}
menu are \e{Width} and \e{Height}, which are self-explanatory.


\C{solo} \i{Solo}

\cfg{winhelp-topic}{games.solo}

You have a square grid, which is divided into square or rectangular
blocks. Each square must be filled in with a digit from 1 to the
size of the grid, in such a way that

\b every row contains only one occurrence of each digit

\b every column contains only one occurrence of each digit

\b every block contains only one occurrence of each digit.

You are given some of the numbers as clues; your aim is to place the
rest of the numbers correctly.

The default puzzle size is 3\by\.3 (a 9\by\.9 actual grid, divided
into nine 3\by\.3 blocks). You can also select sizes with
rectangular blocks instead of square ones, such as 2\by\.3 (a
6\by\.6 grid divided into six 3\by\.2 blocks).

If you select a puzzle size which requires more than 9 digits, the
additional digits will be letters of the alphabet. For example, if
you select 3\by\.4 then the digits which go in your grid will be 1
to 9, plus \cq{a}, \cq{b} and \cq{c}.

I first saw this puzzle in \i{Nikoli} \k{nikoli-solo}, although it's also
been popularised by various newspapers under the name \q{Sudoku} or
\q{Su Doku}.

\B{nikoli-solo} \W{http://www.nikoli.co.jp/puzzles/1/index_text-e.htm}\cw{http://www.nikoli.co.jp/puzzles/1/index_text-e.htm}

\H{solo-controls} \I{controls, for Solo}Solo controls

To play Solo, simply click the mouse in any empty square and then
type a digit or letter on the keyboard to fill that square. If you
make a mistake, click the mouse in the incorrect square and press
Space to clear it again (or use the Undo feature).

If you \e{right}-click in a square and then type a number, that
number will be entered in the square as a \q{pencil mark}. You can
have pencil marks for multiple numbers in the same square.

The game pays no attention to pencil marks, so exactly what you use
them for is up to you: you can use them as reminders that a
particular square needs to be re-examined once you know more about a
particular number, or you can use them as lists of the possible
numbers in a given square, or anything else you feel like.

To erase a single pencil mark, right-click in the square and type
the same number again.

All pencil marks in a square are erased when you left-click and type
a number, or when you left-click and press space. Right-clicking and
pressing space will also erase pencil marks.

(All the actions described in \k{common-actions} are also available.)

\H{solo-parameters} \I{parameters, for Solo}Solo parameters

Solo allows you to configure two separate dimensions of the puzzle
grid on the \q{Type} menu: the number of columns, and the number of
rows, into which the main grid is divided. (The size of a block is
the inverse of this: for example, if you select 2 columns and 3 rows,
each actual block will have 3 columns and 2 rows.)

You can also configure the type of symmetry shown in the generated
puzzles. More symmetry makes the puzzles look prettier but may also
make them easier, since the symmetry constraints can force more
clues than necessary to be present. Completely asymmetric puzzles
have the freedom to contain as few clues as possible.

Finally, you can configure the difficulty of the generated puzzles.
Difficulty levels are judged by the complexity of the techniques of
deduction required to solve the puzzle: each level requires a mode
of reasoning which was not necessary in the previous one. In
particular, on difficulty levels \q{Trivial} and \q{Basic} there
will be a square you can fill in with a single number at all times,
whereas at \q{Intermediate} level and beyond you will have to make
partial deductions about the \e{set} of squares a number could be in
(or the set of numbers that could be in a square). At
\q{Unreasonable} level, even this is not enough, and you will
eventually have to make a guess, and then backtrack if it turns out
to be wrong.

Generating difficult puzzles is itself difficult: if you select
\q{Intermediate} or \q{Advanced} difficulty, Solo may have to make
many attempts at generating a puzzle before it finds one hard enough
for you. Be prepared to wait, especially if you have also configured
a large puzzle size.


\C{mines} \i{Mines}

\cfg{winhelp-topic}{games.mines}

You have a grid of covered squares, some of which contain mines, but
you don't know which. Your job is to uncover every square which does
\e{not} contain a mine. If you uncover a square containing a mine,
you lose. If you uncover a square which does not contain a mine, you
are told how many mines are contained within the eight surrounding
squares.

This game needs no introduction; popularised by Windows, it is
perhaps the single best known desktop puzzle game in existence.

This version of it has an unusual property. By default, it will
generate its mine positions in such a way as to ensure that you
never need to \e{guess} where a mine is: you will always be able to
deduce it somehow. So you will never, as can happen in other
versions, get to the last four squares and discover that there are
two mines left but you have no way of knowing for sure where they
are.

\H{mines-controls} \I{controls, for Mines}Mines controls

This game is played with the mouse.

If you left-click in a covered square, it will be uncovered.

If you right-click in a covered square, it will place a flag which
indicates that the square is believed to be a mine. Left-clicking in
a marked square will not uncover it, for safety. You can right-click
again to remove a mark placed in error.

If you left-click in an \e{uncovered} square, it will \q{clear
around} the square. This means: if the square has exactly as many
flags surrounding it as it should have mines, then all the covered
squares next to it which are \e{not} flagged will be uncovered. So
once you think you know the location of all the mines around a
square, you can use this function as a shortcut to avoid having to
click on each of the remaining squares one by one.

If you uncover a square which has \e{no} mines in the surrounding
eight squares, then it is obviously safe to uncover those squares in
turn, and so on if any of them also has no surrounding mines. This
will be done for you automatically; so sometimes when you uncover a
square, a whole new area will open up to be explored.

All the actions described in \k{common-actions} are also available.

Even Undo is available, although you might consider it cheating to
use it. If you step on a mine, the program will only reveal the mine
in question (unlike most other implementations, which reveal all of
them). You can then Undo your fatal move and continue playing if you
like. The program will track the number of times you died (and Undo
will not reduce that counter), so when you get to the end of the
game you know whether or not you did it without making any errors.

(If you really want to know the full layout of the grid, which other
implementations will show you after you die, you can always use the
Solve menu option.)

\H{mines-parameters} \I{parameters, for Mines}Mines parameters

The options available from the \q{Custom...} option on the \q{Type}
menu are:

\dt \e{Width}, \e{Height}

\dd Size of grid in squares.

\dt \e{Mines}

\dd Number of mines in the grid. You can enter this as an absolute
mine count, or alternatively you can put a \cw{%} sign on the end in
which case the game will arrange for that proportion of the squares
in the grid to be mines.

\lcont{

Beware of setting the mine count too high. At very high densities,
the program may spend forever searching for a solvable grid.

}

\dt \e{Ensure solubility}

\dd When this option is enabled (as it is by default), Mines will
ensure that the entire grid can be fully deduced starting from the
initial open space. If you prefer the riskier grids generated by
other implementations, you can switch off this option.


\C{samegame} \i{Same Game}

\cfg{winhelp-topic}{games.samegame}

You have a grid of coloured squares, which you have to clear by 
highlighting contiguous regions of more than one coloured square;
the larger the region you highlight, the more points you get (and
the faster you clear the arena).

If you clear the grid you win. If you end up with nothing but 
single squares (i.e., there are no more clickable regions left) you
lose.

Removing a region causes the rest of the grid to shuffle up:
blocks that are suspended will fall down (first), and then empty
columns are filled from the right. 

The game generator does not try to guarantee soluble grids;
it will, however, ensure that there are at least 2 squares of each 
colour on the grid at the start (and will forbid custom grids for which
that would be impossible).

Same Game was contributed to this collection by James Harvey.

\H{samegame-controls} \i{Same Game controls}

\IM{Same Game controls} controls, for Same Game
\IM{Same Game controls} keys, for Same Game
\IM{Same Game controls} shortcuts (keyboard), for Same Game

This game can be played with either the keyboard or the mouse.

If you left-click an unselected region, it becomes selected (possibly
clearing the current selection). 

If you left-click the selected region, it will be removed (and the
rest of the grid shuffled immediately).

If you right-click the selected region, it will be unselected. 

The cursor keys move a cursor around the grid. Pressing the Space or
Enter keys while the cursor is in an unselected region selects it;
pressing Space or Enter again removes it as above.

\H{samegame-parameters} \I{parameters, for Same Game}Same Game parameters

These parameters are available from the \q{Custom...} option on the
\q{Type} menu.

\dt \e{Width}, \e{Height}

\dd Size of grid in squares.

\dt \e{No. of colours}

\dd Number of different colours used to fill the grid; the more colours,
the fewer large regions of colour and thus the more difficult it is to
successfully clear the grid.

\dt \e{Scoring system}

\dd Controls the precise mechanism used for scoring. With the default
system, \q{(n-2)^2}, only regions of three squares or more will score
any points at all. With the alternative \q{(n-1)^2} system, regions of
two squares score a point each, and larger regions score relatively
more points.


\C{flip} \i{Flip}

\cfg{winhelp-topic}{games.flip}

You have a grid of squares, some light and some dark. Your aim is to
light all the squares up at the same time. You can choose any square
and flip its state from light to dark or dark to light, but when you
do so, other squares around it change state as well.

Each square contains a small diagram showing which other squares
change when you flip it.

\H{flip-controls} \i{Flip controls}

\IM{Flip controls} controls, for Flip
\IM{Flip controls} keys, for Flip
\IM{Flip controls} shortcuts (keyboard), for Flip

This game can be played with either the keyboard or the mouse.

Left-click in a square to flip it and its associated squares, or
use the cursor keys to choose a square and the space bar or Enter
key to flip.

If you use the \q{Solve} function on this game, it will mark some of
the squares in red. If you click once in every square with a red
mark, the game should be solved. (If you click in a square
\e{without} a red mark, a red mark will appear in it to indicate
that you will need to reverse that operation to reach the solution.)

\H{flip-parameters} \I{parameters, for flip}Flip parameters

These parameters are available from the \q{Custom...} option on the
\q{Type} menu.

\dt \e{Width}, \e{Height}

\dd Size of grid in squares.

\dt \e{Shape type}

\dd This control determines the shape of the region which is flipped
by clicking in any given square. The default setting, \q{Crosses},
causes every square to flip itself and its four immediate neighbours
(or three or two if it's at an edge or corner). The other setting,
\q{Random}, causes a random shape to be chosen for every square, so
the game is different every time.


\C{guess} \i{Guess}

\cfg{winhelp-topic}{games.guess}

You have a set of coloured pegs, and have to reproduce a
predetermined sequence of them (chosen by the computer) within a
certain number of guesses. 

Each guess gets marked with the number of correctly-coloured pegs
in the correct places (in black), and also the number of
correctly-coloured pegs in the wrong places (in white). 

This game is also known (and marketed, by Hasbro, mainly) as
a board game \q{Mastermind}, with 6 colours, 4 pegs per row, and 10 guesses.
However, this version allows custom settings of number of colours
(up to 10), number of pegs per row, and number of guesses. 

Guess was contributed to this collection by James Harvey.

\H{guess-controls} \i{Guess controls}

\IM{Guess controls} controls, for Guess
\IM{Guess controls} keys, for Guess
\IM{Guess controls} shortcuts (keyboard), for Guess

This game can be played with either the keyboard or the mouse.

With the mouse, drag a coloured peg from the tray on the left-hand
side to its required position in the current guess; pegs may also be
dragged from current and past guesses to copy them elsewhere. To
remove a peg, drag it off its current position to somewhere invalid.

Right-clicking in the current guess adds a \q{hold} marker; pegs
that have hold markers will be automatically added to the next guess
after marking.

Alternatively, with the keyboard, the up and down cursor keys can be
used to select a peg colour, the left and right keys to select a
peg position, and the space bar or Enter key to place a peg of the
selected colour in the chosen position. \q{D} or Backspace removes a
peg, and \q{H} adds a hold marker.

When the guess is complete, the smaller feedback pegs will be highlighted;
clicking on these (or moving the peg cursor to them with the arrow keys
and pressing the space bar or Enter key) will mark the current guess,
copy any held pegs to the next guess, and move the \q{current guess}
marker.

If you correctly position all the pegs the solution will be displayed
below; if you run out of guesses (or select \q{Solve...}) the solution
will also be revealed.

\H{guess-parameters} \I{parameters, for Guess}Guess parameters

These parameters are available from the \q{Custom...} option on the
\q{Type} menu. The default game matches the parameters for the 
board game \q{Mastermind}. 

\dt \e{Colours}

\dd Number of colours the solution is chosen from; from 2 to 10
(more is harder).

\dt \e{Pegs per guess}

\dd Number of pegs per guess (more is harder).

\dt \e{Guesses}

\dd Number of guesses you have to find the solution in (fewer is harder).

\dt \e{Allow blanks}

\dd Allows blank pegs to be given as part of a guess (makes it easier, because
you know that those will never be counted as part of the solution). This
is turned off by default. 

Note that this doesn't allow blank pegs in the solution; if you really wanted
that, use one extra colour.

\dt \e{Allow duplicates}

\dd Allows the solution (and the guesses) to contain colours more than once;
this increases the search space (making things harder), and is turned on by
default.


\C{pegs} \i{Pegs}

\cfg{winhelp-topic}{games.pegs}

A number of pegs are placed in holes on a board. You can remove a
peg by jumping an adjacent peg over it (horizontally or vertically)
to a vacant hole on the other side. Your aim is to remove all but one
of the pegs initially present.

This game, best known as \q{Peg Solitaire}, is possibly one of the
oldest puzzle games still commonly known.

\H{pegs-controls} \i{Pegs controls}

\IM{Pegs controls} controls, for Pegs

To move a peg, drag it with the mouse from its current position to
its final position. If the final position is exactly two holes away
from the initial position, is currently unoccupied by a peg, and
there is a peg in the intervening square, the move will be permitted
and the intervening peg will be removed.

Vacant spaces which you can move a peg into are marked with holes. A
space with no peg and no hole is not available for moving at all: it
is an obstacle which you must work around.


\H{pegs-parameters} \I{parameters, for Pegs}Pegs parameters

These parameters are available from the \q{Custom...} option on the
\q{Type} menu.

\dt \e{Width}, \e{Height}

\dd Size of grid in holes.

\dt \e{Board type}

\dd Controls whether you are given a board of a standard shape or a
randomly generated shape. The two standard shapes currently
supported are \q{Cross} and \q{Octagon} (also commonly known as the
English and European traditional board layouts respectively).
Selecting \q{Random} will give you a different board shape every
time (but always one that is known to have a solution).


\C{dominosa} \i{Dominosa}

\cfg{winhelp-topic}{games.dominosa}

A normal set of dominoes has been arranged irregularly into a
rectangle; then the number in each square has been written down and
the dominoes themselves removed. Your task is to reconstruct the
pattern by arranging the set of dominoes to match the provided array
of numbers.

This puzzle is widely credited to O. S. Adler, and takes part of its
name from those initials.

\H{dominosa-controls} \i{Dominosa controls}

\IM{Dominosa controls} controls, for Dominosa

Left-clicking between any two adjacent numbers places a domino
covering them, or removes one if it is already present. Trying to
place a domino which overlaps existing dominoes will remove the ones
it overlaps.

Right-clicking between two adjacent numbers draws a line between
them, which you can use to remind yourself that you know those two
numbers are \e{not} covered by a single domino. Right-clicking again
removes the line.


\H{dominosa-parameters} \I{parameters, for Dominosa}Dominosa parameters

These parameters are available from the \q{Custom...} option on the
\q{Type} menu.

\dt \e{Maximum number on dominoes}

\dd Controls the size of the puzzle, by controlling the size of the
set of dominoes used to make it. Dominoes with numbers going up to N
will give rise to an (N+2) \by (N+1) rectangle; so, in particular,
the default value of 6 gives an 8\by\.7 grid.

\dt \e{Ensure unique solution}

\dd Normally, Dominosa will make sure that the puzzles it presents
have only one solution. Puzzles with ambiguous sections can be more
difficult and sometimes more subtle, so if you like you can turn off
this feature. Also, finding \e{all} the possible solutions can be an
additional challenge for an advanced player. Turning off this option
can also speed up puzzle generation.


\A{licence} \I{MIT licence}\ii{Licence}

This software is \i{copyright} 2004-2005 Simon Tatham.

Portions copyright Richard Boulton and James Harvey.

Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation files
(the "Software"), to deal in the Software without restriction,
including without limitation the rights to use, copy, modify, merge,
publish, distribute, sublicense, and/or sell copies of the Software,
and to permit persons to whom the Software is furnished to do so,
subject to the following conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

\IM{specific} \q{Specific}, menu option
\IM{custom} \q{Custom}, menu option

\IM{game ID} game ID
\IM{game ID} ID, game
\IM{ID format} ID format
\IM{ID format} format, ID
\IM{ID format} game ID, format

\IM{keys} keys
\IM{keys} shortcuts (keyboard)

\IM{initial state} initial state
\IM{initial state} state, initial

\IM{MIT licence} MIT licence
\IM{MIT licence} licence, MIT