Backtrack v2.3
--------------
Invented and implemented by Karl Scherer, December 2001.
Updated December 29, 2001: accelerated search.


Object: Automatically fill any shape with a given polysquare tile.
Watch the operation of a backtracking program in action
and enjoy the solutions it comes up with!
(Several customizable variants for each of the options.)

The selection screen offers you a choice of 12 polysquares.
Select a polysquare to start the corresponding game.
You will be shown a playing area that the computer will try to fill. 

To start, click the playing area.
Zillions will AUTOMATICALLY tile the area without gaps or overlaps
using copies of the given polysquare.

YOU CAN GIVE THE COMPUTER ANY SHAPE MADE FROM SQUARES.
(You can REDESIGN the fill-area very quickly and easily,
either by deleting or adding new positions via 
selecting 'empty' or 'T0' with your right mouse button
or by changing the board setup in the rules file.) 
 
THE PROGRAM WILL DO EVERYTHING ELSE FULLY AUTOMATICALLY!

Given a shape and a tile to fill it with, in general it is not known
whether such a tiling problem has a solution.
'Backtrack' gives you the answers and lets you watch as the computer
plays with the tiles.
 
The game demonstrates tree search by backtracking.
You can invent new puzzles all the time and - best of all - 
let Zillions solve them automatically and in front of your eyes.
If it cannot place a tile, the program tries to rearrange the tile
previously placed and so on.
There is even some 'intelligence' build in.
E.g., if the computer finds an isolated unoccupied square anywhere
on the board, it will backtrack and try other possibilities for 
placing a tile.
Furthermore, some options have tile-specific optimisation routines
built in, which have the effect that not all possible orientations
will actually be tried out.
Such optimisations can be very easily created for any tile.
(If you change to code to improve it, remember that this zrf is designed
for ANY given shape to be filled, not only for rectangles!) 

The system will stop (win) when it has found a tiling,
and also stop (lose) if there is no tiling for the given shape. 

Please note that most options have several variants.
Also note that there are three alternative piece sets available.
You can speed up the game by switching the sound off.


The backtracking method is an essential tool for systematically
solving tiling puzzles and many other problems. 
The search path on the board is also important.
This game 'Backtrack' uses a meandering path, filling one file from top to bottom,
the next file from bottom to top and so on.

 
See also the Zillions games 'Reptiles', 'Y-primes', 'Pento' and 'Y-pento'
for related polysquare problems.

Background design: fractal T011001L by the author.


More freeware and real puzzles and games at my homepage: karl.kiwi.gen.nz .


----------------------------------------------------------------
To play:

Double click the Backtrack icon, or

1. Run "Zillions of Games"
2. Choose "Open Game Rules..." from the File menu
3. Select "Backtrack.zrf" in the Open dialog and click "Open"

Backtrack.zrf is a rules file used by the Windows program
"Zillions of Games".  Zillions of Games allows you to play any
number of games against the computer or over the Internet.
Zillions of Games can be purchased online.  For more information
please visit the Zillions of Games website
              <http://www.zillions-of-games.com> 

 
