## Le Monde puzzle [#1154] The weekly puzzle from Le Monde is another Sudoku challenge:

An n by n grid contains all numbers from 1 till n². Is it possible for fill the grid so that every row and every column has an integer average, for n=5, 7 9?

By sheer random search

````?`=rowSums; `+`=sample
o=function(n){
x=matrix(+(n^2),n)
while(any(c(?x,?t(x))%%n))x=x/x*+x
x}
```

I found solutions for n=3,4,5, quite easily,

```     [,1] [,2] [,3] [,4] [,5]
[1,]   20   15   14   13    3
[2,]   21    4   25    6    9
[3,]    2    1   23   18   11
[4,]   17   12   22   24    5
[5,]   10    8   16   19    7```

correction, for n=6 as well

```     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    4   12   11   23    8   32
[2,]   17   15   14   33    5   30
[3,]   35   28   27    7   13   22
[4,]   31    1    6    2   21   29
[5,]   25   36   20   34   16   19
[6,]   26   10   24    3    9   18
```

but larger values of n require a less frontal attack… Simulated annealing maybe.

### 5 Responses to “Le Monde puzzle [#1154]”

1. George Dontas Says:

an image of my code https://ibb.co/NVMJ6G2

2. Yossi Levy Says:

This is much easier, as there is a simple algorithm by Euler to generate a magic square for any odd n, and the mean of each row and each column, as well as the main diagonals is (n²+1)/2. Regarding even n, this is less simple, but Euler’s general algorithm may provide some hints.

3. George Dontas Says:

An initial idea (not yet converted to an algorithm).

For n odd, it is enough to create the corresponding magic square (https://www.dcode.fr/magic-square). For n even, greater than 2, start from the corresponding magic square and select pairs of columns so that they include numbers (in different rows) with a difference of n / 2. For each column pair, change the positions of those numbers and ignore the corresponding rows and columns for the rest of the procedure.

• George Dontas Says:

My code for even numbered tables (not optimized! – I could’t avoid random sampling).
Start by getting the corresponding magic square from : https://www.dcode.fr/magic-square

library(dplyr)

df2 <- df # number of possible replacements
df3 <- df # the results
init.df <- df

n <- nrow(df)/2

for (k in 1:n){
# table with the number of possible replacements for each value
for (i in 1:nrow(df)){
for (j in 1:ncol(df)){
temp <- df[-i,-j]
x <- df[i,j]+n*c(seq(1,4*n-1,by=2),-seq(1,4*n-1,by=2))
df2[i,j] <- sum(x %in% unname(unlist(temp)))
}
}

# starting column
var <- names(sort(colSums(df2)))
# select min or max number of possible replacements (??)
min.val 0,var]),min(df2[df2[,var]>0,var]))
# the corresponding value
val <- df[df2[,var]==min.val,var]
row.num <- which(df==val,arr.ind = T)
row.num.init <- which(init.df==val,arr.ind = T)
temp % filter(!row_number() %in% c(row.num)) %>%
select(-all_of(var))
v <- c(seq(1,4*n-1,by=2),-seq(1,4*n-1,by=2))
x <- val+n*v[sample.int(length(v))]
res 0)
# the replacement value
repl <- x[res]
# where is it?
pos <- which(df==repl,arr.ind = T)
pos.init <- which(init.df==repl,arr.ind = T)
df3[row.num.init,var] <- repl
df3[pos.init] <- val
vars <- c(var, names(df)[pos])
df % filter(!row_number() %in% c(row.num,pos)) %>%
dplyr::select(-all_of(vars))
df2 <- df
}
# select all of the above and run it until you get no error

rowMeans(df3)
colMeans(df3)

• xi'an Says:

Thank you!

This site uses Akismet to reduce spam. Learn how your comment data is processed.