Le Monde puzzle [#5]

February 10, 2011
By

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

Another Sudoku-like puzzle from the weekend edition of Le Monde. The object it starts with is a 9×9 table where each entry is an integer and where neighbours take adjacent values. (Neighbours are defined as north, west, south and east of an entry.) The question is about whether or not it is possible to find a table such that the sum of the 81 entries is 99. The problem is equivariant under location change, namely if each entry is shifted by a, the constraints are still satisfied but the sum is modified by 81a. If, for instance, a is the (5,5) entry, the overall sum is 81a plus an even number between -360 and +360. Looking at the generation of such tables, I wrote the simple-minded and lengthy  R code that follows:

#Generating an acceptable grid
#where neighbours in space must be neighbours in value

grid=matrix(0,9,9)
neigh=grid*0
#start from the centre
neigh[5,5]=1

for (t in 1:8){

 neigh[neigh==1]=2

 for (i in 1:9){
 for (j in 1:9){

 if (neigh[i,j]==0){

 vois=NULL
 if ((j>1)&&(neigh[i,j-(j>1)]==2)){vois=rbind(vois,c(i,j-1))}
 if ((j<9)&&(neigh[i,j+(j<9)]==2)){vois=rbind(vois,c(i,j+1))}
 if ((i<9)&&(neigh[i+(i<9),j]==2)){vois=rbind(vois,c(i+1,j))}  if ((j>1)&&(neigh[i-(i>1),j]==2)){vois=rbind(vois,c(i-1,j))}

 neigh[i,j]=1-is.null(vois)
 }

 if (neigh[i,j]==1){

 if (dim(vois)[1]==1){

 grid[i,j]=grid[vois]+sample(c(-1,1),1)}else{

 if (min(grid[vois])!=max(grid[vois])){
 grid[i,j]=round(mean(grid[vois]))}else{
 grid[i,j]=grid[vois[1,1],vois[1,2]]+sample(c(-1,1),1)}
 }
 }}
 }}

which provides a random grid centred at zero and satisfying the assumptions. Here is one instance for grid

> grid
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,]    1    0    1    2    1    0   -1    0   -1
 [2,]    0   -1    0    1    0   -1    0    1    0
 [3,]    1    0   -1    0    1    0    1    2    1
 [4,]    2    1    0    1    2    1    2    1    0
 [5,]    1    2    1    0    1    0    1    2    1
 [6,]    2    1    0   -1    0    1    0    1    2
 [7,]   -1    0   -1    0   -1    0   -1    0    1
 [8,]    0    1    0    1    0    1    0   -1    0
 [9,]    1    0   -1    0   -1    0   -1    0    1

A few thousand simulations show that achieving 99[-81] or 99[+81] (i.e. when centred at 1 or -1) is indeed possible. Here is a grid leading to a total sum of 99:

       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,]    1    0   -1    0    1    0    1    2    3
 [2,]    2    1    0   -1    0    1    2    1    2
 [3,]    3    2    1    0    1    2    3    2    3
 [4,]    4    3    2    1    2    3    2    1    2
 [5,]    3    2    1    2    1    2    1    0    1
 [6,]    0    1    2    1    0    1    0    1    0
 [7,]    1    0    1    2    1    2    1    0    1
 [8,]    0   -1    0    1    2    3    2    1    0
 [9,]   -1    0    1    2    1    2    3    2    1

Filed under: R, Statistics 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 on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , , , ,

Comments are closed.

Search R-bloggers


Sponsors

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)