I'm (very) new to Scala, and decided I'd try to get a handle on some of the syntax and general language constructs. This currently doesn't implement any backtracking and will only solve things if they can be derived exactly from the values given in the initial board.
That being said, I don't particularly care about adding backtracking at the moment; this was much more a project to simply deal with some of the simpler language constructs (Basic I/O
and Collections
usage, mainly). I'm far more interested in:
- How I can improve my code: there are definite blocks of "imperativeness" that are hanging around. Can these be replaced with equivalent code in a more functional style?
- Style guidelines: are there any general Scala style guidelines I'm breaking? Names and cases for methods and variables, comments, etc.
- Collection and File I/O usage. Any methods from these that I'm not currently using that would simplify the code?
- Exception handling: currently there is none. I'm not sure how this is done idiomatically in Scala, minus the fact that exceptions are used judiciously. I've left it out mainly out of language ignorance; any pointers on how this could be included here in a functional style would be great.
{Note: I'm aware of the badness of not putting this in a package, but I've left it out here on purpose.}
import scala.collection.mutable.{Map => MMap}
import scala.collection.mutable.HashMap
import scala.collection.mutable.{Set => MSet}
import scala.io.Source
import scala.math.ceil
/** Basic Sudoku Solver.
*
* Currently only supports solving completely "logical" puzzles
* (that is, anything that doesn't need guess-and-check
* style backtracking).
*
*/
object BasicSudokuSolver
{
val rowLength = 9
val columnLength = 9
val allPossible = allPossibleValues()
def main(args: Array[String]) = {
val line = readPuzzleFile(args(0))
val puzzle = linesToMap(line)
var hasChanged = true
//Imperative style code. Each time around, we check if we've solved
//at least one extra value in our puzzle. If we haven't, then we've
//exhausted how much can be filled in by logic alone, and we'd have
//to start guess and check + backtracking to a solution.
while (hasChanged) {
hasChanged = false
//We only want a list indexes of values that haven't been solved yet
val currentUnknown = puzzle.filter(x => x._2 == 0).keys.toIterator
for (index <- currentUnknown) {
val z = filterPossibilities(puzzle, index)
if (z > 0) {
hasChanged = true
puzzle(index) = z
}
}
}
//Create a sorted list from our Map, based on List[Int].
//We want the indexes to come out in the value ordered by row, then column.
val solved = puzzle.toList.sortWith((x, y) => if (x._1(0) == y._1(0)) x._1(1) < y._1(1)
else x._1(0) < y._1(0))
for (v <- solved.zipWithIndex) {
if (v._2 % columnLength == 0) println()
print(v._1._2 + " ")
}
println()
}
/** Reads in a sudoku puzzle. This should conform to the following:
* - Unknown values are 0
* - Known values are their integer value
* - Separator is a simple space (" ")
* - There is a trailing space after the last value, before the newline
* For example, a row of the puzzle may look like:
* 0 0 3 0 2 0 6 0 0 /n
*
* Returns: The puzzle as a single string, separated by spaces.
*/
def readPuzzleFile(name: String): String = {
val source = Source.fromFile(name)
val lines = source.mkString.replace(System.lineSeparator(), "")
source.close
lines
}
/** Given a string containing a sudoku puzzle conforming to spec in the
* comments above readPuzzleFile, will convert this to a Map[List[Int], Int]
* where the List[Int] (Key) contains the row/column index,
* and the Int (Value) contains the puzzle value for that index. Note that
* indexes start at 1, and go through to 9 (inclusive).
*
* Returns: Map containing ((rowIndex, columnIndex), value) pairs
*/
def linesToMap(line: String): MMap[List[Int], Int] = {
val puzzleValues = line.split(" ").map(_.toInt)
val m = new HashMap[List[Int], Int]()
for {
i <- 1 to rowLength
j <- 1 to columnLength
} m += (List(i, j) -> puzzleValues((i - 1) * rowLength + (j - 1)))
m
}
/** Returns: A simple Set[Int] containing all possible values for any
* index prior to removal via constraints. Equivalent to a Set[Int](1 to 9).
*/
def allPossibleValues(): Set[Int] = {
val set = MSet[Int]()
for(i <- 1 to rowLength) set += i
set.toSet
}
/** Filters the set of all possibilities (1 - 9) based on row, column
* and box constraints. Any value which already exists in the same
* column, row, or box is removed from the set of all possibilities.
*
* Returns: the (singular) value that can go into a given index if such a
* singular value exists, otherwise 0.
*/
def filterPossibilities(puzzle: MMap[List[Int], Int], index: List[Int]): Int = {
val columnValues = puzzle.filter(x => x._1(1) == index(1) &&
x._2 != 0).values.toSet
val rowValues = puzzle.filter(x => x._1(0) == index(0) &&
x._2 != 0).values.toSet
val allPoss = allPossible&~(columnValues.union(rowValues).union(getBoxValues(puzzle, index)))
if (allPoss.size == 1) allPoss.toIterator.next else 0
}
/** Returns: All values around an index in its given "box". These are then
* removed from the set of all possibilities in filterPossibilities.
*/
def getBoxValues(puzzle: MMap[List[Int], Int], index: List[Int]):
Set[Int] = {
val boxNumber = List(ceil(index(0) / 3.0).toInt, ceil(index(1) / 3.0).toInt)
val upperBound = List(3 * boxNumber(0), 3 * boxNumber(1))
val lowerBound = List(3 * boxNumber(0) - 2, 3 * boxNumber(1) - 2)
val values = MSet[Int]()
for {
i <- lowerBound(0) to upperBound(0)
j <- lowerBound(1) to upperBound(1)
} values += puzzle(List(i, j))
values.toSet
}
}