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 |
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 |
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 |
Free forum by Nabble - Scala forum | Edit this page |