.
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.
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, you will get a warning when you try to analyze the graph.
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 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, the tiles no longer fit accurately together, 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 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.
Rectangles will not be colored until you press Color for fast coloring or Animate for animated coloring.
The next option can be used to choose between animated coloring and fast coloring.
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.
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.
For each tile, the algorithm uses the neighbor principle to find 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 already. 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 so far 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 a 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 several attempts, the algorithm will arrive at the tile that caused the backtracking and find that the tile now has at least one available color. The tile is then colored, 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 coloring 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.
The buttons Faster, Slower, and Animate / Pause / Resume can be used to control the animated coloring.
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.
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.
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 forty years now, I tend to regard its aesthetic quality as being artistically tenable.
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