7x7 Golomb square

Question

Can you paint $7$ cells of a $7 \times 7$ grid such that the Euclidean distance* between any pair of painted cells is distinct? Good luck!

*The Euclidean distance between cells $(r_1,c_1)$ and $(r_2,c_2)$ is $\sqrt{(r_1-r_2)^2+(c_1-c_2)^2}$.

Answer 1

I don't know how you would be able to deduce a solution to this, so I used a computer. It turns out that the solution is unique (ignoring rotation and reflection).

 X . . X . . .
 . . . . . . .
 X X . . . . .
 . . . . . . .
 . . . . . . .
 . . . . . X .
 . . X . . . X

My C# program does a straightforward exhaustive search:

  using System;
  using System.Collections.Generic;

  namespace TempProg
  {
     class PSEGolombSquare
     {
        private const int N = 7; // grid size
        private const int S = 7; // number of squares

        public static void Main()
        {
           DoSearch(new int[S], 0);
        }

        private static void DoSearch(int[] coords, int nextIndex)
        {
           if (nextIndex == coords.Length)
           {
              // founf a solution
              foreach (int i in coords)
                 Console.Write("{0}{1}  ", i % N, i / N);
              Console.WriteLine();
              return;
           }
           // add another square
           int first = nextIndex == 0 ? 0 : coords[nextIndex - 1] + 1;
           for (int c = first; c < N * N; c++)
           {
              coords[nextIndex] = c;
              if (IsValid(coords, nextIndex + 1))
                 DoSearch(coords, nextIndex + 1);
           }
        }

        private static bool IsValid(int[] coords, int num)
        {
           ISet<int> distances = new SortedSet<int>();
           for (int i = 0; i < num; i++)
           {
              for (int j = i+1; j < num; j++)
              {
                 int d = GetDistance(coords[i], coords[j]);
                 if (distances.Contains(d)) return false;
                 distances.Add(d);
              }
           }
           return true;
        }

        private static int GetDistance(int v1, int v2)
        {
           int dx = v1 % N - v2 % N;
           int dy = v1 / N - v2 / N;
           return dx * dx + dy * dy;
        }
     }
  }

Answer 2

Matt Parker hosted a challenge to solve this puzzle last year. The participants found that there were two distinct solutions for 6x6, one for 7x7, and none for 8x8 or 9x9 (up to rotations/reflections).

https://youtu.be/G0i_YSFvMb0?t=366

According to comments on the video, the search was extended with no solutions found up to 14x14, and you can prove that no solutions exist for larger grids because there are more combinations of pairs of points than there are possible distinct distances.

https://oscarcunningham.com/670/unique-distancing-problem/