Backtracking Sudoku Solver

object FindPath {

  def main(args: Array[String]) = {
    println(findPath('A, 'H, g))
  }

  type Node = Symbol
  type Graph = List[(Node, List[Node])]
  type Route = List[Node]
  private val g: Graph = List(
    ('A, List('C, 'D, 'E)),
    ('B, List('E, 'J)),
    ('C, List()),
    ('D, List('F, 'J)),
    ('E, List('K)),
    ('F, List('K, 'H)),
    ('H, List()),
    ('J, List('H)),
    ('K, List())
  )

  private def neighbours(n: Node, g: Graph): List[Node] = {
    g.filter(adjList ⇒ adjList._1 == n).head._2
  }

  private def findPathList(nbrs: List[Node],
                           dest: Node,
                           g: Graph): Option[Route] = {
    nbrs match {
      case Nil ⇒ None
      case first :: rest ⇒
        findPath(first, dest, g)
          .orElse(findPathList(rest, dest, g))
    }
  }

  private def findPath(orig: Node, dest: Node, g: Graph): Option[Route] = {
    (orig == dest) match {
      case true ⇒ Some(List(orig))
      case false ⇒
        findPathList(neighbours(orig, g), dest, g)
          .map(route ⇒ orig :: route)
    }
  }
}
    

(define graph '((A (C D E))
                (B (E J))
                (C ())
                (D (F J))
                (E (K))
                (F (K H))
                (H ())
                (J (H))
                (K ())))

;; neighbours: Node Graph --> (listof Node)
;;   requires:  v is a node in g
(define (neighbours v g)
  (cond
    [(empty? g) (error "Node not found")]
    [(symbol=? v (first (first g))) (second (first g))]
    [else (neighbours v (rest g))]))

;; (find-path orig dest g) finds path from orig to dest in g if it exists
;; find-path: Node Node Graph --> (anyof (listof Node) false)
(define (find-path orig dest g)
  (cond [(symbol=? orig dest) (list dest)]
        [else (local [(define nbrs (neighbours orig g))
                      (define ?path (find-path/list nbrs dest g))]
                (cond [(false? ?path) false]
                      [else (cons orig ?path)]))]))


;; (find-path/list nbrs dest g) produces path from
;;     an element of nbrs to dest in g, if one exists
;; find-path/list: (listof Node) Node Graph --> (anyof (listof Node) false)
(define (find-path/list nbrs dest g)
  (cond [(empty? nbrs)  false]
        [else (local [(define ?path (find-path (first nbrs) dest g))]
                (cond [(false? ?path)
                       (find-path/list (rest nbrs) dest g)]
                      [else ?path]))]))

                

type Board = Array[Array[Int]]

val bd: Board = Array(
    Array(0, 6, 0, 3, 0, 7, 8, 0, 0),
    Array(0, 0, 0, 0, 9, 0, 0, 0, 0),
    Array(7, 1, 0, 0, 0, 0, 4, 0, 0),
    Array(0, 5, 0, 8, 0, 9, 2, 0, 4),
    Array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    Array(2, 0, 3, 5, 0, 1, 0, 6, 0),
    Array(0, 0, 9, 0, 0, 0, 0, 8, 1),
    Array(0, 0, 0, 0, 1, 0, 0, 0, 0),
    Array(0, 0, 7, 2, 0, 3, 0, 4, 0)
)

/** Find a "route" from the starting board to a complete board. */
def solve(bd: Board): Option[Board] = {
  firstUnsolved(bd) match {
    case None      ⇒ Some(bd)
    case Some(pos) ⇒ solveList(neighbours(bd))
  }
}

/** Find a "route" from one of a list of incomplete boards to a finished board. */
def solveList(bds: List[Board]): Option[Board] = {
  bds match {
    case Nil          ⇒ None
    case bd :: others ⇒ solve(bd).orElse(solveList(others))
  }
}
                

  /** Is it safe or valid to place an i at bd(row, col)? */
  def safe(bd: Board, row: Int, col: Int, i: Int): Boolean = {

    // Find the upper-left corner of the block in which (row,col) appears
    val startRow = row / 3 * 3
    val startCol = col / 3 * 3

    /**
      * Step through the 0..8 cells in the 3x3 block.  Do some
      * fancy stuff with j to get the row and column offset from
      * the upper-left corner of the block.
      * Return true if it's safe to put and i at bd(row)(col).
      */
    def safeBlock(j: Int): Boolean = {
      val r = j / 3
      val c = j % 3
      // This location is OK and either we've reached the bottom right
      // corner of the block or the rest of the block is safe.
      bd(startRow + r)(startCol + c) != i &&
        (j == 8 || safeBlock(j + 1))
    }

    (bd(row).count(p ⇒ p == i) == 0) &&
      (bd.count(arr ⇒ arr(col) == i) == 0) &&
      safeBlock(0)
  }

  /** Find the first unsolved (0) cell in the board.  None if they're all solved. */
  def firstUnsolved(bd: Board): Option[Pos] = {
    for (r ← 0 until bd.length)
      for (c ← 0 until bd(r).length)
        if (bd(r)(c) == 0)
          return Some(Pos(r, c))

    None
  }

  /**
    * Find the first unsolved position.  Return a list of new
    * boards (the neighbours of bd) with the unsolved position
    * filled with valid candidate integers.
    */
  def neighbours(bd: Board): List[Board] = {
    firstUnsolved(bd) match {
      case None      ⇒ List()
      case Some(pos) ⇒
        (for {
          i ← 1 to 9
          if safe(bd, pos.row, pos.col, i)
        } yield {
          newBoard(bd, pos.row, pos.col, i)
        }).toList
    }
  }