These movies have been constructed to help mathematicians understand the algorithm and the halting problem. They show squares fractalized within a square with N=1 and various c values. A difference from the circle "black area" movies is that here periodic boundaries have been used. Familiarity with the basic material in the Shier-Bourke paper is assumed.
You should think of the pattern as beginning with a black square, which is the region to be filled. Each new square is a pale color, and it is surrounded by a red band whose width is the half-width of the next-to-be-placed square. Because of periodic boundaries a given placed square may have several pieces, all of the same color. Thus at each stage the remaining black region(s) is the only place where the center of the next square can go. One can use this formulation to re-state the halting problem: The algorithm never halts if it can be shown that the area of the black region(s) is always > 0.
The framing rate has deliberately been made rather slow so that you can look around a bit before the next square appears. Each movie shows 40 square placements.
The black area diminishes with addition of a new square which takes up some of the space. At the same time, existing black regions grow because the half-width of the next-to-be-placed square is steadily falling according to the defining negative-exponent power law (the "area rule"), and new black regions appear. The total black area divided by the area of the bounding square is the placement probability at the given stage of the algorithm. The total black area may go up or down from one placement to the next in a quite noisy way.
It should be kept in mind that the mathematics of the area rule dictates that in all of these movies the placed squares are "space-filling in the limit" if the algorithm does not halt.
c=1.1. This is a "low density" example. There are large connected black regions at all stages. It would seem intuitively obvious that the algorithm does not halt, but this is far from a formal proof. movie
c=1.2. A proof has been found that the square algorithm is unconditionally nonhalting if c < 4 - 2^3/2 = 1.17 (Ennis). movie
c=1.3. movie
c=1.4. The true upper limit for unconditional nonhalting may be higher than the 1.17 cited above. Numerical studies suggest that the real upper limit is around 1.4. movie
c=1.5. Many runs halt; this one is a "survivor". This is close to the highest usable c value for N=1. It can be seen that the black area is quite small, and at many points in the movie there are only a very few tiny black regions. The boundary fills rapidly, and square-to-square spacings are small. Experience shows that if a run does not halt in the first few placements it does not halt at all. movie
