Scala Style: Valid Sudoku & Breakable Post 7

vikrant
vikrant
Mar 30 · 5 min read

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:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Following is a valid Sudoku

Image for post
Image for post

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.

Image for post
Image for post

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).toList

At 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.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store