import scala.util._

type Pos = (Int, Int)

def print_board(n: Int)(steps: List[Pos]): Unit = {

  for (i <- 0 until n) {

    for (j <- 0 until n) {

      print(f"${steps.reverse.indexOf((i, j))}%3.0f ")

    }

    println

  } 

}

def add_pair(x: Pos)(y: Pos) = 

  (x._1 + y._1, x._2 + y._2)

def dist(n: Int)(y: Pos) = 

  (n / 2 - y._1).abs + (n / 2 - y._2).abs

def is_legal(n: Int)(x: Pos) = 

  0 <= x._1 && 0 <= x._2 && x._1 < n && x._2 < n

def moves(n: Int)(x: Pos): List[Pos] = {

  List(( 1,  2),( 2,  1),( 2, -1),( 1, -2),

       (-1, -2),(-2, -1),(-2,  1),(-1,  2)).map(add_pair(x)).filter(is_legal(n))

}

def moves_filtered(n: Int)(steps: List[Pos])(x: Pos): List[Pos] = {

  moves(n)(x).filterNot(steps.contains(_))

}

def ordered_moves(n: Int)(steps: List[Pos])(x: Pos): List[Pos] = 

  moves_filtered(n)(steps)(x).sortBy((x: Pos) => (moves_filtered(n)(steps)(x).length, dist(n)(x)))

/*def first[A, B](xs: List[A], f: A => Option[B]): Option[B] = xs match {

  case Nil => None

  case x::xs => {

    val result = f(x)

    if (result.isDefined) result else first(xs, f)

  }

}*/

def first[A, B](xs: List[A], f: A => Option[B]): Option[B] =

  xs.par.flatMap(f(_)).headOption

// non-circle tours, including distance

def tour(n: Int)(steps: List[Pos]): Option[List[Pos]] = {

  if (steps.length ==  n * n) //&& moves(n)(steps.head).contains(steps.last)) 

    Some(steps)

  else first(ordered_moves(n)(steps)(steps.head), (x: Pos) => tour(n)(x::steps))

}

//val n = 8

val n = 6

println(s"number simple tours: n = $n")

println(print_board(n)((tour(n)(List((0, 0)))).get))

//println((for (i <- 0 until n; j <- 0 until n) yield tour(n)(List((i, j)))).flatten.distinct.size) 

/*

def first[A, B](xs: List[A], f: A => Option[B]): Option[B] =

  xs.view.flatMap(f(_)).headOption

*/

/*

*/