Archive for sudoku

« Older Entries
Newer Entries »

1500th, 3000th, &tc

Posted in Books, R, Statistics, University life with tags , , , , , , , , , , , , on January 8, 2012 by xi'an

As the ‘Og reached its 1500th post and 3000th comment at exactly the same time, a wee and only mildly interesting Sunday morning foray in what was posted so far and attracted the most attention (using the statistics provided by wordpress). The most visited posts:

Title Views
Home page 203,727
In{s}a(ne)!! 7,422
“simply start over and build something better” 6,264
Julien on R shortcomings 2,676
Sudoku via simulated annealing 2,402
About 1,876
Of black swans and bleak prospects 1,768
Solution manual to Bayesian Core on-line 1,628
Parallel processing of independent Metropolis-Hastings algorithms 1,625
Bayesian p-values 1,595
Bayes’ Theorem 1,537
#2 blog for the statistics geek?! 1,526
Do we need an integrated Bayesian/likelihood inference? 1,501
Coincidence in lotteries 1,396
Solution manual for Introducing Monte Carlo Methods with R 1,340
Julian Besag 1945-2010 1,293
Tornado in Central Park 1,093
The Search for Certainty 1,016

Hence, three R posts (incl. one by Julien and one by Ross Ihaka), three (critical) book reviews, two solution manuals, two general Bayesian posts, two computational entries, one paper (with Pierre Jacob and Murray Smith), one obituary, and one photograph news report… Altogether in line with the main purpose of the ‘Og. The most commented posts:

Post Comments
In{s}a(ne)!! 31
“simply start over and build something better” 30
That the likelihood principle does not hold… 23
Incoherent inference 23
Lack of confidence in ABC model choice 20
Parallel processing of independent Metropolis-Hastings algorithms 19
ABC model choice not to be trusted 17
MCMC with errors 16
Coincidence in lotteries 16
Bessel integral 14
Numerical analysis for statisticians 14

Not exactly the same as above! In particular, the posts about ABC model choice and our PNAS paper got into the list. At last, the top search terms:

Search Views
surfers paradise 1,050
benidorm 914
introducing monte carlo methods with r 514
andrew wyeth 398
mistborn 352
abele blanc 350
nested sampling 269
particle mcmc 269
bayesian p-value 263
julian besag 257
rites of love and math 249
millenium 237
bayesian p value 222
marie curie 221
bonsai 200

(out of which I removed the dozens of variations on xian’s blog). I find it rather sad that both top entries are beach towns that are completely unrelated to my lifestyle and to my vacation places. Overall, more than a  half of those entries do not strongly relate to the contents of the ‘Og (even though I did post at length about Saunderson’s Mistborn and Larsson’s Millenium trilogies). At last, the most popular clicks are

URL Clicks
amazon.com/gp/product/1441915753?ie=UTF8&tag=chrprobboo-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=1441915753 1,243
stat.columbia.edu/~cook/movabletype/mlm 1,039
terrytao.wordpress.com 583
amazon.com/gp/product/0387389792?ie=UTF8&tag=chrprobboo-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=0387389792 575
arxiv.org/abs/1012.2184 531
radfordneal.wordpress.com/2010/08/15/two-surpising-things-about-r 529
romainfrancois.blog.free.fr 505
statisfaction.wordpress.com 404
ceremade.dauphine.fr/~xian/basudo.R 395
stackoverflow.com/questions/3706990/is-r-that-bad-that-it-should-be-rewritten-from-scratch 372
amazon.com/gp/product/0387212396?ie=UTF8&tag=chrprobboo-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=0387212396 298
radfordneal.wordpress.com/2010/09/03/fourteen-patches-to-speed-up-r 298
cs.ubc.ca/~cornebis 288
statisticsforum.wordpress.com 282
arxiv.org/abs/1001.2906 279
arxiv.org/abs/1010.1595 257
amazon.com/gp/redirect.html?ie=UTF8&location=http://www.amazon.com/gp/entity/-/B001H6GSKC&tag=chrprobboo-20&linkCode=ur2&camp=1789&creative=390957 256
ceremade.dauphine.fr/~xian/BCS/solutions.pdf 253
rss.org.uk/main.asp?page=3005 243
www3.interscience.wiley.com/cgi-bin/fulltext/119424936/PDFSTART 216
stat.auckland.ac.nz/~ihaka/downloads/Compstat-2008.pdf 203

which include links to my books on Amazon, Andrew Gelman’s, Terry Tao’s, Radford Neal’s and Romain François’s blogs, the CREST stat students collective blog, and a few arXiv papers of mine’s…

1 Comment »

Dream on!

Posted in Statistics, University life with tags , , , , on May 13, 2011 by xi'an

On Saturday, I was asked to referee Jasper Vrugt’s paper “DREAM(D): an adaptive Markov chain Monte Carlo simulation algorithm to solve discrete, noncontinuous, posterior parameter estimation problems” (I have added the proper upper case letters!) for the journal Hydrology and Earth System Sciences. It may sound surprising that I advertise this refereeing, but Hydrology and Earth System Sciences has the fairly interesting feature that referees’ comments can be turned into a discussion of the paper, along with other spontaneous comments. The only drawbacks are that (a) the discussion remains open for only 8 days and (b) using LaTeX commands is not as straightforward as on WordPress. Here is (more or less) my entry: Continue reading →

5 Comments »

Surprising sudoku

Posted in R, Statistics with tags , on March 1, 2011 by xi'an

[sourcecode language=”r” gutter=”false”]
> printSudoku(z)
+——-+——-+——-+
|   9   |       | 7   5 |
|     6 |       |   9   |
| 4 5 3 | 1 7   | 2 8   |
+——-+——-+——-+
|     5 |     7 |   6   |
| 1   9 | 6 8   |       |
|   8   |   3   |     1 |
+——-+——-+——-+
| 7   2 | 5 9   | 4     |
|       |     2 | 6 7   |
|       |   6   |     2 |
+——-+——-+——-+
[/sourcecode]

Yesterday, I was finishing a sudoku grid in the metro and I ended up with four entries a,b,b,a that could be entered in two symmetric ways! Nothing mathematically surprising. However, this never happened to me before and, while it is obviously a possibility, I had not realised that sudoku creators could choose this option… This is not a well-defined question, but how likely is it that one ends up with such an exchange quadruplet (or rather pair of pairs)?! (The above was written using the sudoku R solver, pointed out by Dirk Eddelbuettel.)

Update: It took silly me a while to spot the single wrong entry! Here is the exact solution provided by sudoku:

[sourcecode language=”r” gutter=”false”]
> printSudoku(solveSudoku(z))
+——-+——-+——-+
| 8 9 1 | 4 2 6 | 7 3 5 |
| 2 7 6 | 8 5 3 | 1 9 4 |
| 4 5 3 | 1 7 9 | 2 8 6 |
+——-+——-+——-+
| 3 4 5 | 2 1 7 | 9 6 8 |
| 1 2 9 | 6 8 5 | 3 4 7 |
| 6 8 7 | 9 3 4 | 5 2 1 |
+——-+——-+——-+
| 7 6 2 | 5 9 8 | 4 1 3 |
| 5 1 8 | 3 4 2 | 6 7 9 |
| 9 3 4 | 7 6 1 | 8 5 2 |
+——-+——-+——-+
[/sourcecode]

3 Comments »

Le Monde puzzle [#5]

Posted in R, Statistics with tags , , , on February 11, 2011 by xi'an

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:

[sourcecode language=”r” gutter=”false”]
#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)}
}
}}
}}
[/sourcecode]

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

[sourcecode language=”r” gutter=”false”]
> 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
[/sourcecode]

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:

[sourcecode language=”r” gutter=”false”]
[,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
[/sourcecode]

5 Comments »

Le Monde puzzle [52]

Posted in R, Statistics with tags , on December 31, 2010 by xi'an

The last puzzle of the year in Le Monde reads as follows (as far as I understand its wording!):

Iter(n,x,y) is the function

[sourcecode language=”r” gutter=”false”]
Iter=function(n,x,y){

if (n==1){
output=trunc(y/10)+x*(y%%10)
}else{
output=Iter(n-1,x,Iter(1,x,y))}

return output
}
[/sourcecode]

Find the seven-digit number z such that
Iter(6,1,z)=12, Iter(6,2,z)=19, Iter(6,3,z)=29,
and Iter(6,-1,z)=Iter(6,-2,z)=Iter(6,-3,z)=0.

Obviously, the brute-force solution of listing all 90 million seven digit numbers until the six constraints are met is feasible (especially around New Year since the mainframe computer is completely at rest!). However, this sounds like the last resort solution and I thus tried first a simulated annealing approach already tested for the sudoku problem a few years ago… (This puzzle is actually of the same nature as the sudoku problem,  in particular because we do know when we find the solution, except that checking for the six conditions to hold is apparently not so straightforward. For us if not for the computer.) Continue reading →

3 Comments »

« Older Entries
Newer Entries »