Opinion
Computing Applications Last byte

Puzzled: Solutions and Sources

Last month (May 2012) we posted a trio of brainteasers concerning designs on square grids. Here, we offer solutions to all three. How did you do?
Posted
  1. 1. Tiling a 4×4 Grid
  2. 2. Circles on a Torus
  3. 3. Diagonals in a 5×5 Grid
  4. Author
  5. Footnotes
  6. Figures

Solution. You were given 16 unit squares, each containing a different combination of vertical crossing line, horizontal crossing line, SW-NE diagonal, and SE-NW diagonal. Your object was to tile a 4×4 grid with these squares in such a way that no line ends before it hits the edge of the grid—or prove it cannot be done. Figure 1 shows a solution, though there are several; it is indeed possible to arrive at one without much trial and effort, by, say, reasoning about how the long diagonal lines should be arranged. Note that if you identify the left and right boundaries of the square grid to form a cylinder, the lines continue to match up. Moreover, if you identify the top and bottom boundaries as well, so you now have a doughnut, or torus, all the lines will be endless loops. The puzzle’s composer, Barry Cipra, noted the curious fact that all solutions work on the torus; see http://www.funmath-club.com/students/sollewitt.html. It is not surprising that the horizontal and vertical lines match up on the torus. They have to. But why do the diagonals happen to match up as well?

Back to Top

2. Circles on a Torus

Solution. In a second version of Puzzle 1, each unit square contained one of the 16 possible combinations of four quarter-circles, each of radius 1/2 and centered at a corner. You were asked to tile a 4×4 grid with these squares so no path ends before it hits the edge of the grid or, better, so an even number of quarter-circles meet at each edge shared by two squares. Figure 2 shows a solution satisfying both conditions, with the additional property that the curves form a collection of circles and semicircles. But you can do better. See if you can find a solution that matches left-right and top-bottom edges so you get nothing but circles on a torus.

Back to Top

3. Diagonals in a 5×5 Grid

Solution. You were asked to place as many diagonals as you can into a 5×5 grid with no two meeting at a corner (or crossing inside a square); Figure 3 shows you can achieve 16 diagonals. To see that more are impossible, note first that there were only 6×6 = 36 vertices in the grid, with each diagonal using two of them, so you certainly cannot get more than 18 diagonals in the grid. Moreover, along each side of the grid are six vertices and only five squares, so, on each side, some vertex will go without a diagonal. If three or more vertices are left without diagonals, the maximum number of diagonals is 16. The only way the four sides can be handled with fewer than three empty vertices is if two are at opposite corners of the grid (at, say, the SW and NE corners) with no other empty vertices along the grid. But then every square touching a side of the grid would have to contain a SE-NW diagonal—an impossibility, because diagonals would then meet at the vertices diagonally opposite the empty grid corners.

Back to Top

Back to Top

Back to Top

Figures

F1 Figure 1.

F2 Figure 2.

F3 Figure 3.

Back to top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More