# Little Sudoku solver

I always have enormous difficulty working out 2D grid addresses, so for me it is easier to work with the List functions. All tests pass and I'm looking for feedback on clarity, functional programming concepts, or extra edge cases.

Source:

class Board(values: Int*) {

require(values.length == 81, "Board must contain 81 cells")

def isSolved(): Boolean = {

val rowsSolved: Seq[Boolean] = (0 until 9).map(i => row(i)).map(Board.solvedSeq)
val colsSolved: Seq[Boolean] = (0 until 9).map(i => column(i)).map(Board.solvedSeq)
val squaresSolved: Seq[Boolean] = {
val pairs = for (x <- 0 until 3; y <- 0 until 3) yield (x, y)
pairs.map(p => {
Board.solvedSeq(square(p._1)(p._2).flatten)
})
}

(rowsSolved ++ colsSolved ++ squaresSolved).distinct == Vector(true)

}

def row(i: Int): Seq[Int] = values.slice(i * 9, (i * 9) + 9)

def column(i: Int): Seq[Int] = (0 until 81).drop(i).grouped(9).map(_.head).map(i => values(i)).toSeq

def square(i: Int): Seq[Seq[Seq[Int]]] = {
Seq(
values.drop(0).sliding(3, 9).grouped(3).toSeq,
values.drop(3).sliding(3, 9).grouped(3).toSeq,
values.drop(6).sliding(3, 9).grouped(3).toSeq
)(i)

}

}

object Board {

def solvedSeq(s: Seq[Int]): Boolean = if (s.distinct.sorted == Seq(1,2,3,4,5,6,7,8,9)) true else false

}

Tests:

import org.scalatest.{FlatSpec, Matchers}

class TestSolver extends FlatSpec with Matchers {

"Sudoku board" should "instantiate with a literal" in {
val newBoard = new Board(
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9
)

newBoard.isSolved() should equal (false)
newBoard.row(0) should equal (List(1,2,3,4,5,6,7,8,9))
newBoard.column(0) should equal (List(1,1,1,1,1,1,1,1,1))
newBoard.square(0)(0).flatten should equal (List(1,2,3,1,2,3,1,2,3))
}

it should "fail if instantiated with wrong number of args" in {

intercept[IllegalArgumentException] {
new Board(1)
}

}

it should "always return the correct row" in {

val newBoard = new Board(
1,1,1,1,1,1,1,1,1,
2,2,2,2,2,2,2,2,2,
3,3,3,3,3,3,3,3,3,
4,4,4,4,4,4,4,4,4,
5,5,5,5,5,5,5,5,5,
6,6,6,6,6,6,6,6,6,
7,7,7,7,7,7,7,7,7,
8,8,8,8,8,8,8,8,8,
9,9,9,9,9,9,9,9,9
)

newBoard.row(0) should equal (Seq(1,1,1,1,1,1,1,1,1))
newBoard.row(1) should equal (Seq(2,2,2,2,2,2,2,2,2))
newBoard.row(2) should equal (Seq(3,3,3,3,3,3,3,3,3))
newBoard.row(3) should equal (Seq(4,4,4,4,4,4,4,4,4))
newBoard.row(4) should equal (Seq(5,5,5,5,5,5,5,5,5))
newBoard.row(5) should equal (Seq(6,6,6,6,6,6,6,6,6))
newBoard.row(6) should equal (Seq(7,7,7,7,7,7,7,7,7))
newBoard.row(7) should equal (Seq(8,8,8,8,8,8,8,8,8))
newBoard.row(8) should equal (Seq(9,9,9,9,9,9,9,9,9))

}

it should "always return the correct column" in {

val newBoard = new Board(
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9,
1,2,3,4,5,6,7,8,9
)

newBoard.column(0) should equal (Seq(1,1,1,1,1,1,1,1,1))
newBoard.column(1) should equal (Seq(2,2,2,2,2,2,2,2,2))
newBoard.column(2) should equal (Seq(3,3,3,3,3,3,3,3,3))
newBoard.column(3) should equal (Seq(4,4,4,4,4,4,4,4,4))
newBoard.column(4) should equal (Seq(5,5,5,5,5,5,5,5,5))
newBoard.column(5) should equal (Seq(6,6,6,6,6,6,6,6,6))
newBoard.column(6) should equal (Seq(7,7,7,7,7,7,7,7,7))
newBoard.column(7) should equal (Seq(8,8,8,8,8,8,8,8,8))
newBoard.column(8) should equal (Seq(9,9,9,9,9,9,9,9,9))
}

it should "always return the correct square" in {

val newBoard = new Board(
1,1,1,4,4,4,7,7,7,
1,1,1,4,4,4,7,7,7,
1,1,1,4,4,4,7,7,7,
2,2,2,5,5,5,8,8,8,
2,2,2,5,5,5,8,8,8,
2,2,2,5,5,5,8,8,8,
3,3,3,6,6,6,9,9,9,
3,3,3,6,6,6,9,9,9,
3,3,3,6,6,6,9,9,9
)

newBoard.square(0)(0).flatten should equal (Seq(1,1,1,1,1,1,1,1,1))
newBoard.square(0)(1).flatten should equal (Seq(2,2,2,2,2,2,2,2,2))
newBoard.square(0)(2).flatten should equal (Seq(3,3,3,3,3,3,3,3,3))
newBoard.square(1)(0).flatten should equal (Seq(4,4,4,4,4,4,4,4,4))
newBoard.square(1)(1).flatten should equal (Seq(5,5,5,5,5,5,5,5,5))
newBoard.square(1)(2).flatten should equal (Seq(6,6,6,6,6,6,6,6,6))
newBoard.square(2)(0).flatten should equal (Seq(7,7,7,7,7,7,7,7,7))
newBoard.square(2)(1).flatten should equal (Seq(8,8,8,8,8,8,8,8,8))
newBoard.square(2)(2).flatten should equal (Seq(9,9,9,9,9,9,9,9,9))

}

it should "know if a a 9-length subsequence is solved" in {

Board.solvedSeq(Seq(1,2,3,4,5,6,7,8,9)) should equal (true)
Board.solvedSeq(Seq(9,6,1,5,7,8,4,3,2)) should equal (true)
Board.solvedSeq(Seq(1,1,1,1,1,1,1,1,1)) should equal (false)
Board.solvedSeq(Seq(1)) should equal (false)

}

it should "know if an entire board is solved" in {

val correctBoard = new Board(
9,6,1,5,7,8,4,3,2,
2,7,3,4,1,9,8,6,5,
8,5,4,6,2,3,1,7,9,
3,8,2,7,6,5,9,1,4,
4,1,7,9,3,2,6,5,8,
5,9,6,1,8,4,7,2,3,
7,2,5,8,9,6,3,4,1,
1,4,8,3,5,7,2,9,6,
6,3,9,2,4,1,5,8,7
)

correctBoard.isSolved() should equal (true)

val incorrectBoard = new Board(
1,1,1,4,4,4,7,7,7,
1,1,1,4,4,4,7,7,7,
1,1,1,4,4,4,7,7,7,
2,2,2,5,5,5,8,8,8,
2,2,2,5,5,5,8,8,8,
2,2,2,5,5,5,8,8,8,
3,3,3,6,6,6,9,9,9,
3,3,3,6,6,6,9,9,9,
3,3,3,6,6,6,9,9,9
)

incorrectBoard.isSolved() should equal (false)

}

}

## 1 Answer

I added four new containers to the Board class (xs, col, pairs, sqr) to avoid recomputing them with each call to isSolved().

isSolved() now generates a single Boolean for each check instead of a Seq of them. This is done with the forall method which returns true if all values in the container are true when evaluated by being Board.solvedSeq.

Lastly, the if-else expression in Board.solvedSeq can be replaced with a comparison operator.

class Board(values: Int*) {

require(values.length == 81, "Board must contain 81 cells")

val xs = 0 until 9
val col = 0 until 81
val pairs = IndexedSeq.tabulate(3, 3)((_, _)).flatten
val sqr = (0 to 6 by 3).map(values.drop(_).sliding(3, 9).grouped(3).toSeq)

def isSolved(): Boolean = {

val rowsSolved: Boolean = xs.map(row).forall(Board.solvedSeq)
val colsSolved: Boolean = xs.map(column).forall(Board.solvedSeq)
val squaresSolved: Boolean =
pairs.forall(p =>
Board.solvedSeq(square(p._1)(p._2).flatten)
)

rowsSolved && colsSolved && squaresSolved
}

def row(i: Int): Seq[Int] = values.slice(i * 9, (i * 9) + 9)

def column(i: Int): Seq[Int] = col.drop(i).grouped(9).map(_.head).map(i => values(i)).toSeq

def square(i: Int): Seq[Seq[Seq[Int]]] = sqr(i)
}

object Board {
val compSeq = 1 to 9
def solvedSeq(s: Seq[Int]): Boolean = s.distinct.sorted == compSeq
}