Sudoku Solver

Sudoku.scala

object Solver extends App{
  
  case class Puzzle (values: Vector[Vector[Option[Int]]]) {
    def printState {
      for (row <- values) {
        println((for (cell <- row) yield {
          cell match {
            case None => "_"
            case Some(i) => i
          }
        }).mkString("|")) 
      }
    }
  }
  
  def getPuzzle(): Puzzle = {
    val puzStr = """???45???2
      |57??8??6?
      |???????3?
      |????????6
      |?64?7?1??
      |????43???
      |??8??????
      |64??39???
      |??2??7?85""".stripMargin('|')
    
     Puzzle((for (l<-puzStr.lines) yield {
       (for (c <- l) yield {
         c match {
           case '?' => None
           case i => Some(i.asDigit)
         }
       }).toVector
     }).toVector)
  }
  
  // Take each None, check what it could possibly be, 
  //   and if only one solution, replace it with a Some
  def stepOnlyChoice(state: Puzzle): Puzzle = {
    var x = -1
    Puzzle((for (line <- state.values) yield {
      x += 1
      var y = -1
      (for (v <- line) yield {
        y += 1
        v match {
          case Some(_) => v //Don't care, already solved 
          case None => solveOnlyChoice(x, y, state)
        }
      }).toVector
      
    }).toVector)
  }
  
  def getCellOptions(x: Int, y: Int, state: Puzzle): Set[Int] = {
    val possible = (1 to 9).toSet
    // Get everything in X row
    val xRow = state.values(x).collect{case Some(c) => c}.toSet
    // Get everything in Y col
    val yCol = (for (r <- state.values) yield r(y)).collect{case Some(c) => c}.toSet 
    // Get everything in 3x3 square
    val xGrid = ((x / 3) * 3) + 1
    val yGrid = ((y / 3) * 3) + 1
    
    val grid = (for (gx <- (xGrid -1 to xGrid +1); gy<- (yGrid -1 to yGrid +1)) yield {
      state.values(gx)(gy)
    }).collect{case Some(c) => c}.toSet
    possible diff (xRow ++ yCol ++ grid)
  }
  
  def solveOnlyChoice(x: Int, y: Int, state: Puzzle): Option[Int] = {
    val left = getCellOptions(x, y, state)
    if (left.size == 1) Some(left.head)
    else None
  }

  def getAllOptions(state:Puzzle): Vector[Vector[Set[Int]]] = {
    var x = -1
    (for (line <- state.values) yield {
      x += 1
      var y = -1
      (for (v <- line) yield {
        y += 1
        v match {
          case Some(v) => Set(v) 
          case None => getCellOptions(x, y, state)
        }
      }).toVector
      
    }).toVector
  }
  
  def stepOnlyCell(state: Puzzle): Puzzle = {
    val allOptions = getAllOptions(state)
    
    // Add up all the sets for cells that relate to a given cell, 
    // then remove that superset from the cell itself - answer 
    // should be empty set or an answer
    var x = -1
    Puzzle((for (line <- state.values) yield {
      x += 1
      var y = -1
      (for (v <- line) yield {
        y += 1
        v match {
          case Some(_) => v //Don't care, already solved 
          case None => solveOnlyCell(x, y, allOptions)
        }
      }).toVector
    }).toVector)
  }
  
  
  def solveOnlyCell(x: Int, y: Int, opts: Vector[Vector[Set[Int]]]): Option[Int] = {
    val possible = opts(x)(y)
    val dx = (0 to 8).filterNot(_ == x)
    val dy = (0 to 8).filterNot(_ == y)
    // Get everything in X row
    val xRow = (for (ny <- dy) yield opts(x)(ny))  
      .foldLeft(Set[Int]())((acc, x) => acc ++ x)
    // Get everything in Y col except self
      
    val yCol = (for (r <- (for (nx <- dx) yield opts(nx))) yield r(y))
      .foldLeft(Set[Int]())((acc, x) => acc ++ x) 

    // Get everything in 3x3 square except self...
    val xGrid = ((x / 3) * 3) + 1
    val yGrid = ((y / 3) * 3) + 1

    val grid = (for (
        gx <- (xGrid -1 to xGrid +1);
        gy<- (yGrid -1 to yGrid +1);
        if ((gx != x) || (gy != y))) yield {
      opts(gx)(gy)
    }).foldLeft(Set[Int]())((acc, x) => acc ++ x) 
    
    // OK, do I have one option remaining for the 3x3, row, or col?
    val setGrid = possible diff grid 
    val setRow = possible diff xRow 
    val setCol = possible diff yCol
      
    if (setGrid.size == 1) Some(setGrid.head)
    else if (setRow.size == 1) Some(setRow.head)
    else if (setCol.size == 1) Some(setCol.head)
    else None    
  }
  
  def run(state: Puzzle): Puzzle = {
    val newState = stepOnlyCell(stepOnlyChoice(state)) 
    
    // Are we as done as we can be? (NB. can't just check 
    //   for absence of None, as it might be unsolvable)
    if (newState == state) state
    else run(newState)
  }
  
  run(getPuzzle).printState
}