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

[Achim Zeileis]

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)
> }
> 
> <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
>