Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Simple sudoku solvers based on scala streams
package sudoku
class BoxMappedSudoku {
val EmptyValue = '0'
val MaxValue = 9
val allValues = "123456789".toList
val indexes = (0 to 8).toList
val boxCoordinates = (0 to 2).toList
def getX(pos: Int): Int = pos % MaxValue
def getY(pos: Int): Int = pos / MaxValue
def box(pos: Int): List[Int] = {
def base(p: Int): Int = (p / 3) * 3
val x0 = base(getX(pos))
val y0 = base(getY(pos))
val ys = (y0 until y0 + 3).toList
(x0 until x0 + 3).toList.flatMap(x => ys.map(x + _ * 9))
}
val boxes = boxCoordinates flatMap (x => boxCoordinates map (x * 3 + _ * 3 * 9)) map box
class Board(val game: String) {
val empty = game indexOf EmptyValue
val isDone = empty == -1
def updated(pos: Int)(value: Char): Board = new Board(game updated (pos, value))
def row(y: Int): List[Char] = indexes map (col => game(y * MaxValue + col))
def col(x: Int): List[Char] = indexes map (row => game(x + row * MaxValue))
def box(pos: Int): List[Char] = (boxes filter (_ contains pos)).head map game
def toAvoid(pos: Int): List[Char] = (col(getX(pos)) ++ row(getY(pos)) ++ box(pos)).distinct
def candidates(pos: Int): List[Char] = allValues diff toAvoid(pos)
def next: Stream[Board] = candidates(empty).toStream map updated(empty)
override def toString: String = "\n" + (game sliding (MaxValue, MaxValue) mkString "\n")
}
def build(game: String): Board = new Board(game)
def from(path: Stream[Board]): Stream[Board] = path match {
case h #:: t => h #:: from(t ++ h.next)
case _ => Stream.empty
}
def steps(game: String): Stream[Board] = from(Stream(build(game)))
def solve(game: String): Board = steps(game).filter(_.isDone).head
}
package sudoku
object play {
val sudoku = new Sudoku //> sudoku : sudoku.Sudoku = sudoku.Sudoku@7e8bf0
val sample = "651702090" + "030416257" + "742500006" +
"000040562" + "460125038" + "523860000" +
"285694371" + "004378625" + "376251849"
//> sample : String = 651702090030416257742500006000040562460125038523860000285
//| 694371004378625376251849
//sudoku.solve(sample)
val game = "100459000" + "803070900" + "000008000" +
"508002600" + "900060007" + "007900105" +
"000200000" + "006080204" + "000594003"
//> game : String = 10045900080307090000000800050800260090006000700790010500020
//| 0000006080204000594003
//sudoku.solve(game)
val hardGame = "014060300" + "620004009" + "080050600" +
"060200003" + "070010050" + "500009060" +
"006020030" + "100500092" + "007090410"
//> hardGame : String = 0140603006200040090800506000602000030700100505000090600
//| 06020030100500092007090410
sudoku.solve(hardGame) //> res0: sudoku.play.sudoku.Board =
//| 714962385
//| 625834179
//| 389157624
//| 961285743
//| 472613958
//| 538749261
//| 896421537
//| 143576892
//| 257398416
val optimizedSudoku = new BoxMappedSudoku //> optimizedSudoku : sudoku.BoxMappedSudoku = sudoku.BoxMappedSudoku@1d8add3
optimizedSudoku.solve(hardGame) //> res1: sudoku.play.optimizedSudoku.Board =
//| 714962385
//| 625834179
//| 389157624
//| 961285743
//| 472613958
//| 538749261
//| 896421537
//| 143576892
//| 257398416|
}
package sudoku
class Sudoku {
type Position = (Int, Int)
val EmptyValue = '0'
val MaxValue = 9
val allValues = "123456789".toList
val indexes = (0 to 8).toList
class Board(val game: String) {
val empty = game indexOf EmptyValue
val emptyPosition = (empty % MaxValue, empty / MaxValue)
val isDone = empty == -1
def updated(pos: Int, value: Char): Board = new Board(game updated (pos, value))
def row(y: Int): List[Char] = indexes map (col => game(y * MaxValue + col))
def col(x: Int): List[Char] = indexes map (row => game(x + row * MaxValue))
def box(pos: Position): List[Char] = {
def base(p: Int): Int = (p / 3) * 3
val x0 = base(pos._1)
val y0 = base(pos._2)
val ys = (y0 until y0 + 3).toList
(x0 until x0 + 3).toList.flatMap(x => ys.map(y => game(x + y * MaxValue)))
}
def toAvoid(pos: Position): List[Char] = (col(pos._1) ++ row(pos._2) ++ box(pos)).distinct
def candidates(pos: Position): List[Char] = allValues diff toAvoid(pos)
def next: Stream[Board] = candidates(emptyPosition).toStream map (c => updated(empty, c))
override def toString: String = "\n" + (game sliding (MaxValue, MaxValue) mkString "\n")
}
def build(game: String): Board = new Board(game)
def from(path: Stream[Board]): Stream[Board] = path match {
case h #:: t => h #:: from(t ++ h.next)
case _ => Stream.empty
}
def steps(game: String): Stream[Board] = from(Stream(build(game)))
def solve(game: String): Board = steps(game).filter(_.isDone).head
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment