Enigmatic Code

Programming Enigma Puzzles

Enigma 1009: Squared square

From New Scientist #2164, 12th December 1998 [link]

The diagram shows the simplest solution to the classical problem of dissecting a square into a number of smaller squares all with sides which are integers, no two the same. Unfortunately, the dimensions (several of which are prime numbers) have been deleted.

By studying the diagram with care can you determine the side of the outer square?

[enigma1009]

2 responses to “Enigma 1009: Squared square

  1. Jim Randell 24 May 2019 at 8:13 am

    (See also: Enigma 1491, Enigma 17, Enigma 1251, Enigma 1241).

    We can use the technique of examining horizontal and vertical slices of the diagram that I used in Enigma 1241, except that this time the variables consist of the dimensions of the 21 smaller squares and the larger square that they fit in to (so 22 variables in all).

    The linear equations give us a system of 22 equations, but the system is not complete (as we can scale up all the squares by the same amount and get further solutions). But if we fix the value of the smallest square, say at 1, then we can solve the system of equations to get the size of all the other squares in relation to the smallest square.

    I’ve recently enhanced the Gaussian Elimination solver (originally written for Enigma 287) and made it available in the enigma.py library as [[ matrix.linear() ]].

    This Python program uses the [[ matrix.linear() ]] solver to solve the system of equations, verifies the (non-linear) area constraint, and then scales the solutions up so that they are all integers. It runs in 121ms.

    Run: [ @repl.it ]

    from enigma import matrix, mgcd, printf
    
    # variables
    vs = "abcdefghijklmnpqrstuvx"
    
    # combinations that equal x
    combs = [
      # horizontal slices
      "utr", "utbq", "uinq", "mkinq", "mkdfnq", "mcjafnq", "mcjhv", "lgjhv", "lesv", "psv",
      # vertical slices
      "umlp", "umgep", "ukcgep", "ukcgs", "ukjs", "tidjs", "tidahs", "tifhs", "tnhs", "tnv", "rbnv", "rqv",
    ]
    
    # construct the 22 equations in 22 variables
    eqs = list(list((int(v in s) if v != 'x' else -1) for v in vs) for s in combs)
    
    # construct a vector of length n, consisting of u and the rest z
    vec = lambda n, u=1, z=0: [u] + [z] * (n - 1)
    
    # the system is incomplete, so suppose a = 1
    eqs.insert(0, vec(len(vs)))
    
    # solve the equations
    s = matrix.linear(eqs, vec(len(eqs)))
    
    # verify the area constraint
    assert s[-1] ** 2 == sum(v ** 2 for v in s[:-1])
    
    # turn the results into the smallest possible integers
    g = mgcd(*s)
    s = list(v / g for v in s)
    
    # output the variables
    for (k, v) in zip("abcdefghijklmnpqrstuvx", s):
      printf("[{k} = {v}]")
    
    # the solution is x
    printf("x = {x}", x=s[-1])
    

    Solution: The outer square is 112 × 112 units.

    The dimensions of the smaller squares are: 2, 4, 6, 7, 8, 9, 11, 15, 16, 17, 18, 19, 24, 25, 27, 29, 33, 35, 37, 42, 50.

    So there are 7 squares with prime dimensions: 2, 7, 11, 17, 19, 29, 37.

    If the diagram was scaled up there would be no squares with prime dimensions.

  2. Hugh Casement 24 May 2019 at 9:51 am

    It’s possibly of interest that this smallest set of 21 squares was discovered in 1962 by Adrianus Duijvestijn: see   https://en.wikipedia.org/wiki/Squaring_the_square
    I don’t know what computer he used, but it probably occupied about an acre of floor space and consumed enough electricity to cook dinners for a whole school.

    It was previously thought that 24 squares was the fewest possible.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: