[R-sig-finance] [offtopic] solving sudoku in R?
Gabor Grothendieck
ggrothendieck at gmail.com
Fri Jan 27 15:35:39 CET 2006
You could try the lpSolve package.
On 1/27/06, Krishna Kumar <kriskumar at earthlink.net> wrote:
> 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
> then we just return to the original matrix
> if (all(work)) {
> oMat<-work # voila!
> return(oMat)
> }
> }
> }
> return(bMat)
> }
>
> <cid:part1.01050202.07020505 at earthlink.net>
>
> _______________________________________________
> R-sig-finance at stat.math.ethz.ch mailing list
> https://stat.ethz.ch/mailman/listinfo/r-sig-finance
>
More information about the R-sig-finance
mailing list