# [R-sig-finance] [offtopic] solving sudoku in R?

Fri Jan 27 13:23:38 CET 2006

```As sudoku seems to be in fad this season how about a fast solver in R. ?
I wrote a little thingie that just does an exhaustive search and was
wondering if this could be speeded up,
I am particularly interested in putting some intelligence in to it and
any  speedups that could be done.

Currently doing,
>  system.time(sudoku())
[1] 18.25  0.02 18.43    NA    NA

18 secs for the default puzzle.Also is there a way to count function
evaluations in R (a-la-matlab flops)?.

Suggestions welcome.

Best,
Kris

# ref: http://en.wikipedia.org/wiki/Sudoku
# Simple nobrains solver
# Krishna Kumar
# oMat is the original puzzle,bMat keeps a backup
sudoku<-function(oMat=NULL,bMat=NULL)
{
if (length(oMat) < 1)
{ # use this sudoku if none is given
oMat<-matrix(c(0, 1, 0 ,0 ,0 ,0, 0, 7, 0,
3, 0, 2 ,1 ,0 ,9, 8, 0, 4,
0 ,0, 0, 5, 0, 8, 0, 0, 0,
6, 0, 0, 0, 9, 0, 0, 0, 2,
0, 4, 0, 0, 0, 0, 0, 3, 0,
8, 0, 0, 0, 3, 0, 0, 0, 7,
0, 0, 0, 9, 0, 5, 0, 0, 0,
2, 0, 4, 7, 0, 3, 9, 0, 1,
0, 9, 0, 0, 0, 0, 0, 4, 0),9,9)
print(oMat)
}
indx<-which(oMat==0,arr.ind=T) # where are the empty cells
if(length(indx) > 0) {
row.num<-indx[,1]
col.num<-indx[,2]
}
else {
print("solution")
return(oMat) #voila!
}
x<-row.num[1]
y<-col.num[1]
for (i in 1:9) # try 1 to 9
{ sub.y<-1+3*floor((y-1)/3) # find the submatrix 3x3 block for the
current solution
sub.x<-1+3*floor((x-1)/3)
if (!( any(oMat[x,]==i) | any(oMat[,y]==i) |
any((oMat[seq(sub.x,sub.x+2),seq(sub.y,sub.y+2)]==i)) )) { # if valid
number
work<-oMat
work[x,y]<-i
work<-Recall(oMat=work,bMat=oMat); # solve with this if we fail
if (all(work))  {
oMat<-work # voila!
return(oMat)
}
}
}
return(bMat)
}