[offtopic] solving sudoku in R?

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

[offtopic] solving sudoku in R?

Krishna Kumar-2
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:[hidden email]>

_______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-sig-finance
Reply | Threaded
Open this post in threaded view
|

Re: [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:[hidden email]>
>
> _______________________________________________
> [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
Reply | Threaded
Open this post in threaded view
|

Re: [offtopic] solving sudoku in R?

Gabor Grothendieck
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)
> }
>
> <cid:[hidden email]>
>
> _______________________________________________
> [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
Reply | Threaded
Open this post in threaded view
|

Re: [offtopic] solving sudoku in R?

Martin Maechler
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
Reply | Threaded
Open this post in threaded view
|

Re: [offtopic] solving sudoku in R?

Krishna Kumar-2
In reply to this post by Krishna Kumar-2
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))


}


_______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-sig-finance
Reply | Threaded
Open this post in threaded view
|

Re: [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 <[hidden email]> 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))
>
>
> }
>
>
>
> _______________________________________________
> [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