This is an exercise in optimizing data access algorithms (patterns),
domain specific data representations, and code microarchitecture.
Optimization results are obvious, considering the calculation efforts
needed for larger figures.
Some considerations about symmetry have been done as well.
Recursive patterns
A recursive approach is to construct figures from a smaller
figure set, and that one from an even smaller set etc., e.g. size 4
from size 3 from size 2 from size 1 (a single square).
The sqfig program implements this pattern.
Non-recursive patterns
A non-recursive approach is to generate all square patterns
populating a certain area, and check the candidates for the wanted
properties (e.g. connectivity), to get the solution set.
The sqfigb program implements this pattern.
Figure generating patterns
The figures in question (e.g. sqfig #2.1.2 in the first sample
below) can be calculated by the accompanying program
(sqfig,
provided as source and binary), invoked with that figure specification
(#2.1.2) as a program argument.
Generating larger figures by adding a square
This sample of adding a square starts with the simplest figure
(sqfig #1.1.1
º
sqfig #1.1
º
sqfig #1), one square sized (leaving away the degenerate case of an
empty, square-less, figure [sqfig #0]).
The square in question can of course be added on any figure's edge that
is not yet connected to a an existing square, sometimes resulting, based
on the figure's symmetry, in duplicate results.
[A source figure's symmetry could be considered, to suppress
some duplicate result generation, but since most figures are
rather asymmetrical, the gain would be small; and the duplicate
result reduction step can't be left away due to duplicate results
generated from unrelated source figures.]
+--+ | | | | +--+ | | | | +--+sqfig #2.1.2 | ||||
| | ||||
+--+--+ | | | | | | +--+--+sqfig #2.1.1 | ¬ |
+--+ | | | | +--+sqfig #1 | ® |
+--+--+ | | | | | | +--+--+sqfig #2.1.1 |
| ¯ | ||||
+--+ | | | | +--+ | | | | +--+sqfig #2.1.2 |
+--+ | | | | +--+--+ | | | | | | +--+--+sqfig #3.2.1 | ¬ |
+--+--+ | | | | | | +--+--+ | | | | +--+sqfig #3.2.3 |
| ¯ | | |
+--+ | | | | +--+--+ | | | | | | +--+--+sqfig #3.2.2 | ® |
+--+--+ | | | | | | +--+--+ | | | | +--+sqfig #3.2.4 |
+--+--+ | | | | | | +--+--+--+ | | | | | | +--+--+sqfig #4.5.1 | « |
+--+ | | | | +--+--+ | | | | | | +--+--+ | | | | +--+sqfig #4.5.2 |
Sample siblings eight-tuple (sqfig #5.8), obtained by mirror
and rotation operations:
+--+ +--+ +--+ +--+
| | | | | | | |
| | | | | | | |
+--+ +--+--+ +--+ +--+--+
| | | | | | | | | |
| | | | | | | | | |
+--+--+ +--+--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+--+
| | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+ +--+--+--+--+ +--+--+ +--+ +--+--+--+--+ +--+--+ +--+ +--+--+--+--+
| | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | |
+--+--+--+ +--+--+ +--+ +--+ +--+--+--+ +--+ +--+ +--+--+
sqfig #5.8
Tilings
Some of the figure sets (e.g. the distinct figure set of size 5
[pentominoes]) produce rectangular tilings (some of the others don't;
e.g. with size 4 [of all the #4 figures, only figure #4.3 has a parity
disbalance, which makes it impossible to fit them into a rectangle]).
+--------+--+--------+--------+
| | | | |
| | | | |
| +--+--+ +--+ +--+ +-----+
| | | | | | |
| | | | | | |
| | +--+ +--+ +-----+ +--+
| | | | | | | | |
| | | | | | | | |
+--+--+ +--+ +--+ +--+ | |
| | | | | | |
| | | | | | |
| +--+--+ +--+ +--+--+ |
| | | | | |
| | | | | |
+--------+-----+ +-----+--+ |
| | | |
| | | |
+--------------+-----------+--+
first size 5 10*6 tiling
Continuous tilings
Some of the figure sets do not produce tilings that fit into a
single rectangle cell, but in more than one cell.
Such tilings can be used all the same to tile larger areas, just the
edges will pose problems.
.--+--------+--. . | | . . | | . +--+--+ +--+ | | | | | | | | | | +--+-----+ | | | | | | +-----+-----+ | | | | | | | +-----------+--+ | º |
+--------+-----+ | | | | | | +--+--+ +--+ +--+ | | | | | | | | | +--+-----+ | | | | | | +-----+-----+ | | | | | | | +-----------+--+ |
A sample of a more irregular shaped continuous tiling:
+--------+--+-----+
| | | |
| | | |
+--+--+ +--+ +--+ +--+-----+
| | | | | | |
| | | | | | |
+--+ | +--+ +--+ | +--+ +--+
| | | | | | | |
| | | | | | | |
| +--+ +--+--+--+ +--+--+ |
| | | | | | |
| | | | | | |
+-----+ +--+ +-----+ +--+
| | | | |
| | | | |
+-----+--------+ +--------+--+-----+
| | | |
| | | |
+--------------+--------+--+ +-----+
| |
| |
+-----------+
first size 5 10*6 continuous tiling
Note that size 3 doesn't even produce continuous tilings, but different
(in this cases rotamere) tilings can be annealed to give a rectangular
cell:
+--+--------+-----+
| | | |
| | | |
| +--+-----+--+ |
| | | |
| | | |
+-----+--------+--+
two annealed size 3 tilings
Order
An order in enumerating squares, figures, tilings, etc is needed for
program data structures (e.g. primary index, for fast search).
This order can be achieved by specifying compare methods for these
entities.
The compare methods for larger entities may build on those for smaller
ones.
A square may be seen as a two letter word out of an alphabet consisting of non-negative integer numbers. The compare methods for a square will typically define {0,0} < {1,1}. Since two coordinates [X and Y] are involved with a square, a precedence needs to be defined, e.g. Y over X, which defines {1,0} < {0,1}. [This can be seen as the X coordinate being represented by the least significant bits.]
A figure may be seen as an ordered word of squares, the size of the figure being the length of the word. Comparing two figures will compare the figures' squares stepwise until a difference is found. That difference (i.e. the first distinct square) defines the figure order. One may define that if the figures have different size and are the same up to the shorter size: smaller figure < larger figure. [Such an approach may be seen as a generalized string compare algorithm.]
A tiling may be seen analogously, as a word of figures. A figure's first square (defined by the square compare method, see above) defines the figure's position in the 'figure word'.
Such models are independent of symmetry properties (e.g. rotameres need
not have neighborhood property in this ordering scheme).
This may make the computationally fundamental part of ordering simpler
and more performant.
Symmetry
Several considerations about figures' and tilings' symmetries
will reduce the result sets (and hence make enumeration
counts more interesting) and reduce the search space
(which is very performance relevant with the backtracking algorithms).
Tiling symmetry
Tilings with pieces of size 4 or greater can't have symmetry
axes, since there is always at least one non-symmetric tiling piece,
e.g. the L-shaped one, which can't be reflected
by any axis.
So the number of solutions in these cases is always a multiple of four
[to get the number of distinct solutions, one might
{alternatively} count all solutions and divide that count by
4 (which would be slower though)].
Solution reduction is usually enforced by confining a specified piece to a board's specified quadrant. If that piece lies on a board's symmetry axis and itself is symmetrical to that axis (as the I-shaped {first} piece is), a second piece must be considered, and so on. Since the second piece is usually the asymmetric L-shaped piece, this search won't go too far.
A flexible algorithm may chose to keep indices for the X and Y symmetry indicating up to which piece symmetry is maintained.
The quadrant calculation can be done by means of calculating a piece's
pivot (center of mass/gravity), which is a quite cheap operation, that
can be done while checking whether the piece fits into the
target position.
If a pivot lies on the axis in question, typically some knowledge of the
piece's symmetry is assumed (for performance).
It is however not mandatory that partial tiling solutions (generated in
the context of assembling tilings) exist that trigger a check for a
second piece's pivot (and tests have shown that with the chosen
search strategy, the size 5 tiling search doesn't trigger such a case).
Continuous tiling origin
The origin in a continuous tiling can be chosen ad liberate, so a
solution can be translated to any of the board's positions.
The e.g. 640 solutions of a 4*5 continuous tiling are reduced by factor
20 (which is the total number of positions in a 4*5 board) to 32 by
'freezing' a specified piece (the first one, for convenience)
to the zero position.
These 32 solutions are further reduced by factor 4 by freezing another
piece's (the second, for convenience, which must be and is asymmetric)
layout to 2 of 8 rotameres/mirrors.
Bitmaps
A different approach for figure generation is based on reducing the set
of possible bitmaps of n pixels in a n*n
area.
The comb(n*n,n) bitmap patterns [e.g. comb(25,5) = 53130
bitmaps with 5 pixels] are reduced (filtered) to the properly connected
bitmaps [e.g. 63 for pentominoes].
Symmetry considerations lead to the number of distinct figures [e.g. 12
pentominoes].
Output encodings
Different encodings for figure and tiling output have been
implemented.
Among these encodings are found:
plain ASCII encoding
(using -, |, +;
see
this;
or using only _, |
[suited for very compact representation];
see
this),
Terminal font encoding
(using textual-graphic characters,
which is similar to ASCII encoding, offering more special codes
such as the four corners and graphically better suited codes
such as a longer dash code [however less portable];
see this),
and
HTML encoding
(using [XBM] [bitmap] images and (optionally) HTML
tables;
see
this).
Possible additional encodings that are not implemented include:
[embedded] PostScript output,
PDF output (simplified, evaluated PostScript),
SVG,
and
bitmap image representations (raw, GIF, PNG, ...).
Terminologies
These figures constructed from squares joined side by side are
used to be called polyominoes.
The size specific polyomino names are monomino, domino,
tromino/triomino, tetromino, pentomino, hexomino, and so on.
Mathematically, they are sometimes referred to as
n-ominoes.
Lattice animal is yet another name for a polyomino (animal
being the term for a sphere's topological equivalent; see links for even
more terminologies).
Of the polyominoes, only distinct sets of size 1, 2, and 5 polyominoes can be arranged into a rectangle. Size 4 and 6 polyominoes have parity disbalances (if the pieces are checkered, there will always be more of one color, so they can't fit a [balanced] rectangle). Sets of polyominoes of size 7 and larger will contain pieces with cavities which cannot be filled by neighbor figures (and hence cannot be used to fill integral shapes; see links for solutions for non-integral shapes, etc).
Pentominoes (size 5 polyominoes) are often used as puzzles. The puzzle problem may be to tile all of the (12) pentominoes or a subset into a rectangle or some other shape.
There is also a nomenclature for the pentomino pieces based on their resemblance to latin letters (see this). The mapping is {F, I, L, N, P, T, U, V, W, X, Y, Z} to {#5.9, #5.1, #5.2, #5.8, #5.4, #5.7, #5.5, #5.6, #5.10, #5.12, #5.3, #5.11}. Yet another mapping seems to be {O, P, Q, R, S, T, U, V, W, X, Y, Z} to {#5.1, #5.4, #5.2, #5.9, #5.8, #5.7, #5.5, #5.6, #5.10, #5.12, #5.3, #5.11}.
Building figures out of triangles or hexagons (instead of squares) e.g. leads to polyiamonds and polyhexes.
[Info thanks to the many web pages about this topic!
(Some of them can be found
here.)]
Ideas implemented
Many aspects were considered to cut down calculation overheads, e.g.
in search strategies and temporary memory allocation.
;-)
-encoding:
Chose the appropriate output encoding.
Output goes to standard-output.
See the summary usage information (-? option) for available
encodings.
Default is ASCII.
-imagesize (html-with-images encoding):
Specify image sizes put into HTML output.
Default is 8.
-imagesuffix (html-with-images encoding):
Specify image files suffix.
Default is .xbm.
-local (html-with-images encoding):
Use local, relative image references in HTML output.
-plotsize:
Specify square edge size.
Default is 3.
Shortcut would be -3.
[See the application's summary usage information
(application -?)
for options' applicability.]
sqfig usage
See the many samples above for the
sqfig size[.number[.sibling]] usage.
sqfig -? will provide summary usage information:
usage:
sqfig
[-encoding {ASCII, underscores, Terminal-font, html-with-images}
[-imagesize <size>]
[-imagesuffix <suffix>]
[-local]]
[-plotsize <size>|-<size>]
[{-counts|-plots|-texts}
[<uppersize>]]
[<size>[.<number>[.<sibling>]] ...]
See the common options too.
-counts:
Calculate and display figure counts.
An upper size (exclusive) can be specified.
-plots:
Enumerate and plot figures.
An upper size (exclusive) can be specified.
[See also -encoding.]
-texts:
Enumerate figures and print their textual representation.
An upper size (exclusive) can be specified.
size
or
size.number
or
size.number.sibling:
Plot specified figure lists / sibling lists / figures
(more than one can be specified).
Sample:
sqfig -counts:
figure size 0: 0 figures (0 distincts)
figure size 1: 1 figures (1 distincts)
figure size 2: 2 figures (1 distincts)
figure size 3: 6 figures (2 distincts)
figure size 4: 19 figures (5 distincts)
figure size 5: 63 figures (12 distincts)
figure size 6: 216 figures (35 distincts)
figure size 7: 760 figures (108 distincts)
figure size 8: 2725 figures (369 distincts)
figure size 9: 9910 figures (1285 distincts)
...
sqtile usage
sqtile -? will provide summary usage information:
usage:
sqtile
[-continuous]
[-counts]
[-encoding {ASCII, Terminal-font, html-with-images}
[-imagesize <size>]
[-imagesuffix <suffix>]
[-local]]
[-plotsize <size>|-<size>]
[-skipsymmetrical]
[-size <size>
[-x <size>]]
See the common options too.
-continuous:
Continuously tile,
i.e. pieces can be laid out to be split on two tiling areas.
Produces many more solutions.
-counts:
Calculate and display tiling counts.
[See also -skipsymmetrical.]
-skipsymmetrical:
Skip (ignore) symmetrical tiling solutions.
This will usually cut the number of solutions by factor 4.
-size:
Do the tilings for a specified figure size.
-x:
Do the tilings for a specified X dimension size.
Smaller X are found faster.
[-size option is required.]
Sample:
sqtile -counts -skipsymmetrical -size 5:
figure size 5: 1*60 board: 0 distinct tilings
figure size 5: 2*30 board: 0 distinct tilings
figure size 5: 3*20 board: 2 distinct tilings
figure size 5: 4*15 board: 368 distinct tilings
figure size 5: 5*12 board: 1010 distinct tilings
figure size 5: 6*10 board: 2339 distinct tilings
sqfigb usage
sqfigb (the non-recursive approach) does counts
only.
sqfigb works with bitmaps and has modest memory
requirements, since the generated figures are not kept in
memory and are not needed for symmetry considerations, etc.
Copyright Notice and Disclaimer
Copyright (C) 2003 Eric Laroche. All rights reserved. This program is free software; you can redistribute it and/or modify it. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
-local option)
Use any convenient tool, like unzip, pkunzip, winzip or
Java's jar with an xf argument.
How do I convert the sources for my Unix system?
E.g. with vi: :%s/C-vC-m//C-m where
C-V e.g. means pressing the Control key
together with the v key.
How can I properly use the # character on my Unix system shell?
Either quote it (\#) or leave it away (sqfig
too works without it).
Is there something wrong with plotsize 1?
Yes. Using plotsize 1 (and [the default] ASCII output encoding) you can't tell whether certain lines are connected or not. This is the case if there is a one square sized concavity, as e.g. in #5.5.1, which is, plotted in size 1, not distinguishable from #6.12.1. Anyway, it makes sense to have this representation for the unproblematic cases (and the non-ASCII encodings); it is left to the user not to use plotsize 1 plots in inappropriate cases. Plotsize 0 however is ok, since in that special cases, not the squares' borders but their contents are plotted.
Is there something wrong with
-encoding underscores -plotsize 1?
Yes.
Since the underscores encoding doesn't paint the vertices and
plotsize 1 does only show vertices, the
-encoding underscores -plotsize 1 output is empty (only
newlines).
Why is the underscores encoding not supported by
sqtile?
This is an implementation problem. The intermediate line-merger used in the underscores encoding is not appropriate for tilings. As tilings don't separate each cell, the line-merger can't merge/purge all lines that need to be. This leads to Y dimensions stretched at some locations (i.e. looks quite ok but has subtle errors). There's no place for hatching (as e.g. used in the sqtile backtracking visualization) in this condensed representation too.
How did you get the smoother output as e.g. found here?
Use the -encoding Terminal-font option.
Are there seemingly duplicate sqtile continuous tiling outputs?
Yes. E.g. figure size 2 tilings allow two tiling cell layouts: the figure contained in the cell and the figure split on two cells. The latter is unfortunately not distinguished by the plot function / tiling representation.
Are there other problems present with continuous tiling plots?
Yes. Since the plot function has no connectivity information (see question above), any piece that is split on two tiling cells while the two parts touch (i.e. the pieces go 'thru' the tiling), misses the border between the parts. This is a problem too with tilings consisting of pieces larger than size 2. A contrary problem does arise e.g. with figure #5.5.1 (U-shaped size 5 piece) in some 3*20 continuous tilings: this time a dotted border is drawn instead of a solid border, for reasons of weak connectivity heuristics.
I don't have permanent network connectivity; where can the bitmaps
for the html-with-images encoding be found?
Here.
(See also this document's sources section.)
[-local option is required]
How can I visualize the tiling backtracking algorithm?
Provide the plotter routine as info callback arguments
['forward' and/or 'back' callback argument] in the
tilingEngine() call
(see e.g. this for the
[unsucessful] size 4 4*5 [non-continuous] backtracking).
Is the backtracking performance better with small X dimension or large X dimension?
The backtracking algorithm is faster with small X dimensions. Rows get filled first and filling small rows reveals unfillable cavities earlier, which leads to earlier backtracking, which is much faster than back tracking late.
Why don't you exchange the X/Y dimensions when calculating solutions for e.g. a 12*5 board instead of a 5*12 board, to make things much faster?
Although it runs much slower, the user controls (let-the-user-decide pattern). This can be used to e.g. illustrate the different run times. In 'automatic' mode (without X dimension option), suppressing symmetrical solutions, larger Xs than Ys are not used.
Why don't you use recursive functions in the backtracking algorithm (as often seen)?
Recursive functions are avoided to be able to (potentially) solve tilings with a larger number of pieces (that e.g. however have a lean solution path tree to run in reasonable time), while preventing stack overflows.
Parts of the algorithm descriptions in this page are a bit unclear, is more information available?
Yes, the program code source is the ultimate reference; it's reasonably documented too.
Are the programs' makefiles portable?
Not really. But they're not very complex, easy to port.
Can you explain the compiler flags used in the
makefiles?
Yes:
-nologo
suppresses the copyright information banner found in some compilers
[to make the compiler output more terse and errors/warnings more easily
spottable];
-W4
sets maximal warning level
[as should be, see
C coding
guidelines];
-Za
ensures ANSI/ISO-C compatibility
[helps to avoid non-portabilities];
-GF
uses read-only literal string pooling
[lessens the program's image size and also helps to avoid
non-portabilities];
-MD
uses dynamic C-library
[lessens the program's image size];
-link -incremental:no
suppresses incremental linking
[lessens the program's image size and suppresses irrelevant warnings];
-O2
optimizes for speed (note: not maximal optimization is
chosen, for the sake of stability)
[makes things faster and lessens the program's image size];
-DOPTIM32
defines the OPTIM32 macro to include optimized code (that
is only implemented for 32-bit platforms)
[makes things faster];
(optional)
-Zi
includes debug information
[to debug/test];
Why don't you use libraries (of object files) instead of object file references?
To keep the build process simple.
Do you expect identifier names namespace problems?
Yes, likely.
Software development in C
will likely lead to
namespace
problems.
Some identifiers have a prefix (e.g. sqsearch),
some have a postfix (e.g. putenvx),
some don't have either (e.g. getFigureSet),
but even using these rather small prefixes consequently
wouldn't guarantee to solve the namespace problems (see link too).
As the program sources are provided, it will be easy and
convenient to adapt to such problems (otherwise the adapter
software pattern would have to be applied).
What is missing?
arbitrary shapes to be tiled
[with e.g. index -2 meaning not-part-of-the-board];
tiling with double sets / etc of figures
[produces e.g. solutions for #4];
user specified shapes and figure sets;
even more elaborated board state resetting in backtrack steps
(sqfigb);
Where do I send bug reports to?
To laroche@lrdev.com.
There will however be no reward for it.
;-)
Can I link to this page?
Yes. Please feel free to do so.
Can I get update notifications?
Yes.
Drop a mail to laroche@lrdev.com and I'll send you
notifications when this page (and affiliated pages) is updated.
Drop a mail too if you don't want to receive these notifications
anymore.
Links
sqtile generated samples.sqtile (-encoding html-with-images)
generated samples.