Scala Style: Valid Sudoku & Breakable Post 7
This is 7th post in the series I am writing to explain how I try to write good scala code. Scala let you ride beautiful code with very less scope for error. In this post I will also touch on how to use breakable in Scala.
Personally I try to avoid usingbreakin Scala. It makes me think harder and write better programs. But I am a Scala learner too and yet not able to reach to level where I can write best possible code without using break.
Still to me sometime using break is wise. But till now I never used it in production code. It is mostly for programming challenges (or interview questions).
Also I will use a var for this solution, I am still trying to findout how I can get rid of it. But probably this is one of the situation where having a var is good.
Today we will go through on such question.
Problem
(following description and image is shamelessly stolen from leetcode)
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits
1-9without repetition. - Each column must contain the digits
1-9without repetition. - Each of the 9
3x3sub-boxes of the grid must contain the digits1-9without repetition.
Following is a valid Sudoku
Solution
Simple algorithm is — Visit each element, check if there is a duplicate of it in its row, column and subBox (i.e. 3x3 matrix). if you find one such element then you can say that its invalid , else it is a valid.
There are some optimizations you can do to this solution by remembering already validated row but storing them in secondary DS, I am not coding for them. I just want to talk about Scala Style not about some interview preparation.
Back to solution.
We can define following to start working on solution.A Sudoku can represented as a 2 dimensional array
val input = Array(Array('8','3','.','.','7','.','.','.','.'),
Array('6','.','.','1','9','5','.','.','.'),
Array('8','.','.','.','6','.','.','.','3'),
Array('4','.','.','8','.','3','.','.','1'),
Array('.','9','8','.','.','.','.','6','.'),
Array('7','.','.','.','2','.','.','.','6'),
Array('.','6','.','.','.','.','2','8','.'),
Array('.','.','.','4','1','9','.','.','5'),
Array('.','.','.','.','8','.','.','7','9'))Here . is empty cell and allowed chars are Seq(‘1’,’2',’3',’4',’5',’6',’7',’8',’9').
Finally method we will write is of following structure
def isValidSudoku(board: Array[Array[Char]]): Boolean = {var valid = true
0 until 9 foreach { row =>
0 until 9 foreach { col =>
// logic - here }
}
valid
Essentially for each element we have has three pieces now
- Validate row for duplicate
- Validate Column for duplicate
- Valid Subbox for duplicate
If you read my last post about matrix in scala you will know getting row and column as list is easy. What to do for Subbox? We need to find some property for them. See this diagram, it shows index of first element of each.
For each element if can find what is the starting position of its box, we can solve this problem.
After some trial and error, I came to this formula . If (row,col) is pos in matrix, its subbox starts at (3 * (row / 3), 3* (col / 3) ). Try it.
With above logic, given pos of element, getting all elements of its subbox (as list) is
def getSubBoxes(row: Int, col: Int):List[Char] =
(0 until 3).toList.flatMap { r =>
(0 until 3).toList.map { c =>
board(row + r)(col + c)
}
}Getting element of a column is -
board.toList.map(_ (col))and finally row
board(row).toListAt this point we have all three lists. List of elements in row, col and subbox. now we just need to check if each of them has only unique element (except . which is empty cell). A small function for that
def validCollection(cells: List[Char]):Boolean = {
val filledCells = cells.filter(_ != '.')
filledCells.isEmpty ||
(filledCells.distinct.size == filledCells.size && filledCells.forall(AllowedChars.contains(_)))}
Finally putting it all together
def validCollection(cells: List[Char]):Boolean = {
val filledCells = cells.filter(_ != '.')
filledCells.isEmpty || (filledCells.distinct.size == filledCells.size && filledCells.forall(AllowedChars.contains(_)))
}
def isValidSudoku(board: Array[Array[Char]]): Boolean = {
def getSubBoxes(row: Int, col: Int):List[Char] = {
(0 until 3).toList.flatMap { r =>
(0 until 3).toList.map { c =>
board(row + r)(col + c)
}
}
} var valid = true
0 until 9 foreach { row =>
0 until 9 foreach { col =>
valid = List(board(row).toList, board.toList.map(_ (col)), getSubBoxes(row/3, col/3)).foldLeft(valid) {
case (valid, collection) => if (valid) {
if (validCollection(collection)) true else false
} else valid
}
}
}
valid
}
Make it faster
This is good and it works, but this solution has a drawback. Even if first element itself fails the check.. it validates all remaining one. Input like following
Array(Array('8','3','.','.','7','.','.','.','.'),
Array('6','.','.','1','9','5','.','.','.'),
Array('8','.','.','.','6','.','.','.','3'),
Array('4','.','.','8','.','3','.','.','1'),
Array('.','9','8','.','.','.','.','6','.'),
Array('7','.','.','.','2','.','.','.','6'),
Array('.','6','.','.','.','.','2','8','.'),
Array('.','.','.','4','1','9','.','.','5'),
Array('.','.','.','.','8','.','.','7','9'))Thats because of foldLeft . I tried hard to fix it, but could not come up with some thing which is better than using break. We add a break on first invalid match. Following is same function with `break`.
def isValidSudokuBreak(board: Array[Array[Char]]): Boolean = {
import util.control.Breaks._
def getSubBoxes(row: Int, col: Int):List[Char] = {
val l = (0 until 3).toList.flatMap { r =>
(0 until 3).toList.map { c =>
board(row + r)(col + c)
}
}
l
}
var res = true;
breakable {
0 until 9 foreach { row =>
0 until 9 foreach { col =>
List(board(row).toList, board.toList.map(_ (col)), getSubBoxes(3 * (row / 3), 3* (col / 3))).foldLeft(true) {
case (valid, collection) => if (!valid) { res = false; break} else {
if (validCollection(collection)) true else false
}
}
}
}
}
res
}This version is 10 times more faster. Off-course its not true scala style anymore. I am sure someone with more scala skills can do it better. I am looking for them. Till then this is the version which I recommend to people.
