Sudoku Solver Made Simple Using Scala List

sudoku.scala

// Sudoku Solver

object SudokuSolver {

  type Board = Array[Array[Char]]
  type Chars = Array[Char]
  case class Position(i: Int, j: Int, char: Char = '.')
  type Positions = List[Position]

  def printBoard(board: Board):Unit = {

    def printRow(row: Chars, sb: StringBuffer): Unit = {
      var prefix = ""
      for (e <- row) {
        sb.append(prefix)
        sb.append(e)
        prefix = ","
      }
    }

    val sb:StringBuffer = new StringBuffer()

    for (row <- board) {
      printRow(row, sb)
      sb.append('\n')
    }

    println(sb.toString)
  }

  val elementSet = Set('1','2','3','4','5','6','7','8','9')

  def filledWrong(move: Position, positions: Positions): Boolean = {
      println("xs", move.j, move.i/3 )
      positions.exists(x => (move.char == x.char) && (move.i == x.i || move.j == x.j || (move.i/3 == x.i/3 && move.j/3 == x.j/3)))
  }

  def makeMove(filledPositions: Positions, emptyPosition: Positions): Seq[(List[Position], List[Position])] = {
      val element = emptyPosition.head
      val possibleMoves = elementSet.toList.map(c => ( element.copy(char = c) , filledPositions, emptyPosition.tail))
      possibleMoves.filterNot{ case(ele, filled, _) => filledWrong(ele, filled)}.map { case(ele,filled, empty) => (ele :: filled, empty)}
  }

  def mySolver(seq: List[(Positions, Positions)]): Option[Positions] = {

      val existSolution = seq.filter(x => x._1.size == 81 && x._2.size == 0 ).headOption

      if (existSolution.isDefined){
        existSolution.map(_._1)
      } else {
        println("Search Space is ", seq.size)
        mySolver(seq.flatMap(x => makeMove(x._1, x._2)))
      }
  }

  def solve(b: Board): Board = {

    val positions: Positions = {
        for {
          i <- 0 to 8
          j <- 0 to 8
        } yield Position(i, j, b(i)(j))
      }.toList

    val emptyPosition: Positions = positions.filter(_.char == '.')
    val filledPositions: Positions = positions.filter(_.char != '.')
    val start = (filledPositions,emptyPosition)

    print("Filled and empty positions are", filledPositions.length, emptyPosition.length)
    val solution: Option[Positions] =mySolver(List(start))

    val res: Board = Array.ofDim[Char](9,9)

    if (solution.headOption.isDefined) {
       solution.head.foreach(x => {
         res(x.i)(x.j) = x.char
       })
      printBoard(res)
    }

    res
  }

  def main(args: Array[String]): Unit = {
    
    val input: Board = Array(
    Array('5','3','.','.','7','.','.','.','.'),
    Array('6','.','.','1','9','5','.','.','.'),
    Array('.','9','8','.','.','.','.','6','.'),
    Array('8','.','.','.','6','.','.','.','3'),
    Array('4','.','.','8','.','3','.','.','1'),
    Array('7','.','.','.','2','.','.','.','6'),
    Array('.','6','.','.','.','.','2','8','.'),
    Array('.','.','.','4','1','9','.','.','5'),
    Array('.','.','.','.','8','.','.','7','9'))


    val output = Array(
     Array('5','3','4','6','7','8','9','1','2'),
    Array('6','7','2','1','9','5','3','4','8'),
    Array('1','9','8','3','4','2','5','6','7'),
    Array('8','5','9','7','6','1','4','2','3'),
    Array('4','2','6','8','5','3','7','9','1'),
    Array('7','1','3','9','2','4','8','5','6'),
    Array('9','6','1','5','3','7','2','8','4'),
    Array('2','8','7','4','1','9','6','3','5'),
    Array('3','4','5','2','8','6','1','7','9')
    )

    printBoard(input)
    val res = solve(input)

    val ele:List[Char] =  res.toList.flatMap(_.toList)

    assert( output.toList.flatMap(_.toList) sameElements  res.toList.flatMap(_.toList), "Solver Does not works for Sudoku.")
  }
}

A simple bfs expansion of solution space using lists.