# Le Monde puzzle [#1088]

March 28, 2019
By

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

A board (Ising!) Le Monde mathematical puzzle in the optimisation mode, again:

On a 7×7 board, what is the maximal number of locations that one can occupy when imposing at least two empty neighbours ?

Which I tried to solve by brute force and simulated annealing (what else?!), first defining a target

```targ=function(tabz){
sum(tabz[-c(1,9),-c(1,9)]-1.2*(tabz[-c(1,9),-c(1,9)]*tabz[-c(8,9),-c(1,9)]
+tabz[-c(1,9),-c(1,9)]*tabz[-c(1,2),-c(1,9)]
+tabz[-c(1,9),-c(1,9)]*tabz[-c(1,9),-c(8,9)]
+tabz[-c(1,9),-c(1,9)]*tabz[-c(1,9),-c(1,2)]>2))}
```

on a 9×9 board where I penalise prohibited configuration by a factor 1.2 (a wee bit more than empty nodes). The perimeter of the 9×9 board is filled with ones and never actualised. (In the above convoluted products, the goal is to count how many neighbours of the entries equal to one are also equal to one. More than 2 is penalised.) The simulated annealing move is then updating the 9×9 grid gridz:

```temp=1
maxarg=curarg=targ(gridz)
for (t in 1:1e3){
for (v in 1:1e4){
i=sample(2:8,1);j=sample(2:8,1)
newgrid=gridz;newgrid[i,j]=1-gridz[i,j]
newarg=targ(newgrid)
if (log(runif(1))
and calls to the procedure always return 28 entries as the optimum, as in
[,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]    1    0    1    0    1    0    1
[2,]    0    1    1    0    1    1    0
[3,]    1    1    0    1    0    1    1
[4,]    0    0    1    0    1    0    0
[5,]    1    1    0    1    0    1    1
[6,]    0    1    1    0    1    1    0
[7,]    1    0    1    0    1    0    1

As it happens, I had misread the wording of the original puzzle, which considered a dynamic placement of the units on the board, one at a time with two free neighbours imposed.

var vglnk = { key: '949efb41171ac6ec1bf7f206d57e90b8' };

(function(d, t) {
var s = d.createElement(t); s.type = 'text/javascript'; s.async = true;
var r = d.getElementsByTagName(t)[0]; r.parentNode.insertBefore(s, r);
}(document, 'script'));

Related
ShareTweet

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.