How many squares of any size are there on an 8x8 chessboard?
Tags: math, sequences, puzzles
Published: 2020-02-04 15:09:23

---
title: How many squares of any size are there on an 8x8 chessboard?
published: true
description: A problem illustrating some principles of discrete math
tags: math, sequences, puzzles
---

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](https://en.wikipedia.org/wiki/Sequence)
* 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.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/y1p2zntzbep43lfiuupl.png)

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.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/3pqiwmb9y1corjly7uj7.png)

#### 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)


![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/ba2xoxne9qmnj6rxv0dn.png)

If n = 3, the number of squares on your n x n grid is: 0<sup>1</sup> + 1<sup>2</sup> + 2<sup>2</sup> + 3<sup>2</sup> 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, Δ<sup>3</sup> 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 Δ<sup>k</sup>-constant

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

a<sub>n</sub> = an<sup>3</sup> + b<sup>2</sup> + cn + d

Note: a<sub>n</sub> 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.

a<sub>0</sub> = 0 = a(0)<sup>3</sup> + b(0)<sup>2</sup> + c(0) + d

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

a<sub>1</sub> = 1 = a(1)<sup>3</sup> + b(1)<sup>2</sup> + c(1) + 0
a<sub>1</sub> = 1 = a + b + c

a<sub>2</sub> = 5 = a(2)<sup>3</sup> + b(2)<sup>2</sup> + c(2) + 0
a<sub>2</sub> = 5 = 8a + 4b + 2c

a<sub>3</sub> = 14 = a(3)<sup>3</sup> + b(3)<sup>2</sup> + c(3) + 0
a<sub>3</sub> = 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.

a<sub>1</sub> = 1 = a + b + c
a<sub>2</sub> = 5 = 8a + 4b + 2c
a<sub>3</sub> = 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:

a<sub>n</sub> = 1/3(n)<sup>3</sup> + 1/2(n)<sup>2</sup> + 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`