**A**fter a long lag *(due to my missing the free copies distributed at Paris-Dauphine!)*, here is a Sudoku-like Le Monde mathematical puzzle:

*A grid of size (*n,n)* holds integer values such that any entry larger than 1 is the sum of one term in the same column and one term in the same row. What is the maximal possible value observed in such a grid when n=3,4?*

**T**his can be solved in R by a random exploration of such possible grids in a simulated annealing spirit:

mat=matrix(1,N,N)
goal=1
targ=function(mat){ #check constraints
d=0
for (i in (1:(N*N))[mat>1]){
r=(i-1)%%N+1;c=(i-1)%/%N+1
d=d+(min(abs(mat[i]-outer(mat[-r,c],mat[r,-c],"+")))>0)}
return(d)}
cur=0
for (t in 1:1e6){
i=sample(1:(N*N),1);prop=mat
prop[i]=sample(1:(2*goal),1)
d=targ(prop)
if (10*log(runif(1))/t<cur-d){
mat=prop;cur=d}
if ((d==0)&(max(prop)>goal)){
goal=max(prop);maxx=prop}}

returning a value of 8 for n=3 and 37 for n=4. However, the method is quite myopic and I tried instead a random filling of the grid, using each time the maximum possible sum for empty cells:

goal=1
for (v in 1:1e6){
mat=matrix(0,N,N)
#one 1 per row/col
for (i in 1:N) mat[i,sample(1:N,1)]=1
for (i in 1:N) if (max(mat[,i])==0) mat[sample(1:N,1),i]=1
while (min(mat)==0){
parm=sample(1:(N*N)) #random order
for (i in parm[mat[parm]==0]){
r=(i-1)%%N+1;c=(i-1)%/%N+1
if ((max(mat[-r,c])>0)&(max(mat[r,-c])>0)){
mat[i]=max(mat[-r,c])+max(mat[r,-c])
break()}}}
if (goal<max(mat)){
goal=max(mat);maxx=mat}}

which recovered a maximum of 8 for n=3, but reached 48 for n=4. And 211 for n=5, 647 for n=6… For instance, here is the solution for n=4:

[1,] 1 5 11 10
[2,] 2 4 1 5
[3,] 48 2 24 1
[4,] 24 1 22 11

Continue reading →