The Dot Game

Always a work in progress

The antidote to boredom is curiosity

I often find that the mundane and seemingly simple things can, when explored, lead to rather unexpected outcomes. This is a tale of my journey into the world of dots, and it all started, as many things do, with the antidote to boredom: curiosity.

A riveting math class had led me to stare at my notepad, doodling in between the dots, when I pondered the question:

How many dots can you have on a unit grid so that the gradient between any two dots is unique?

Repeated gradients: invalid

Valid solution

It soon became clear that the theoretical maximum number of dots, D, that can be placed on a dot grid of size N is, for all grids, N + 1, as once there are two dots in any row or column, no more can be placed. For N x M grid:

Now it was on to the task of finding the solutions with the theoretical maximum number of dots. 2 and 3 were simple, but 4 took a considerable amount of time. 5 took over 20 minutes, but 6 was seemingly impossible.

Please try to solve the puzzle yourself. (There are multiple solutions.)

To see a list of all unique solutions up to a 6 grid:

Lists of Unique solutions

Method

For many hours, days in fact, I tried to reason on paper the logic behind this seemingly simple game. Eventually, picking the project up years later, I had the skill and foolishness to this time attempt to solve this with code.

Initially, a random search was used to find solutions. We select random coordinates, and if any gradients are shared, a new point is chosen until a solution is found, or we terminate and start again after x number of tries.

This method was used to find solutions up to a 6-grid, but only 7 dots could be placed on a 7-grid. The number of dots placed in higher-order grids is shown in Figure 1.

Clearly, proof was required to confirm whether the limit for the 7 by 7 could not be reached, so an exhaustive search method was coded. But as grid sizes increase, the search time increases with 2^N. The waiting game began.

Faster methods were later discovered, such as calculating an upper bound on the search to discard a branch if it will not reach the maximum possible value, as well as precomputing all gradients.

Figure 1: Number of solutions for higher-order grids. Shown are grids with high certainty of being maximised.

Unique Solutions

Now, through an exhaustive search, all possible solutions could be identified, and it was confirmed that you cannot place 8 dots on a 7 grid. The 6 grid is the largest size at which you can have the maximum number of dots. (It is still untested for higher grid sizes due to computation time.)

But how many unique solutions are there? For the 2D case, six matrices can be used to compare all solutions and eliminate duplicates. The number of unique solutions (after rotation, reflection, inversion, etc) is shown in Figure 2. This process is by far the most computationally expensive to run.

Figure 2: Number of unique solutions.

The 3 unique solutions for placing 7 dots on a 6 by 6:

Theory

Although the solutions were found, the reason behind them was still a mystery. To approach the problem from a more mathematical background, the number of gradients was investigated. This was completed using exhaustive methods in Python.

Figure 3 highlights the complexity of the problem. The Spikes are present due to a large increase in new gradients when a prime number grid is used. Due to the somewhat random nature of prime numbers, it became clear that I do not possess the mathematical tools to solve this theoretically.

Possibly, there are many factors, such as the number of available gradients compared to the amount of new points, as the grid size increases. No such limiting factor has been found, nor is it clear why the shape of Figure 1 is as it is.

Recently, upon further research, papers have been found on this question by:

Erdős, P., Graham, R.L., Ruzsa, I.Z. and Taylor, H. (1992) ‘Bounds for arrays of dots with distinct slopes or lengths’
Peile, R.E. and Taylor, H. (2000) ‘Sets of points with pairwise distinct slopes’

which attempt to determine the maximum number of points, D, for larger grids (n x n), with Peile and Taylor quoting:

However, it appears that this is by no means a well-discussed problem.

Due to random searching, it is uncertain whether the grid has been maximised, so the estimate on the data is a lower bound (if more points are found, we obtain a steeper curve). As shown in Figure 4, using a random sampling method I found:

Figure 3: New gradients generated as grid size increases

Figure 4: Approximate fit of data for maximising square grids.

Figure 5: 8 dots on a 7 x 8 grid

Rectangluar Solutions

The problem can be generalised to rectangular grids. The maximum number of dots on an N x M grid is still limited to N + 1, but the number of unique solutions increases dramatically, as shown in Figure 6.

Interestingly, we can now get 8 dots on a 7 x 8 grid with 25 unique solutions. (Figure 5).

Figure 6: Maximum number of points for an N x M grid. Green reaches the theoretical maximum.

Figure 7: Number of different unique solutions of maximum possible points on an N x M grid.

Figure 8: The only solution to constraining a 7 x 8 grid with 4 dots.

Minimum Solutions

What is the minimum number of points we can select so that no more can be selected? In other words, what is the least number of dots to constrain the grid?

The minimum number of dots required to constrain an N x M grid is illustrated in Figure 9, along with the number of unique solutions in Figure 10. The empty squares indicate that the computation time was too long, suggesting a very large number of unique solutions.

The most intriguing point is a 7 x 8 grid with only one unique solution. (Figure 8).

Figure 9: The minimum number of dots to constrain an N x M grid

Figure 10: Number of unique solutions

The move to 3D

Figure 11: The single unique solution for 8 dots on a 3 grid in 3D.

The trivial limit for 2D of N + 1 dots on an N-sized grid cannot, as far as I am aware, be extended to the case of higher dimensions. After looking at the somewhat scarce literature, only estimates have been found. This complicates the search as we do not know what the theoretical maximum could be. Additionally, the computation time for exhaustive search gains an additional factor of N^(3/2). We compare aligned vectors instead of gradients for 3D (it is possible to use vectors for 2D, but this approach is more computationally intensive).

Furthermore, visualisation becomes significantly more challenging, and finding solutions without the aid of computers, at least for me, is virtually impossible, as shown in Figure 11. Especially when discerning whether two solutions are the same, as in 3D, 48 matrices are required for verification.

Possible applications

Figure 12: The 14 Bravais lattices in 3D, showing symmetry to the 14 unique solutions for a 4 grid in 2D. Image: Kittel, Intro to solid state physics

Relation to condensed matter Physics

There is a notable comparison between the number of unique solutions for a 2, 3, and 4 grid in 2D: 1, 5, and 14, respectively. This is the number of Bravais lattices in 1D, 2D and 3D in the field of condensed matter physics, as shown in Figure 12. This is most probably a coincidence, as unfortunately, this breaks for 4D. But considering the crystal nature of lattices and the symmetry rules governing crystal systems, it does lead one to ponder, and at the very least distract one from the rest of the lecture.

At a stretch

This problem has no regard for distances, which limits its possible uses in real-world applications; yet, these arrangements of dots may be helpful. This is because, given a set of axes, only one vector is needed to specify 2 points. This could be used in sensor arrays, for example, as it allows one to unambiguously identify which two sensors produced a measurement.

An Ode to Beautiful Uselessness

It has been many years since I began this project, and I have learned more than I could ever have initially imagined, more about my own condition. What was initially a test of my logical thought challenged me to ponder what I wish to do with this life, and sent me into spirals questioning why.

I presented my project to my academic supervisor, summarising what is outlined above. I got the following response.

' I would be happy to work with you, but I can't work on things that are solely beautiful... I only address them during my holidays when I feel I can be extravagant. My physics has to be useful and beautiful.'

I know somewhere in this world, this problem has been solved, and for someone, it was likely a Tuesday afternoon's work. Why should I spend my time searching for a path that has probably been walked before? As time ticks on, how many paths are left undiscovered? Is it arrogance or bravery that leads one to want to find a new path rather than to extend the ones that come before?

Well, I shall conclude that this project has taught me, and shall continue to teach me, to pursue what I love and find passion in what sparks my curiosity, even if the same curiosity has been explored by many. For whatever path we take, the sun always sets in the west.