# Downloads

## Bouwkamp code

Squared rectangles and squared squares are often represented in a concise form known as Bouwkamp code (or Bouwkampcode), named after C.J. Bouwkamp who invented this notation and popularised its use. Bouwkamp code consists of a string of numbers giving firstly the number of squares in the dissection (called the Order), the width and height of the square dissection, where width >= height, and finally the sizes of the squares of the tiling, often called the elements, as integers e1, e2, e3, ... en (with or without parentheses or commas), which are arranged from left to right and then top to bottom in quite an extensive method of identification.

In the published literature parentheses and commas are used to group consecutive squares in a horizontal row and the groups are in order of decreasing height.

The Bouwkamp code parentheses are not required to reconstruct the tiling but they make it easier to sketch a tiling by hand and all published literature uses them. Bouwkamp code without parentheses and commas has been named tablecode and introduced by J.D. Skinner. It is simpler and shorter. The Bouwkampcode and tablecode for the 69 x 61 Squared Rectangle figure above is 9 69 61 (36,33)(5,28)(25,9,2)(7)(16) and 9 69 61 36 33 5 28 25 9 2 7 16. Tablecode, Bouwkampcode and Bouwkamp code are used interchangeably in this site.

## Extended Bouwkampcode

There are several additional fields which are sometimes included in the Bouwkampcode, we can call these codes Extended Bouwkampcode ; In datafiles from this site the additional fields are included after the main Bouwkampcode. An asterix * is used to divide the Bouwkampcode fields from the additional fields. These additional fields are used for captions, ie placing information such as the tiling id, discoverer, isomer number, year of discovery underneath the tiling in illustrations in webpages such as those on this site or in the production of postscript images of squared squares.

The extra Bouwkampcode fields;
• The order, height and width are usually the first three fields, but are not always included in the main Bouwkampcode itself, as they are not parenthesised, but are often included in the extra fields.
• The initials of the author/discoverer (3 uppercase alpha characters) eg , AJW, CJB, JDS.
• The year of discovery.
• A unique SPSS ID. For SPSS the ID is the size concatenated with an uppercase alphabet string representing the position of that SPSS in the sorted listing of SPSSs of that size, of the same order. If there is only one square of that size the alphabet string is A, if it is the second square of that size its string is B and so on. The alphabet string of the 27th square of a given size is AA, 28th is AB, and so on. For example, the 27th simple square perfect square of order 28 of size 1068 in tablecode (see below) with ID, author and year ;
29 1068 1068 615 453 186 267 193 87 68 90 153 24 129 81 19 49 106 27 63 348 76 45 300 260 100 15 10 35 25 60 160 * 1068AA A&P 2010
• A unique CPSS ID. For CPSS the ID is the size concatenated with an lowercase alphabet string representing the position of that CPSS in the sorted listing of CPSSs of that size, of the same order. A CPSS ID also has a single field giving the number of isomers. Each isomer CPSS can be uniquely identified by using an alternate field composed of two numbers and a separator mark, giving the position of that CPSS in the listing of its isomer CPSSs. For example;
24 175 175 (81,38,56)(20,18)(3,16,55)(14,5,1)(4)(9)(39)(51,30)(29,31,64)(43,8)(35,2)(33) * 175a THW (4) 1948 or
24 175 175 (81,38,56)(20,18)(3,16,55)(14,5,1)(4)(9)(39)(51,30)(29,31,64)(43,8)(35,2)(33) * 175a THW (1/4) 1948
• SISS are currently unnamed but could also be given a unique ID, some combination of size and an alphanumeric string.

Rotations and reflections of a square tiling may create different Bouwkamp codes. Canonical Bouwkamp code is the unique code which is the highest Bouwkamp code, the one that is numerically largest (comparing elements going left to right) from the Bouwkamp codes of all possible rotated and reflected versions of that square tiling.

If squared rectangles and squared squares are put into canonical Bouwkamp code form, duplicates of existing tilings can easily be identified, new discoveries can be verified and complete catalogues for many low order tilings can be made in a compact text form, suitable for computer data processing, document production, browser viewing and computer graphics rendering.

For SPSRs the canonical Bouwkamp code is also the one corresponding to the dissection in landscape orientation where the largest corner element is in the top left corner and is listed first out of the elements. This is easy to check.

For SPSSs only the first two elements need to be examined for highest Bouwkamp code, that is the largest corner square in the top left corner and largest boundary square adjacent to it, which goes on its right. These two elements are the first and the second listed elements in the canonical Bouwkamp code.

For Imperfect tilings (SISSs, SISRs) it may be necessary to examine all elements in the Bouwkamp code to determine the canonical highest Bouwkamp code.

We refer to different squared squares with the same elements as isomers. The smallest order for SPSS isomers is 25 for pairs and 28 for triples. By definition a CPSS is one of at least four isomers. A CPSS is one of up to 8 isomers in order 25, 16 isomers in orders 26 and 27, and 48 isomers in order 28. The Sprague square of order 55 is one of 12,582,912 isomers! For every order there is a CPSS catalogue with only a representative CPSS for each set of isomers. For the lowest orders there are also catalogues which include all the isomers.

Unfortunately many CPSS in the published literature are not recorded in any discernably consistent canonical Bouwkamp code representation.

The CPSS canonical representative on this website is the CPSS isomer with the 'highest Bouwkampcode' (by element values, not lexicographically).

## J.D. Skinners Bouwkamp codes

J.D. Skinner has supplied the following listing and tablecode for squared squares from orders 21 to order 30. This file has not been updated since 2003..

biglist.zip(41k) has a listing of the squared squares by order, size/id and type (SIMP/COMP) - the size/id is different from the system used on this website, it is a concatenation of the size and an uppercase alpha character(s) where ALL perfect squared squares of a given order (both SPSS and PSS) are indexed. The size/id in biglist.zip is used to refer to the corresponding Bouwkamp code in the 00table.zip file. Discoverers initials are included.

00table.zip(558k) contains the corresponding Bouwkamp codes (in tablecode form).

## David Moews Bouwkamp codes

David Moews has an explanation and an example of the use of Bouwkamp code.

David Moews homepage has Bouwkamp codes of all simple perfect squared rectangles (SPSR) of orders from 9 to 16, and Bouwkamp codes of all perfect squared squares (PSS) of orders from 21 to 24 (and some of orders from 25 to 27.)

## A.J.W. Duijvestijn's order 26 SPSS, 2x1 SPSR paper and Bouwkamp codes

The AMS has provided a free download of Duijvestijn's paper on Order 26 simple perfect squared squares (SPSSs) and 2x1 simple perfect squared rectangles (SPSRs). Copies have been supplied of the missing Bouwkamp codes TableI Order 26 SPSSs and TableII Order 26 2x1 SPSRs which originally accompanied the paper.

# Catalogues of Perfect Squared Squares

## Software

### Jim William's squared square finders and enumeration scripts (CPSS & SPSS) September (2014)

Jim Williams has produced a suite of software which can be used to enumerate complete orders of squared squares. This file jbw2014.zip includes the source files and includes an explanatory file USAGE.txt which is reproduced below;

######################################
find_all_cpss.scr <max_order>

SUMMARY
This script prints all CPSSs up to order "max_order". This script illustrates how the other scripts
and programs work together to find all compound perfect squared squares. The script does not
parallelize the search which needs to be done for any practical large search. It is just intended
to illustrate the algorithm and usage of the other scripts and programs.

######################################
find_all_spss.scr <max_order>

SUMMARY
This script prints all SPSSs up to order "max_order". The search is parallelized four ways to
illustrate the parallelization. A practical script to search larger orders would likely
need a higher level of parallelization.

######################################
build.scr
This is a simple script that builds all C++ programs. Edit this file to change compile options.

######################################
gen_graphs -e <max_edges> [-n <max_nodes>] [-c <connectivity>] [-m <modulus> -r <residue>] [-s] [-a] [-t]

SUMMARY
This program generates all simple planar graphs with nodes having a minimum degree of 3. Connectivity
may be specified as 2-connected or 3-connected. Output format is ascii format chosen to be
compatible with plantri. Each output line (written to stdout) contains one graphs. Format looks like this.
7 bcde,aefc,abfd,acg,agb,bgc,dfe
First number is the number of nodes. Each node is represented by a letter: a, b, c, ... Each node is
listed in order separated by commas and contains a list of the connecting nodes in clockwise order.

OPTIONS
-e <max_edges>
This is the only required option and specifies the maximum number of edges in the graph. All graphs
with less than or equal to that number of edges, and which meet the other requirements, are output.

-n <max_nodes>
This options specifies the maximum number of nodes. Only graphs with less than or equal to this
number of nodes are output. If omitted, then max_nodes defaults to "max_edges/2 + 1" which is usually
what you want anyway.

-c <connectivity>
"connectivity" must be 2 or 3. If this options is omitted, then connectivity defaults to 2. If searching
for SPSS, then this should be set to 3. Usually set to 2 for most other uses.

-s <min_square_side>
This applies a determinant check to all output graphs. Unless half the determinant of the associated matrix
(equal to the graph complexity) has a square factor of at least "min_square_side" the graph is usually
not output. Because the determinant check is quick and applied before some other necessary checks, this
option not only drastically reduces the quantity of output but also provides a 25% speedup of the
gen_graphs program. This option should be used when searching for SPSS. A value of 100 works fine for
that.

-a This option applies a different determinant filter. If the number of edges is equal to "max_edges" then
the graph is output only if the determinant is divisible by 13. If the number of edges is equal to
"max_edges-1" then the graph is output only if the determinant is either divisible by 13 or divisible by 21.
This filter should be used when generating perfect rectangles that can be paired with APS to form CPSS.

-m <modulus> -r <residue>
This options allow subdividing a problem to facilitate parallelization. The entire set of graphs
corresponding to specified parameters is divided into a number of pieces with the number equal to "modulus".
Only the piece designated by "residue" is printed. "residue" should range from zero to "modulus" minus one.

-t <mod_threshold>
Changes the mod threshold to <mod_threshold>. If not specified, then mod_threshold will default to 25.
mod/res algorithm generates all graphs with number of edges less than or equal to mod_threshold and only
prints every M'th one where M is the modulus. For graphs with more than mod_threshold edges, there are
generated and printed only if they are extensions of a graph that was printed. Increasing mod_threshold
will increase the compute overhead but make the compute time and number of outputs more equal for different
values of "res". The default value, 25, seems like a good compromise that usually works well.

######################################
findpr [-s] [-d] [-a <augmentation_limit>] [-o <max_cpss_order> -f <filter_file>]

SUMMARY
This program accepts as standard input the output of gen_graphs. Using each graph input it checks to see
if any perfect rectangles can be constructed from the graph and prints the Bouwkamp codes for the rectangles.

OPTIONS
-s
If this option is given, only squares will be printed. Use this to search for perfect squares.

-d
Print duals. By default, dual suppression is implemented. Any graph with more nodes than faces will be
ignored, and any graph with equal number of nodes and faces, will reject any perfect rectangle if the
preferred orientation requires a 90 degree rotation. If this option is specified, all PRs will be
printed including duals.

-a <augmentation_limit>
Any perfect rectangle can be augmented by adding an additional square adjacent where the square size
is equal to the full width or height of the original rectangle. This process may be iterated.
So a non-augmented PR of order N will create two augmented PRs of order N+1, two augmented PRs
of order N+2, etc. With this option, all augmented rectangles will be printed up to order
"augmentation_limit".

-o <max_cpss_order> -f <filter_file>
This option applies a filter to the generated perfect rectangles. This is used when searching for
rectangles that pair with an APS to form a CPSS. The aspect ratio of the rectangle is checked
against the list in "filter_file" to see if there is an APS with the same aspect ratio such that the
combined order of the rectangle and the APS is less than or equal to "max_cpss_order".

The format of the filter_file should be as follows:
<order> <width> <height>
<order> <width> <height>
<order> <width> <height>
<order> <width> <height>
<order> is the order of the corresponding APS. This is a count of all the component squares of the
APS but not including the embedded rectangle. <width> and <height> are the width and height of
the embedded rectangle with width being the greater of the two, and the pair expressed in least
terms (no common factors). The file must be sorted in ascending order of aspect ratio,
where the aspect ratio is width divided by height.

Note that the filter test is applied only to the base rectangle, not to any augmentations. Therefore
the original APS should be "de-augmented" for purposes of creating the filter file. For example
if an APS of order N has an embedded rectangle which is 14 by 9, then the filter file should contain
the following lines. (Example does not show them correctly sorted.)
N 14 9
N+1 9 5
N+2 5 4
N+3 4 1
One can think of these as derived APSes where a square is iteratively cut off the end of the embedded
rectangle.

######################################
findaps [-s] [-d] [-a <augmentation_limit>] [-o <max_cpss_order> -f <filter_file>]

SUMMARY
This program accepts as standard input the output of gen_graphs. Using each graph input it checks to see
if any APS (almost perfect squares) can be created from the graphs. An APS is defined as a subdivision
of a square into a number of squares, each of different size, plus one rectangle. In the general case
the rectangle may be a square and may be the same size as one of the other squares.

OPTIONS
-o <max_cpss_order> -f <filter_file>
This option applies a filter to the generated APS. This is used when searching for APS that pair with
a perfect rectangle to form a CPSS. The aspect ratio of the embedded rectangle in the APS is checked
against the list in "filter_file" to see if there is any PR with the same aspect ratio such that the
combined order of the rectangle and the APS is less than or equal to "max_cpss_order".

The format of the filter_file should be as follows:
<order> <width> <height>
<order> <width> <height>
<order> <width> <height>
<order> <width> <height>
<order> is the order of the corresponding PR. <width> and <height> are the width and height of
the perfect rectangle with width being the greater of the two, and the pair expressed in least
terms (no common factors). The file must be sorted in ascending order of aspect ratio,
where the aspect ratio is width divided by height.

######################################
find_basic_isomers [-a] [-b] [-c] [-r] [-S] [-C]

SUMMARY
This program accepts as standard input a list of squared squares or squared rectangles in either
bouwkamp code or table code format. The output is determined by the command line options, but the
default behavior is to generate all basic isomers and print the preferred one. Basic isomers are
defined as all isomers (rearangement of the component squares) that can be created by either
rotating or reflecting rectangular regions contained in the PSS or PSR. The preferred one is
the lexically largest one, comparing each number of its output code in succession.

OPTIONS
-a
This option causes the program to print all basic isomers. Only the preferred orientation
of each isomer is printed. Default behavior is to print only the preferred isomer.

-b
Causes the output to be Bouwkamp code. Default is table code.

-c
Prints an isomer count at the end of each output line.

-r
Prints all rotations and reflections. Default behavior is to print only preferred orientation.

-S
Prints only simple squared squares or squared rectangles. Default is to print both simple
and compound.

-C
Prints only compound squared squares or squared rectangles. Default is to print both simple
and compound.

######################################
build.scr

SUMMARY
Simple script that compiles all the C++ programs.

######################################
create_pr_filter_list.scr

SUMMARY
Accepts as standard input a list of APS. Output is a filter file in the format to be used by "findpr".

######################################
create_aps_filter_list.scr

SUMMARY
Accepts as standard input a list of PRs. Output is a filter file in the format to be used by "findaps".

######################################
convert_pr_to_aps.scr

SUMMARY
Any perfect rectangle can be converted to an APS by adding an additional complementary rectangle
adjecent to its entire width. This script accepts as standard input a list of PRs and outputs
the generated APSes.

######################################
sort_pr_aps.scr

SUMMARY
This scripts accepts as standard input a list of PRs and APSes and sorts them by aspect ratio.
The output of this script is what is required by "find_candidate_pairs.scr"

######################################
find_candidate_pairs.scr

SUMMARY
This script accepts as standard intput a list of PRs and APSes. The list must be sorted by
aspect ratio. For PR, the aspect ratio is the width divide by height of the entier rectangle,
and for APS it is the width divide by height of the embedded rectangle.

Output from the script is a list of pairs, each pair consisting of on PR and one APS with the
same aspect ratio. Each line of output contains one such pair, with "##" as the separator.

######################################
pairs2cpss.scr

SUMMARY
This script accepts as standard input a list of pairs as generated by "find_candidate_pairs.scr"
and outputs a list of CPSS that can be generated from the pairs. Format of the output is
bracket code. The script scales the rectangle and the APS, checks there are no duplicate
square sizes. The bracket code places the embedded rectangle in brackets, or double brackets
if it needs to be rotated 90 degress.

######################################
bracket2bcode

SUMMARY
This program accepts as standard intput the bracket code output by "pairs2cpss.scr". It performs
the mechanical but messy operation of converting the bracket code to standard Bouwkamp code which
is then output.

### Jim William's squared square finders March (2014)

The algorithm behind Jim Williams algorithm is explained in full here.

Here's a brief explanation by Jim;

"The basic idea is to take the electrical network associated with a square and split it roughly in half by cutting exactly three nodes. This seems to be possible for most (but not all) low order squares, and probably close to half of squares up to order 33. The outer loops create a large library of “half networks” and the inner loop attempts to pair up two halves to form a perfect square."

Jim's software is available here. The following files, consisting of program code and scripts are;
graphgen.cpp
create_3library.cpp
search.cpp
all_graphs2
all_graphs3
decompose_file.scr
drive_search.scr

The function of each file is explained the README file

### MANDRILL; Lorenz Milla, and Stuart Anderson's modified plantri with plugin and squared square finders (mandrill-plugin.c & plantrimod.c), Bouwkampcoder (sqt-mod7) and compound/simple Bouwkampcode classifier (bk2cs4). Mandrill

Stuart Anderson's sqfree, sqfind and sqt were rewritten and optimised by Lorenz Milla. Lorenz replaced the Boost library with C arrays and handwritten linear algebra routines; LU decomposition was replaced with LDL decomposition (planar maps are symmetrical, so LDL Cholesky decomposition is possible and twice as fast as LU decomposition). Lorenz adapted McKay and Brinkmann's plantri (modified as plantrimod.c) to filter graphs using the determinant factorisation technique as they were produced, he was also able to speed up the routines in Stuart's sqfind and sqt programs, and write a plantri plugin (mandrill-plugin.c) which incorporated sqfind and sqfree. Mandrill is a combination of the names Milla and Anderson. The end result was squared square software 35 times faster than what was used early in 2013. This made it possible to complete the enumeration of order 31 and 32 compound perfect (CPSSs), simple perfect (SPSSs) and simple imperfect squared squares (SISSs) in under 2 months.

The theory upon which Kirchhoff matrix determinant factorisation is used to produce squared square candidates, is based on the 1940 paper, "The dissection of rectangles into squares", R. L. Brooks, C. A. B. Smith, A. H. Stone, and W. T. Tutte. In the paper, equations 2.33, 2.34 and theorem 6.12 along with the definition that preceeds it give the theoretical justification.

The modified plantri with the mandrill plugin produces graphs which are candidates for squared squares. About 11% of graphs are candidates and only those that have the required determinant factorisation property are produced and saved by the program. Those graphs are then transformed into electrical networks with unit resistances. The currents and voltages of the networks are interpreted as squared tilings and recorded as Bouwkampcodes (in tablecode form) with sqt-mod7. The Bouwkampcoder program sqt-mod7 separates tiling tablecodes into the applicable categories of square/rectangle, imperfect/perfect and compound/simple. It is a recommended that a post-production check be done for compound/simple classification using bk2cs4, or bk2cs, or Armin Singer's findcpss as there are no known cases where sqt-mod7 has incorrectly classified compound or simple squared squares but there is a single known case where sqt-mod7 incorrectly classified a compound imperfect squared rectangle.

The sources for mandrill-plugin.c, plantrimod.c, sqt-mod7 and bk2cs4 are available here.

The mandrill-plugin source has instructions on required modifications, compilation and usage (from the source);

// To COMPILE this you must do some changes to plantri.c (version 4.5) or use the modified version plantrimod.c:
// 1. Add this line: #define PLUGIN "mandrill-plugin.c"
// 2. Change line 190 to: #define CPUTIME 0
// 3. Change line 18523 to: dosummary = 0;
// 4. Comment out the lines 18034-18087.
// Then compile like this: gcc plantrimod.c -o mandrill.exe -O4 -static -lm
// The -lm option is needed to include math.h in linux.

// USAGE: mandrill.exe -pc2m3v 12 v12.bin 2> man_v12.txt
// this analyzes only those graphs with f >= v (faces / vertices)
// but it counts the other ones too (f < v).
// If you don't want to count the f < v graphs you can enter a lower edge bound
// like in the plantri guide: mandrill.exe -pc2m3e22:v 12 v12.bin 2> man_v12.txt
// As the upper edge bound is not really implemented in plantri,
// you don't gain any speed if you enter an upper edge bound.
// The upper edge bound can also be done by setting the maxorder parameter (see below).

Because of the large number of graphs to be produced, it is usual to write a batch file or shell script to automate the processing, i.e.;

For linux;

#!/bin/bash
for ((c=10709;c<=10825;c++)) do ./mandrill -pc2m3v 17 \$c/13000 v17-\$c-13000.bin 2> man_v17-\$c-13000.txt done

For Windows;

for /l %%n in (0,1,877) do mandrill.exe -pc2m3v 17 %%n/13000 v17_%%n_13000.bin 2> man_v17_%%n_13000.txt

### Stuart Anderson's squared square finders (sqfree and sqfind) and Bouwkampcoder (sqt) March (2013)

sqfree and sqfind operate on plantri planarcode binary files. Both programs find graphs that correspond to squared squares, extract them and save them as extracted files (x_files) in the plantri format. The sqfree program is the faster program of the two, (about 3 times faster) it uses factoring of the Kirchhoff/laplacian graph matrix determinant to find likely graph candidates for squared squares. The output of sqfree, an x_file is then processed by sqfind, creating an x_x_file as output. To convert the x_x_files to squared square Bouwkampcodes, and to filter the Bouwkampcodes into simple, compound, perfect or imperfect, sqt is run on the x_x_files.

One could dispense with sqfree, by creating x_files with sqfind, and creating Bouwkampcode/tablecode from the x_files with sqt, but this is a much slower process. Sqt can also be used directly on plantri output, but if finding squared squares from plantri files is the goal, it is much, much faster to search first with sqfree and sqfind. If the aim is to produce squared rectangles, not squared squares, then sqt alone must be used.

Compile with g++ for Linux and Mac and MinGW for Windows 7. The Boost C++ ublas library needs to be installed.

All 3 programs are in this zip file

### David Moews simple perfect squared rectangles (SPSRs) generator (GPL!)

David Moews homepage also has GPL'd software (written in C) to produce simple perfect squared rectangles (SPSRs).

graph.c enumerates all simple perfect squared rectangles with order 20 or below (the order can easily be varied by editing the source). Each rectangle's order, size, and Bouwkamp code is printed, one rectangle to a line. Also, some statistics on graphs used to generate the rectangles are printed.

### Stuart Anderson's ssh (squared square hunter)

Stuart Anderson's 'ssh.exe' (squared square hunter - finds SPSS, SISS, SPSR and SISR) - this binary was produced using an out of date object LEDA research library in 2001 and is no longer supported by the author. Due to the existence and availability of much faster software, with better capabilities on this website, and security objections to leaving downloadable executables on the site , ssh.exe has been removed from this webpage.

ssh is still quite a useful program for producing squared rectangles and squared squares in the orders 9 - mid 20s', although it is too slow for searching large graph classes in higher orders, it quite quickly produces excellent Bouwkampcode and tablecode if the graphs corresponding to squared squares are already found. It will crash on degree 2, 2-connected plantri graphs, so is unsuitable for CPSS searches. ssh runs on WinXP, Vista, Windows 7 as well as under wine on ubuntu. If you need it, and require instructions on how to use it, email me. (stuart.errol.anderson@gmail.com)

### Stuart Anderson's, Armin Singer's and Lorenz Milla's Bouwkampcode Utilities Collection;

A number of C,C++ programs have been written to assist in the cataloging, processing and analysis of square tilings.

• tc2bkp (tablecode to Bouwkampcode; S. Anderson) - Squared rectangles and squared squares are represented in a concise notation called Bouwkampcode. Bouwkampcode without the parentheses and commas is called tablecode. Tablecode is easier to work with in computer programs. It is possible to convert between the two formats. Converting Bouwkampcode to tablecode is trivial as it involves replacing parentheses and commas with whitespace, however converting the other way is not trivial and involves constructing the tiling geometrically and then placing the parentheses correctly, which is what tc2bkp does. The other utility programs operate on either Bouwkampcode or tablecode, but most produce output in tablecode, so if you require Bouwkampcode as the final product you will need this program to convert the tablecode. To use, type tc2bkp followed by the Bouwkampcode file.

• bk2ps (Bouwkampcode to postscript; S. Anderson) - converts Bouwkampcodes (or tablecodes) into postscript booklets. You have a choice of 1, 6, 12 or 20 tilings per page. While one can construct a tiling from Bouwkampcode by hand, it is convenient to let the computer produce the graphics. To use, just type the program name, you will be prompted for the number of tilings per page, and an input file.
• bc2latex (for converting Bouwkampcodes to LaTex) use Armin Singer's (see below) linux/unix bc2latex . Usage example ; cat spss.txt | ./bc2latex > latex.txt.
• tc2tex (for converting tablecode to LaTex) use Lorenz Milla's, (see below) linux/unix/Windows tc2tex . Usage example : tc2tex input.txt , Windows users can drag and drop the input text file onto tc2tex.exe, reads only the FIRST line from the text file and creates a LaTeX-file "squares.tex".
• bc2mp (for converting Bouwkampcodes to Metapost) use Armin Singer's linux/unix bc2mp (see below). Usage example ; cat spss.txt | ./bc2mp > metapost.txt.
• bk2all (Bouwkampcode to all; S. Anderson) - simple squared squares and squared rectangles can be oriented in 8 different ways, usually only one 'canonical' orientation is chosen (with the largest corner square at the top left, and the larger of the two squares adjacent to it on the top). If you want all 8 tablecodes of a particular dissection, use this program to generate them. This program will operate on compounds but does not produce compound isomers, only the whole tiling is reoriented, not any included smaller dissections (the 'trivial' isomers - not the compound isomers). To use, type the program name followed the Bouwkampcode filename.
• bk2cs & findcpss (bk2cs - Bouwkampcode to compound/simple; S. Anderson, findcpss- finds CPSSs ; A. Singer) - In the study of squared squares and squared rectangles, there are 3 important categories for dissections into squares;
• A dissection into squares is either a square dissection or a rectangle dissection [a rectangle can be a square, but we mean non-square rectangle], (there are other kinds such as squared hexagons but they dont concern us here)
• A dissection is either perfect (every square is a different size) or imperfect (some squares are the same size), and;
• A dissection is either simple or compound. A simple dissection does not contain a smaller squared rectangle or squared square, while a compound dissection does. Determining if a dissection is square/rectangular or perfect/imperfect is easy to program and can be done as the dissections are generated. Determining if a dissection is simple or compound is not a trivial operation, although it is easy to spot the difference by eye, it not so easy to program a computer to do so, and to do it efficiently requires some ingenuity. In the theory of squared rectangles 3-connected planar graphs with a identified edge (c-nets) produce simple tilings, and 2-connected graphs produce compound tilings. This is generally true, but there are exceptions, it is possible for c-nets to produce compounds in rare circumstances. In the higher orders what is rare at lower orders becomes more frequent and a means of separating simples from compounds is necessary, particularly if one is interested in enumerating the exact number of tilings of each kind for a given order of tilings.
bk2cs is a program that inputs Bouwkampcodes or tablecodes and separates them into 2 files, simple and compound. To use, type the program name, bk2cs followed by a Bouwkampcode filename. Armin Singer (see below) has also written a linux/unix filter program findcpss to select CPSS's from a Bouwkampcode listing. Usage ; cat pss.txt | ./findcpss > cpss.txt
• bk2cpss (Bouwkampcode to CPSS; S Anderson) - If one substitutes a squared square into the elements of that or another squared square, and scales both so that all squares are integers, then a new squared square is the result. If this is applied to a Bouwkampcode (or tablecode) listing, and if any resulting imperfects are filtered out then a new collection of CPSSs is the result. Starting with a single PSS, an unlimited supply of CPSSs can be created by performing this operation iteratively. As the smallest PSS (21 : 112 AJD) has 21 squares, performing this operation creates a CPSS of order 41 (one square is lost to become the container for the included square, so these varieties of CPSS start at order 41. SISSs with a single imperfection can also be used to create CPSSs, these SISSs start at order 22. To use, type the program name, bk2cpss followed by a Bouwkampcode filename.
• bk2ism & findflips (bk2ism - Bouwkampcode to isomers; S. Anderson, findflips; A. Singer) - if a dissection of a certain size squared square or rectangle can be done in more than one way (not counting the 8 trivial 'isomers' produced by bk2all) using the same set of squares, then the different dissections are called isomers. This program takes sorted Bouwkampcode/tablecode and finds any isomers. As with bk2all the program will operate on compounds but does not produce compound isomers. Isomers had an important role to play in the history of squaring the square, they also make good puzzles. To use, type the program name, bk2ism followed by a Bouwkampcode filename. bk2ism has been designed to work for perfects only, Armin Singer (see below) has also written a linux/unix program findflips to identify isomers in a Bouwkampcode listing. It works for both perfects and imperfects. Usage ; cat spss.txt | ./findflips > isomers.txt
• bk2mb (Bouwkampcode to maximum square not on the boundary; S. Anderson) - If one looks at squared squares and squared rectangles it appears that the largest square is always in a corner. In fact there are rare exceptions, it is possible for the largest square not to touch the boundary of the tiling at all. This program searches Bouwkampcode/tablecode and finds those particular dissections.
• bk2x & findcross (Bouwkampcode to crossed square; S. Anderson, findcross - finds crossed squares; A Singer) - A cross in a squared square or squared rectangle occurs where 4 squares meet at a point. In compound imperfect tilings (such as a bathroom floor with tiles all the same size) this is the norm and is completely unremarkable, however in simple and compound perfect tilings it is a very rare event. This program searches Bouwkampcode/tablecode and finds squared rectangles and squared squares with crosses. To use, type the program name, bk2x followed by a Bouwkampcode filename. Armin Singer (see below) has also produced findcross which performs the same task. Usage; cat spss.txt | ./findcross > crosses.txt
• bk2sss (Bouwkampcode to squared squares squared; S. Anderson/Stijn Van Dongen) - If one takes a squared square, shrinks it and places copies inside each square of the squared square, then one can create a 'fractal' squared square. This program inputs Bouwkampcode/tablecode and uses postscript code 'sqile.ps' by Stijn Van Dongen to create 'fractal' squared squares in postscript. The postscript can be hand edited to change various parameters, such as reverse colouring and recursion level. Type the program name followed by the Bouwkampcode filename.
• findnice (another short C program by Armin Singer to search for "nice" SPSS or CPSS). 'Nice' being PSS where the smallest square is as large as possible. Usage; spss.txt | ./findnice > nice.txt These tilings make good 'fractal' squared squares (use bk2sss to create them)
• bk2canon (Bouwkampcode to canonical tablecode; S. Anderson ) Converts Bouwkampcode to canonical Bouwkampcode (in tablecode form). A squared square or squared rectangle can be rotated and reflected in 8 ways. Each of the 8 ways has a different Bouwkampcode. One of those 8 codes is the canonical code of that tiling. For perfect squarings it is the code with the largest corner element in the top left square, and the larger of the 2 elements adjacent to it on it's right. For imperfect squarings the same rule applies but further elements of the 8 codes may need to be compared, element by element, the canonical code is the largest code lexicographically speaking, based on numerical comparison of corresponding elements in the canonical code.

Stuart's programs are written in standard C++ and dont require any special libraries. In Linux, they compile with the gnu compiler at the commandline, for example;
g++ -O3 -Wall bk2all.cpp -o bk2all
In linux move the executables to /usr/bin directory; e.g. for Debian ubuntu
sudo mv bk2all /usr/bin
so the program(s) can be called from anywhere on the computer.

In Windows, Stuart's programs have been compiled with the MinGW C++ compiler, available from here. the following example creates a standalone windows binary;
g++ -Wall -O4 -static bk2all.cpp -o bk2all

All Stuart Anderson's programs are in the zip files; bkutil.zip . (compiled executables have been removed from the zip file, you will need to compile the sources yourself, for Windows the free MinGW is recommended), bkutil.zip has source code for Windows/Linux/Mac. Source code for Microsoft Visual C++ is no longer supplied, as this compiler required different timing code and executables compiled on WinXP would not run on Windows 7, whereas MinGW compiled executables run on both. Armin Singer's programs are in the squaredance package.

If you are using Windows, the UnxUtils is a very good package of general unix/linux commandline utilities, converted to run as windows executables. Great for sorting and sifting data (like large collections of Bouwkampcode files).

### Armin Singer's Squaredance and Bouwkampcode Utilities

Armin Singer has produced squaredance to display squared squares as a slideshow along with his own collection of Bouwkampcode Utilities. Designed for Xwindows (linux, unix). On linux, "tar xzf squaredance-0.10.tgz" will unpack the package and put its files into a subdirectory named squaredance-0.10. Invoking "make" in this directory should produce the squaredance executable. You may need the xorg libraries and the symlinks, headers, and object files needed to compile and link programs which use the standard C library. In ubuntu these can be installed with sudo apt-get install xorg-dev libc6-dev .

From the readme file;

The squaredance package will show you simple perfect squared squares using XVideo. Most parts of it are taken form Open Source (xorg, tvtime). Only a few things have been added by asi AT equicon.de.

There is no fancy GUI but just the things needed to enjoy the show. But there are some useful utilities to deal with lists of Bouwkamp Codes (suitable for both the table representation and the traditional form).

The package contains the following source files:
• barlistuser.hpp ......... just a small C++ interface module
• bars.[ch]pp ............. some code dealing with horizontal "bars", used to convert Bouwkamp Codes to drawable information
• bc2latex.cpp ............ a filter to convert Bouwkamp Codes to LaTeX pictures
• bc2mp.cpp ............... a filter to convert Bouwkamp Codes to Metapost
• bcsize.[ch]pp ........... tiny module to determine the square size
• findcpss.cpp ............ a filter to select CPSS's from a BC list - not needed to build the squaredance executable
• findcross.cpp ........... a filter to select squares containing a cross - not needed to build the squaredance executable
• findflips.c ............. a filter to extract isomers - not needed to build the squaredance executable
• findnice.c .............. another short C program to search for "nice" SPSS or CPSS - not needed to build the squaredance executable
• histogram.c ............. a short C program to analize element size distributions - not needed to build the squaredance executable
• main.cpp ................ main squaredance module - look at this first
• makefile ................ the package makefile to be used by make(1)
• myxev.c ................. a modified xev.c from the Xorg sources
• squaredance.[ch]pp ...... the squaredance core machinery using xvideoshow.*
• xvideoshow.[ch]pp ....... XVideo code taken from the tvtime source RPM

Some datafiles containing lines with Bouwkamp Codes have been included:

21.txt .................. Duijvestijn's order 21 SPSS found in 1978
crosses.txt ............. SPSS containing crosses
nice1.txt ............... "nice" SPSS dissections (no tiny elements)
nice2.txt ............... "nice" SPSS dissections (no very similar elements)
quadflip1.txt ........... a set of 4 dissection isomers
quadflip2.txt ........... another set of 4 dissection isomers
tripleflips.txt ......... some sets of triple dissections isomers

There is a download script named mklist you may use to download many SPSS and CPSS dissections data from www.squaring.net. By default, the squaredance executable uses spss.txt and a delay of 1000ms between frames. Please refer to main.cpp for supported options and/or just try

./squaredance --help

Enjoy it, but do not fight against minor strange effects. (varying line width, interfering colors etc.)

### Lorenz Milla's utilities

tc2tex - written by Lorenz Milla, Germany - April 2012 - Version 1.0.
Draws a rectangle (or square), dissected into squares;
Requires one argument: the name of the input text file.
usage example: tc2tex input.txt
Windows users can drag and drop the input text file onto tc2tex.exe.
Reads in the tablecode from the first line of the input file, for example:
21 112 112 50 35 27 8 19 15 17 11 6 24 29 25 9 2 7 18 16 42 4 37 33
Reads only the FIRST line from the text file, and only in this format.
Creates a LaTeX-file "squares.tex".

tc2ctex written by Lorenz Milla, and
comptcutils.zip which contains five programs:
simptc2canon converts tablecodes to their canonical isomer, ignoring all substructures.
comptc2all generates for most CPSS the whole CPSS class.
comptc2canon converts most CPSS tablecodes to their canonical isomer.
sortfile generates batch files for the sorting algorithm of Win32 CoreUtils.
splitbyorder reads in tablecode or Bouwkampcode, splits into several files, depending on the order.
There is a make file to compile with MinGW.
simptc2canon, comptc2all, comptc2canon, sortfile and splitbyorder written by Lorenz Milla, Dossenheim, Germany, November 2013.
From the source codes;

﻿// #########################################################################################################
// # simptc2canon - written by Lorenz Milla, Dossenheim, Germany, Version: 03/Nov/2013. #
// # reads in tablecode and converts it to canonical tablecode without looking at compound substructures. #
// # requires one argument: the inputfilename. #
// # outputs one tablecode per line to inputfilename-simpcanon.txt, #
// # where it adds a numbering in the end, counting through the different isomers. #
// # feel free to modify! #
// #########################################################################################################
//
// #########################################################################################################
// # comptc2canon - written by Lorenz Milla, Dossenheim, Germany, Version: 03/Nov/2013. #
// # reads in tablecode, looks for compound substructures, generates all isomers, outputs the canonical. #
// # requires one argument: the inputfilename. #
// # outputs one tablecode per line to inputfilename-canon.txt, #
// # where it adds a numbering in the end, counting through the different isomers. #
// # CPSS with too complex substructures can't be processed, are saved to inputfilename-canon-problem.txt #
// # Up to order 30 it proved to work well with all the CPSS, but in higher orders it's incomplete #
// # and I can't guarantee anything, because the different cases in the code grew a bit confusing. #
// # feel free to modify! #
// #########################################################################################################
//
// #########################################################################################################
// # comptc2all - written by Lorenz Milla, Dossenheim, Germany, Version: 03/Nov/2013. #
// # reads in tablecode, looks for compound substructures, generates full isomer class (in most cases). #
// # requires one argument: the inputfilename. #
// # outputs one tablecode per line to inputfilename-all.txt, #
// # where it adds a numbering in the end, counting through the different isomers. #
// # in most cases it outputs every isomer once (in the easiest case with one subrectangle it outputs #
// # 4*8 tablecodes), but in some cases it output twice as many as it should (every tablecode twice), #
// # so you must afterwards identify the doublings, for example with the unix sort -u command. #
// # CPSS with too complex substructures can't be processed, are saved to inputfilename-all-problem.txt #
// # Up to order 30 it proved to work well with all the CPSS, but in higher orders it's incomplete #
// # and I can't guarantee anything, because the different cases in the code grew a bit confusing. #
// # feel free to modify! #
// #########################################################################################################
//
// #########################################################################################################
// # sortfile - written by Lorenz Milla, Dossenheim, Germany, Version: 03/Nov/2013. #
// # generates batch files for the sorting algorithm of CoreUtils: #
// # http://gnuwin32.sourceforge.net/packages/coreutils.htm #
// # To run the batch file under windows, you will need the following binaries from the URL above: #
// # sort.exe, libiconv2.dll, libintl3.dll #
// # feel free to modify! #
// #########################################################################################################
//
// #########################################################################################################
// # splitbyorder - written by Lorenz Milla, Dossenheim, Germany, Version: 03/Nov/2013. #
// # reads in tablecode or Bouwkampcode, splits into several files, depending on the order. #
// # requires one argument: the inputfilename. #
// # outputs one tablecode per line to inputfilename-(order).txt #
// # feel free to modify! #
// #########################################################################################################
//
// Similar to tc2tex, tc2ctex converts compound tablecode to LaTeX-files, also drawing a small picture of the substructures.
from the source;
// #####################################################################################################################
// tc2ctex - compound tablecode to latex (works also with simple squared squares).
//
// handles an input file with one tablecode per line, where every tablecode has two additional strings in the end:
// format is the same as above program
//
// requires one argument: the inputfilename.
//
// outputs one latex file per line from inputfilename.
//
// latex-files have to be compiled latex => PS => PDF !
//
//Three examples (tex and pdf files) are included
//
// ######################################################################################################################
// feel free to modify!

### Richard Parris windisc program

Windisc displays squared rectangles and their associated c-nets (WinXP)

See Richard Parris 'peanut software homepage' for a range of maths programs and his windisc page for a copy of that software.

To use windisc to view squared rectangles and c-nets, start the program, select Windows -> graphs, then select File -> New -> Squared Rectangle. Some of the viewing parameters can be edited under View -> Squared Rectangles. Updated 2nd September 2014