Basic (Logical Only) Sudoku Solver

Question

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
    }      
} 

Answer 1

There are some things that can improved here. First, try to find the most appropriate data structure that does what you want. Why a List with x and y coordinates instead of a Tuple2 or even better a Position?

---

Why does allPossibleValues exists?

(1 to 9).toSet or Set(1 to 9: _*) is enough.

---

Never return error values like in filterPossibilities, instead use the Option monad:

if (allPoss.size == 1) allPoss.toIterator.next else 0
// should be used as
if (allPoss.size == 1) allPoss.headOption else None

Furthermore, try to prefix find before methods returning Option.

---

Don't prefix get before a method name unless you try to interoperate with Java code - in functional languages everything returns a value, thus there is no need to mark this as a property of a method.

getBoxValues -> boxValues

---

source.mkString.replace(System.lineSeparator(), "") is equivalent to source.getLines.mkString

---

map.filter(f).keys is equivalent to map.collect{case (k,v) if f => k}

---

A Map[Position, Int] can easily be sorted with map.toList.sortBy(_._1) when you provide an implicit Ordering[Position] (preferable in the companion object of Position because of automatic import)

---

Instead of your imperative way to print out the Sudoku, you can use something of the form

seqOfDim2 map (_ mkString " ") mkString "\n"

---

In Scala normally one does never create a collection with new, instead the companion objects should be used. These provide factories in order to hide the information which collection is created. Appending to mutable collections can normally be avoided with yield (of the for-comprehension) or with a fold.

---

Instead of accessing values in a Seq by its index or in a tuple by its corresponding _x methods, just use pattern matching:

scala> val List(a, b) = List(1, 2)
a: Int = 1
b: Int = 2

scala> val (a, b) = (1, 2)
a: Int = 1
b: Int = 2

---

To get rid of ugly side effects monads can be used. But for I/O there is no I/O-monad in Scala. Instead we have to use some method chaining on Iterator:

val value = Iterator.iterate(start)(f).dropWhile(f).next

---

Use classes to avoid unnecessary parameters to methods. Methods that operate on the same values can be methods on class

case class Sudoku(puzzle: Map[Position, Int]) {
  def findPossibility(pos: Position): Option[Int] = ???
  def boxValues(pos: Position): Set[Int] = ???
}

// instead of
def findPossibility(puzzle: Map[Position, Int], pos: Position): Option[Int] = ???
def boxValues(puzzle: Map[Position, Int], pos: Position): Set[Int] = ???

This also brings more OO into your code.

---

You can use util.Try (another monad) to get rid of exceptions.

---

At the end your code can look like this:

import scala.util._

/**
 * Basic Sudoku Solver.
 *
 * Currently only supports solving completely "logical" puzzles
 * (that is, anything that doesn't need guess-and-check
 * style backtracking).
 *
 */
object BasicSudokuSolver {

  def main(args: Array[String]) = {
//    val input = readPuzzleFile("sudoku")

    val input =
      """0 6 0 8 0 0 2 0 9
3 2 1 0 6 0 0 7 0
0 9 0 0 0 0 6 5 3
0 0 0 0 1 7 0 6 0
4 0 0 3 0 2 0 0 5
0 1 0 6 8 0 0 0 7
1 3 0 0 0 9 0 4 0
0 5 0 0 4 0 9 3 8
6 0 9 0 0 8 0 0 0""" split "\n"

    val linesToPuzzle = Try {
      val data = input map (_ split " " map (_.toInt))
      val puzzle = for (x <- 1 to 9; y <- 1 to 9) yield Position(x, y) -> data(x - 1)(y - 1)
      puzzle.toMap
    }

    linesToPuzzle match {
      case Failure(e) => println(e)
      case Success(startPuzzle) =>
        val field = solveSudoku(startPuzzle).field.toList.sortBy(_._1)
        val actual = field map (_._2) grouped 9 map (_ mkString " ") mkString "\n"

        val expected =
          """5 6 4 8 7 3 2 1 9
3 2 1 9 6 5 8 7 4
8 9 7 4 2 1 6 5 3
9 8 3 5 1 7 4 6 2
4 7 6 3 9 2 1 8 5
2 1 5 6 8 4 3 9 7
1 3 8 2 5 9 7 4 6
7 5 2 1 4 6 9 3 8
6 4 9 7 3 8 5 2 1"""

        assert(actual == expected)
        println("ok")
    }

  }

  def solveSudoku(startField: Map[Position, Int]): Sudoku = {
    val iter = Iterator.iterate(Sudoku(startField, solved = false))(_.solveStepByLogic)
    val end = iter dropWhile (!_.solved)
    end.next
  }

  /**
   * 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 (" ")
   * 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): Seq[String] = {
    val source = io.Source.fromFile(name)
    val lines = source.getLines.toList
    source.close
    lines
  }
}

object Position {
  implicit val ordering: Ordering[Position] = new Ordering[Position] {
    def compare(p1: Position, p2: Position) = {
      val comp = p1.x - p2.x
      if (comp == 0) p1.y - p2.y else comp
    }
  }
}
case class Position(x: Int, y: Int)

object Sudoku {
  val possibleValues = (1 to 9).toSet
}
case class Sudoku(field: Map[Position, Int], solved: Boolean) {
  import Sudoku._

  def solveStepByLogic: Sudoku = {
    val currentUnknown = field collect { case (p, i) if i == 0 => p }
    val found = for {
      pos <- currentUnknown.toList
      p <- findPossibility(pos).toList
    } yield pos -> p

    Sudoku(field ++ found, found.isEmpty)
  }

  /**
   * 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 findPossibility(pos: Position): Option[Int] = {
    val columnValues = field.collect { case (p, i) if p.y == pos.y && i != 0 => i }.toSet
    val rowValues = field.collect { case (p, i) if p.x == pos.x && i != 0 => i }.toSet
    val allPoss = possibleValues &~ (columnValues | rowValues | boxValues(pos))

    if (allPoss.size == 1) allPoss.headOption else None
  }

  /**
   * Returns: All values around an index in its given "box". These are then
   * removed from the set of all possibilities in filterPossibilities.
   */
  private def boxValues(pos: Position): Set[Int] = {
    import math.ceil
    val (xb, yb) = (ceil(pos.x / 3.0).toInt, ceil(pos.y / 3.0).toInt)
    val (xub, yub) = (3 * xb, 3 * yb)
    val (xlb, ylb) = (3 * xb - 2, 3 * yb - 2)

    val values = for {
      x <- xlb to xub
      y <- ylb to yub
    } yield field(Position(x, y))

    values.toSet
  }
}