Figure 1.  Squared rectangle.
Each square is called a tile.  Each thin black horizon-
tal line is called a bar. Try and place the mouse over
a tile or a bar, and watch the Figure to the right.
Figure 2.  Corresponding graph.
Each red line is called an edge.  Each grey circle is
called a vertex. Try and place the mouse over an
edge or a vertex, and see what hap­pens.

Squared Rectangle Calculator:  Welcome To The User Guide

1.  Can a rec­tan­gle be divi­ded up into squares of dif­ferent sizes?

Sometimes.  If all the squares are of dif­fer­ent sizes, the rect­angle is called per­fect.  If two or more squares are the same size, the rect­angle is called im­per­fect.  The rect­angle shown in Figure 1 is perfect.
Touchscreen?  Smartphone?  Try!  The site is mobile friendly.  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 rect­angles of your own.  Many of the rect­angles you con­struct are likely to be im­per­fect.  But with some training and a little luck, you may be able to change an imper­fect rect­angle into a perfect rectangle.

They should, strictly speaking, be called an imperfect squared rectangle and a perfect squared rectangle.  There is more termin­ology 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.

What is what in Figures 1 and 2

A tile is merely another name for a square. There are twelve colored tiles in Figure 1. The size of each tile is shown in a label in the middle of the tile if there is room. Tile sizes are measured in rectangle units, also simply called units.

A bar is a black horizontal line with one or more tiles above and/or below it. There are seven bars in Figure 1. Can you find them?

A graph is a drawing that describes the structure of a perfect or imper­fect rect­angle. Figure 2 is a graph that describes the struc­ture of the rect­angle in Figure 1. The graph contains the same infor­mation as the rect­angle, 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 corre­sponds to a bar in the rect­angle.

An edge is a straight line between two vertices. The graph in Figure 2 has twelve edges. Each edge in the graph corre­sponds to a tile in the rect­angle. If there is a tile between two bars in the rect­angle, then there is also an edge between the two corre­spond­ing vertices in the graph.

A canvas is a rec­tan­gular area used for graphics and other purposes. The rect­angle canvas and the graph canvas are the areas on which the rect­angle 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).

If you are visiting this page for the first time, you might try and press the Clear Rectangle button.  The rect­angle disappears and the graph canvas turns greenish. Then press Go. The program will compute and draw the rect­angle that corre­sponds to the graph – which is, in our case, the same rect­angle as before. The graph canvas turns whitish.

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.

Now, doubleclick on vertex number 6 to remove it. The vertex should disappear. (Instead of double­click, 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 auto­matically 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!

There are other buttons. Very briefly, the buttons do the following:

Buttons on the Button Canvas

Options. Shows or hides the option canvas. The options are described in Section 11.

Color. Colors the tiles instantly. The button can be used only when the option Color rect­angles auto­matically is unchecked and the rect­angle canvas shows a rect­angle with uncolored tiles.

Animate. Colors the tiles step-by-step. The button can be used only when the option Color rectangles automatically is unchecked and the rect­angle canvas shows a rect­angle 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 rect­angle 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 con­fig­u­ra­tions per second. Each time an edge con­fig­u­ra­tion is found to corre­spond to a rect­angle of a quality that matches or is better than the desired quality indi­cated in the selected menu item, the rect­angle 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 down­wards 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 corre­spond­ing rect­angle will be shown on the rect­angle canvas. If the graph is not valid, an error message will appear in a box or on the rect­angle 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).

As you may have discovered already, if you place the cursor over an edge, the edge changes its color and the corre­spond­ing tile becomes highlighted. When a tile is high­lighted, its color changes, and a ring showing the tile’s original color appears around the tile’s center. In this way, a tile’s position and color become visible even when the tile itself is too small to be discerned.

Similarly, if you place the cursor over a vertex, the vertex changes its color and the corre­spond­ing 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 corre­spond­ing 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 corre­spond­ing 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 rect­angle are some­times said to form a “tiling” or, less precisely, a “tessellation” of the rectangle.)

A descrip­tion of what­ever you have posi­tioned 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 corre­spond to which edges and which bars corre­spond 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 rect­angle 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 corre­spond­ing vertex.)

2. How to permute tile colors

The tiles in Figure 1 are colored in the order [red, yellow, green, blue] as far as the neighbor principle permits. The neighbor principle says that no two neighbor tiles can have the same color. The frame that surrounds the rectangle (green in Figure 1) counts as a neighbor of any tile that touches it. Two tiles that touch one another only at a corner are allowed to have the same color.

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 rect­angle’s surrounding frame will get that color. The tiles will be re-colored auto­matically as to comply with the neighbor principle.

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 differ­ently. 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.

3. Live Show: Create graphs automatically

An inner edge is an edge that is not one of those edges that go around the graph’s periphery. In other words, an inner edge is not a hull edge.

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 corre­spond­ing rect­angle only if the rect­angle 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:

Live Show Filters in Drop-Down Menu on the Button Canvas

Imperfect rectangles allowed:
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 rect­angle is considered imperfect and will not be shown. All other rect­angles 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.

A graph must have at least six vertices in order for a Live Show to produce a perfect rectangle. It must have eleven or more vertices for a search for perfect squares to be meaningful. If your graph has too few vertices, a confirm box will warn you.

Negative tile sizes allowed is the recommended setting when searching for perfect rect­angles, because when a rect­angle 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 pro­cessor 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 2017, 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 confirm box will show 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.

Advanced visitors may notice that a Live Show some­times presents the same graph, and therefore the same rect­angle, 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 rect­angle only once.

4. Rectangle canvas.  Graph canvas.  Move.  Resize.  Edit mode

The rectangle canvas is the rectangular area on which the rect­angle in Figure 1 is drawn. The graph in Figure 2 is sim­i­larly drawn on the graph canvas. Both canvases can be moved and resized.

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 simul­ta­ne­ously 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.)

When the graph canvas is in edit mode, you can add or remove vertices or edges, or move the vertices. If a rect­angle is shown in the rect­angle canvas and you press Clear rect­angle in order to remove it, the graph canvas goes into edit mode auto­matically. 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, the tiles can be moved.

5. How to select, add, and remove vertices and edges

The graph canvas must be in edit mode for most of the following opera­tions to work. The purpose is to avoid unintentional changes of the graph.

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:
New Select the vertex, then doubletap at an empty place on the graph canvas.  (It works also 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:
New Select the edge, then doubletap at an empty place on the graph canvas.  (It works also 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.

6. How to move a vertex

If you want to move a vertex to a different position on the graph canvas, first make sure the graph canvas is in edit mode. Then place the cursor above the vertex, hold the left mouse button down, and move the mouse.  On the touchscreen, tap the vertex and hold down, then move.

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 rect­angle was shown on the rect­angle canvas, it will be removed, as it does not necessarily corre­spond to the graph any more.

Once you have designed a rectangle, is there a way to save it on your disk?

This site reads nothing from your computer and stores nothing on it.

But you can save a  Bouwkampcode  (see below)  for the rect­angle or a description of its corre­spond­ing graph manually, and later reconstruct the rect­angle 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:

How To Move A Rectangle Or A Graph To And From Your Clipboard

Type  W  (upper–case).
Or:  Press the  Options  button and check  Show textarea,  then  –  on the textarea canvas, when it has become visible  –  press  Write.

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 rect­angle 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 rect­angle from it.

What is a Bouwkampcode?

A Bouwkampcode is a short description of a squared rectangle in text form.  It is named after the Dutch matematician and physicist C. J. Bouwkamp who used that kind of notation in the early history of squared rectangles and squared squares.

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 rect­angle’s width, and the rect­angle’s height.

You can draw a rectangle manually from its Bouwkampcode with pencil on paper, starting from the rect­angle’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. Willi­ams in 2016.5

For a demo, copy one of the variants to your clip­board, paste it into the textarea as explained above, and press Read on the textarea canvas.  The rectangle will be computed and drawn on the rect­angle 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, respec­tively, Simple Perfect Squared Rectangle and Simple Perfect Squared Square.)

7. Tiles with negative sizes, and other imperfections

Some rect­angles look perfect at first sight, but are found upon closer inspection to contain one or more tiles whose sizes are negative or zero. The existence of such tiles is a sign that the graph describes the rect­angle inaccurately. There is nothing wrong with the rect­angle;  this kind of imper­fection would, in fact, be invisible had it not been for the appearance of negative numbers or zeroes in tile and edge labels. A slight modification of the graph is often enough to turn tile sizes from negative to positive, or to remove zero-sized tiles. More about that later in this Section.

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 corre­spond­ing 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 corre­spond­ing edge.

If instead you position the cursor over a rect­angle’s surrounding frame, a description of the rect­angle 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 rect­angle shown in Figure 1, means:
The rect­angle 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.

(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.)

A rectangle is also considered imperfect if two or more tiles are the same size.  If a rect­angle is imperfect, a quick way to see why is to type i. The program will highlight one or more culprit tiles along with their corre­spond­ing edges, and provide a little explanation on the message canvas. To unhighlight, type i again.

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 corre­spond­ing 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 rect­angle will disappear because it no longer corre­sponds to the graph.  Press the  Go  button, or tap the empty rectangle canvas, to compute the modified rect­angle.  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 corre­spond­ing tile is zero, the edge can be removed without affecting the rect­angle. It may happen that all edges connected to a vertex corre­spond 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 rect­angle.

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 corre­spond 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 corre­spond to perfect or imperfect rectangles have some traits in common:

Guidelines for Constructing Graphs

Any vertex except the one at the top must have at least one incoming edge to end on it from above. Any vertex except the one at the bottom must have at least one out­going edge to start down­wards from it. If not, a confirm box will warn you when you try to analyze the graph.

Edges are not allowed to intersect. An alert box will warn you 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 auto­matically before computing the corre­spond­ing rect­angle  (unless you have unchecked that option, which is not recommended).

Some rectangles appear on the screen with tile borders that are not equally thick. Isn’t that a bug that can be fixed?

No. It is a deep fundamental problem. If the rectangle has more units than the canvas has pixels, the rect­angle 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 an alert box with 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.

8. Options (Elementary)

To see the option canvas, press the Options button, or type o.
To hide the option canvas, press Hide on the option canvas, or press the Options button again, or type o again.

We shall need just two options right now:

Color rectangles automatically

When unchecked:
Rectangles will not be colored until you press Color for fast coloring or Animate for animated coloring.

When checked:
The next option can be used to choose between animated coloring and fast coloring.

Use animated coloring when coloring is automatic

This option is unchecked as default. You may check or uncheck it any time, even during an ongoing Live Show, to choose between animated coloring and fast coloring.

9. Animated Coloring

In animated coloring, the tiles of a rectangle are colored step-by-step starting from the top left corner.

To see animated coloring at work, do, for instance, the following.

Press the Options button or type o to see the option canvas.

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.)

For each tile, the algorithm finds out which colors are available for that tile. A color is available for the tile if it has not been used to color any of those of the tile’s neighbors that have been colored so far. The rect­angle’s surrounding frame counts as a neighbor of any tile that touches it.

If a tile has more than one available color, the algorithm will look for the one that was used the fewest times for those tiles that have been colored already during that particular coloring. Available colors that have been used equally often (or not at all, as will be the case for the first few tiles) will be used in the order  [red, yellow, green, blue]  as far as possible. You can change that order if you want (Section 2).

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 rect­angle.

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 rect­angle’s lower boundary get a new color.

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

10. History + Notes and References

The problem of dividing a rect­angle into squares of different sizes was addressed well before the advent of the computer. As early as 1925 it was known1 that a rect­angle with sides 32 and 33 units could be divided into 9 squares with sides of 1, 4, 7, 8, 9, 10, 14, 15, and 18 units.

During the years 1936–38, four students at Trinity College, Cambridge, constructed a number of perfect rect­angles 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 rect­angle 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 rect­angle, 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 equations2 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.

Perfect squared square of order 21 embroidered on a pillow.
Photo: Bjarne Pagh Byrnak 2011. Public Domain
Figure 3.  The perfect squared square of order 21 discovered by A. J. W. Duijvestijn in 1978, em­broidered on a pillow later the same year.
(Cross stitch by Magda Julie Bomholt)

Others later continued their work. In 1978, a perfect square of order 21 was dis­covered4 by A. J. W. Duijvestijn of Twente University of Technology in the Nether­lands, 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 pre­sented me with a perfect square of order 21 as a gift, embroi­dered on a pillow (Figure 3). Having en­joyed the sight of it every day for more than thirty years now, I tend to regard its aesthetic quality as being artistically tenable.

DISCLAIMER

Touchscreen functionality was developed on the author’s  Samsung Galaxy S6 smart­phone. The code uses only primitive touch events, likely to work the same way across browsers and operating systems;  but it has so far been verified only in Android.

The Live Show algorithm that is part of this website was developed by intuition, not by theo­retical analysis. Results obtained by using the algorithm should not be regarded as scientific proof. The algorithm searches for perfect rect­angles fairly well, but perfect squares are rare in comparison, and the algorithm is inefficient when used to search for perfect squares. It is also inefficient when searching for perfect rect­angles if the graph has more than about 15 vertices.

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, tell it to continue. If you want to study squared rect­angles 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 rect­angle 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 rect­angle of order 64 in a fraction of a second.

Finally, do not forget to visit some of the many excellent websites5 on perfect squared rect­angles that exist!

(Author:  Bjarne Pagh Byrnak)

ACKNOWLEDGMENT

The wz_jsgraphics.js library written by Walter Zorn was used for the squared rectangles.  Source: www.walterzorn.de/en.  (A slightly modified version of wz_jsgraphics.js is presently used, with DOM methods replacing embedded HTML in string literals.)  More information and a demo can be found on the Walter Zorn page at this site.

The jsbn BigInteger library, written by Tom Wu of Stanford University, was 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 could equally well have been used. However, jsbn was found to solve the equations much faster – and visitors do not have to wait for Java to start up.

NOTES AND REFERENCES

[1] Outlines of early work, including biographies, may be found, for instance, at
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 rect­angles,” 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 at
http://doc.utwente.nl/68433/1/Duijvestijn78simple.pdf .
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 rect­angles 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 rect­angles 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.)

11. Options (Advanced)

Color rectangles automatically

This option is checked as default. If it is checked and the program is executing a Live Show, you can use the next option to choose between fast coloring or animated coloring. If you uncheck it and a Live Show is not going on, you can use the buttons color and animate to choose between fast and animated coloring.

Use animated coloring when coloring is automatic

This option is unchecked as default. You may check or uncheck it to switch between animated coloring and fast coloring any time, even during an ongoing Live Show. More about animated coloring in Section 9.

Add hull edges automatically

Purpose:
To assist the user in keeping the hull edges up-to-date when vertices are created, removed, or moved. The hull edges are those edges that go around the graph’s periphery (i.e., those that a rubber band stretched around the graph would follow). Hull edges around the periphery are always present in a graph that represents a perfect or an imperfect rect­angle.

When checked:
The edges around the graph’s periphery are updated whenever a vertex has been created, removed, or moved.

When unchecked (not recommended):
Edges around the graph’s periphery must be created manually. To analyze a graph with one or more hull edges missing is sometimes possible but not very useful.

Plot printable

When unchecked:
The graphics is shown in the normal manner.

When checked:
The graphics is shown in a manner that makes it more suitable for printing.

Background colors for the document body, the rectangle canvas, and the graph canvas are set to white in order to save ink. Canvas borders are made invisible, and so are the links at the top of the page. Note that the canvases may still be moved and resized.

If you do not want this guide to be printed along with the graphics, navigate to one of the no-text versions as the very first step.

Assuming that you do not want the main buttons to show up in print, type b to hide the button canvas. Type b again if and when you later want to get it back. Similarly, you may type m to hide or show the message canvas.  (Instead of those keystrokes, some of the options below may equally well be used.)

If your browser has a Print Background setting, you should probably switch it on.

To make a browser print the graphics may be tricky, and you may have to experiment with other browser settings too, or even with the choice of browser.

As of May 2016, Chrome seems to print better than Firefox.  In case of trouble, a simple solution is to take a screenshot, paste it into your favorite graphics program, and print from there.

Show rectangle   (key shortcut: r)

When checked:
The rectangle canvas is visible.

When unchecked:
The rectangle canvas is not visible.

Show graph   (key shortcut: g or G)

When checked:
The graph canvas is visible.

When unchecked:
The graph canvas is not visible.

Show main buttons   (key shortcut: b or B)

When checked:
The button canvas is visible.

When unchecked:
The button canvas is not visible.

Show palette   (key shortcut: p or P)

When checked:
The palette canvas is visible.

When unchecked:
The palette canvas is not visible.

Show message canvas   (key shortcut: m or M)

When checked:
The message canvas is visible.

When unchecked:
The message canvas is not visible.

Show textarea   (key shortcut: t or T)

When checked:
The textarea is visible.

When unchecked:
The textarea is not visible.

Number of animated coloring solutions to show for each rectangle

The value of the option indicates how many colorings you want to see when using
animated coloring (Section 9).

Default value: 1.
Minimum value: 1.
Maximum value: 10000.

Time delay (ms) between successive animated coloring solutions

When an animated coloring has finished and additional coloring solutions are to be shown, the algorithm pauses for the indicated time interval before it starts computing the next coloring solution. Default value: 3000 ms, that is, three seconds.
Minimum value: 1.
Maximum value: 20000.

Tile border thickness (pixels)

The value defines the thickness (pixels) of the black tile borders.

Default value: 1.
Minimum value: 0.
Maximum value: 6.

Edge thickness (pixels)

The value defines the thickness (pixels) of the edges shown on the graph canvas.

Default value: 2.
Minimum value: 0.
Maximum value: 9.

Time delay (ms) after a Live Show has found a rectangle

When a rectangle of the desired kind has been found and displayed on the rect­angle canvas, the program pauses for a certain time interval before it starts searching for another rect­angle.

The value determines the length (milliseconds) of that time interval.

Default value: 2000 ms, that is, two seconds.
Minimum value: 0.
Maximum value: 20000.

Number of Live Show engine operations to execute before taking a break

Searching for perfect rectangles may be a computation-intensive task. The program will regularly stop, take a break of a suitable length, and resume. It will typically do so several times per second. If it didn't, and if rect­angles of the desired kind are not often found, the browser would sooner or later assume that the script has gone into an endless loop and urge you to terminate it.

This option and the next two options may be used to fine-tune the program’s performance. The default settings assume that you might want to use the computer for other purposes now and then while the program is running. If you want to fine-tune, look at your processor’s activity level in the Taskmanager or similar program and experiment a little. The best settings may depend on the type of processor, the number of processors you computer has, and the speed of your browser’s JavaScript engine.

The value determines how many times a certain type of function call is executed before the program takes a break.

Default value: 15000 for Firefox and Google Chrome, between 11000 and 13000 for other browsers.
Minimum value: 1.
Maximum value: 30000.

Effect of increasing the number:
The search may proceed a little faster – but your browser may urge you to stop the script.

Effect of decreasing the number:
The computer can more easily be used for other purposes while a Live Show is running.

Time delay (ms) when the Live Show engine takes a break

The value determines the length (milli­seconds) of the break the program takes when a lump of function calls did not result in the discovery of a rect­angle of the desired quality.

Default value: 120.
Minimum value: 0.
Maximum value: 2000.

Effect of increasing the number:
The computer can more easily be used for other purposes while a Live Show is going on.

Effect of decreasing the number:
The Live Show may proceed a little faster.

12. Key shortcuts

The shortcuts below are case insensitive except where indicated.  If your browser has reserved a lower-case letter for its own purpose, it may sometimes help to use the upper-case letter, and vice versa.
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
The arrow keys have their usual function, which is to scroll the page if the document is in the foreground, or select the next or previous item in the drop-down menu if that element has focus.

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.

APPENDIX.  Messages on the Message Canvas During a Live Show

A message such as
 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.

Edges forming a path through some inner vertices of a subgraph
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 upper­most 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 sub­graphs. The sub­graphs will be of cate­gory A and B, re­spec­tively, if both have inner vertices. The cate­gory of a graph or subgraph with no inner vertices is N.

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.




Home    No Guide 7 11 12 28 0    Walter Zorn Graphics    Top of page    Who?