25 lines Sudoku solver in Scala

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

25 lines Sudoku solver in Scala

Moez A. Abdel-Gawad
The following Scala program (initially written in OCaml) uses
simple brute-force to solve standard Sudoku.

<code>

object SudokuSolver extends Application {
   // The board is represented by an array of strings (arrays of chars),
   // held in a global variable m. The program begins by reading 9 lines
   // of input to fill the board
   var m: Array[Array[char]] = List.tabulate( 9, (x:int) =>
Console.readLine.toArray).toArray;

   // For printing m, a method print is defined
   def print = {Console.println(""); m map (carr=>Console.println(new
String(carr)))}

   // The test for validity is performed by looping over i=0..8 and
   // testing the row, column and 3x3 square containing the given
   // coordinate
   def invalid(i:int, x:int, y:int, n:char): boolean =
     i<9 && (m(y)(i) == n || m(i)(x) == n ||
       m(y/3*3 + i/3)(x/3*3 + i % 3) == n || invalid(i+1, x, y, n))

   // Looping over a half-closed range of consecutive integers [l..u)
   // is factored out into a higher-order function
   def fold(f: (int,int)=>int, accu:int, l:int, u:int):int =
     if(l==u) accu else fold(f, f(accu, l), l+1, u)

   // The search function examines each position on the board in turn,
   // trying the numbers 1..9 in each unfilled position
   // The function is itself a higher-order fold, accumulating the value
   // accu by applying the given function f to it whenever a solution m
   // is found
   def search(x:int, y:int, f:(int)=>int, accu:int):int = Pair(x, y) match {
     case Pair(9, y) => search(0, y+1, f, accu) // next row
     case Pair(0, 9) => f(accu)                 // found a solution
     case Pair(x, y) => if(m(y)(x) != '0') search(x+1, y, f, accu) else
       fold((accu:int, n:int) =>
            if(invalid(0, x, y, (n + 48).asInstanceOf[char])) accu else {
              m(y)(x) = (n + 48).asInstanceOf[char];
              val newaccu = search(x+1, y, f, accu);
              m(y)(x) = '0';
              newaccu}, accu, 1, 10)}

   // The main part of the program uses the search function to accumulate
   // the total number of solutions
   Console.println("\n"+search(0,0,i => {print; i+1},0)+" solution(s)")
}

</code>

The program demonstrates that the immutability of
String in Java/Scala is an annoyance (and that
Scala's 'asInstanceOf', as well as some other con-
structs, is verbose). It seems the program cannot
be made significantly shorter though. Any attempt
to make it more efficient using useful-to-humans-
only strategies would certainly make it's code
longer. It seems, in fact, the program does not
need to be made more efficient as it solves many/
most well-formed puzzles in less than a second,
including the most fiendish and diabolical!

After compiling the program you can run it using:

   scala SudokuSolver < puzzle

where puzzle is a sample text file containing the
following (0 stands for blanks):

001005300
050490000
000102064
000000750
600000001
035000000
460903000
000024090
003600100

The output of the program for that puzzle should be:

241865379
356497218
879132564
194386752
682579431
735241986
467913825
518724693
923658147

1 solution(s)

--
-Moez

======================================================

"There is no end to what a man can achieve, if he does
  not mind who gets the credit." -Ahmad Deedat

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: 25 lines Sudoku solver in Scala

Greg Fitzgerald
Has anyone seen one shorter than the Haskell version?

http://web.math.unifi.it/users/maggesi/haskell_sudoku_solver.html

Thanks,
Greg


On 8/28/06, Moez A. Abdel-Gawad <[hidden email]> wrote:
The following Scala program (initially written in OCaml) uses
simple brute-force to solve standard Sudoku.

<code>

object SudokuSolver extends Application {
   // The board is represented by an array of strings (arrays of chars),
   // held in a global variable m. The program begins by reading 9 lines
   // of input to fill the board
   var m: Array[Array[char]] = List.tabulate( 9, (x:int) =>
Console.readLine.toArray).toArray;

   // For printing m, a method print is defined
   def print = {Console.println(""); m map (carr=>Console.println(new
String(carr)))}

   // The test for validity is performed by looping over i=0..8 and
   // testing the row, column and 3x3 square containing the given
   // coordinate
   def invalid(i:int, x:int, y:int, n:char): boolean =
     i<9 && (m(y)(i) == n || m(i)(x) == n ||
       m(y/3*3 + i/3)(x/3*3 + i % 3) == n || invalid(i+1, x, y, n))

   // Looping over a half-closed range of consecutive integers [l..u)
   // is factored out into a higher-order function
   def fold(f: (int,int)=>int, accu:int, l:int, u:int):int =
     if(l==u) accu else fold(f, f(accu, l), l+1, u)

   // The search function examines each position on the board in turn,
   // trying the numbers 1..9 in each unfilled position
   // The function is itself a higher-order fold, accumulating the value
   // accu by applying the given function f to it whenever a solution m
   // is found
   def search(x:int, y:int, f:(int)=>int, accu:int):int = Pair(x, y) match {
     case Pair(9, y) => search(0, y+1, f, accu) // next row
     case Pair(0, 9) => f(accu)                 // found a solution
     case Pair(x, y) => if(m(y)(x) != '0') search(x+1, y, f, accu) else
       fold((accu:int, n:int) =>
            if(invalid(0, x, y, (n + 48).asInstanceOf[char])) accu else {
              m(y)(x) = (n + 48).asInstanceOf[char];
              val newaccu = search(x+1, y, f, accu);
              m(y)(x) = '0';
              newaccu}, accu, 1, 10)}

   // The main part of the program uses the search function to accumulate
   // the total number of solutions
   Console.println("\n"+search(0,0,i => {print; i+1},0)+" solution(s)")
}

</code>

The program demonstrates that the immutability of
String in Java/Scala is an annoyance (and that
Scala's 'asInstanceOf', as well as some other con-
structs, is verbose). It seems the program cannot
be made significantly shorter though. Any attempt
to make it more efficient using useful-to-humans-
only strategies would certainly make it's code
longer. It seems, in fact, the program does not
need to be made more efficient as it solves many/
most well-formed puzzles in less than a second,
including the most fiendish and diabolical!

After compiling the program you can run it using:

   scala SudokuSolver < puzzle

where puzzle is a sample text file containing the
following (0 stands for blanks):

001005300
050490000
000102064
000000750
600000001
035000000
460903000
000024090
003600100

The output of the program for that puzzle should be:

241865379
356497218
879132564
194386752
682579431
735241986
467913825
518724693
923658147

1 solution(s)

--
-Moez

======================================================

"There is no end to what a man can achieve, if he does
  not mind who gets the credit." -Ahmad Deedat


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: 25 lines Sudoku solver in Scala

Boris Borcic-2
Greg Fitzgerald wrote:
> Has anyone seen one shorter than the Haskell version?
>
> http://web.math.unifi.it/users/maggesi/haskell_sudoku_solver.html
>
> Thanks,
> Greg

At

http://markbyers.com/moinmoin/moin.cgi/ShortestSudokuSolver

there are sudoku solvers in C,Perl,Ruby and Python, all less than 200 chars long
(and of course rather ugly). Winner is Ruby with 130 bytes.

Personally, I'd would be more interested in a competition that balances
concision with performance (and measures code in tokens rather than bytes).

Best, bb

Loading...