I've been doing some experimentation with Scala lately, mostly by reading the Wampler / Payne Programming Scala in O'Reilly Labs. Learning a language by reading about it is deceptive, so I've been looking for an excuse to write some non-trivial Scala code with which to better exercise and test my knowledge of the language.
After skimming the Daily WTF's Praxis for Automating the Knight's Tour, it seemed like a tractable problem that would be fun to code up in Scala, so I proceeded to do just that. It's a brute-force solution to the problem, and I'm not yet sure how idiomatic my Scala code is, but it does, at least, solve the problem:
class KnightsTour(val dimensions : Pair[int,int], val startPosition : Pair[int,int] ) {
val relativeMoves = List( Pair(2,1), Pair(2,-1), Pair(-2,1), Pair(-2,-1), Pair(1,2), Pair(-1,2), Pair(1,-2), Pair(-1,-2) )
val xPositions = 0 until dimensions._1
val yPositions = 0 until dimensions._2
val tourLength = dimensions._1 * dimensions._2;
var closedTours = 0;
var openTours = 0;
def printPaths() : Unit = {
printChildPaths( List(startPosition) )
println( "There were " + ( openTours + closedTours ) + " tours (" + openTours + " open, " + closedTours + " closed)." );
}
def printChildPaths( path : List[ Pair[int,int] ] ) : Unit = {
val moves = getMoves( path.first );
if( path.size == tourLength ) {
if( moves.contains(startPosition) ) {
closedTours += 1
println( "Found a closed tour: " + path )
} else {
openTours += 1
println( "Found an open tour: " + path )
}
} else {
moves.filter( move => !path.contains(move) ).foreach( move => printChildPaths( move :: path ) )
}
}
def getMoves( position: Pair[int,int] ) : List[Pair[int,int]] = {
relativeMoves.map( move => Pair(position._1 + move._1, position._2 + move._2 ) ).filter( withinDimensions )
}
def withinDimensions( position: Pair[int,int] ) : boolean = {
return xPositions.contains( position._1 ) && yPositions.contains( position._2 )
}
}
val tour = new KnightsTour( Pair(3,4), Pair(0,0) )
tour.printPaths();
All in all, I'm pleased with it, although I'm sure i'll read this again later and wince at my early Scala code. Comments welcome.
