Minimum number of moves for a knight to hop from a given source square to destination on the chess board

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace ConsoleApplication1
{
    class Point
    {
        public int x, y;
        public Point()
        {
            x = 0;
            y = 0;
        }
        public Point(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            int[,] chessBoard = new int[8, 8];
            string start = "a1";
            string end = "h8";
            Point startPoint = new Point();
            startPoint = GetCoordinate(start);
            Point endPoint = new Point();
            endPoint = GetCoordinate(end);
            int numberOfMoves = 0;
            while (startPoint.x != endPoint.x || startPoint.y != endPoint.y)
            {
                chessBoard[startPoint.x, startPoint.y] = -1;
                Point[] jumpStart = PossibleJumps(startPoint, chessBoard);
                Point[] jumpEnd = PossibleJumps(endPoint, chessBoard);
                if (CheckDestination(jumpStart, endPoint))
                {
                    numberOfMoves++;
                    break;
                }
                else if (CheckCommon(jumpStart, jumpEnd))
                {
                    numberOfMoves += 2;
                    break;
                }
                else
                {
                    int distance = 0, position = 0;
                    for (int i = 0; i < jumpStart.Length; i++)
                    {
                        if (i == 0)
                        {
                            distance = GetDistance(jumpStart[i], endPoint);
                            position = i;
                        }
                        else
                        {
                            if (distance > GetDistance(jumpStart[i], endPoint))
                            {
                                distance = GetDistance(jumpStart[i], endPoint);
                                position = i;
                            }
                        }
                    }
                    startPoint = jumpStart[position];
                    numberOfMoves++;
                }
            }
            Console.WriteLine("Minimum number of moves = " + numberOfMoves);
        }
        public static Point GetCoordinate(string str)
        {
            int x = 0, y = 0;
            switch (str[0])
            {
                case 'a':
                    x = 0;
                    break;
                case 'b':
                    x = 1;
                    break;
                case 'c':
                    x = 2;
                    break;
                case 'd':
                    x = 3;
                    break;
                case 'e':
                    x = 4;
                    break;
                case 'f':
                    x = 5;
                    break;
                case 'g':
                    x = 6;
                    break;
                case 'h':
                    x = 7;
                    break;
            }
            y = int.Parse(str[1].ToString()) - 1;
            Point P = new Point(x, y);
            return P;
        }
        public static int GetDistance(Point P1, Point P2)
        {
            return (Math.Abs(P1.x - P2.x) + Math.Abs(P1.y - P2.y));
        }
        public static Point[] PossibleJumps(Point P, int[,] chessBoard)
        {
            ArrayList xArray = new ArrayList();
            ArrayList yArray = new ArrayList();
            //Point 1
            if (P.x - 1 >= 0 && P.y + 2 <= 7)
            {
                if (chessBoard[P.x - 1, P.y + 2] != -1)
                {
                    xArray.Add((int)(P.x - 1));
                    yArray.Add((int)(P.y + 2));
                }
            }
            //Point 2
            if (P.x + 1 <= 7 && P.y + 2 <= 7)
            {
                if (chessBoard[P.x + 1, P.y + 2] != -1)
                {
                    xArray.Add((int)(P.x + 1));
                    yArray.Add((int)(P.y + 2));
                }
            }
            //Point 3
            if (P.x + 2 <= 7 && P.y + 1 <= 7)
            {
                if (chessBoard[P.x + 2, P.y + 1] != -1)
                {
                    xArray.Add((int)(P.x + 2));
                    yArray.Add((int)(P.y + 1));
                }
            }
            //Point 4
            if (P.x + 2 <= 7 && P.y - 1 >= 0)
            {
                if (chessBoard[P.x + 2, P.y - 1] != -1)
                {
                    xArray.Add((int)(P.x + 2));
                    yArray.Add((int)(P.y - 1));
                }
            }
            //Point 5
            if (P.x + 1 <= 7 && P.y - 2 >= 0)
            {
                if (chessBoard[P.x + 1, P.y - 2] != -1)
                {
                    xArray.Add((int)(P.x + 1));
                    yArray.Add((int)(P.y - 2));
                }
            }
            //Point 6
            if (P.x - 1 >= 0 && P.y - 2 >= 0)
            {
                if (chessBoard[P.x - 1, P.y - 2] != -1)
                {
                    xArray.Add((int)(P.x - 1));
                    yArray.Add((int)(P.y - 2));
                }
            }
            //Point 7
            if (P.x - 2 >= 0 && P.y - 1 >= 0)
            {
                if (chessBoard[P.x - 2, P.y - 1] != -1)
                {
                    xArray.Add((int)(P.x - 2));
                    yArray.Add((int)(P.y - 1));
                }
            }
            //Point 8
            if (P.x - 2 >= 0 && P.y + 1 <= 7)
            {
                if (chessBoard[P.x - 2, P.y + 1] != -1)
                {
                    xArray.Add((int)(P.x - 2));
                    yArray.Add((int)(P.y + 1));
                }
            }
            Point[] pArray = new Point[xArray.Count];
            for (int i = 0; i < pArray.Length; i++)
            {
                pArray[i] = new Point();
                pArray[i].x = (int)xArray[i];
                pArray[i].y = (int)yArray[i];
            }
            return pArray;
        }
        public static bool CheckCommon(Point[] P1, Point[] P2)
        {
            for (int i = 0; i < P1.Length; i++)
            {
                for (int j = 0; j < P2.Length; j++)
                {
                    if (P1[i].x == P2[j].x && P1[i].y == P2[j].y)
                    {
                        return true;
                    }
                }
            }
            return false;
        }
        public static bool CheckDestination(Point[] P1, Point P)
        {
            for (int i = 0; i < P1.Length; i++)
            {
                if (P1[i].x == P.x && P1[i].y == P.y)
                {
                    return true;
                }
            }
            return false;
        }
    }
}

Output
=======
Minimum number of moves = 6
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s