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

[Gabor Grothendieck]

For a 9x9 s board set up a constraint for
each of the 9 columns, each of the 9 rows and each
of the 3x3 boxes.

On 1/27/06, Krishna Kumar <kriskumar at earthlink.net> wrote:
> Achim thanks for pointing to David's package not being on R-help I
> missed the recent announcement.
> Gabor thanks for lpSolve. Any hints ?
>
> >>What __ON EARTH__  has this to do with R-SIG-Finance ??
> >>REALLY, this belongs to R-help and nowhere else!
>
> Martin, Ya it is a very tenuous link but my motivation was to generate ideas. And to get
> pointers to R-packages out there. I will try R-help next time.
>
> David, Thanks for sending me the updated version. I will have a go at
> it. From the preliminary comparison your original
>  version is faster my updated version see attached does better and at
> times is blazingly fast but lacks consistency..
> As you can see I use random permutations but it still is brute force and
> the search tree is different in any two attempts.
> I think it might be worth trying to compare the speed over a set of
> problems with different levels of complexity.
>
> And for what it is worth I have attached a simple sudoku generator.
>  > puzzle<-gensudoku(entropy=30)
> Generates a puzzle, entropy determines the difficulty.
>
> Best,
> Kris
>
>
>
>
>
>
>
> # Kris
> # Ver 1.2 does random permutations
> # oMat is the original puzzle,bMat keeps a backup
> mysudoku<-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]
> search.num <-sample(1:9)
> for (i in search.num) # try 1 to 9 in random order
>    { 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)
> }
>
>
>
> ## To invoke just source the file and do
> ## puzzle<-gensudoku(entropy=30)
> ## entropy determines the complexity/difficulty of the puzzle
>
> gensudoku<-function(entropy=10)
> {
>        latingrid<-function()
>        { #inner function
>                P<-sample(1:9)
>                        R<-sample(1:9)
>                        M<-matrix(0,9,9)
>                        for (coll in 1:9)
>                        {
>                                for(roww in 1:9)
>                                {
>                                        M[roww,coll] <- P[ ((roww+R[coll]) %% 9)+1]
>
>                                }
>
>                        }
>                return(M)
>        }
>
>        foo.goo<-list(flag=F)
>                while (!foo.goo$flag)
>                {
>                        oMat<-latingrid()
>                        foo.goo<-foogoo(oMat,entropy)
>                #       flag<-foo.goo$flag
>                }
>        cat("\n Good Luck with Puzzle #",trunc(runif(1)*1e6),"\n")
>        cat("-------------------------------------------------------------------\n")
>        print(foo.goo$puzzleMat)
>        cat("-------------------------------------------------------------------\n")
>        return(foo.goo$puzzleMat)
> }
>
>
>
> foogoo<-function(oMat,entropy)
> {
>
>        for (x in 1:9) # try 1 to 9
>        {
>                for (y in 1:9) # try 1 to 9
>                { sub.y<-1+3*floor((y-1)/3) # find the submatrix 3x3 block for the current matrix
>                sub.x<-1+3*floor((x-1)/3)
>                submat<-(oMat[seq(sub.x,sub.x+2),seq(sub.y,sub.y+2)])
>                l.submat<-length(which(submat==oMat[x,y]))
>                if ( any(oMat[x,-y]==oMat[x,y]) | any(oMat[-x,y]==oMat[x,y]) | l.submat>1 )  { # if not a valid grid
>                                        return(list(flag=FALSE))        }
>
>                }
>
>        }
>        solMat<-oMat
>        puzzleMat<-oMat
>        # so we have a consistent grid let us throw some points away
>        # this can help control the complexity
>        howmany.pt<- trunc(30+runif(1)*entropy);howmany.pt<-min(howmany.pt,50)
>        puzzleMat[-(trunc(runif(howmany.pt)*81))]<-0
>        #print(solMat)
>
>        return(list(flag=TRUE,puzzleMat=puzzleMat))
>
>
> }
>
>
>
> _______________________________________________
> R-sig-finance at stat.math.ethz.ch mailing list
> https://stat.ethz.ch/mailman/listinfo/r-sig-finance
>
>
>