# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1723: Four lots of dots

From New Scientist #2890, 10th November 2012 [link]

The picture shows 16 dots drawn in an evenly spaced 4-by-4 square array. How many squares can be made using four of the dots as the vertices? In fact there are 20, including the one shown.

I have now drawn another square array of the same type but with a larger number of dots. This time the number of squares possible is four times the number of dots.

How many dots have I drawn?

[enigma1723]

### 3 responses to “Enigma 1723: Four lots of dots”

1. Jim Randell 7 November 2012 at 6:12 pm

The following Python program is a constructive approach that counts the number possible squares on the grid. It runs in 44ms.

If you want a fast non-constructive approach it turns out there is a simple formula that generates the required sequence (see OEIS sequence A002415).

```from itertools import count
from enigma import irange, printf

# a square with diagonal (x1, y1) - (x2, y2)
def square(n, x1, y1, x2, y2):
# consider the square with doubled co-ordinates
# determine the centre of the square
(cx, cy) = (x1 + x2, y1 + y2)
# translate the centre to the origin
(x, y) = (2 * x1 - cx, 2 * y1 - cy)
# determine the other corners of the translated square
# rejecting any that lie off the grid
vs = set(((x1, y1), (x2, y2)))
for (xn, yn) in ((y, -x), (-y, x)):
(x, r) = divmod(cx + xn, 2)
if r > 0 or x < 0 or x > n: return None
(y, r) = divmod(cy + yn, 2)
if r > 0 or y < 0 or y > n: return None
return vs

# count the number of squares for an (n+1) x (n+1) grid
def squares(n):
r = 0
# starting point of the diagonal is x1, y1
for y1 in irange(0, n):
for x1 in irange(0, n):
# end point is x2, y2
for y2 in irange(y1, n):
for x2 in irange(x1 + 1, n):
# make the square with this diagonal
if square(n, x1, y1, x2, y2): r += 1
return r

# try increasing grid sizes
for n in count(2):
s = squares(n - 1)
n2 = n * n
printf("{n}x{n} grid, {n2} dots, {s} squares")
if n == 4: assert s == 20 # check we get the right value when n=4
if s == 4 * n2: break
```

Solution: You have drawn 49 dots.

Using the formula S(n) = n²(n² – 1)/12, we are looking for the value of n² where S(n) = 4n², so n²(n² – 1) = 48n², or n² – 1 = 48, hence n² = 49.

• Jim Randell 12 November 2012 at 2:54 pm

Here’s a different way of counting the squares:

```from itertools import count, product
from enigma import irange, printf

# count the number of squares with offset (a, b)
def nsquares(n, a, b):
r = 0
# start at <x1, y1> on the grid and consider the other 3 vertices
for (x1, y1) in product(irange(0, n - 1), irange(0, n - 1)):
(x2, y2) = (x1 + a, y1 + b)
if x2 > n or y2 > n: continue
(x3, y3) = (x2 - b, y2 + a)
if y3 > n: continue
(x4, y4) = (x3 - a, y3 - b)
if x4 < 0: continue
r += 1
return r

# count the number of squares for an (n+1) x (n+1) grid
def squares(n):
r = 0
# consider squares with horizontal offset of a
# and vertical offset b (where a + b <= n)
for b in irange(0, n - 1):
for a in irange(1, n - b):
r += nsquares(n, a, b)
return r

# consider increasing grids
for n in count(2):
s = squares(n - 1)
n2 = n * n
printf("{n}x{n} grid, {n2} dots, {s} squares")
if n == 4: assert s == 20 # check we get the right value when n=4
if s == 4 * n2: break
```

It turns out that `nsquares(n, a, b)` = [(n + 1) – (a + b)]2, so the sequence we are generating is:

`S(n) = sum(csum(i2 for i in range(1, n)))`

where `csum()` is the cumulative sum function from the enigma.py library.

And if you crunch the maths you get: S(n) = (n4 – n2)/12.

2. Brian Gladman 8 November 2012 at 5:09 pm

Here is my version.

```# x_max and y_max are the width and height of the grid with grid
# points (x, y) such that 0 <= x <= x_max and 0 <= y <= y_max.
from itertools import product, count

# for a square with vertexes on grid points (x0, y0) and (x1, y1),
# check that the remaining two vertexes are both within the grid
def check(x0, y0, x1, y1, x_max, y_max):
if 0 <= x0 + y0 - y1 <= x_max and 0 <= y0 + x1 - x0 <= y_max:
if 0 <= x1 + y0 - y1 <= x_max and 0 <= y1 + x1 - x0 <= y_max:
return True
return False

def cnt_sq(x_max, y_max):
cnt = 0
# place the first grid point
for x0, y0 in product(range(0, x_max), range(0, y_max)):
# the second grid point must be right of the first to
# avoid counting duplicate squares
for x1 in range(x0 + 1, x_max + 1):
# and it must not be below the first
for y1 in range(y0, y_max + 1):
# check that the other two vertexes are within the grid
if check(x0, y0, x1, y1, x_max, y_max):
cnt += 1
return cnt

for n in count(1):
# look for an n value such that the number of squares
# is four times the number of grid points
if cnt_sq(n, n) == 4 * (n + 1) ** 2:
print('Answer =', (n + 1) ** 2)
break
```

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