# Minimum steps to reach target by a Knight In Scala

Given a chessboard of N size (square matrix), the position of Knight and position of a target, find out minimum steps (both count and exact steps) from start to target for a Knight.

If it is not possible to reach to the given position, return -1 as step count.

Here is my implementation in Scala (assuming N = 4 or 4X4 chess board):

import scala.collection.mutable._

object KnightMoves extends App {
case class Pos(row: Int, col: Int)
val Size = 4

def calculateMoves(from: Pos, target: Pos ): (Int, Seq[Pos])= {
val pendingPos = collection.mutable.Queue[Pos](from)
val positionVisited = collection.mutable.HashMap[Pos, (Int, Seq[Pos])](from -> (0, Seq()))
var targetReached = false

while(pendingPos.nonEmpty && !targetReached) {
val p = pendingPos.dequeue()
possibleMoves(p) foreach { position =>
if ( position == target) {
targetReached = true
} else if (!(positionVisited contains position)) {
pendingPos enqueue position
}
positionVisited += position -> ((positionVisited(p)._1 + 1,(positionVisited(p)._2 ++ Seq(p))))
}
}
if (targetReached) positionVisited(target) else (-1, Seq())
}

def isValidPos(position: Pos): Boolean =
((0 until Size) contains position.row) && ((0 until Size) contains position.col)

def possibleMoves(position: Pos): List[Pos] =
List(Pos(position.row - 2, position.col + 1),
Pos(position.row - 2, position.col - 1),
Pos(position.row + 2, position.col + 1),
Pos(position.row + 2, position.col - 1),
Pos(position.row - 1  , position.col + 2),
Pos(position.row - 1  , position.col - 2),
Pos(position.row + 1  , position.col + 2),
Pos(position.row + 1  , position.col - 2)
) filter( pos => isValidPos(pos))

println(calculateMoves(Pos(0,1),Pos(0,0)))
println(calculateMoves(Pos(0,1),Pos(0,2)))
}


This program generates the following output for two test statements at bottom.

(3,ArrayBuffer(Pos(0,1), Pos(2,0), Pos(1,2)))
(3,ArrayBuffer(Pos(0,1), Pos(2,2), Pos(1,0)))


## 1 Answer

At first glance, the isValidPos() method looks to be clear and succinct, requiring only two tests to see if the passed position is on the board.

def isValidPos(position: Pos): Boolean =
((0 until Size) contains position.row) && ((0 until Size) contains position.col)


But it turns out that the contains() method on a Range is a bit complicated and most valid positions will have to pass around 10 if checks before the method returns true, so there are probably more efficient ways to get the same result.

But a bigger question is, can this be done without any mutable collections or variables?

One approach is to create a Knight class that holds all current valid board positions and the history of how each position was arrived at and then, when taking the next step, instead of modifying the Knight instance you create a new immutable Knight instance with all the new information built from the current (old) data.

type Cell = (Int,Int)

class Knight(dim :Int, history :Map[Cell,Cell], val cells :Set[Cell]) {
def this(dim :Int, cell :Cell) = this(dim, Map(cell->(-1,-1)), Set(cell))

def backtrack(cell :Cell) :List[Cell] =
if (history(cell) == (-1,-1)) cell :: Nil
else                          cell :: backtrack(history(cell))

def next :Knight = (new Knight(dim, _:Map[Cell,Cell], _:Set[Cell])).tupled{
cells.foldLeft((history, Set.empty[Cell])){
case ((hMap,cSet),(x,y)) =>
val newSet = Set((x-2, y-1), (x-2, y+1), (x-1, y-2), (x-1, y+2)
,(x+1, y-2), (x+1, y+2), (x+2, y-1), (x+2, y+1)
).filter{ case (a,b) =>
a >= 0 && a < dim && b >= 0 && b < dim && !hMap.keySet((a,b))
}
(hMap ++ newSet.map(_ -> (x,y)).toMap, cSet ++ newSet)
}
}
}

def knightMoves(boardSize :Int, knight :Cell, target :Cell) :List[Cell] = {
def loop(k1 :Knight, k2 :Knight) :List[Cell] = {
val met :Set[Cell] = k1.cells.intersect(k2.cells)
if (met.nonEmpty) k1.backtrack(met.head).reverse ++
k2.backtrack(met.head).tail
else if (k1.cells.isEmpty || k2.cells.isEmpty) Nil
else if (k1.cells.size > k2.cells.size) loop(k1, k2.next)
else                                    loop(k1.next, k2)
}
loop(new Knight(boardSize, knight), new Knight(boardSize, target))
}

knightMoves(3,(0,1),(1,1))    //res0: List[Cell] = List()
knightMoves(14,(0,1),(10,12)) //res1: List[Cell] = List((0,1), (2,2), (4,3), (6,4), (7,6), (8,8), (9,10), (10,12))


Some efficiency is obtained here by making the target position a Knight instance as well. That way they can "move" toward each other and, as soon as they intersect, a path from one to the other is found.