## DEV Community is a community of 880,569 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Samuel Kendrick

Posted on • Updated on

# How many squares of any size are there on an 8x8 chessboard?

The chessboard is an inessential detail, so let's re-phrase the question:

How many squares, of any size, are there on an 8x8 grid?

Eventually, it'll be:

How many squares, of any size, are there on an n x n grid?

Some tools that I'll be using to solve this problem:

• Sequences
• Basic arithmetic
• A nifty property of sequences called Δ-k constants and which help us find "closed" formulas (more on that later)

As is common in problem solving, the simplest examples illustrate the problem and give a starting point.

#### A 0x0 grid

There are zero squares of any size.

#### A 1x1 grid

There is one square of size 1x1.

#### A 2x2 grid

This is where the "of any size" bit takes on meaning. In a 2x2 grid there are actually 5 squares "of any size." This is because a 2x2 grid contains 4 1x1 squares and then a single square of size 2x2.

You can see here that there are 5 squares of multiple sizes. There are four 1x1 squares and then a 2x2 square (the dashed-square). There are 4 + 1 = 5 total squares.

#### A 3x3 grid

A 3x3 grid is nothing but nine 1x1 squares, four 2x2 squares, and one 3x3 square. I've highlighted one of the four 2x2 squares (they contain numbers `1,2,4,5`). There are 9 + 4 + 1 = 14 total squares.

#### A pattern emerges

Enter sequences:

In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order does matter

Let's write the total number of squares as a sequence. The "index" of each item in the sequence represents `n` in the `n x n` grid:

`0, 1, 5, 14`

Each element in our total number of squares sequence can be defined as a the sum of all previous totals up to, and including, the current total. Put another way:

0x0 -> 0 squares (0)
1x1 -> one 1x1 square + zero 0x0 squares (1 + 0)
2x2 -> four 1x1 squares + one 2x2 square + zero 0x0 squares (4 + 1 + 0)
3x3 -> nine 1x1 squares + four 2x2 squares + one 3x3 square + zero 0x0 squares (9 + 4 + 1 + 0)

If n = 3, the number of squares on your n x n grid is: 01 + 12 + 22 + 32 or `0 + 1 + 4 + 9 = 14`.

Answering our original question is now easy.

How many squares of any size are there on an 8x8 grid?

You just sum the squares from 0 to n.

`sum([i**2 for i in range(0, 9)]) # 204`

Recall that `range` counts from `0` up to `9`, but not including `9`.

#### Finding a closed formula

We can find a closed formula to calculate this without the summation. For example, you could add all the terms of a sequence of 1, 2 ,3, ..., n to find the total. Or your could use this handy equation:

`total = (n(n+1)) / 2`

Compare: `1+2+3+4+5 = 15` and `(5(5+1))/2 = 15`.

Let's take our sequence and extend it with a few more elements:

`1, 5, 14, 30, 55`

We can find a pattern of sorts by taking the differences between terms. We can form another sequence of terms (the differences) which will always be one element shorter than the original.

``````1, 5, 14, 30, 5
4, 9, 16, 25
5, 7, 9
2, 2
``````

We took differences three times in order to reach a constant. What we just did there was find the Δ-k constant. In this case, Δ3 constant.

This is important for this reason:

The closed formula formula for a sequence will be a degree k polynomial if and only if the sequence is Δk-constant

This means our closed formula will be a degree k (3) polynomial or:

an = an3 + b2 + cn + d

Note: an represents the nth element of a, which is our sequence: `0, 1, 5, 14, 30, 55`. The 0th term is 0, the 1st term is 1, the second term is 5, etc.

a0 = 0 = a(0)3 + b(0)2 + c(0) + d

The above simplified to: d = 0—an important piece of information.

a1 = 1 = a(1)3 + b(1)2 + c(1) + 0
a1 = 1 = a + b + c

a2 = 5 = a(2)3 + b(2)2 + c(2) + 0
a2 = 5 = 8a + 4b + 2c

a3 = 14 = a(3)3 + b(3)2 + c(3) + 0
a3 = 14 = 27a + 9b + 3c

Now we have a system of equations which we can solve for to get the values of a, b, and c.

a1 = 1 = a + b + c
a2 = 5 = 8a + 4b + 2c
a3 = 14 = 27a + 9b + 3c

To save time, I will wave my hand and solve that system:

a = 1/3
b = 1/2
c = 1/6

With these values, we now have our closed formula:

an = 1/3(n)3 + 1/2(n)2 + 1/6(n)

If n = 8: `1/3(8)^3 + 1/2(8)^2 + 1/6(8) = 204`
If n = 800: `1/3(800)^3 + 1/2(800)^2 + 1/6(800) = 170986800`