4x4 4-color Golomb square

Question

This is a variation of my previous puzzle

Can you paint a $4 \times 4$ grid with $4$ colors, such that for every color the Euclidean distance* between any pair of cells of that color 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 think the answer is

Yes

C D D B
A C B C
A D A C
D B B A

First of all,

I identified all the possible distances on the 4x4 grid. They are: 1 (1x0), 2 (1x1), 4 (2x0), 5 (2x1), 8 (2x2), 9 (3x0), 10 (3x1), 13 (3x2), 18 (3x3). Since there are 9 possible distances in total, we can't have five cells with the same color (which makes 10 distances which can't be all different due to Pigeonhole principle). Therefore, each of 4 colors must occupy 4 cells each.

Then,

I went ahead to find some 4-cell patterns with six different distances that fit on a 4x4 grid:

o . . o
. o . o (1, 2, 4, 5, 9, 10)

o . o
o . .
. . .
. . o (1, 4, 5, 8, 9, 13)

o . o .
o . . .
. . . .
. . . o (1, 4, 5, 10, 13, 18)

o . . .
o . o .
. . . o (1, 2, 4, 5, 10, 13)

the last of which is pretty interesting because

given the two portions of the pattern

A . . .
A . B .
. . . B

rotating each pattern would fill the 4x4 grid nicely without overlapping

B A A B
A B B A
A B B A
B A A B

and therefore the entire grid. This gives the answer at the top.

Answer 2

It seems that

There are 106 solutions, not accounting for symmetries and rotations.

Here are some ways

to color the grid

These were found with an exhaustive algorithmic search. My code in R:

    # Create the grid
grid<-data.frame(x=1:4,b=1) %>% left_join(data.frame(y=1:4,b=1)) %>% mutate(b=1:16)
squaredDiff<-function(a) (a-lag(a))^2
squaredDist<-function(n,p){grid %>% filter(b %in% c(n,p)) %>% summarise(across(.cols = c(x,y),.fns = squaredDiff)) %>% sum(na.rm=TRUE)}

# list possible ways to place one colour
solutions<-data.frame(p1=numeric(0),p2=numeric(0),p3=numeric(0),p4=numeric(0))
for(p1 in 1:13){
  for(p2 in (p1+1):14){
    for(p3 in (p2+1):15){
      d<-c(squaredDist(p1,p2),squaredDist(p1,p3),squaredDist(p3,p2))
      if(!anyDuplicated(d)){
        for(p4 in (p3+1):16){
          dd<-c(d,squaredDist(p1,p4),squaredDist(p4,p3),squaredDist(p4,p2))
          if(!anyDuplicated(dd)){
            solutions %>% add_row(p1,p2,p3,p4)->>solutions
          }
        }
      }
    }
  }
}
# There are 184 ways
l<-nrow(solutions)

# sets of 4 solutions
setOf4<-data.frame(s1=numeric(0),s2=numeric(0),s3=numeric(0),s4=numeric(0))
for(s1 in 1:(l-3)){
  for(s2 in (s1+1):(l-2)){
    v<-c(solutions[s1,],solutions[s2,]) %>% unlist %>% unname()
    if(!anyDuplicated(v)){
      for(s3 in (s2+1):(l-1)){
        vv<-c(v,solutions[s3,]) %>% unlist %>% unname()
        if(!anyDuplicated(vv)){ print(vv)
          for(s4 in (s3+1):l){
            vvv<-c(vv,solutions[s4,]) %>% unlist %>% unname()
            if(!anyDuplicated(vvv)){ print(vvv)
              setOf4<<-setOf4 %>% add_row(s1,s2,s3,s4)
            }
          }
        }
      }
    }
  }
}
# There are 106 solutions
nrow(setOf4)->nbSolutions

# Visualization
oneSetOf4<-tibble(x=numeric(),y=numeric(),c=numeric())
solutions %>% filter (row_number() %in% (setOf4[sample(x = 1:nbSolutions,size = 1),] %>% unlist %>% unname)) -> tempTab
for(c in 1:4){
  for(d in (tempTab[c,] %>% unlist %>% unname)) {
    oneSetOf4 %>% bind_rows(grid %>% filter(b==d) %>% select(x,y) %>% mutate(c=c)) -> oneSetOf4
  }
}
oneSetOf4 %>% mutate(c=as.character(c)) %>%  gf_tile(c~x+y) + theme_minimal() + scale_fill_brewer(palette = "YlOrRd") +theme(legend.position = "none")