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
*/

/*

*/