1
\$\begingroup\$

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)))
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.