Skip to content

Instantly share code, notes, and snippets.

@pathikrit
Last active April 12, 2024 15:00
Show Gist options
  • Save pathikrit/a32e17832296befd6b94 to your computer and use it in GitHub Desktop.
Save pathikrit/a32e17832296befd6b94 to your computer and use it in GitHub Desktop.
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 guess(x: Int) = solve(board.updated(r, board(r).updated(c, x)), cell + 1)
val used = board.indices.flatMap(i => Seq(board(r)(i), board(i)(c), board(s*(r/s) + i/s)(s*(c/s) + i%s)))
(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"))
@EDGutterres
Copy link

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
Copy link

ayeo commented Feb 13, 2020

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment