Last active
April 4, 2020 09:33
-
-
Save syte/7284302fc46cf1ce989ae7670a7ebbcc to your computer and use it in GitHub Desktop.
Sudoku Solver
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Capable of solving any N * N sudoku puzzle in exponential time :P | |
| */ | |
| import scala.math.sqrt | |
| type Board = Array[Array[Int]] | |
| case class Cell(x: Int, y: Int, value: Int) | |
| class Sudoku(var board: Board) { | |
| def solve(): Boolean = { | |
| findCell match { | |
| case Some(cell) => { | |
| for (value <- 1 to board.size) { | |
| if (canFill(cell, value)) { | |
| board(cell.x).update(cell.y, value) | |
| if (solve()) { | |
| return true | |
| } | |
| } | |
| } | |
| board(cell.x).update(cell.y, 0) | |
| false | |
| } | |
| case _ => true | |
| } | |
| } | |
| def print(): Unit = { | |
| board.foreach(r => println(f"[${r.mkString(", ")}]")) | |
| } | |
| private def canFill(cell: Cell, value: Int): Boolean = { | |
| val row = cell.x | |
| val col = cell.y | |
| for (pos <- 0 until board.size) { | |
| if (board(row)(pos) == value || board(pos)(col) == value) { | |
| return false | |
| } | |
| } | |
| // Handle variable block sizes. Messy. But who cares since this will never be used again. | |
| val blockSize = sqrt(board.size).toInt | |
| val start = Tuple2((row % blockSize) * blockSize, (col % blockSize) * blockSize) | |
| val end = Tuple2(start._1 + blockSize - 1, start._1 + blockSize - 1) | |
| for (row <- start._1 until end._1; col <- end._1 until end._2) | |
| if (board(row)(col) == value) | |
| return false | |
| true | |
| } | |
| private def cells: IndexedSeq[Cell] = { | |
| for (x <- 0 until board.size; y <- 0 until board.size) | |
| yield new Cell(x, y, board(x)(y)) | |
| } | |
| private def findCell(): Option[Cell] = { | |
| cells.find(_.value == 0) | |
| } | |
| } | |
| val sudoku = new Sudoku(Array( | |
| Array(3, 2, 6, 5, 0, 8, 4, 0, 0), | |
| Array(5, 2, 0, 0, 0, 0, 0, 0, 0), | |
| Array(0, 8, 7, 0, 0, 0, 0, 3, 1), | |
| Array(0, 0, 3, 0, 1, 0, 0, 8, 0), | |
| Array(9, 0, 0, 8, 6, 3, 0, 0, 5), | |
| Array(0, 5, 0, 0, 9, 0, 6, 0, 0), | |
| Array(1, 3, 0, 0, 0, 0, 2, 5, 0), | |
| Array(0, 0, 0, 0, 0, 0, 0, 7, 4), | |
| Array(0, 0, 5, 2, 0, 6, 3, 0, 0), | |
| )) | |
| if(sudoku.solve) { | |
| sudoku.print() | |
| } | |
| else { | |
| println("Aint got no solutions") | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment