Archive for Colosseo

a journal of the imperial centuries

Posted in Books, Kids, Mountains, pictures, Running, Travel, University life, Wines with tags , , , , , , , , , , , , , , , , , , , , , , , , , on February 9, 2026 by xi'an

Over my trip to Rome, I managed to finish Titanium Noir, a science-fiction novel by Nick Harkaway, about an old-school detective trying to solve a murder in a society where a happy fews can become Titans, enhanced humans (aka transhumans) with larger bodies and higher life expectancy, except when they get killed of course. This is a rather enjoyable book, even though the science-fiction part does not play so well, since almost everything sounds like it was the 50’s, the 1950’s! Even the dialogues, which are somewhat outdated (no one uses gumshoe anymore!). But apart from that, the detective work is enough of a page turner and the final twist not completely predictable. Enjoyable maybe not to the point of continuing the series, since the twist cannot happens twice! Also read the very short novella Human Resources by Adrian Tchaikovsky, hugely if shortly disappointing!

Cooked winter standards (at home) like butternut soup and pulled pork. And pissaladière. Had two meals made of tonnarelli pasta, while 25H in Rome, a square variant to the spaghetti. One before strolling to the Fori Romani to watch the most recent excavations. And to admire the new Colosseo-Fori Imperiali metro station (with reconstituted household wells! And exhibits of objects found at their bottom).

Unrelated, but I watched MIU 404, a rather silly police series set in Tokyo, whose main appeals resides in exposing some issues in the modern Japanese society, like stalking or the status of migrants. But don’t expect realistic resolutions of the crime(s) motivating each episode…

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

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