Basic (Logical Only) Sudoku Solver

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

//Impera

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

StackExchange Code Review Q#24461, answer score: 10