Site icon R-bloggers

Le Monde puzzle [#755?]

[This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Le Monde puzzle of last weekend was about sudoku-like matrices.

Consider an (n,n) matrix containing the integers from 1 to n². The matrix is “friendly” if the set of the sums of the rows is equal to the set of the sum of the columns. Find examples for n=4,5,6. Why is there no friendly matrix when n=9?

Checking for small n’s seems easy enough:

friend=function(n){
s=1
while (s>0){
  A=matrix(sample(1:n^2),ncol=n)
  s=sum(abs(sort(apply(A,1,sum))-
        sort(apply(A,2,sum))))}
A
}

For instance, running

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

produces right answers. But the case n=6 proved itself almost too hard for brute-force handling!!! I have no time to devise a simulated-annealing code to speed up the resolution so this will have to wait till the next weekend edition of Le Monde. As to why n=9 does not enjoy a solution… (When n=2 there is no solution, as proven by the brute force exhibition of all cases.)


Filed under: R Tagged: Le Monde, mathematical puzzle, R, sudoku
To leave a comment for the author, please follow the link and comment on their blog: Xi'an's Og » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.