2
\$\begingroup\$

I'm working through a Sudoku solver problem that I found at UPenn (no it's not my homework ;)). I'm a beginner at Scala, and I'm trying to write good functional code (not that this particular method really demonstrates that...).

A problem that keeps occurring for me involves trying to use Lists but not using vars, as per good Scala practice. In fact, vars are marked down in the assignment.

In the below method that prints a Scala board plus any unsolved values, I maintain a List of unsolved values. However I have to set this List as a var because I need to reassign it for each iteration of my loop. I don't think that using ImmutableList is a better solution.

What's a better approach here? Should I be re-writing this entire method to be tail recursive? I think that could be difficult and the resulting code might not be as readable. Also am I using too many ifs? Should every if be replaced with pattern matching in Scala?

/**
  * Displays a Sudoku board in a clear readable format. For any unsolved cells, possible answers are printed below
  * alongside their x and y coordinates.
  * @param message a string to display before the board is printed
  * @param board the Sudoku board itself
  */
def printBoard(board: Board, message: String = "Printing a board", displayPossibleValues: Boolean = true) = {
  val rowSeparator = "+ - - - + - - - + - - - +"
  var possibleValues = List[(Int, Int, List[Int])]()
  println(message)
  println(rowSeparator)
  for (i <- 0 until rows) {
    if (i == 3 || i == 6) {
      println(rowSeparator)
    }
    print("| ")
    for (j <- 0 until cols) {
      if (j == 3 || j == 6)
        print("| ")
      val currentCell = board(i)(j)
      if (currentCell.length == 1 && currentCell(0) != 0)
        print(currentCell.mkString + " ")
      else {
        print("x ")
        possibleValues = possibleValues :+ new Tuple3(i + 1, j + 1, currentCell)
      }
    }
    print("|")
    println
  }
  println(rowSeparator)
  if (displayPossibleValues) {
    println("Remaining values:")
    println(possibleValues.mkString("\n"))
  }
  println
}

Sample output from this method:

+ - - - + - - - + - - - +
| 2 8 4 | x 9 3 | 1 6 7 |
| 3 6 9 | 4 7 1 | x x 5 |
| 1 5 7 | 8 2 6 | 4 9 3 |
+ - - - + - - - + - - - +
| 5 7 6 | x 4 x | x 3 1 |
| 8 9 2 | 1 3 5 | 6 7 4 |
| 4 1 3 | x 6 x | 9 x x |
+ - - - + - - - + - - - +
| 7 2 x | x 8 9 | x 4 6 |
| 6 4 x | x 1 2 | x x x |
| 9 3 8 | 6 5 4 | 7 1 2 |
+ - - - + - - - + - - - +
Remaining values:
(1,4,List(3, 5, 9))
(2,7,List(2, 8))
(2,8,List(2, 8))
(4,4,List(2, 9))
(4,6,List(8, 9))
(4,7,List(2, 8))
(6,4,List(2, 7))
(6,6,List(7, 8))
(6,8,List(2, 5, 8))
(6,9,List(2, 8))
(7,3,List(1, 5))
(7,4,List(3, 9))
(7,7,List(3, 5))
(8,3,List(5, 8))
(8,4,List(3, 7))
(8,7,List(3, 5, 8))
(8,8,List(5, 8))
(8,9,List(8, 9))
\$\endgroup\$
2
\$\begingroup\$

First some minor points :

  • You create a tuple with new Tuple3(x, y, z), more ideomatic would be (x, y, z).
  • You were having troubles with using a var and immutable.List, it is perfectly ok to use mutable.ListBuffer inside your function. You just need to turn it into a List before returning, but since you are just printing out possibleValues I would just use ListBuffer.

Then my major point: I would split up printBoard in multiple functions :

  • reprBoard : a function which returns a textual representation (a String) of a Board.
  • possibleValuesOpenCells : a function which returns all the possible values of the empty cells of a Board.

You could then use these two functions in printBoard to print out the Board and the possible numbers for every open cell.

Below you find a possible implementation of reprBoard which is a little more functional (I have simplified Board to a matrix of numbers, but it should be simple to adjust this code to use your actual Board) :

// an open cell = 0
type Board = Vector[Vector[Int]]

def reprBoard(board: Board): String = {
  // I have made it independent of the size of the board
  // so you could pass a 9x9, a 4x4, ... sudoku board
  val rowLength = board.headOption.map(_.size).getOrElse(0)
  val size = Math.sqrt(rowLength.toDouble).toInt
  val rowSeparator = 
    intersperse(size, "+ ", Vector.fill(size * size)("- ")).mkString.trim
  val colSeparator = "| "

  // it depends of the implementation of Board if you can map over the rows 
  // and columns, but you should be able to do something similar
  val rows = board.map { row =>
    val cells = row.map ( cell =>
      if (cell != 0) s"$cell " else "x "
    )
    intersperse(size, colSeparator, cells).mkString.trim
  }
  intersperse(size, rowSeparator, rows).mkString("\n")
}

// a help function which adds an extra element every `n` elements and at
// the start and the end
// eg. intersperse(1, 0, Vector(1, 2))  ->  Vector(0, 1, 0, 2, 0)
def intersperse[A](n: Int, value: A, vector: Vector[A]) = 
  vector.grouped(n).foldLeft(Vector.empty[A])((acc, elem) => 
    acc ++ Vector(value) ++ elem
  ) ++ Vector(value)

Which you could use as :

import scala.util.Random

// generate a random row with two open cells for testing
def randomRow = 
  Random.shuffle(Random.shuffle(Vector.range(1, 10)).drop(2) ++ Vector(0, 0))

val board = Vector.fill(9)(randomRow)

reprBoard(board)
// + - - - + - - - + - - - +
// | 6 3 9 | x 8 1 | 5 7 x |
// | x 6 7 | x 2 5 | 4 8 3 |
// | 3 9 8 | x 2 7 | x 6 1 |
// + - - - + - - - + - - - +
// | 9 1 5 | 2 3 7 | 8 x x |
// | x 1 3 | x 7 8 | 2 6 5 |
// | 8 1 4 | 9 5 7 | x 6 x |
// + - - - + - - - + - - - +
// | 3 7 4 | x 6 1 | x 2 9 |
// | 4 6 3 | 7 x 8 | 2 5 x |
// | 7 2 5 | 8 9 4 | x x 6 |
// + - - - + - - - + - - - +

In possibleValuesOpenCells you could :

  • use your nested for loop if the cells themselves don't have their coordinates
  • or use a nested map like I did in reprBoard (when you don't need the i and j to create the tuple, you could also look if zipWithIndex can solve this)

printBoard then could look like :

def printBoard(board: Board, message: String = "Printing a board", 
               displayPossibleValues: Boolean = true) = {
  println(message)
  println(reprBoard(board))
  println("Remaining values:")
  possibleValuesOpenCells(board).foreach(println)
}

You need to loop the board twice this way, but I think this is a (very) minor price to pay in comparision with the improved clarity.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.