Shortest path for knight to move from source to destination on a chess board

Question: You have a chess board and are given source and destination cells. You need to come up with the shortest path for the knight to travel from the source to the destination.

Answer/Explanation: Given a source cell, a knight can travel to all the remaining cells on the chess board. From a given location, a knight has at most 8 possible steps that it can take - we need to ensure that the knight does not leave the boundaries. If we consider each cell to be a node and a move from one cell to another as an edge, we can be build a graph. However in the interest of this problem, we want to build a tree instead - since there is no point getting back to a cell that was already visited. Since we want the shortest path, we want to exhaust all possibilities at a level in the tree before we go to the next level - sounds familiar? We can use a BST to traverse and check if the destination was reached. We also keep track of the parent cell in the BST so as to be able to build the path at the end.

/// <summary>
/// Class to keep track of the cells in the chess board.
/// </summary>
public class Cell:IComparable<Cell>
{
    public int Row { get; set;}

    public int Column { get; set; }

    public Cell Parent { get; set; }

    public int CompareTo(Cell other)
    {
        var otherCell = (Cell)other;
        return (this.Row == otherCell.Row && this.Column == otherCell.Column) ? 0 : 1;
    }

    public override int GetHashCode()
    {
        var key = Row.ToString() + Column.ToString();
        return key.GetHashCode();
    }

    public override bool Equals(object obj)
    {
        var other = obj as Cell;
        return (other != null) && (other.Row == this.Row) && (other.Column == this.Column);
    }
}

/// <summary>
/// Class that has implementation of the logic to move the knight
/// </summary>
public class MoveKnight
{
    public static void Test()
    {
        var src = new Cell() { Row = 4, Column = 5 };
        var dest = new Cell() { Row = 0, Column = 0 };
        var instance = new MoveKnight();
        var result = instance.Move(src, dest);
    }

    /// <summary>
    /// Method that performs the BST and returns one of the shortest paths
    /// for the knight to move from source to destination
    /// </summary>
    /// <param name="source"></param>
    /// <param name="dest"></param>
    /// <returns></returns>
    public List<Cell> Move(Cell source, Cell dest)
    {
        var dict = new Dictionary<Cell, bool>();
        List<Cell> rtnList = null;
        var queue = new Queue<Cell>();
        queue.Enqueue(source);
        dict.Add(source, true);

        while(queue.Count != 0)
        {
            var cell = queue.Dequeue();
            if (cell.Row == dest.Row && cell.Column == dest.Column)
            {
                rtnList = GetList(cell, dict);
                break;
            }

            var moves = GetMoves(cell, dict);
            AddItemsToQueue(queue, moves, cell);
        }

        return rtnList;
    }

    /// <summary>
    /// Returns the list of cells from the dest to the source by backtracking
    /// </summary>
    /// <param name="dest"></param>
    /// <param name="dict"></param>
    /// <returns></returns>
    private List<Cell> GetList(Cell dest, Dictionary<Cell, bool> dict)
    {
        var rtnList = new List<Cell>();
        var parent = dest.Parent;
        rtnList.Add(dest);
        while (parent != null)
        {
            rtnList.Add(parent);
            parent = parent.Parent;
        }
        return rtnList;
    }

    /// <summary>
    /// Adds cells to the queue for BST, this also keeps track of the parent for back tracking
    /// </summary>
    /// <param name="queue"></param>
    /// <param name="list"></param>
    /// <param name="parent"></param>
    private void AddItemsToQueue(Queue<Cell> queue, List<Cell> list, Cell parent)
    {
        foreach (var cell in list)
        {
            cell.Parent = parent;
            queue.Enqueue(cell);
        }
    }

    /// <summary>
    /// Given a source cell and a dictionary of visited cells, 
    /// returns that list of cells that the knight can move to.
    /// </summary>
    /// <param name="source"></param>
    /// <param name="dict"></param>
    /// <returns></returns>
    private List<Cell> GetMoves(Cell source, Dictionary<Cell, bool> dict)
    {
        var rtnValue = new List<Cell>();
        Cell cell = null;
        // top left
        var row = source.Row - 2;
        var col = source.Column - 1;
        cell = new Cell { Row = row, Column = col };
        if (IsValid(row) && IsValid(col) && !dict.ContainsKey(cell))
        {
            rtnValue.Add(cell);
            dict.Add(cell, true);
        }

        // top right
        row = source.Row - 2;
        col = source.Column + 1;
        cell = new Cell { Row = row, Column = col };
        if (IsValid(row) && IsValid(col) && !dict.ContainsKey(cell))
        {
            rtnValue.Add(cell);
            dict.Add(cell, true);
        }

        // left top
        row = source.Row - 1;
        col = source.Column - 2;
        cell = new Cell { Row = row, Column = col };
        if (IsValid(row) && IsValid(col) && !dict.ContainsKey(cell))
        {
            rtnValue.Add(cell);
            dict.Add(cell, true);
        }

        // left bottom
        row = source.Row + 1;
        col = source.Column - 2;
        cell = new Cell { Row = row, Column = col };
        if (IsValid(row) && IsValid(col) && !dict.ContainsKey(cell))
        {
            rtnValue.Add(cell);
            dict.Add(cell, true);
        }

        // right top
        row = source.Row - 1;
        col = source.Column + 2;
        cell = new Cell { Row = row, Column = col };
        if (IsValid(row) && IsValid(col) && !dict.ContainsKey(cell))
        {
            rtnValue.Add(cell);
            dict.Add(cell, true);
        }

        // right bottom
        row = source.Row + 1;
        col = source.Column + 2;
        cell = new Cell { Row = row, Column = col };
        if (IsValid(row) && IsValid(col) && !dict.ContainsKey(cell))
        {
            rtnValue.Add(cell);
            dict.Add(cell, true);
        }

        // bottom left
        row = source.Row + 2;
        col = source.Column - 1;
        cell = new Cell { Row = row, Column = col };
        if (IsValid(row) && IsValid(col) && !dict.ContainsKey(cell))
        {
            rtnValue.Add(cell);
            dict.Add(cell, true);
        }

        // bottom right
        row = source.Row + 2;
        col = source.Column + 1;
        cell = new Cell { Row = row, Column = col };
        if (IsValid(row) && IsValid(col) && !dict.ContainsKey(cell))
        {
            rtnValue.Add(cell);
            dict.Add(cell, true);
        }
        return rtnValue;
    }

    /// <summary>
    /// Checks whether a given a given index is valid on the chess board
    /// </summary>
    /// <param name="rowCol">Input index</param>
    /// <returns></returns>
    private bool IsValid(int rowCol)
    {
        if (rowCol >= 0 && rowCol <=7)
        {
            return true;
        }

        return false;
    }

}