# 4x4 4-color Golomb square

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}$$.

• Does this mean: for each colour c, the set of distances between cells of colour c must have 6 distinct elements; or does it mean that the set of all distances between cells of the same colour must be a set with 24 distinct elements? Nov 23, 2021 at 16:56

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.

• Very nice solution, well done! Nov 22, 2021 at 9:43
• Can you find other solutions? Nov 22, 2021 at 9:58
• @DmitryKamenetsky I solved it by specifically looking for the 90-degree symmetry, and found a different solution ( row column coordinates 1,1; 2,1; 2,4; 3,3). There are probably many solutions without that symmetry. Nov 22, 2021 at 10:16
• Now I can see a couple other patterns that can fill two T-shapes, one symmetric (2,7,13,14/3,4,10,15) and another asymmetric (4,7,13,14 and the rest). That already makes quite a few different solutions. Nov 22, 2021 at 10:22

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)){
}
}
}
}
}
}
# 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)
}
}
}
}
}
}
}
# 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")

• great work! I didn't realize there are so many. Nov 22, 2021 at 13:16
• @DmitryKamenetsky : I adapted my code for any grid size and I had the surprise to discover that with n=5, there is no solution to put the 5 colors, even though there are 280 configurations for choosing 5 tiles with distinct distances. Nov 22, 2021 at 14:43
• This is my finding too. For n>4 I couldn't find any solutions with n colours. Nov 22, 2021 at 23:28
• I can confirm that there is no solution for n=6 either (and only 16 ways to place one color). Nov 23, 2021 at 7:21
• @GregMartin In the linked puzzle it was already shown that the number of ways of placing n pieces of one colour is impossible for n=8, so this puzzle is impossible too. No larger ones have been found. According to the video in the linked answer, size 16 and larger are proved impossible. It is unclear to me whether sizes 11-15 have been fully checked. (I think I did 8-10 myself.) So it looks like there can be no solutions to the n-colour version for n>4. Nov 23, 2021 at 14:31