Sudoku Solver

SudokuSolver.scala

import scala.annotation.tailrec

object SudokuSolver {

	type IndexGroup = Seq[Int]

	def main(args: Array[String]): Unit = {

		val undefined = 0
		val domain = (1 to 9).toSet
		val field1 = IndexedSeq(
			8, 0, 0, /***/ 0, 0, 4, /***/ 0, 1, 3,
			0, 5, 0, /***/ 0, 7, 6, /***/ 9, 0, 0,
			7, 0, 9, /***/ 0, 0, 0, /***/ 0, 0, 0,
			/************************************/
			/************************************/
			6, 0, 0, /***/ 0, 0, 0, /***/ 3, 4, 5,
			2, 0, 0, /***/ 0, 0, 0, /***/ 0, 0, 8,
			1, 3, 4, /***/ 0, 0, 0, /***/ 0, 0, 9,
			/************************************/
			/************************************/
			0, 0, 0, /***/ 0, 0, 0, /***/ 2, 0, 4,
			0, 0, 7, /***/ 6, 5, 0, /***/ 0, 9, 0,
			9, 6, 0, /***/ 8, 0, 0, /***/ 0, 0, 7
		)
		val field2 = IndexedSeq(
			0, 0, 0, /***/ 7, 1, 0, /***/ 5, 0, 0,
			7, 0, 2, /***/ 0, 0, 0, /***/ 0, 0, 0,
			0, 0, 0, /***/ 0, 9, 0, /***/ 1, 8, 0,
			/************************************/
			/************************************/
			0, 4, 0, /***/ 0, 0, 6, /***/ 0, 9, 0,
			9, 0, 0, /***/ 0, 0, 0, /***/ 0, 5, 0,
			3, 0, 7, /***/ 0, 0, 4, /***/ 0, 0, 0,
			/************************************/
			/************************************/
			0, 6, 0, /***/ 0, 0, 0, /***/ 0, 0, 2,
			0, 0, 0, /***/ 8, 7, 0, /***/ 0, 0, 0,
			5, 0, 8, /***/ 0, 0, 0, /***/ 0, 0, 3
		)
		val field = IndexedSeq(
			0, 3, 1, /***/ 0, 0, 0, /***/ 0, 0, 4,
			4, 0, 5, /***/ 7, 2, 0, /***/ 6, 1, 0,
			0, 7, 6, /***/ 0, 0, 0, /***/ 0, 0, 5,
			/************************************/
			/************************************/
			0, 5, 0, /***/ 9, 1, 0, /***/ 0, 0, 0,
			0, 0, 0, /***/ 0, 0, 0, /***/ 0, 0, 0,
			0, 0, 0, /***/ 0, 6, 4, /***/ 0, 5, 0,
			/************************************/
			/************************************/
			5, 0, 0, /***/ 0, 0, 0, /***/ 2, 8, 0,
			0, 4, 9, /***/ 0, 8, 2, /***/ 5, 0, 1,
			3, 0, 0, /***/ 0, 0, 0, /***/ 4, 6, 0
		)

		val width = 9
		val squareSize = width / 3

		val rows    =    rowGroups(field, width)
		val columns = columnGroups(field, width)
		val rects   =   rectGroups(field, width, squareSize, squareSize)

		println("Input:")
		printSudoku(width, squareSize, rows, field, undefined)

		val start = System.currentTimeMillis()
		val solution_? = solve(field, domain, undefined, rows ++ columns ++ rects)
		val delta = System.currentTimeMillis() - start
		println(s"The solver took ${delta}ms!")
		solution_? match {
			case Right(solution) =>
				println("Result:")
				printSudoku(width, squareSize, rows, solution, undefined)
			case Left(reason) =>
				println(s"No solution found: $reason")
		}
	}

	def printSudoku[T](width: Int, squareSize: Int, rows: Seq[IndexGroup], sudoku: Seq[T], undef: T): Unit =
		println(rows.map(_.map(sudoku).grouped(squareSize).map(_.mkString(" ").replace(undef.toString, " ")).mkString(" | ")).grouped(squareSize).map(_.mkString("\n")).mkString(s"\n${"―" * (width * 2 + squareSize)}\n"))

	def solve[T](field: IndexedSeq[T], domain: Set[T], undefined: T, groups: Seq[IndexGroup])(implicit ordering: Ordering[T]): Either[String, Seq[T]] = {

		if (field.filter(_ != undefined).exists(!domain.contains(_))) Left("Field contains values which are not in the domain, unsolvable!")
		else {

			val groupLookup = groups.foldLeft(Map.empty[Int, Vector[Int]]) { (lookup, group) =>
				group.foldLeft(lookup) { (lookup, index) =>
					val cur = lookup.getOrElse(index, Vector.empty)

					lookup + (index -> (cur ++ group.filter(_ != index)))
				}.mapValues(_.distinct)
			}

			val initialField = field.map {
				case `undefined` => domain
				case v => Set(v)
			}

			val reducedField = reduceSearchSpace(initialField, groupLookup)
			//			print(reducedField)

			val solution =
				if (reducedField.exists(_.isEmpty)) Left("At least one field as been eliminated during constraint satisfaction.") // the puzzle is not solvable with the given constraints
				else if (reducedField.exists(_.size > 1)) searchSolution(reducedField, groupLookup).toRight("No solution found.") // the the search space has been reduced
				else Right(reducedField) // easy puzzle will be reduced the to solution

			solution.map(_.map(_.head))
		}
	}

	@tailrec
	def reduceSearchSpace[T](field: IndexedSeq[Set[T]], groups: Map[Int, Seq[Int]]): IndexedSeq[Set[T]] = {
		val nextField = field.indices.zip(field).map {
			case (_, cellDomain) if cellDomain.size <= 1 => cellDomain
			case (i, cellDomain) => cellDomain.diff(findConstrains(field, groups(i), i))
		}

		if (field.equals(nextField)) nextField
		else reduceSearchSpace(nextField, groups)
	}

	def findConstrains[T](field: Seq[Set[T]], groups: Seq[Int], i: Int): Set[T] = {
		groups.map(field).filter(_.size == 1).flatten.toSet
	}

	def searchSolution[T](initialField: IndexedSeq[Set[T]], groups: Map[Int, Seq[Int]])(implicit ordering: Ordering[T]): Option[Seq[Set[T]]] = {
		def nextIndex(field: IndexedSeq[Set[T]], from: Int): Int =
			field.indexWhere(_.size > 1, from)

		def search(currentField: IndexedSeq[Set[T]], offset: Int): Option[Seq[Set[T]]] = {
			//			print(currentField)
			val next = nextIndex(currentField, offset)
			if (next == -1) Some(currentField)
			else iterateOptions(currentField, next, currentField(next))
		}

		def isValid(currentField: IndexedSeq[Set[T]], value: T, index: Int, groups: Seq[Int]): Boolean =
			!findConstrains(currentField, groups, index).contains(value)

		@tailrec
		def iterateOptions(field: IndexedSeq[Set[T]], index: Int, options: Set[T]): Option[Seq[Set[T]]] = {
			if (options.nonEmpty) {
				if (isValid(field, options.head, index, groups(index))) {
					search(field.updated(index, Set(options.head)), index) match {
						case None => iterateOptions(field, index, options.tail)
						case r => r
					}
				} else iterateOptions(field, index, options.tail)
			} else None
		}

		search(initialField, 0)
	}

	def print[T](field: Seq[Set[T]])(implicit ordering: Ordering[T]): Unit = {
		val strings = field.map {
			case d if d.size == 1 => d.head.toString
			case d if d.isEmpty => "X"
			case d => s"[${d.toSeq.sorted.mkString(", ")}]"
		}
		val maxLen = strings.map(_.length).max
		strings.map(_.padTo(maxLen, ' ')).grouped(9).foreach {line =>
			println(line.mkString("  "))
		}
	}

	def ceiledDivision(len: Int, width: Int): Int = math.ceil(len / width.toDouble).toInt

	def rowGroups(field: Seq[_], width: Int): Seq[IndexGroup] = {
		(0 until ceiledDivision(field.length, width))
			.map(_ * width)
			.map(base => base until math.min(base + width, field.length))
	}

	def columnGroups(field: Seq[_], width: Int): Seq[IndexGroup] = {
		val height = ceiledDivision(field.length, width)
		(0 until width)
			.map(col => (0 until height).map(row => row * width + col).filter(_ < field.length))
	}

	def rectGroups(field: Seq[_], width: Int, squareWidth: Int, squareHeight: Int): Seq[IndexGroup] = {

		val height = ceiledDivision(field.length, width)
		val gridWidth = ceiledDivision(width, squareWidth)
		val gridHeight = ceiledDivision(height, squareHeight)

		(for {
			outerY <- 0 until gridHeight
			outerX <- 0 until gridWidth
		} yield {
			(for {
				y <- (0 until squareHeight).map(outerY * squareHeight + _) if y < height
				x <- (0 until squareWidth).map(outerX * squareWidth + _) if x < width
			} yield y * width + x).filter(_ < field.length)
		}).filter(_.nonEmpty)
	}

}