Skip to content

Instantly share code, notes, and snippets.

@gordonpassy

gordonpassy/SudokuSolver.scala

Forked from pathikrit/SudokuSolver.scala
Created October 22, 2018 13:01
Show Gist options
  • Save gordonpassy/77a1f99883bdc3b95b69d65bd90ee1e8 to your computer and use it in GitHub Desktop.
Save gordonpassy/77a1f99883bdc3b95b69d65bd90ee1e8 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @pathikrit pathikrit revised this gist Jul 14, 2015. 1 changed file with 5 additions and 6 deletions.
    11 changes: 5 additions & 6 deletions SudokuSolver.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -1,18 +1,17 @@
    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)

    1 to n diff (board.indices flatMap cells) collectFirst Function.unlift(guess)
    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
    @@ -26,4 +25,4 @@ val board = $( //0s denote empty cells
    $(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")
    println(solve(board).get.map(_ mkString " ") mkString "\n")
  2. @pathikrit pathikrit created this gist Apr 8, 2015.
    29 changes: 29 additions & 0 deletions SudokuSolver.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,29 @@
    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)

    1 to n diff (board.indices flatMap cells) 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")