[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