<p><div><div><div><div data-width="100" data-show-faces="false" data-send="true" data-layout="button_count" data-height="21" data-href="https://www.r-bloggers.com/le-monde-puzzle-1001/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://xianblog.wordpress.com/2017/03/27/le-monde-puzzle-1001/"> R – Xi'an's Og</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p><strong><img height="185" alt="" width="273" src="https://encrypted-tbn3.gstatic.com/images?q=tbn:ANd9GcRsQd3v7efgSlmsNPKddzl-oQS9fZOF8a68V6KPmf5dnmI_EJ66rw">A</strong>fter a long lag <em>(due to my missing the free copies distributed at Paris-Dauphine!)</em>, here is a <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/2013/12/13/sudoku-break/">Sudoku</a>-like <a title="Le Monde puzzle [website]" target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/2011/09/03/le-monde-puzzle-website/">Le Monde mathematical puzzle</a>:</p>
<blockquote>
<p><em>A grid of size (</em>n,n)<em> 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?</em><em><br>
</em></p>
</blockquote>
<p><strong>T</strong>his can be solved in R by a random exploration of such possible grids in a simulated annealing spirit:</p>
<pre>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],&quot;+&quot;)))>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&lt;cur-d){ 
      mat=prop;cur=d} 
  if ((d==0)&amp;(max(prop)>goal)){
     goal=max(prop);maxx=prop}}</pre>
<p>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:</p>
<pre>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)&amp;(max(mat[r,-c])>0)){
      mat[i]=max(mat[-r,c])+max(mat[r,-c])
      break()}}}
    if (goal&lt;max(mat)){
    goal=max(mat);maxx=mat}}
</pre>
<p>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:</p>
<pre>[1,]    1    5   11   10
[2,]    2    4    1    5
[3,]   48    2   24    1
[4,]   24    1   22   11
</pre>
<p><span></span></p>
<p>While the update in the above is random and associated with the first term in the permutation, it may be preferable to favour the largest possible term at each iteration, which I tried as</p>
<pre>while (min(mat)==0){
parm=sample(1:(N*N))
val=0*parm
for (i in parm[mat[parm]==0]){
    r=(i-1)%%N+1;c=(i-1)%/%N+1
        if ((max(mat[-r,c])>0)&amp;(max(mat[r,-c])>0)){
      val[i]=max(mat[-r,c])+max(mat[r,-c])}
      }
#largest term
i=order(-val)[1];mat[i]=val[i]}
</pre>
<p>For n=4, I did not recover the maximal value 48, but achieved larger values for n=5 (264) and n=6 (2256).</p>
<p>As an aside, the R code sometimes led to a strange error message linked with the function sample(), which is that too large a bound in the range produces the following</p>
<pre>> sample(1:1e10,1)
Error: cannot allocate vector of size 74.5 Gb
</pre>
<p>meaning that 1:1e10 first creates a vector for all the possible values. The alternative</p>
<pre>> sample.int(1e10,1)
[1] 7572058778
</pre>
<p>works, however. And only breaks down for 10¹².</p>
<p>Filed under: <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/category/kids/">Kids</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/category/statistics/r-statistics/">R</a> Tagged: <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/le-monde/">Le Monde</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/mathematical-puzzle/">mathematical puzzle</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/r/">R</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/sample/">sample</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/sudoku/">sudoku</a> <a target="_blank" rel="nofollow" href="http://feeds.wordpress.com/1.0/gocomments/xianblog.wordpress.com/33067/"><img alt="" src="http://feeds.wordpress.com/1.0/comments/xianblog.wordpress.com/33067/" border="0"></a> <img alt="" src="https://i1.wp.com/pixel.wp.com/b.gif?resize=1%2C1&ssl=1" border="0" data-recalc-dims="1"></p>
<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="https://xianblog.wordpress.com/2017/03/27/le-monde-puzzle-1001/"> R – Xi'an's Og</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a title="The R Project for Statistical Computing" rel="nofollow" href="https://www.r-project.org/">R</a> news and <a title="R tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/tutorial">tutorials</a> on topics such as: <a title="Data science" rel="nofollow" href="https://www.r-bloggers.com/search/data%20science">Data science</a>, <a title="Big Data" rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data">Big Data, <a title="R jobs" rel="nofollow" href="https://www.r-users.com/">R jobs</a>, visualization (<a title="ggplot and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2">ggplot2</a>, <a title="Boxplots using lattice and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/boxplot">Boxplots</a>, <a title="Maps and gis" rel="nofollow" href="https://www.r-bloggers.com/search/map">maps</a>, <a title="Animation in R" rel="nofollow" href="https://www.r-bloggers.com/search/animation">animation</a>), programming (<a title="RStudio IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/RStudio">RStudio</a>, <a title="Sweave and literate programming" rel="nofollow" href="https://www.r-bloggers.com/search/sweave">Sweave</a>, <a title="LaTeX in R" rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX">LaTeX</a>, <a title="SQL and databases" rel="nofollow" href="https://www.r-bloggers.com/search/SQL">SQL</a>, <a title="Eclipse IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/eclipse">Eclipse</a>, <a title="git and github, Version Control System" rel="nofollow" href="https://www.r-bloggers.com/search/git">git</a>, <a title="Large data in R using Hadoop" rel="nofollow" href="https://www.r-bloggers.com/search/hadoop">hadoop</a>, <a title="Web Scraping of google, facebook, yahoo, twitter and more using R" rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping">Web Scraping</a>) statistics (<a title="Regressions and ANOVA analysis tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/regression">regression</a>, <a title="principal component analysis tutorial" rel="nofollow" href="https://www.r-bloggers.com/search/PCA">PCA</a>, <a title="Time series" rel="nofollow" href="https://www.r-bloggers.com/search/time+series">time series</a>, <a title="finance trading" rel="nofollow" href="https://www.r-bloggers.com/search/trading">trading</a>) and more...
<img height="1" alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/y5kTW1gzDdU"></a></div>