Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# pathikrit/SudokuSolver.scala

Last active Mar 19, 2021
Sudoku Solver in Scala
 val n = 9 val s = Math.sqrt(n).toInt type Board = IndexedSeq[IndexedSeq[Int]] def solve(board: Board, cell: Int = 0): Option[Board] = (cell%n, cell/n) match { case (r, `n`) => Some(board) case (r, c) if board(r)(c) > 0 => solve(board, cell + 1) case (r, c) => def cells(i: Int) = Seq(board(r)(i), board(i)(c), board(s*(r/s) + i/s)(s*(c/s) + i%s)) def guess(x: Int) = solve(board.updated(r, board(r).updated(c, x)), cell + 1) val used = board.indices.flatMap(cells) (1 to n).diff(used).collectFirst(Function.unlift(guess)) } ////////////////////////////////////////////////////////////////// import scala.collection.{IndexedSeq => \$} val board = \$( //0s denote empty cells \$(1, 0, 0, 0, 0, 7, 0, 9, 0), \$(0, 3, 0, 0, 2, 0, 0, 0, 8), \$(0, 0, 9, 6, 0, 0, 5, 0, 0), \$(0, 0, 5, 3, 0, 0, 9, 0, 0), \$(0, 1, 0, 0, 8, 0, 0, 0, 2), \$(6, 0, 0, 0, 0, 4, 0, 0, 0), \$(3, 0, 0, 0, 0, 0, 0, 1, 0), \$(0, 4, 0, 0, 0, 0, 0, 0, 7), \$(0, 0, 7, 0, 0, 0, 3, 0, 0) ) println(solve(board).get.map(_.mkString(" ")).mkString("\n"))

### estaub commented Apr 9, 2015

 A fairly easy and very powerful first optimization to make is to make each solution subtree start with the cell that is most restricted - has the most values in its row+column+grid, rather than go in matrix order.

### pathikrit commented Apr 15, 2015

 @estaub: Totally agree. My goal here was to demonstrate the minimum viable solution i.e. shortest but readable code that can solve a puzzle under a second on my Macbook...

### EDGutterres commented Oct 16, 2019

 Hello, I'm new to Scala, and I'd like to know: Is there a way to make this a 6x6 board without the "Sub-Cells" part of the Sudoku puzzle? How would one do that?

### ayeo commented Feb 13, 2020 • edited

 I have been experimenting with this algorithm for a while. I finally came up with slighty easier to understand readable version (I hope so) :) Maybe someone will find this useful for reasoning about ``````def possibleDigits(board: Board, r: Int, c: Int): Seq[Int] = { def cells(i: Int) = Seq(board(r)(i), board(i)(c), board(s*(r/s) + i/s)(s*(c/s) + i%s)) val used = board.indices.flatMap(cells) (1 to 9).diff(used) } def solve(board: Board, cell: Int = 0): Option[Board] = (cell%n, cell/n) match { case (0, 9) => Some(board) //cell=81 board solved case (r, c) if board(r)(c) > 0 => solve(board, cell + 1) case (r, c) => possibleDigits(board, r, c) .flatMap(n => solve(board.updated(r, board(r).updated(c, n)))) //put n at (r,c) position .headOption //return first not None element or None (if not exists) } `````` The algorithm is masterpiece to me! Elegant and concise.
to join this conversation on GitHub. Already have an account? Sign in to comment