# [offtopic] solving sudoku in R?

6 messages
Open this post in threaded view
|

## [offtopic] solving sudoku in R?

 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) } _______________________________________________ [hidden email] mailing list https://stat.ethz.ch/mailman/listinfo/r-sig-finance
Open this post in threaded view
|

## Re: [offtopic] solving sudoku in R?

 On Fri, 27 Jan 2006 07:23:38 -0500 Krishna Kumar wrote: > As sudoku seems to be in fad this season how about a fast solver in > R. ? Try install.packages("sudoku") :-) David Brahm has written this. What is still missing is a sudoku generator... Best, Z > 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) > } > > > > _______________________________________________ > [hidden email] mailing list > https://stat.ethz.ch/mailman/listinfo/r-sig-finance> _______________________________________________ [hidden email] mailing list https://stat.ethz.ch/mailman/listinfo/r-sig-finance
Open this post in threaded view
|

## Re: [offtopic] solving sudoku in R?

 In reply to this post by Krishna Kumar-2 You could try the lpSolve package. On 1/27/06, Krishna Kumar <[hidden email]> 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) > } > > > > _______________________________________________ > [hidden email] mailing list > https://stat.ethz.ch/mailman/listinfo/r-sig-finance> _______________________________________________ [hidden email] mailing list https://stat.ethz.ch/mailman/listinfo/r-sig-finance
Open this post in threaded view
|

## Re: [offtopic] solving sudoku in R?

 In reply to this post by Achim Zeileis >>>>> "Achim" == Achim Zeileis <[hidden email]> >>>>>     on Fri, 27 Jan 2006 13:54:11 +0100 writes:     Achim> On Fri, 27 Jan 2006 07:23:38 -0500 Krishna Kumar wrote:     >> As sudoku seems to be in fad this season how about a fast solver in     >> R. ?     Achim> Try install.packages("sudoku") :-)     Achim> David Brahm has written this. What is still missing is a sudoku     Achim> generator... David Brahm has his next version of 'sudoku' -- greatly enhanced in testing. What __ON EARTH__  has this to do with R-SIG-Finance ?? REALLY, this belongs to R-help and nowhere else! Martin     Achim> Best,     Achim> Z     >> 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, _______________________________________________ [hidden email] mailing list https://stat.ethz.ch/mailman/listinfo/r-sig-finance