Archive for sudoku

Le Monde puzzle [#869]

Posted in Books, Kids, R, Statistics, University life with tags , , , , , , , on April 27, 2014 by xi'an

A Le Monde mathematical puzzle once again in a Sudoku mode:

In an nxn table, all integers between 1 and n appear n times. If max denotes the maximum over the numbers of different integers on all rows and columns,  what is the minimum value of max when n=7? when n=11?

I tried to solve it by the following R code (in a pre-breakfast mode in my Reykjavik Airbnb flat!):

#pseudoku
n=7
T=10^4
vals=rep(1:n,n)
minmax=n
for (t in 1:T){
  psudo=matrix(sample(vals),ncol=n)
  maxc=maxr=max(sapply(apply(psudo,1,unique),length))
  if (maxc<minmax)
     maxr=max(sapply(apply(psudo,2,unique),length))
  minmax=min(minmax,max(maxc,maxr))
  }

but later realised that (a) the

sapply(apply(psudo,1,unique),length)

failed when all rows or all columns had the same number of unique terms and (b) I did not have to run the whole matrix:

vals=rep(1:n,n)
minmax=n
for (t in 1:T){
  psudo=matrix(sample(vals),ncol=n)
  maxc=max(length(unique(psudo[1,])),length(unique(psudo[,1])))
  i=1
  while((i<n)&(maxc<minmax)){
   i=i+1
   maxc=max(maxc,
        length(unique(psudo[i,])),
        length(unique(psudo[,i])))}
  minmax=min(minmax,maxc)
  }

gaining a factor of 3 in the R execution. With this random exploration, the minimum value returned was 2,2,2,3,4,5,5,6,7,8 for n=2,3,4,5,6,7,8,9,10,11. Half-hearted simulating annealing during one of the sessions of AISTATS 2014 did not show any difference…

sudoku break

Posted in pictures, R, Statistics with tags , , , , on December 13, 2013 by xi'an

sudo291113While in Warwick last week, one evening after having exhausted my laptop battery, I tried the following Sudoku (from Libération):

>   printSudoku(readSudoku("libe.dk"))
  +-------+-------+-------+
  | 4   6 |   2   | 3   9 |
  |   3   |       |   2   |
  | 7   2 |       | 5   6 |
  +-------+-------+-------+
  |       | 9 4 5 |       |
  | 5     | 7 6 2 |     1 |
  |       | 3 1 8 |       |
  +-------+-------+-------+
  | 6   9 |       | 1   3 |
  |   7   |       |   9   |
  | 3   1 |   9   | 4   7 |
  +-------+-------+-------+

and could not even start. As it happened, this was a setting with no deterministic move, i.e. all free/empty entries had multiple possible values. So after trying for a while and following trees to no obvious contradiction (!) I decided to give up and on the next day (with power) to call my “old” sudoku solver (built while at SAMSI), using simulated annealing and got the result after a few thousand iterations. The detail of the exploration is represented above, the two colours being code for two different moves on the Sudoku table. Leading to the solution

  +-------+-------+-------+
  | 4 8 6 | 5 2 1 | 3 7 9 |
  | 1 3 5 | 6 7 9 | 8 2 4 |
  | 7 9 2 | 8 3 4 | 5 1 6 |
  +-------+-------+-------+
  | 2 1 3 | 9 4 5 | 7 6 8 |
  | 5 4 8 | 7 6 2 | 9 3 1 |
  | 9 6 7 | 3 1 8 | 2 4 5 |
  +-------+-------+-------+
  | 6 2 9 | 4 8 7 | 1 5 3 |
  | 8 7 4 | 1 5 3 | 6 9 2 |
  | 3 5 1 | 2 9 6 | 4 8 7 |
  +-------+-------+-------+

I then tried a variant with more proposals (hence more colours) at each iteration, which ended up being stuck at a penalty of 4 (instead of 0) in the final thousand iterations. Although this is a one occurrence experiment, I find it interesting that having move proposals may get the algorithm stuck faster in a local minimum. Nothing very deep there, of course..!

sudo301113

random sudokus

Posted in Books, R, Statistics with tags , , , on June 4, 2013 by xi'an

In a paper arXived on Friday, Roberto Fontana relates the generation of Sudoku grids to the one of Latin squares (which is unsurprising) and to maximum cliques of a graph (more surprising). The generation of a random Latin square proceeds in three steps:

  1. generate a random Latin square L with identity permutation matrix on symbol 1 (in practice, this implies building the corresponding graph and picking one of the largest cliques at random);
  2. modify L into L’ using a random permutation of the symbols 2,…,n in L';
  3. modify L’ into L” by a random permutation of the columns of L’.

A similar result holds for Sudokus (with the additional constraint on the regions). However, while the result is interesting in its own right, it only covers full Sudokus, rather than partially filled Sudokus with a unique solution, whose random production could be more relevant. (Or maybe not, given that the difficulty matters.) [The code uses some R packages, but then moves to SAS, rather surprisingly.]

the most human human

Posted in Books, University life with tags , , , , , , , , , , , , , , on May 24, 2013 by xi'an

“…the story of Homo sapiens trying to stake a claim on shifting ground, flanked on both sides by beast and machine, pinned between meat and math.” (p.13)

No typo in the title, this is truly how this book by Brian Christian is called. It was kindly sent to me by my friends from BUY and I realised I could still write with my right hand when commenting on the margin. (I also found the most marvellous proof to a major theorem but the margin was just too small…)  “The most human human: What artificial intelligence teaches us about being alive” is about the Turing test, designed to test whether an unknown interlocutor is a human or a machine. And eventually doomed to fail.

“The final test, for me, was to give the most uniquely human performance I could in Brighton, to attempt a successful defense against the machines.” (p.15)

What I had not realised earlier is that there is a competition every year running this test against a few AIs and a small group of humans, the judges (blindly) giving votes for each entity and selecting as a result the most human computer. And also the most human … human! This competition is called the Loebner Prize and it was taking place in Brighton, this most English of English seaside towns, in 2008 when Brian Christian took part in it (as a human, obviously!).

“Though both [sides] have made progress, the `algorithmic’ side of the field [of computer science] has, from Turing on, completely dominated the more `statistical’ side. That is, until recently.” (p.65)

I enjoyed the book, much more for the questions it brought out than for the answers it proposed, as the latter sounded unnecessarily conflictual to me, i.e. adopting a “us vs.’em” posture and whining about humanity not fighting hard enough to keep ahead of AIs… I dislike this idea of the AIs being the ennemy and of “humanity lost” the year AIs would fool the judges. While I enjoy the sci’ fi’ literature where this antagonism is exacerbated, from Blade Runner to Hyperion, to Neuromancer, I do not extrapolate those fantasised settings to the real world. For one thing, AIs are designed by humans, so having them winning this test (or winning against chess grand-masters) is a celebration of the human spirit, not a defeat! For another thing, we are talking about a fairly limited aspect of “humanity”, namely the ability to sustain a limited discussion with a set of judges on a restricted number of topics. I would be more worried if a humanoid robot managed to fool me by chatting with me for a whole transatlantic flight. For yet another thing, I do not see how this could reflect on the human race as a whole and indicate that it is regressing in any way. At most, it shows the judges were not trying hard enough (the questions reported in The most human human were not that exciting!) and maybe the human competitors had not intended to be perceived as humans.

“Does this suggest, I wonder, that entropy may be fractal?” (p.239)

Another issue that irked me in the author’s perspective is that he trained and elaborated a complex strategy to win the prize (sorry for the mini-spoiler: in case you did  not know, Brian did finish as the most human human). I do not know if this worry fear to appear less human than an AI was genuine or if it provided a convenient canvas for writing the book around the philosophical question of what makes us human(s). But it mostly highlights the artificial nature of the test, namely that one has to think in advance on the way conversations will be conducted, rather than engage into a genuine conversation with a stranger. This deserves the least human human label, in retrospect!

“So even if you’ve never heard of [Shanon entropy] beofre, something in your head intuits [it] every time you open your mouth.” (p.232)

The book spend a large amount of text/time on the victory of Deep Blue over Gary Kasparov (or, rather, on the defeat of Kasparov against Deep Blue), bemoaning the fact as the end of a golden age. I do not see the problem (and preferred the approach of Nate Silver‘s). The design of the Deep Blue software was a monument to the human mind, the victory did not diminish Kasparov who remains one of the greatest chess players ever, and I am not aware it changed chess playing (except when some players started cheating with the help of hidden computers!). The fact that players started learning more and more chess openings was a trend much before this competition. As noted in The most human human,  checkers had to change its rules once a complete analysis of the game had led to  a status-quo in the games. And this was before the computer era. In Glasgow, Scotland, in 1863. Just to draw another comparison: I like playing Sudoku and the fact that I designed a poor R code to solve Sudokus does not prevent me from playing, while my playing sometimes leads to improving the R code. The game of go could have been mentioned as well, since it proves harder to solve by AIs. But there is no reason this should not happen in a more or less near future…

“…we are ordering appetizers and saying something about Wikipedia, something about Thomas  Bayes, something about vegetarian dining…” (p.266)

While the author produces an interesting range of arguments about language, intelligence, humanity, he missed a part about the statistical modelling of languages, apart from a very brief mention of a Markov dependence. Which would have related to the AIs perspective. The overall flow is nice but somehow meandering and lacking in substance. Esp. in the last chapters. On a minor level, I also find that there are too many quotes from Hofstadter’ Gödel, Escher and Bach, as well as references to pop culture. I was surprised to find Thomas Bayes mentioned in the above quote, as it did not appear earlier, except in a back-note.

“A girl on the stairs listen to her father / Beat up her mother” C.D. Wright,  Tours

As a side note to Andrew, there was no mention made of Alan Turing’s chess rules in the book, even though both Turing and chess were central themes. I actually wondered if a Turing test could apply to AIs playing Turing’s chess: they would have to be carried by a small enough computer so that the robot could run around the house in a reasonable time. (I do not think chess-boxing should be considered in this case!)

tak1ng sudoku ser1ously

Posted in Books, Statistics, University life with tags , , , , , on March 14, 2013 by xi'an

“There is something deeply satisfying in encountering opacity.” (p.9)

I think it was last summer at the Australasian Statistics conference in Adelaide that I saw this book by Jason Rosenhouse and Laura Taalman, Taking Sudoku seriously: The math behind the World’s most popular pencil puzzle. (Or was it in Kyoto at the ISBA meeting?!) In any case, I mentioned my long-term interest in this puzzle (as readers of the ‘Og will undoubtedly have noticed!) and proposed to write a review for Chance. A few weeks later the book arrived at home. Which was a mistake as my wife who is a much deeper Sudoku fanatic than I stole the book with a vague promise to write the review! It is only a few weeks ago that I was able to truly get the book (if not the review) back…

“This is surely the most trivial of pursuits.” (p.4)

In case you never tried to solve a Sudoku puzzle, open your favourite newspaper, news website or phone, and you should immediately find one of those 9×9 squares to fill with integers between 1 and 9, under three sets of constraints: row-wise, column-wise, and block-wise. (The book describes all kinds of variations with no particularly added value.) Depending on the number of integers already present on the grid and on their location, the resolution of the puzzle gets from obvious to close to impossible by hand. This range in the difficulty and the resulting challenges may explain for the popularity of the method, although it remains a mystery to many bystanders. There are many strategies for solving Sudokus, from the (Sherlock Holmes) elimination of obviously impossible values to branching processes carrying guesses until a binary conclusion. The book covers some of those: forced cells, twins, X-wings, and Ariadne’s thread (moving from Star Wars to The Lord of the Ring!). It however does not bring any novel technique to solve Sudokus, at least at the pencil level, so potential readers with this intent in mind should abstain!

“Sudoku is math in the small.” (p.171)

Now many may wonder about the connections between Sudokus and mathematics. Some mathematicians are clearly sceptical. For instance, I remember discussing solving Sudoku grids in the métro with a friend and Mathematics colleague from Paris-Dauphine and she was quite surprised by this fascination, as she did not see any mathematical appeal in the exercise. In my eyes, this is a logical puzzle at the very least (there is one way of setting all the entries and some obligatory paths for filling the grid that have to be exposed), which makes Sudoku vaguely mathematical. I am also attracted by the automated resolution of those puzzles, as shown by my simulated annealing attempt a (long) while ago, even though I am aware that the state-of-the-art codes are beyond my reach. (They are not detailed either in the book.) Reading this book actually made me think of potential alternatives for simulating annealing, from using additional integers during relaxation, to solving a set of algebraic equations under relaxed constraints. (I wonder if Gröbner bases are used by the fastest resolution codes.)

“We are unaware of any result about Sudoku puzzles provable using the techniques of graph-coloring that could not have been arrived at more easily by other means.” (p.133)

Taking Sudoku Seriously does exhibit some of those connections, it may however feel contrived for some readers (and unintelligible to others), as the mathematical objects have an existence of their own and do not appear to directly contribute to the resolution of the puzzle. An exception in the first case is the one of Latin and Greco-Latin squares in Chapters 2 and 4, which are Sudokus of sort, while an exception to the second is the mention of Gröbner bases in Chapter 8 for solving sets of algebraic equations providing the solution to Sudokus in the form of complex roots of unity. Some number theory gets introduced along the way, as well as algebra (permutation and symmetry groups, polynomials) and graph theory. Analysis is rather absent from this volume and so is probability (hence simulated annealing). Except for a rather artificial and unrelated entry about Newton’s cannonball and Archimede’s derivation of the area of a circle in Chapter 7.

“We have a number of different audiences in mind.” (p.xi)

A few days prior to finish reading the book, I received my copy of Significance with a review of Taking Sudoku Seriously by Nicola Tilt. Glancing quickly at it, I read she was wondering about the intended audience for the book, which also is an issue with me. Neophytes and mathematicians alike will learn little about maths from reading the book, since the difficult questions (like counting the number of Sudokus and of non-equivalent Sudokus, or creating Sudokus) are not answered. The most interesting input is, in my opinion, the discussion of computer-based mathematical proofs. From the four-colour theorem to counting the number of Sudokus, to counting the number of fundamentally different Sudoku squares [as 5,472,730,538]. Unfortunately, the book publication date (April 2011) means that it missed the “big news”, namely the resolution of what the authors call “The rock star problem”, which is the determination of “the minimum number of starting clues possible in a Sudoku puzzle with a unique solution” (p.164). On Jan. 1, 2012, Gary McGuire, Bastian Tugemann, and Gilles Civario from University College Dublin used a mix of mathematics and computer power to prove that the minimum is indeed 17, as posited by the authors. (A result to feature prominently in the revised edition, if any!)

“We are curious for a living.” (p.191)

To conclude, and to be fair with the authors, the book reads nicely (on high quality glossy paper), once you limit your expectations to see some links between maths and Sudokus, it offers a lot of Sudokus and related puzzles, with solutions at the back of the book, and, above all, it teaches to some degree mathematical reasoning by running complete arguments on 4×4 Shidokus and extrapolating the results to the 9×9 Sudokus (or not, as in the case of polynomials where the extrapolation does not work, Section 8.2). Worth perusing on your way to work, trying to complete the puzzle at hand before the next stop!

As a postultimate remark, a paper by Hiroshi Watanabe from the University of Tokyo was arXived a few days ago: it contains further links about the mathematical properties of Sudokus, incl. one with a nine-state Potts model, but mostly a simulated annealing algorithm to find a “difficult” Sudoku. Contrary to my early attempt, this algorithm explores the space of all Sudoku puzzles, thus moves from one Sudoku to another at each iteration (“with the Metropolis criterion with the Boltzmann weight”, I wonder why Boltzmann?!).The hardest sudoku found by this method is represented below: it has a depth of 10 and would require 50,000 backtracking attempts to solve! Just “impossible to solve by hand”. (It took the equivalent of 11 cpu-core-years to create it.) As pointed out to me by Anthony Leverrier, from INRIA, the author added in the second version of his arXiv preprint that the puzzle can be easily solved by hand… So you may give it a try.

The hardest Sudoku ever, by H. Watanabe

AMSI lecturer

Posted in pictures, Statistics, Travel, University life with tags , , , , , , on March 20, 2012 by xi'an

In conjunction with my summer trip down under in July-August, I have been nominated an AMSI-SSAI Lecturer. (AMSI stands for Australian Mathematical Sciences Institute and SSAI for Statistical Society of Australia Inc.) In essence, this means I will travel in several places around Australia to give talks and meet people. This is quite exciting, although I find the prospect of giving a public lecture (as opposed to academic talks) a wee daunting. (Simulation seems like a safe topic, though, as it is hard to fail to find manageable examples. Simulated annealing for sudokus was the first to come to my mind.)

simulated annealing for Sudokus [2]

Posted in Books, pictures, R, Statistics, University life with tags , , , , , , , on March 17, 2012 by xi'an

On Tuesday, Eric Chi and Kenneth Lange arXived a paper on a comparison of numerical techniques for solving sudokus. (The very Kenneth Lange who wrote this fantastic book on numerical analysis.) One of these techniques is the simulated annealing approach I had played with a long while ago.  They seem to use the same penalisation function as mine, i.e., the number of constraint violations, but the moves are different in that they pick pairs of cells without clues (i.e., not constrained) and swap their contents. The pairs are not picked at random but with probability proportional to exp(k), if k is the number of constraint violations. The temperature decreases geometrically and the simulated annealing program stops when the zero cost is achieved or when a maximum 10⁵ iterations are reached. The R program I wrote while visiting SAMSI had more options, but it was also horrendously slow! The CPU time reported by the authors is far far lower, almost in the range of the backtracking solution that serves as their reference. (Of course, it is written in Fortran 95, not in R…) As in my case, the authors mentioned they sometimes get stuck in a local minimum with only 2 cells with constraint violations.

So I reprogrammed an R code following (as much as possible) their scheme. However, I do not get a better behaviour than with my earlier code, and certainly no solution within seconds, if any. For instance, the temperature decrease in 100(.99)t seems too steep to manage 105 steps. So, either I am missing a crucial element in the code, or my R code is very poor and clever Fortran programming does the trick! Here is my code

target=function(s){
tar=sum(apply(s,1,duplicated)+apply(s,2,duplicated))
for (r in 1:9){
bloa=(1:3)+3*(r-1)%%3
blob=(1:3)+3*trunc((r-1)/3)
tar=tar+sum(duplicated(as.vector(s[bloa,blob])))
}
return(tar)
}

cost=function(i,j,s){
#constraint violations in cell (i,j)
  cos=sum(s[,j]==s[i,j])+sum(s[i,]==s[i,j])
  boxa=3*trunc((i-1)/3)+1;
  boxb=3*trunc((j-1)/3)+1;
  cos+sum(s[boxa:(boxa+2),boxb:(boxb+2)]==s[i,j])
  }

entry=function(){
  s=con
  pop=NULL
  for (i in 1:9)
    pop=c(pop,rep(i,9-sum(con==i)))
  s[s==0]=sample(pop)
  return(s)
  }

move=function(tau,s,con){
  pen=(1:81)
  for (i in pen[con==0])
        pen[i]=cost(((i-1)%%9)+1,trunc((i-1)/9)+1,s)
  wi=sample((1:81)[con==0],2,prob=exp(pen[(1:81)[con==0]]))
  prop=s
  prop[wi[1]]=s[wi[2]]
  prop[wi[2]]=s[wi[1]]

  if (runif(1)<exp((target(s)-target(prop)))/tau)
    s=prop
  return(s)
  }

#Example:
s=matrix(0,ncol=9,nrow=9)
s[1,c(1,6,7)]=c(8,1,2)
s[2,c(2:3)]=c(7,5)
s[3,c(5,8,9)]=c(5,6,4)
s[4,c(3,9)]=c(7,6)
s[5,c(1,4)]=c(9,7)
s[6,c(1,2,6,8,9)]=c(5,2,9,4,7)
s[7,c(1:3)]=c(2,3,1)
s[8,c(3,5,7,9)]=c(6,2,1,9)

con=s
tau=100
s=entry()
for (t in 1:10^4){
  for (v in 1:100) s=move(tau,s,con)
  tau=tau*.99
  if (target(s)==0) break()
  }
Follow

Get every new post delivered to your Inbox.

Join 667 other followers