import scala.annotation.tailrec
object CW7c {
type Pos = (Int, Int)    // a position on a chessboard 
type Path = List[Pos]    // a path...a list of positions

def is_legal(dim: Int, path: Path)(x: Pos) : Boolean = {
    if((x._1 >= 0) && (x._2 >= 0) && (x._1 < dim) && (x._2 < dim)){
       !(path.contains(x))
    } else false
 }

def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = {
  val lst = List( (1,2),(2,1),(2,-1),(1,-2), (-1,-2),(-2,-1),(-2,1),(-1,2) )
  val mapping = lst.map(s => ( s._1 + x._1, s._2 + x._2) )   
       for( i <- mapping if ( is_legal(dim,path)(i) )) yield i     
  }

def ordered_moves(dim: Int, path: Path, x: Pos) : List[Pos] = {
legal_moves(dim,path,x).sortBy(legal_moves(dim,path,_).length  )
}

def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] ={
  if(xs.isEmpty)
  None 
  else {
            val b = f(xs.head)
            if (b!=None)
            b
          else
             first(xs.tail,f)
       }
  }

def first_closed_tour_heuristic(dim: Int, path: Path) : Option[Path] = {
  if (dim < 5) None 
    else 
        if(path.length==dim*dim) Some(path)
       else 
      first(ordered_moves(dim,path,path.head),y => first_closed_tour_heuristic(dim, y::path))
  }
  
}


first_closed_tour_heuristic(6, List((3, 3)))