// Sudoku

//========

// call parallel version with

//

// scala -cp scala-parallel-collections_2.13-0.2.0.jar sudoku_test.scala 

//

// or

//

// scalac -cp scala-parallel-collections_2.13-0.2.0.jar sudoku_test.scala

// java -cp .:scala-library-2.13.0.jar:scala-parallel-collections_2.13-0.2.0.jar Sudoku

object Sudoku extends App { 

import scala.collection.parallel.CollectionConverters._

type Pos = (Int, Int)

val emptyValue = '.'

val maxValue = 9

val allValues = "123456789".toList

val indexes = (0 to 8).toList

def empty(game: String) = game.indexOf(emptyValue)

def isDone(game: String) = empty(game) == -1 

def emptyPosition(game: String) = {

  val e = empty(game)

  (e % maxValue, e / maxValue)

}

def get_row(game: String, y: Int) = indexes.map(col => game(y * maxValue + col))

def get_col(game: String, x: Int) = indexes.map(row => game(x + row * maxValue))

def get_box(game: String, pos: Pos): List[Char] = {

    def base(p: Int): Int = (p / 3) * 3

    val x0 = base(pos._1)

    val y0 = base(pos._2)

    for (x <- (x0 until x0 + 3).toList;

         y <- (y0 until y0 + 3).toList) yield game(x + y * maxValue)

}         

def update(game: String, pos: Int, value: Char): String = 

  game.updated(pos, value)

def toAvoid(game: String, pos: Pos): List[Char] = 

  (get_col(game, pos._1) ++ get_row(game, pos._2) ++ get_box(game, pos))

def candidates(game: String, pos: Pos): List[Char] = 

  allValues.diff(toAvoid(game, pos))

def search(game: String): List[String] = {

  if (isDone(game)) List(game)

  else {

    val cs = candidates(game, emptyPosition(game))

    cs.par.map(c => search(update(game, empty(game), c))).toList.flatten

  }

}

def pretty(game: String): String = 

  "\n" + (game.grouped(maxValue).mkString(",\n"))

val game2 = """8........

              |..36.....

              |.7..9.2..

              |.5...7...

              |....457..

              |...1...3.

              |..1....68

              |..85...1.

              |.9....4..""".stripMargin.replaceAll("\\n", "")

// for measuring time

def time_needed[T](i: Int, code: => T) = {

  val start = System.nanoTime()

  for (j <- 1 to i) code

  val end = System.nanoTime()

  s"${(end - start) / 1.0e9} secs"

}

println(time_needed(10, search(game2)))

}