# 25 lines Sudoku solver in Scala

3 messages
Open this post in threaded view
|
Report Content as Inappropriate

## 25 lines Sudoku solver in Scala

 The following Scala program (initially written in OCaml) uses simple brute-force to solve standard Sudoku. 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)") } 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
Open this post in threaded view
|
Report Content as Inappropriate

## Re: 25 lines Sudoku solver in Scala

 Has anyone seen one shorter than the Haskell version?http://web.math.unifi.it/users/maggesi/haskell_sudoku_solver.htmlThanks, GregOn 8/28/06, Moez A. Abdel-Gawad <[hidden email]> wrote: The following Scala program (initially written in OCaml) usessimple brute-force to solve standard Sudoku.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(newString(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)")}The program demonstrates that the immutability ofString in Java/Scala is an annoyance (and that Scala's 'asInstanceOf', as well as some other con-structs, is verbose). It seems the program cannotbe made significantly shorter though. Any attemptto make it more efficient using useful-to-humans-only strategies would certainly make it's code longer. It seems, in fact, the program does notneed 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 < puzzlewhere puzzle is a sample text file containing thefollowing (0 stands for blanks):001005300050490000000102064000000750600000001035000000460903000 000024090003600100The output of the program for that puzzle should be:2418653793564972188791325641943867526825794317352419864679138255187246939236581471 solution(s) ---Moez======================================================"There is no end to what a man can achieve, if he does  not mind who gets the credit." -Ahmad Deedat