Tuesday, October 3, 2017

a Truchet puzzle mystery

I thought it would be fun to create a page of Truchet puzzles, and while doing this I noticed something that surprised me: even though they were randomly generated, all puzzles of the same size had the exact same level of complexity.

a single puzzle piece
that can be rotated into 4 positions

In these puzzles, Truchet tiles like the one above are used to create a specific pattern. All the pieces are the same - it is just a question of rotating them correctly to make the pattern you are aiming for.

a Truchet puzzle: can you make this pattern
using only Truchet tiles?

We can make these Truchet puzzles a bit more interesting if we have a specific starting arrangement, and add the restriction of using the smallest number of moves (clockwise rotations of individual tiles) to get from the starting arrangement to the target arrangement.

how many clockwise rotations of tiles will it take to transform
the square on the left to the one on the right?

On this page, you can try out some puzzles like this. Because you are only allowed to rotate pieces clockwise, you may have to rotate a given tile 0, 1, 2 or 3 times in order to get it into the desired position.

Please give it a try: https://dmackinnon1.github.io/truchet/match.html

When setting up this puzzle page, I used a restricted set of arrangements for both the starting and target arrangements. For the starting arrangement, I have all the Truchet tiles in the same position. Let's call this  type of arrangement a uniform Truchet square. There will be 4 different uniform Truchet squares of a given size; here is one for n = 6:

a uniform Truchet square: all tiles
are in the same position

Because I like the way they look, I chose the target arrangements to always have 4-fold rotational symmetry. An important choice as it turns out. These Truchet squares have sides of even length, and can be divided up into 4 quadrants - as we move around the quadrants in a clockwise direction, the pattern in each quadrant is a 90 degree rotation of the pattern in the preceding quadrant.

you can make Truchet squares with 4-fold rotational
symmetry - they tend to look nice.

With these restrictions, I found that:
  • All 2x2 puzzles are solvable in 6 moves.
  • All 4x4 puzzles are solvable in 24 moves.
  • All 6x6 puzzles are solvable in 54 moves.
Mysteriously, no matter what pattern was chosen for the target, all puzzles of the same size required the same number of moves to solve. 

symmetric puzzles of the same size always
have the same number of required moves

In general, it turns out that for any Truchet square T with side length n and 4-fold rotational symmetry, T will always be 6*(n/2)^2 rotations away from any uniform Truchet square.

This was more puzzling than the original puzzles: how could my randomly generated puzzles all require the same number of moves to solve?

To understand why this is the case, we can find a way to count all the rotations required to transform a uniform Truchet square into one that has four-fold rotational symmetry, and see that this does not depend on a particular choice of either the starting arrangement or the target. This turns out to be easier than you might expect.
Let U be a uniform Truchet square of side length n, and T be a Truchet square with 4-fold rotational symmetry, also of side length n. We'll count how many rotations it takes to transform U into T
Let t1 be a tile in the first quadrant of U. If we consider its image under rotation into the other quadrants, we have a set of 4 tiles, t1, t2, t3, and t4. One of these will be aligned with the corresponding tile in T (since the tiles in T that lie in the same positions as t1, t2, t3, and t4 are rotated through all 4 positions, while the tiles of U are all in the same position). It will require 0 moves for this tile be put into the same position as the corresponding tile of T. As we move around the quadrants to the other images of our selected tile, they will all be in the same position (U is uniform), but the corresponding tiles of T will be rotated. The corresponding tiles of T will be 1, 2, and 3 rotations ahead from the tiles of U. So each tile in the first quadrant will, along with its images under rotation, contribute 0+1+2+3 = 6 rotations to the overall number of rotations required to transform U into T. There are (n/2)^2 tiles in the first quadrant, hence the total number of rotations required to transform U into T will be 6*(n/2)^2.
for a given n, it always takes the same number of moves
 to transform a uniform Truchet square U into another
one, T, if T has 4-fold rotational symmetry

The reason for all the puzzles requiring the same number of moves is the 4-fold symmetry of the target (and the uniformity of the starting arrangement). If we allowed non-symmetrical target arrangements, or varied the starting arrangements used, the number of rotations required to transform our starting arrangement into the target arrangement could lie anywhere between 0 and 3n^2.

a 24 x 24 Truchet square with 4-fold rotational
symmetry - starting from a uniform square, how
many moves would be required to re-create it? 

Why do the Truchet squares with rotational symmetry seem particularly nice? The human brain loves symmetry, but in the case of Truchet squares, it seems particularly appropriate to be drawn to arrangements like these. Individual Truchet tiles lack rotational symmetry - this lack of symmetry is what gives them their expressive power. By arranging them into a square pattern that does have rotational symmetry, we are overcoming the asymmetry of the original tile, appealing maybe to our need to unify opposites, or to express a sense of dialectical tension.

Some earlier posts on Truchet tiles:
truchet en plus
truchet tiles

Friday, September 15, 2017

a polynomial division calculator

Many visitors to this blog come to see the posts about dividing polynomials using the grid method (like this one).  A while ago, I put up a page which generates examples that (hopefully) illustrate this method.

Well, I am excited to say that the examples page has been enhanced with the addition of a simple calculator, which allows you to provide your own polynomials for dividing.

This is not a sophisticated calculator - the polynomials you provide need to be in expanded form, and they have to be single variable polynomials using "x" for the variable - don't try to be fancy or tricky, please.

For example, you may want to try something like this:
After you provide your polynomials, hitting the calculate button will trigger the parser, that will let you know of any errors. If all goes well, you are prompted to have the calculator show the answer:

If you click the Show Answer button, the answer and the grid used for division is shown.


Finally, clicking on the Show Additional Steps button will walk you through how the grid was filled in to obtain the answer.

I hope that this page turns out to be helpful. Please let me know of any issues you run into when using it.

Grid Division Calculator: dmackinnon1.github.io/polygrid/calc.html

Grid Division Example Generator: dmackinnon1.github.io/polygrid


Monday, July 17, 2017

interactive chladni figure page

A while back there were some posts about generating Chladni Figures using R scripts. These scripts generated some pretty nice images, I thought. But, to experiment a bit more it would be nice to have something interactive, so I put together this page, which you can use to make images like the one below.


Adding more vibrations to the surface, you can get some pretty intricate looking patterns:


If you would like to try it out, please visit: https://dmackinnon1.github.io/chladni/ (source here).

Saturday, April 29, 2017

truchet en plus

Since the previous post, I have been playing around with more variations on Truchet tiles (using this page). The variety of appealing patterns that you can create from these simple tiles is impressive.

the humble Truchet tile

For example, using this simple base tile you can create a path-like effect, even to the extent that paths can seem to weave under and over each other. The patterns below use this effect to suggest links and knots.

Truchet patters for two links (left)
and a trefoil knot (right)

Slight variations in the base tile can produce interesting effects. Here's an example that uses the traditional Truchet base tile.


Bulging the dark right triangle into a quarter circle allows us create something that looks quite different, even though it consists of exactly the same tile placements. Squares are replaced by circles, V-patterns replaced by tulips, and we end up with organic and densely packed patterns.


A common variation on the Truchet tile is the Smith tile, which consists of two quarter circles at opposite corners. Unlike the traditional Truchet, the Smith base tile has 180 degree symmetry, but because it lacks 90 degree symmetry, it can still be used to produce interesting and appealing patterns (if we had quarter circles in all four corners, the constructed patterns would always be the same - an array of circles). Using this tile, we end up with circles and blobby regions that create paths and zones across the grid.


A small change to the Smith tile allows us to eliminate the 180 degree symmetry and regain the expressiveness of the traditional tile patterns. For example replacing one of the quarter circles with a square means that some circles in our original pattern become squares, some remain circles, and some take on a lemon-shape, while the overall pattern retains the same topology as it has in the Smith version.


Another small change (using a diagonal line in place of the square) produces patterns that look quite different at fist: our paths now resemble strange jigsaw shapes. A closer look shows how the essential features are retained.


Even with all the possible variations, the original tile retains its charm. Can you see the four trefoils in the pattern below?


Sunday, March 26, 2017

truchet tiles

A short while back, I posted about the images found in books about Froebelian kindergarten exercises, like The Paradise of Childhood (on Google Books here). These old books provide great examples of patterns and designs that can be easily drawn by hand with graph paper, in many cases only using arrangements of congruent 45-90 triangles.


Nineteenth Century Froebelian Doodles

A surprising variety of patterns can be formed by restricting things even further, considering the case where each square is cut in half along a diagonal with half of the square coloured black, the other coloured white (i.e. no blank or completely filled squares, as are found in the images above).

Some arrangements of four Truchet Tiles

Arrangements of these tiles were studied extensively by Sebastien Truchet, whose book on the subject (Method for creating an infinite number of different designs with squares halved into two colours along a diagonal) can be found online here.


Truchet tiles, as they became known, have been studied extensively and generalised to include other tile sets that are not rotationally symmetrical. In the image below, we start with a traditional Truchet tiling, then only show the diagonals, and finally replacing the diagonals with quarter circles, centred around the vertices where the diagonals used to touch (these tiles, introduced by Cyril Stanley Smith, create interesting patterns of blob-like paths and circles).

Three popular variations on Truchet tiles:
traditional, diagonal, and semi-circles


To play around with these I've put together a "Truchet Tiles" page here.

There are a number of illustrations in Truchet's text that are worth checking out, and you can reproduce them using the page mentioned above. Here is tiling "38" from Truchet:

tile pattern 38 from Truchet

Here is the same tiling using the Truchet tile page, also rendered using only diagonals and the Smith tiles.
tile pattern 38, generated here


There are lots of questions that can be asked about arrangements of the tiles. Truchet enumerates some of the possible arrangements using symbols and illustrations - below are the first two tables of rows of tiles that he lists (how many will be in the next two tables?).


Here is another rendering of one of Truchet's original patterns, number 52:


And replacing the traditional truchet tiles with similarly oriented diagonal and Smith tiles -  as you might have noticed, doing this looses information by a factor of 2 for each tile:


Try out the Truchet tile page here: https://dmackinnon1.github.io/truchet/.

Update: More truchet fun in this post.

Friday, March 24, 2017

probability simulations using R

An ongoing side project of mine is learning how to use the statistics scripting language R, and have been putting putting together R markdown files that set up simulations for a variety of probability problems. You can find some of them here: https://dmackinnon1.github.io/r_examples/.

These are simulations that generate data based on problems like the Birthday problem, the Monty Hall problem, and the Burnt Pancake problem. Learning scripting languages aside, it is always good to keep digging into probability problems: they confuse practically everyone.

Tuesday, March 7, 2017

Ulam's two step cellular automata


Above are some of the nice images generated by a cellular automata described in one of Martin Gardner's essays about Conway's Game of Life (you can find the essays here). Cells have four neighbours (north, south, east, west), and follow only two rules that are applied at each step: if a cell has one live neighbour it turns on, and if a cell is on it turns off after two steps. The images above start happening around step 100 after turning on a single cell at the centre of a 61 by 61 grid.

You can play with these here. Eventually, these will start to repeat or disappear completely (I suspect they will oscillate, but have not found out when yet). On a 5 by 5 board, a single central cell will lead to a pattern that dies out in 10 generations; once you get to the uniform checkerboard state, the next is an empty board.



Monday, March 6, 2017

the ants go marching...


It's not exactly pride or satisfaction, but some related feeling, when you see your little ant marching off on the highway that emerges from the initial chaos it seemed lost in. Keep marching little buddy.


You can create a small ant farm here, if you'd like.

Saturday, February 11, 2017

fibonacci foolery

Some misleading dissections

Consider a square whose sides are 5 units in length. We are going to dissect the square by cutting it as shown below.  We can then re-arrange the pieces to form a rectangle.


But wait, the square has area 5 * 5 = 25, while the rectangle has area 8 * 3 = 24... somewhere we lost one square unit. This paradoxical result tells us that something is wrong, but what is it?

Let's look at another very similar dissection, this time using a square with sides length 8 units, sliced up and re-assembled in a similar way:


Here the square has area 8 * 8 = 64, but the rectangle has area 13 * 5 = 65. In this case we have gained one square unit (maybe borrowed from puzzle above?).

In both cases, the discrepancy in the areas tells us that we are doing something illegal when we re-assemble the square into the rectangle. You can see where the problem is if you look at the triangles within the rectangles. Consider the first problem, where we split up the length 5 into lengths 2 and 3. Can we really put those pieces together? Apparently not - if we try to fit one of the triangles and quadrilaterals pieces together, we find that they don't actually form a right-triangle - the hypotenuse is not straight, it bumps out a bit:



In the (2,3,5) problem, if the figure did line up properly, the large triangle with base 8 and height 3 would be similar to the smaller triangle with base 5 and height 2. This would mean that 2/5 equals 3/8, which is not true. If we place the original triangle of base on top of the larger triangle, the pieces would not line up:


The Fibonacci connection

You may have noticed something familiar in the numbers used in the dissections above. Both triples (2, 3, 5), used in the first dissection, and (3, 5, 8), used in the second, are successive terms in the Fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, ..

The Fibonacci sequence is defined recursively by:



Can we construct another misleading dissection using the next Fibonacci triple (5, 8, 13)? Let's see:


Our square in this case has area 13 * 13 = 169, while our rectangle has area 21 * 8 = 168. So we are back to losing a square unit when we re-assemble the dissected square into the rectangle.

It turns out that Fibonacci triples like these will always generate these "off by one" illusions, because three successive terms in the Fibonacci sequence always obey the Cassini identity, which expresses the situation shown in these diagrams: if you have a Fibonacci triple (a, b, c), then the product of a times c is going to be either one more or one less than the square of b. More precisely, Cassini tells us:

The Cassini identity can be proved in a variety of ways, including induction. For n = 1, we have 0*1-1 = -1, so the identity is satisfied.  If we assume the relationship holds for n = - 1, we can prove the n = k case as follows:


See some more proofs of the Cassini identity here.

A Golden Solution

This dissection and re-assembly of the square into a rectangle looks like a nice one, and we'd like to find a case where it works: we want to find where to cut so that the square pieces fit correctly into the rectangle and the areas of the figures match up. Clearly basing the cut on the Fibonacci numbers won't work...

Let's start with a square whose sides are length 1. We would like to find two numbers a and b such that we can perform the dissection and assembly as shown below.


What we would like is the area of the rectangle to equal that of the square:


And taking the positive solution from the quadratic formula, we get:

We used the capital Greek letter Phi here because this quantity is known as the golden ratio conjugate, making the base of our rectangle, 1 + b, equal to the golden ratio.

This is a nice surprise because of the close association between Fibonacci numbers and the golden ratio  -  the quotient of consecutive Fibonacci numbers becomes closer and closer to the golden ratio as the Fibonacci numbers get larger.

So, while using Fibonacci numbers in the dissection always yields nice deceptions which alternate between gaining and loosing a square unit, slicing the square using the golden ratio (or golden ratio conjugate) gives us a perfect re-assembly of the square into a rectangle.


Sunday, January 29, 2017

build your own knight's tour

A couple of posts back I mentioned some knight and king's tour puzzles that I had put together (knights here, kings here). I've added another page based on the same underlying framework where you can build your own knight's tour.

You start off with something like this:


Green squares indicate a legal move, and the numbers on each square tell you how many open moves are available from that square.

Visited squares are marked with a check, and a map of your path is traced on the image below the board.



The "Warnsdorff" heuristic for finding a tour is to always move to a square with the lowest number of available moves. This heuristic works well - it often leads you to a successfully completed tours. You can try this approach, or experiment with others. In the example above, following this method presents you with two choices initially (moving to one of the two squares with 2 open neighbours), but at the third move leaves you with only one option.

Whatever approach you take, if you feel you've made a wrong move, or find that you are completely blocked, hit the "backtrack" button to move back one step.

Some older posts on knight tours:
Knight Moves
Closing Time
Punctured Tours

Wednesday, January 18, 2017

a julia and mandelbrot fractals page

A Julia dendrite

A few years back, I posted about generating my first image of a Mandelbrot set using Processing. I decided to do it again, mostly to get some more JavaScript practice. So now a page that generates some Mandelbrot and Julia set fractals is available here.

AnotherJulia set fractal

The fractals are generated almost exactly as described in that earlier post. The only difference is the JavasScript and HTML infrastructure. Source is here for the curious.