1 

     2 // Part 1 about finding and counting Knight's tours

     3 //==================================================

     4 

     5 object CW7a extends App{

     6 

     7 type Pos = (Int, Int)    // a position on a chessboard 

     8 type Path = List[Pos]    // a path...a list of positions

     9 

    10 //(1a) Complete the function that tests whether the position 

    11 //     is inside the board and not yet element in the path.

    12 

    13 //def is_legal(dim: Int, path: Path)(x: Pos) : Boolean = ...

    14 

    15 def is_legal(dim: Int, path: Path)(x: Pos) : Boolean = {

    16   

    17 // if ((x._1<dim && x._2<dim) && (x._1>0 || x._2>0)) false else !path.contains(x)

    18  

    19   if (x._1 < 0 || x._2 < 0) false 

    20   else if (x._1 < dim && x._2 < dim && !path.contains(x)) true 

    21   else false

    22  

    23   

    24 }

    25 

    26 

    27 

    28 def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = {

    29   

    30   val allPossibleMoves = List((x._1+1, x._2+2), (x._1+2, x._2+1), (x._1+2, x._2-1), (x._1+1, x._2-2), (x._1-1, x._2-2), (x._1-2, x._2-1), (x._1-2, x._2+1), (x._1-1, x._2+2));

    31  

    32   //val finalList = allPossibleMoves.filter((a=>a._1<dim && a._2<dim && x._1 >= 0 && a._2 >= 0));

    33   

    34   val finalList = for(pos<-allPossibleMoves if(is_legal(dim,path)(pos))) yield pos;

    35   

    36   // println("Space in board: " + dim*dim + " for dim: " + dim)

    37    

    38   

    39   finalList.toList;

    40     

    41   

    42 }

    43 

    44 println(legal_moves(8, Nil, (2,2)))

    45 println(legal_moves(8, Nil, (7,7)))

    46 println(legal_moves(8, List((4,1), (1,0)), (2,2)))

    47 println(legal_moves(8, List((6,6)), (7,7)))

    48 println(legal_moves(1, Nil, (0,0)))

    49 println(legal_moves(2, Nil, (0,0)))

    50 println(legal_moves(3, Nil, (0,0)))

    51 

    52 println("=================================================================================")

    53 println("================================Comparision output===============================")

    54 println("=================================================================================")

    55 

    56 println(legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))

    57 println(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))

    58 println(legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))

    59 println(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))

    60 println(legal_moves(1, Nil, (0,0)) == Nil)

    61 println(legal_moves(2, Nil, (0,0)) == Nil)

    62 println(legal_moves(3, Nil, (0,0)) == List((1,2), (2,1)))

    63 

    64 

    65 def count_tours(dim: Int, path: Path) : Int = {

    66      

    67   val allMovesFromCurrentPosition = legal_moves(dim, path, path.head);

    68   

    69   if (path.length == dim*dim) 1 else  {

    70     

    71     if (allMovesFromCurrentPosition.size == 0 ) 0  else {

    72       

    73       allMovesFromCurrentPosition.map( element => count_tours(dim, element::path)).sum

    74       

    75       

    76     }

    77     

    78   }

    79   

    80 }

    81     

    82   

    83 

    84 println ( count_tours(5, List((0,0))) )

    85 

    86 def enum_tours(dim: Int, path: Path) : List[Path] = {

    87   

    88      val allMovesFromCurrentPosition = legal_moves(dim, path, path.head);

    89   

    90   if (path.length == dim*dim) List(path) else  {

    91     

    92   allMovesFromCurrentPosition.map( element => enum_tours(dim, element::path)).flatten ;

    93       

    94       

    95       }

    96     }

    97   println ( enum_tours(6, List((0,2))).size)

    98 }

    99 

   100 

   101 

   102 

   103 

   104  

   105  

   106 //(1b) Complete the function that calculates for a position 

   107 //     all legal onward moves that are not already in the path. 

   108 //     The moves should be ordered in a "clockwise" manner.

   109  

   110 //def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = ...

   111 

   112 

   113 

   114 

   115 //some test cases

   116 //

   117 //assert(legal_moves(8, Nil, (2,2)) == 

   118 //  List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))

   119 //assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))

   120 //assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == 

   121 //  List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))

   122 //assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))

   123 

   124 

   125 //(1c) Complete the two recursive functions below. 

   126 //     They exhaustively search for knight's tours starting from the 

   127 //     given path. The first function counts all possible tours, 

   128 //     and the second collects all tours in a list of paths.

   129 

   130 //def count_tours(dim: Int, path: Path) : Int = ...

   131 

   132 

   133 //def enum_tours(dim: Int, path: Path) : List[Path] = ...