No text

0 11

12 28

Home

0 11

12 28

Home

Each square is called a

tal line is called a

a tile or a bar, and watch the Figure to the right.

Each red line is called an

called a

edge or a vertex, and see what happens.

On the mobile, use landscape mode.

But a larger screen might give you a better experience.

Tap this box if you want to visit one of the text-free 'No Guide' versions.

But a larger screen might give you a better experience.

Tap this box if you want to visit one of the text-free 'No Guide' versions.

Unless, of course, you have replaced it.

This site lets you build rectangles of your own. Many of the rectangles you construct are likely to be imperfect. But with some training and a little luck, you may be able to change an imperfect rectangle into a perfect rectangle.

They should, strictly speaking, be called an *imperfect squared rectangle* and a
*perfect squared rectangle*. There is more terminology below –
but first a practical suggestion:

You might prefer to view Figures 1 and 2 in a separate window or tab while reading this text. Simply keep the Shift key down and click or tap the box above. Then you will not have to scroll up and down through the text repeatedly. To navigate to another window or another tab (typically Alt+Tab or Ctrl+Tab, depending on your browser) is more convenient.

1. Top of text
Buttons
Top of page

2. Permute tile colors

3. Live Show: Create graphs automatically

4. Canvas: Move, Resize. Edit Mode

5. Select, add, remove vertices and edges

6. How to move a vertex

7. Tiles with negative or zero sizes

8. Options (Elementary)

9. Animated Coloring

10. History Notes and References

11. Options (Advanced)

12. Key shortcuts No Guide

A 2. Permute tile colors

3. Live Show: Create graphs automatically

4. Canvas: Move, Resize. Edit Mode

5. Select, add, remove vertices and edges

6. How to move a vertex

7. Tiles with negative or zero sizes

8. Options (Elementary)

9. Animated Coloring

10. History Notes and References

11. Options (Advanced)

12. Key shortcuts No Guide

A **graph** is a drawing that describes the structure of a perfect or imperfect rectangle.
Figure 2 is a graph that describes the structure of the rectangle in Figure 1.
The graph contains the same
information as the rectangle, but is easier to modify manually.

A **vertex** is rendered as a gray circle.
There are seven numbered vertices in the graph in Figure 2.
Each vertex in the graph corresponds to a bar in the rectangle.

An **edge** is a straight line between two vertices.
The graph in Figure 2 has twelve edges.
Each edge in the graph corresponds to a tile in the rectangle.
If there is a tile between two bars in the rectangle,
then there is also an edge between the two corresponding vertices in the graph.

A **canvas** is a rectangular area used for graphics and other purposes.
The *rectangle canvas*
and the *graph canvas* are the areas on which the rectangle in Figure 1
and the graph in Figure 2 are drawn.

The *button canvas* near the top of the page is used for program control.
So are the *option canvas*, the *palette canvas*, and the *textarea canvas*, but these
are not shown until you ask for them. Various kinds of information from the program is sometimes displayed
in the thin, yellow *message canvas* that exends across the page immediately below the button canvas.

Some canvases can be moved and resized (Section 4), others can only be moved. They can all be made invisible by unchecking some option or by using a key shortcut (Section 12).

When the graph canvas is greenish, it is in **edit mode**. You may change the graph when
the graph canvas is in edit mode. Let us say you want to remove vertex number 6. Try the following:

If the graph canvas is not already in edit mode, press *Edit Graph*.

There are other buttons. Very briefly, the buttons do the following:
Now, doubleclick on vertex number 6 to remove it. The vertex should disappear.
(Instead of doubleclick, you may also position the cursor over the vertex, then type *S*,
then type *D*. On the touchscreen, tap the vertex; when it has become blue,
double-tap an empty place on the canvas to make the vertex disappear.)

The three edges that were connected to the vertex will disappear along with it.

The remaining vertices will be renumbered. A new edge will be created automatically from vertex 3 to the former vertex 7 that has now become number 6. This does not happpen in general, but an edge is created in this case because the program insists that a valid graph must have edges all the way around its periphery.

The rectangle will disappear, because it does not correspond to the new graph.

Does the new graph correspond to a rectangle? Press *Go* to find out.
(Or:

New Tap or click the empty rectangle canvas.)

It does – and, by pure luck, the new rectangle turns out to be perfect!

**Color**. Colors the tiles as fast as possible, which usually means instantly. The button can be
used only when the option *Color rectangles automatically* is
unchecked and the rectangle canvas shows a rectangle with uncolored tiles.

1. Top of text
Buttons
Top of page

2. Permute tile colors

3. Live Show: Create graphs automatically

4. Canvas: Move, Resize. Edit Mode

5. Select, add, remove vertices and edges

6. How to move a vertex

7. Tiles with negative or zero sizes

8. Options (Elementary)

9. Animated Coloring

10. History Notes and References

11. Options (Advanced)

12. Key shortcuts No Guide

2. Permute tile colors

3. Live Show: Create graphs automatically

4. Canvas: Move, Resize. Edit Mode

5. Select, add, remove vertices and edges

6. How to move a vertex

7. Tiles with negative or zero sizes

8. Options (Elementary)

9. Animated Coloring

10. History Notes and References

11. Options (Advanced)

12. Key shortcuts No Guide

**Animate**. Colors the tiles step-by-step. The button can be used only when
the option *Color rectangles automatically* is unchecked
and the rectangle canvas shows a rectangle with uncolored tiles.

**Faster**. Increases the speed of animated coloring.

**Slower**. Reduces the speed of animated coloring.

**Colors**. Shows or hides the palette canvas
(Section 2).

**Clear Rectangle**. Makes the rectangle to disappear.
The graph canvas goes into edit mode so that you can change the graph if you want.
Press *Go*, or tap or click the empty rectangle canvas, to compute and display a rectangle again.

**Live Show**. A long sequence of graphs is generated automatically one by one.
A rectangle is computed and displayed for each graph.
When you want to stop the show, press *Stop*.

**Drop-Down Menu**. Used to specify which quality a rectangle must have in order to be displayed
during a Live Show.

A Live Show typically examines more than a thousand edge configurations per second.
Each time an edge configuration is found to correspond to a rectangle of
a quality that matches or is better than the desired quality indicated in the selected menu item,
the rectangle is constructed and displayed.

The best possible quality is that of a perfect square (which should properly be called a *perfect
squared square*). The worst is that of an imperfect rectangle.

**Stop**. Interrupts a Live Show.

A dialog box will present a little statistics, and ask you if you really want to stop.

**Go**. Analyzes the graph and constructs the corresponding rectangle.

The button cannot be used during a Live Show. The graph must be valid: No intersecting edges;
any vertex, except the one at the top of the graph, must have at least one edge coming down to it from above;
and any vertex, except the one at the bottom, must have at least one edge going downwards from it. The
edges around the graph’s periphery must all be present, and will be inserted if missing. If
the graph is valid, the corresponding rectangle will be shown on the rectangle canvas.
If the graph is not valid, an error message will appear in a box or on the rectangle canvas.

**Edit Graph**. Brings the graph canvas in or out of edit mode.

When the graph canvas is in edit mode, the graph can be modified manually (Sections 5
and 6).

Similarly, if you place the cursor over a vertex, the vertex changes its color and the corresponding bar gets highlighted. When a bar is highlighted, it gets fat and grey.

If you place the cursor over a tile in Figure 1, the corresponding edge in Figure 2 changes its color.

On the touchscreen, tap a tile, an edge, or a vertex, and something similar will happen. The graph canvas should probably not be in edit mode when you do these experiments.

If your computer has a mouse or a touchpad and you place
the cursor over a bar in Figure 1, the corresponding vertex in Figure 2 changes
its color. The vertex actually gets selected.
Precise positioning is required in order to place the cursor over a bar, because the standard thickness
of a bar is only one pixel. The option *Tile border thickness* may
be used to thicken them. (The term “bar” was coined by the author for brevity;
the technical term is “horizontal dissector.” Similarly, the kind of graph used here
is called a “p-net” in the literature – and the tiles that cover a squared
rectangle are sometimes said to form a “tiling” or, less precisely,
a “tessellation” of the rectangle.)

A description of whatever you have positioned the cursor over will often appear in
the message canvas. If a vertex or an edge is described as being "in hull", it means that it is
part of the graph’s periphery – in other words, it is one of those edges or
vertices that a rubber band would follow or touch if stretched around the graph.
They will be called *hull edges* and *hull vertices* in the following.

A few experiments of the above kind should give you a feeling for which tiles correspond to which edges and which bars correspond to which vertices.

(If you experiment with imperfect rectangles, you may find cases where a black horizontal line actually consists of two or more contiguous bars belonging to different vertices. The length of a bar may be zero in rare cases when the rectangle contains tiles of size zero. Such a bar of zero length is not highlighted, and you cannot place the cursor above it – but a little information about it will appear on the message canvas if you place the cursor over the corresponding vertex.)

The frame of the rectangle in Figure 1 is green. You can change the frame’s color
if you want. Press the *Colors* button, or type *p* (short for *Palette*).
The *palette canvas* will pop up. On its top you will see four color cards with one color each.
Tap or click one of them and the rectangle’s surrounding frame will get that color.
The tiles will be re-colored automatically as to comply with the neighbor principle.

1. Top of text
Buttons
Top of page

2. Permute tile colors

3. Live Show: Create graphs automatically

4. Canvas: Move, Resize. Edit Mode

5. Select, add, remove vertices and edges

6. How to move a vertex

7. Tiles with negative or zero sizes

8. Options (Elementary)

9. Animated Coloring

10. History Notes and References

11. Options (Advanced)

12. Key shortcuts No Guide

2. Permute tile colors

3. Live Show: Create graphs automatically

4. Canvas: Move, Resize. Edit Mode

5. Select, add, remove vertices and edges

6. How to move a vertex

7. Tiles with negative or zero sizes

8. Options (Elementary)

9. Animated Coloring

10. History Notes and References

11. Options (Advanced)

12. Key shortcuts No Guide

You can change the order in which the program uses the four colors when coloring the tiles. The lower part of the palette is filled with twenty-four color cards, each showing the four colors arranged differently. Click or tap the card that shows the colors in the order you want, and the colors will be used in that order as far as the neighbor principle permits. (The tiles may or may not actually be re-colored; this is because two different cards may lead to the same coloring in some cases.)

When you feel you have experimented with the colors long enough and want the palette to disappear,
press the *Colors* button again or type *p* again, or press *Hide* on the palette.

If you press the *Live Show* button, the program will first remove all inner edges from the graph.
The program pauses for a second or two, in order to demonstrate how the graph looks without inner edges.
Then the program begins to construct graphs, one after the other, with inner edges added systematically
in all possible ways. The vertices will be kept unchanged, and so will the edges around the periphery.

A graph constructed during a Live Show will be shown together with its corresponding rectangle only if the rectangle matches the criterion you have chosen as a filter in the drop-down menu on the button canvas. Here is how the various menu items work:

All imperfect or perfect rectangles that the program constructs will be shown, including those that contain negative-sized and/or zero-sized tiles.

**Negative and zero tile sizes allowed:**

A rectangle is not shown if it has two tiles of the same non-zero size.
If the size of one tile is positive and the size of another tile is negative and the absolute
values of the two tile sizes are equal (for example, one is size forty-two and another is
minus forty-two), then the rectangle is considered imperfect and will not be shown. All
other rectangles are shown. They are perfect except for the presence of tile or edge
labels with the wrong sign or with a zero value.

**Negative tile sizes allowed:**

Same as the foregoing, except that rectangles that contain zero-sized tiles are not shown.

**Perfect rectangles or squares:**

A rectangle is shown only if all tile sizes are positive and different.

**Perfect squares:**

A rectangle is shown only if it is a square, i.e., if its four sides are equally long.
A square will be shown even if one or more tiles have negative or zero sizes, but not
if two tiles have the same size or the same absolute size.

A perfect square should, strictly speaking, be called a *perfect squared square*.

*Negative tile sizes allowed* is the recommended setting when searching for
perfect rectangles, because when a rectangle has many tiles, it is very likely that some
tiles have negative sizes.

If you search for perfect squares in a Live Show, you are likely to get disappointed. Your processor will typically run for hours without finding any.

But there are exceptions: One of the *No Guide* versions of this page has a graph with eleven
vertices that lets a Live Show produce a perfect square in a minute or two. The link is
simply 11.
Click it, press *Clear Rectangle*, select *Perfect squares* in the drop-down menu, press
*Live Show*, and wait patiently.

There is also a graph with 12 vertices. It used to keep my old venerable 1.4 GHz Intel Celeron processor busy for almost ten minutes before the Live Show found a perfect square. But that was several years ago; browsers and JavaScript engines have since improved, and, as of 2019, the time is less than half a minute.

Press the *Stop* button to stop a Live Show when you feel it has been running long enough.
A dialog box will present a little statistics and ask you if you really want to stop.
If not, press *Cancel* on the confirm box and the search will continue. In return for your effort,
the edges that were being examined will be shown on the graph canvas.

Note that the buttons *Faster* and *Slower* refer to the speed of Animated Coloring
(Section 9), not the speed of a Live Show. Some of
the options may be used to fine-tune a Live Show.

Some technical information may appear now and then on the message canvas while a Live Show is running. You do not have to look at it. A brief explanation can be found near the end of this document, in case you are interested.

2. Permute tile colors

3. Live Show: Create graphs automatically

4. Canvas: Move, Resize. Edit Mode

5. Select, add, remove vertices and edges

6. How to move a vertex

7. Tiles with negative or zero sizes

8. Options (Elementary)

9. Animated Coloring

10. History Notes and References

11. Options (Advanced)

12. Key shortcuts No Guide

Advanced visitors may notice that a Live Show sometimes presents the same graph, and therefore the same rectangle, more than once. To write a program that produces each graph only once, without keeping a list of graphs already presented, was long thought to be difficult. Now, there are signs out there that the graph theorists are making progress. If you can afford the time, please feel free to write a program that presents each graph and rectangle only once.

To **move** a canvas, position the cursor at an empty place inside the canvas, then keep the left
mouse button down and move the mouse. On the touchscreen, tap and hold down, then move.

To **resize** a canvas, position the cursor at an empty place on it,
then keep the Shift key and the left mouse button down simultaneously and move the mouse.

New On the touchscreen, resize is by tap + tap–and–hold + drag, that is,
you doubletap but hold down the second time, then move. (It works also with a mouse or touchpad.)

When the graph canvas is in **edit mode**, you can add or remove vertices or edges, or move the vertices.
If a rectangle is shown in the rectangle canvas and you press *Clear rectangle* in
order to remove it, the graph canvas goes into edit mode automatically.
To bring the graph canvas in and out of edit mode, you may also press the *Edit Graph* button,
or type *e*. If no vertex and no edge is selected (see next section), you may doubleclick or
doubletap an empty place on the graph canvas to bring it in and out of edit mode.

When the rectangle canvas shows a rectangle, individual tiles can be moved. Try and move all the tiles out of position, then ask somebody else to put the rectangle together again!

To **select a vertex**, click or tap it at a time when no other vertex is selected;
or move the mouse over it while holding the Shift key down;
or position the cursor over the vertex and type *S* or *s*.

To **unselect a selected vertex**, click or tap it, or click or tap an empty place on the graph canvas;
or type *S* or *s*.

To **select an edge**, click or tap it, or position the cursor over the edge and
type *S* or *s*.
If no vertex is selected, then you may select an edge by moving the mouse over
the edge while holding the Shift key down.

To **unselect a selected edge**, click or tap it, or click or tap an empty place
on the graph canvas; or type *S* or *s*.

(Note: A lower–case *s* may have side effects in the Vivaldi
browser. More about Vivaldi in the key shortcuts section.)

To **create a new vertex**, choose an empty position on the graph canvas where you want the
new vertex, and click or tap there. If an edge was selected, that edge will merely get unselected
and you will have to click or tap again. The same will happen if an existing vertex was selected already,
with one exception: If you keep the Shift key down while you click, a new vertex will be created,
and the new vertex will become selected; in that case, if an existing vertex was already selected,
a new edge will be created between that vertex and the new vertex.

To **remove a vertex**, doubleclick it, or select it and type *Del* or
*d* or *D*.

Or use this touchscreen–friendly method: Select the vertex, then doubletap at an empty place
on the graph canvas. (It also works if you doubleclick with a mouse.)

When you remove a vertex, all edges connected to it will disappear along with it.

To **create a new edge** between two vertices, select one of the two vertices as explained above,
then click or tap the other to create the edge. Instead of clicking the second vertex, you
may also position the mouse over it and type *s*. The second vertex will become
selected if you keep the Shift key down during the process.

A fast way to create several edges is to keep the Shift key down while moving the mouse over successive vertices, or even while creating successive new vertices.

An attempt to create a new edge between two vertices that are already connected by an edge will not damage anything; the old edge will be kept and a new edge will not be created.

In order to **remove an edge**, doubleclick on it, or select it and press *Del* or
*d* or *D*.

Or use this touchscreen–friendly method: Select the edge, then doubletap at an empty
place on the graph canvas. (It also works with a mouse.)

The rule mentioned above, saying that the graph canvas must be in edit mode for the above features to work,
has a touchscreen–friendly exception:

New A vertex or an edge can be selected or unselected by tap or click regardless
of edit mode.

2. Permute tile colors

3. Live Show: Create graphs automatically

4. Canvas: Move, Resize. Edit Mode

5. Select, add, remove vertices and edges

6. How to move a vertex

7. Tiles with negative or zero sizes

8. Options (Elementary)

9. Animated Coloring

10. History Notes and References

11. Options (Advanced)

12. Key shortcuts No Guide

The vertex will follow suit, and so will any edges connected to it.

For fine adjustment, you may select the vertex and use the arrow keys to move the selected vertex one pixel at a time to the left, right, up, or down. (The touchscreen provides no way to do so.)

The vertices will be renumbered top–down if necessary after you have moved a vertex. If a rectangle was shown on the rectangle canvas, it will be removed, as it does not necessarily correspond to the graph any more.

But you can save a *Bouwkampcode* (see below) for the rectangle or a description of
its corresponding graph manually, and later reconstruct the rectangle or the graph from it.

This page has a built–in textarea that can be used for the purpose.

Here is one way to do it – in full detail:

Or: Press the

The effect depends on whether or not a rectangle is shown:

If the rectangle canvas is visible and a rectangle is shown on it, then a Bouwkampcode describing that rectangle will be written into the textarea.

If the rectangle canvas is not visible or a rectangle is not shown on it, then a description of the graph will be written into the textarea.

(To choose between the two possibilities, note that you can at any time press *Clear Rectangle* to remove the
rectangle temporarily, and press *Go* to get it back.)

Now, click the interior of the textarea as if you wanted to change the text in it, but do not change anything. A caret ("text cursor") will appear in the textarea.

Select all content of the textarea, and copy it to your clipboard (typically Ctrl+a and Ctrl+c on the keyboard; a slightly different procedure on the touchscreen.)

On the textarea canvas, press *Hide* to make the textarea invisible.

Open a simple text editor such as Notepad. Paste the content of the clipboard into it, then save the text to a file on your disk.

When you later want to see the rectangle again, open first the file with a text editor and
copy the Bouwkampcode or graph description to your clipboard.

To feed the content of the clipboard into this program, do the following:

Visit this page or any of the *No Guide* versions, for instance, the one with
0 vertices.

Type *t*, or check the option *Show
textarea*. The textarea will become visible. Make sure it is empty.
If not, press "Clear".

Click the interior of the textarea as if you wanted to type a text into it. Paste the content of the clipboard into the textarea (Ctrl+v or equivalent).

Press the *Read* button on the textarea canvas. Or: Press
the *Hide* button to make the textarea invisible,
then type *R* (upper–case).

The program will read the content of the textarea.

If the content is a Bouwkampcode, a rectangle will be drawn.

If the content is a graph description, a graph will be created accordingly and you may
press the *Go* button to try and compute a rectangle from it.

A Bouwkampcode is essentially a list of tile sizes. They are often grouped together with a round or square bracket around the sizes of those tiles that extend downwards from each bar. The list may or may not be preceded by three numbers indicating the number of tiles, the rectangle’s width, and the rectangle’s height.

You can draw a rectangle manually from its Bouwkampcode with pencil on paper, starting from the rectangle’s upper left corner – or you can let this program draw it on your screen.

Some variants of Bouwkampcode that the program will recognize are listed below.

All of the first five variants describe one and the same rectangle. It was published
by Zbigniew Moroń in 1925.^{1} It has nine tiles, and
is therefore said to be of *order* 9.

The rectangle described in the sixth variant
was reported by P. J. Federico around 1978.^{5} This beautiful
rectangle is remarkable in that the largest tile does not touch the boundary.

Perfect squares with
that property have later been found too; the seventh variant, denoted JBW, is an equally
beautiful example. It is one of more than two million perfect squared squares of order 35 found
by J. B. Williams in 2016.^{5}

For a demo, copy one of the variants to your clipboard, paste it into the textarea as
explained above, and press *Read* on the textarea canvas. The
rectangle will be computed and drawn on the rectangle canvas. A graph will not be shown.

It should be possible to do the same with most Bouwkampcodes you find on the Internet.

When you later want to work with graphs again, then clear the rectangle, press *Edit Graph*, and
click or tap on the graph canvas to create some vertices.

(The multiplication sign × in the third variant is character code number 215.
The letter *x* in the fourth variant may be either lower-case or upper-case.
The code in the fifth variant, without brackets or commas, should properly be called a tablecode
or a Skinner code.
The asterisk in some of the variants means that the rest of the line is a comment.

The variant denoted Willcocks is a CPSS, or Compund Perfect Squared Square, so called
because some of the tiles form an embedded perfect rectangle.
A perfect squared rectangle or a perfect squared square in which this is not the case is called an
SPSR or an SPSS, which means, respectively, Simple Perfect Squared Rectangle and Simple Perfect
Squared Square.)

2. Permute tile colors

3. Live Show: Create graphs automatically

4. Canvas: Move, Resize. Edit Mode

5. Select, add, remove vertices and edges

6. How to move a vertex

7. Tiles with negative or zero sizes

8. Options (Elementary)

9. Animated Coloring

10. History Notes and References

11. Options (Advanced)

12. Key shortcuts No Guide

The size of a tile is shown in the label at the center of the tile if there is room for it, and sometimes in another label at the midpoint of the corresponding edge. The size of a tile will also be shown on the message canvas if you position the cursor over the tile or over the corresponding edge.

If instead you position the cursor over the rectangle’s surrounding frame, a description of the rectangle will appear on the message canvas, for instance, as follows.

1N2Z. Imperfect 8 by 6. Order 12. Pixels/unit: 42. Color backtrackings: 2

The description in the above example, which does not refer to the rectangle shown in
Figure 1, means:
The rectangle has one negative-sized tile and two tiles of size zero;

it is imperfect;

it is 8 units wide and 6 units high;

it has 12 tiles;

one rectangle unit fills 42 pixels on the screen;

and the coloring algorithm had to backtrack twice because it ran out of colors.

A rectangle is also considered imperfect if two or more tiles are the same size. If a rectangle
is imperfect, a quick way to see why is to type it is imperfect;

it is 8 units wide and 6 units high;

it has 12 tiles;

one rectangle unit fills 42 pixels on the screen;

and the coloring algorithm had to backtrack twice because it ran out of colors.

(Color backtracking is described in Section 9 below. The number of backtrackings is reported both for fast coloring and for animated coloring, because the basic algorithm is the same.)

New Instead of typing *i*, you may also tap or click an empty point on the
graph canvas at a time when the graph canvas is not in edit mode and no vertex and no edge is selected.

If a tile size is negative, you can often modify the graph a little bit and change the tile into one with
a positive size. First, look at the corresponding edge (the one that changes its color
when you position the cursor over the tile). The edge is usually tilted. Try and move one of its
end vertices up or down until the edge tilts the opposite way.
The rectangle will disappear because it no longer corresponds to the graph. Press the
*Go* button, or tap the empty rectangle canvas, to compute the modified rectangle. With a
little luck, the tile will have changed its sign, but there may still be other imperfections to correct.

If the label on an edge says that the size of the corresponding tile is zero, the edge can
be removed without affecting the rectangle. It may happen that all edges connected to a vertex
correspond to tiles of size zero. Such a vertex is said to be *passive*, and is described as
such on the message canvas. It can be removed without affecting the rectangle.

If two or more tiles have the same size, and you do not want this to be the case, a minor change in the edge configuration often helps. If several edges form a polygon with no edges inside it, it may help to add some. If two adjacent hull edges and one inner edge form a triangle with no vertices inside it, the two tiles that correspond to the two hull edges are usually of the same size. It may help to replace the inner edge with an edge from the vertex where the two hull edges meet to some vertex in the graph’s interior.

You will probably get more good ideas as you gain experience.

Graphs that correspond to perfect or imperfect rectangles have some traits in common:

Edges are not allowed to intersect. You will get a warning if you try to analyze a graph in which one edge intersects another.

Hull edges must normally be present all the way around the graph. The program will insert missing hull edges automatically before computing the corresponding rectangle (unless you have unchecked that option, which is not recommended).

No. It is a deep fundamental problem. If the rectangle has more units than the canvas has pixels, the rectangle must be reduced in size before it can be drawn on the canvas. Each reduced tile size has to be rounded to a whole number of pixels. But rounding means that tiles of different sizes are reduced in size by slightly different factors. When this has been done, then the tiles do not fit accurately together any more, and there will be small gaps here and there.

Another fundamental problem arises if three vertices lie on a straight line. You will get a warning in such cases. It usually helps to move one or more of the three vertices a pixel or two in a direction away from the line. A built-in auto-correction facility will offer to do that for you, with or without success. You can also do it manually.

To hide the option canvas, press

We shall need just two options right now:

Uncheck *Color rectangles automatically*.

Press *Hide* on the option canvas, or press the *Options* button again, or type *o* again,
to hide the option canvas.

Press *Clear Rectangle* on the button canvas. The rectangle will disappear.

Press *Go*. The rectangle will be drawn without colors.

Press *Animate*. The rectangle will be colored step-by-step.
The button’s function changes temporarily to *Pause* / *Resume*.

Press *Slower* or *Faster* to change the speed of animated coloring.

(The *Color* button gives you fast coloring. *Colors* is
for changing the colors.)

2. Permute tile colors

3. Live Show: Create graphs automatically

4. Canvas: Move, Resize. Edit Mode

5. Select, add, remove vertices and edges

6. How to move a vertex

7. Tiles with negative or zero sizes

8. Options (Elementary)

9. Animated Coloring

10. History Notes and References

11. Options (Advanced)

12. Key shortcuts No Guide

If no color is available for the tile, the tile is temporarily colored gray.
The algorithm then reverses direction and proceeds backwards (it *backtracks* while uncoloring
the tiles) until it finds a tile that could have been given a different color at an earlier stage.
The algorithm changes the color of that tile and tries to proceed forwards from there.

Sooner or later, perhaps after many backtrackings, the algorithm will have found a color that fits both the tile and its neighbors. The tile gets that color, and the algorithm proceeds to the next tile.

For most rectangles, the problem of coloring the tiles has several or even many solutions.
The *Four-Color Theorem* says that there is always at least one solution. If you would like to
see more solutions than just the first one the algorithm finds, you may change the value of the
option *Number of animated coloring solutions to show for each rectangle*.

When the algorithm proceeds from one coloring solution to the next, it backtracks (instantly in this case) as if it had run out of colors at the end. In many cases, this means that only one or a few tiles near the rectangle’s lower boundary get a new color.

The buttons *Faster*, *Slower*, and *Animate / Pause / Resume* can be used
to control the animated coloring.

During the years 1936–38, four students at Trinity College, Cambridge, constructed a number of perfect rectangles in the hope of finding a perfect squared square. A perfect squared square is one that is completely made up of smaller squares, no two of which are the same size. The four students discovered the first known perfect square in 1938. It was divided into 69 smaller squares, and so it was said to be a perfect square of order 69.

Working with pencil and paper, they made this discovery after having found that a
squared rectangle could be represented by a type of diagram that looked much like an electric
cirquit. (You may think of the graph in Figure 2 as an example of such a diagram.) Kirchhoff’s laws
state that if an electric current is sent through the cirquit, then no electric charge accumulates
at any node, and no net current circulates around any loop.
For a diagram that represents a perfect or imperfect squared rectangle, it is easily seen that
similar laws apply. This means that, once you have drawn such a diagram
on a piece of paper, you can write down some equations^{2} to be
solved for the tile sizes.

One of the four students, Willam T. Tutte, told the story many years later
as a guest writer in one of Martin Gardner’s books on recreational
mathematics.^{3}
The above is based on Tutte’s article which is also
available online.

Photo: Bjarne Pagh Byrnak 2011. Public Domain
*Figure 3.* The perfect squared square of order
21 discovered by A. J. W. Duijvestijn in 1978,
embroidered on a pillow later the same year.

(Cross stitch by Magda Julie Bomholt)

(Cross stitch by Magda Julie Bomholt)

Others later continued their work. In 1978, a perfect square of order 21
was discovered^{4} by A. J. W. Duijvestijn of Twente University
of Technology in the Netherlands, who – according to a brief report in the *Scientific American*
later the same year – employed a highly sophisticated computer program.

A proof of the four-color theorem had been published just two years earlier.
The theorem states that any map can be colored with no more than four colors such that no two neighbor
countries have the same color.
I recall having suggested to a family member that the perfect square could be so colored.
Two months later, she
presented me with a perfect square of order 21 as a gift,
embroidered on a pillow (Figure 3).
Having enjoyed the sight of it every day for more than forty years now, I tend to regard
its aesthetic quality as being artistically tenable.

In May 2015, Firefox sometimes did not update the graph's edges during a Live Show. In February 2017, Firefox sometimes failed to update the background color of a canvas. Both phenomena were related to the use of the relatively new html5 canvas element. Workarounds were implemented and they seem to work; but no guarantee can be given.

Equations are solved in floating-point numbers for graphs with up to and including 63 edges,
and in extended integer arithmetics if the graph has 64 or more edges.

This is thought to provide a reasonable balance between speed and reliability.
In case a graph with fewer than 64 edges needs extended arithmetics, the corresponding
rectangle will not be shown. An error message will appear in the rectangle canvas instead.

The sample graph with 28 vertices is processed in extended arithmetics. The speed of extended integer arithmetics is slower than standard arithmetics. In case your browser urges you to stop the script, let it continue. If you want to study squared rectangles of high order on a larger scale, you should probably use a dedicated program written in a high–performance compiled language.

Standard arithmetics is always used to represent the final result. This imposes a limitation: The width or height of a rectangle cannot exceed 9007199254740991 units. Rectangles bigger than that will not be shown.

But despite its limitations, the present script provides you with a geometrical puzzle in which you can do many experiments without having to download anything. And, after all, it computes and draws a perfect rectangle of order 64 in a fraction of a second.

Finally, do not forget to visit some of the many excellent
websites^{5} on perfect squared rectangles that exist!

(Author: Bjarne Pagh Byrnak)

The *jsbn BigInteger* library, written by Tom Wu of Stanford University, is used for extended integer
arithmetics. Source:
www-cs-students.stanford.edu/~tjw/jsbn.

The library was slightly modified for compatibility with an old version of the Opera browser.
In Opera versions as of 2014 or later, the modification is no longer needed.

(The *java.math.BigInteger* library was tried, too; it worked well and could have been
used. However, *jsbn* was found to solve the equations much faster.)

A JavaScript version of the *pnpoly* function, written in C by W. Randolph Franklin, is used to
determine if a given point is inside a given polygon.

Secure browsing is optional:

The URLs you use to access this site may begin with either*https://* (secure)
or *http://* (not secure), depending on your choice.

If secure browsing causes problems in your geographical region, use*http://*.

The URLs you use to access this site may begin with either

If secure browsing causes problems in your geographical region, use

www.squaring.net/history_theory/history_theory.html

and at

math.arizona.edu/~ime/ATI/Math%20Projects/C1_MathFinal_Papenfus.pdf.

[2] A more direct method for setting up such equations is used on this site. It is briefly described in Charles H. Jepsen, “Dissections of p:q rectangles,” Mathematics of Computation, Vol.65, No.214 (April 1996) 771-778.

[3] Willam T. Tutte, “Squaring the Square.” Chapter 17 in
Martin Gardner, “The Second Scientific American
Book of Mathematical Puzzles and Diversions: A New Selection.”
Simon and Schuster, New York, 1961.
Full text of the book’s Chapter 17 at

http://www.squaring.net/history_theory/brooks_smith_stone_tutte_II.html
.

Danish translation by Carl-Otto Johansen:
Willam T. Tutte, “Kvadratets kvadrering.” Kapitel 17 i
Martin Gardner, “Mere morsom matematik. Anden samling.”
Borgens forlag 1964.

[4] A. J. W. Duijvestijn, “A Simple Perfect Square of Lowest Order.”

Journal of Combinatorial Theory, Series B 25, 240-243 (1978). Full text (pdf)

at
https://ac.els-cdn.com. More results (pdf) by Duijvestijn and a list of

references in
Math. Comp. 65 No.215, July 1996, 1359-1364
.

Duijvestijn’s thesis, including some technicalities of the computer he used in 1962, at
http://alexandria.tue.nl/repository/books/44157.pdf
.

[5] For instance:

Catalogs of perfect rectangles and squares can be found at
www.squaring.net together with literature, history, biographies,
theory, software, etc.

David Moews presents the source code of a C program to search for perfect rectangles at
djm.cc/dmoews.html.

The Trinity Mathematical College uses the order-21 perfect square as a logo and
presents a photograph of another perfect square used as part of a table design at

www.srcf.ucam.org/tms/about-the-tms/the-squared-square.

Federico sent his squared rectangle of order 19, with the largest element not on the boundary, to Duijvestijn and Leeuw
"two years ago," according to
this
paper which was received by the journal on August 18, 1980.

Advanced visitors may study a new method to speed up the search for perfect squared squares
at squaring.net/history_theory/james_williams.html.

Catalogs of the 2578081 simple perfect squared squares of order 35, enumerated by J. B. Williams,
may be found at squaring.net/sq/ss/spss/o35/spsso35.html.

(Tip: The very large *.ps* file may be viewed smoothly and problem free in a
Linux document viewer.)

b | Hide / Show button canvas |

c | Clear textarea |

d | Remove selected vertex or edge |

e | Graph canvas edit mode on / off |

g | Hide / Show graph canvas |

i | Highlight / unhighlight imperfection of rectangle or graph |

m | Hide / Show message canvas |

n | Hide / Show top navigation bar |

o | Show / hide option canvas |

p | Show / hide palette canvas |

r | (case sensitive) Hide / Show rectangle canvas |

R | (case sensitive) Read from textarea |

S or s | Select moused vertex or edge, or unselect vertex or edge |

t | Show / hide textarea |

W or w | Write graph description to textarea |

< | (historical) Move selected vertex one pixel to the left |

> | (historical) Move selected vertex one pixel to the right |

+ or " | (historical) Move selected vertex one pixel up |

– or ' | (historical) Move selected vertex one pixel down |

With one exception: If a vertex is selected and the graph canvas is in edit mode, the arrow keys may be used to move the vertex left, right, up or down one pixel at a time.

The latter feature, which is relatively new, replaces the last four key shortcuts in the table above.
(And, if you want to remove a selected vertex or a selected edge when the graph canvas is in edit mode,
you may now type *Del* in place of *d*.)

You may still use the old shortcuts, but you should be aware of a few things.

Opera and Vivaldi use + and – for zooming in and out. If you are using Opera, this site will take the following action on them, in an attempt to mitigate the conflict: If a vertex is selected and the graph canvas is in edit mode, the selected vertex will be moved one pixel up or down; if not, Opera will be allowed to zoom.

In Vivaldi, you may use " and
' for moving a selected vertex up or down.
In order to select or unselect a vertex or an edge by keystroke in Vivaldi, use *S*
(upper case).

As an alternative, advanced Opera and Vivaldi users may have discovered that the settings in these browsers are very flexible and may be adjusted to meet most needs.

A message such as
*Figure A-1.* Grid case 13

(least significant bit on top)
"Grid 13" indicates a subset of the graph’s inner vertices. Edges are created to form a path through
the vertices in the subset. The path will start from a hull vertex somewhere above the uppermost vertex
in the subset. It will end at a hull vertex below the lowest vertex in the subset.
The path will divide the graph into two subgraphs. The subgraphs will be of category *A*
and *B*, respectively, if both have inner vertices.
The category of a graph or subgraph with no inner vertices is *N*.

Grid 13. Level 0: Examining subgraph A 0 0 [1,2,4,6,10][3,5,7,9]is a snapshot, taken while a graph or a subgraph with peripheral vertices 1,2,4,6,10 and inner vertices 3,5,7,9 was being worked on.

"A 0 0 " is a category of graph or subgraph followed by the number of subgraphs with and without unconnected inner vertices waiting to be processed.

"Level 0" is a level of recursion.

(least significant bit on top)

The number 13 written in binary notation is 1101. Reverse the order and you get the four black numbers in Figure A-1 at the right. Thus, a value of 13 indicates the grid case where edges are created to form a path through the first, third and fourth inner vertex, but not through the second.

Each of the two new subgraphs will be similarly processed at the next higher level of recursion, and so on. The second vertex will soon get a path through it, and so will all other inner vertices of the graph. When all vertices have become connected, rectangles can be computed and possibly drawn.

If a graph or subgraph has four inner vertices, there will be 16 different grid cases. They are processed in reverse order, starting with 15 and ending with 0. A graph or subgraph with five inner vertices would have 32 grid cases (processed from 31 through 0), etc.

The grid case value shown on the message canvas always refers to the full original graph at recursion level 0. This is so even when a higher level of recursion is indicated elsewhere in the message. (Grid cases are used, but not shown, at higher levels.) The rest of the message refers to the graph or subgraph that was actually being worked on at the time when the snapshot was taken.

The term “grid” is meant to allude to the gaps between the vertices.