SudokuSolver.scala

package core.misc

import scala.util.Random

/**
 * Created by mishael on 5/6/15.
 *
 */
object SudokuSolver {

	type Board = IndexedSeq[IndexedSeq[Option[Int]]]

	val n = 9
	val n2 = math.pow(n, 2).toInt
	val s = Math.sqrt(n).toInt
	val emptyBoard: Board = IndexedSeq.fill(n)(IndexedSeq.fill(n)(None))

	def solve(board: Board, cell: Int = 0, possibleAssignmentFunc: (Int, Int, Board) => Seq[Int] = possibleAssignments): Option[Board] =
		if(cell == n2)
			Some(board)
		else
			indices(cell) match {
				case (r, c) if board(r)(c).nonEmpty => solve(board, cell + 1, possibleAssignmentFunc)
				case (r, c) =>
					def guess(x: Int) = solve(board.updated(r, board(r).updated(c, Some(x))), cell + 1, possibleAssignmentFunc)
					possibleAssignmentFunc(r, c, board).collectFirst(Function.unlift(guess))
			}

	def generate(numEmptyCells: Int, seed: Long = 17): Board = {
		val rand = new Random(seed)
		def randomPossibleAssignments(r: Int, c: Int, board: Board) = rand.shuffle(possibleAssignments(r, c, board))

		val full = solve(emptyBoard, 0, randomPossibleAssignments).get
		rand.shuffle(0 to n2 - 1)
			.take(numEmptyCells).map(indices)
			.foldLeft(full){case (boardAcc, (r, c)) => boardAcc.updated(r, boardAcc(r).updated(c, None))}
	}

	def solutionToString(solution: Option[Board]) = solution match {
		case Some(b) => b.map{_.map(_.get).mkString(" ")}.mkString("\n")
		case _ => "No solution find"
	}

	def boardToString(board: Board) = board.map{_.map(_.map(_.toString).getOrElse("_")).mkString(" ")}.mkString("\n")

	private def possibleAssignments(r: Int, c: Int, board: Board) = {
		val restrictions = for {
			i <- board.indices
			cell <- Seq(board(r)(i), board(i)(c), board(s*(r/s) + i/s)(s*(c/s) + i%s))
			value <- cell
		} yield value

		(1 to n).diff(restrictions)
	}

	private def indices(cell: Int) = (cell%n, cell/n)
}


object SudokuExample extends App {
	import SudokuSolver._

	import scala.collection.{IndexedSeq => $}
	val board = $(                        //0s denote empty cells
		$(1, 0, 0, 0, 0, 7, 0, 9, 0),
		$(0, 3, 0, 0, 2, 0, 0, 0, 8),
		$(0, 0, 9, 6, 0, 0, 5, 0, 0),
		$(0, 0, 5, 3, 0, 0, 9, 0, 0),
		$(0, 1, 0, 0, 8, 0, 0, 0, 2),
		$(6, 0, 0, 0, 0, 4, 0, 0, 0),
		$(3, 0, 0, 0, 0, 0, 0, 1, 0),
		$(0, 4, 0, 0, 0, 0, 0, 0, 7),
		$(0, 0, 7, 0, 0, 0, 3, 0, 0)
	).map(_.map {
		case 0 => None
		case x => Some(x)
	}
		)

	println(solutionToString(solve(board)))

	val sampledBoard = generate(50)
	println(boardToString(sampledBoard))

	println(solutionToString(solve(sampledBoard)))
}