info@meritcampus.com    +91-85006-22255
...

In chess, assuming that the columns are numbered A to H and the rows are numbered 1 to 8. Write a program to find the path of a horse from one position to another position. The path returned should be the shortest (minimum number of steps). Assume that there is nothing else on the chess board.

Input (ChessPosition, ChessPosition) Output List (ChessPosition)
C2, B3 [C2, A1, B3]
G1, H1 [G1, E2, G3, H1]
B7, A8 [B7, A5, C4, B6, A8]
A1, H8 [A1, B3, A5, C4, B6, A8]
G1, H1 [G1, E2, G3, H1]
B7, A8 [B7, A5, C4, B6, A8]
G2, B8 [G2, E1, C2, B4, A6, B8]

class GetHorsePath

{    public static void main(String s[])
{
ChessPosition start = new ChessPosition('A', 2);
ChessPosition end = new ChessPosition('B', 6);
System.out.println("Horse path from A2 to B6 is : " + getHorsePath(start, end));

}

public static List<ChessPosition> getHorsePath(ChessPosition start, ChessPosition end) {
//Write a code here to identify the positions which the horse has to take to move from start to end
}

//If required write any additional methods here
}
class ChessPosition {

char column;
int row;

public ChessPosition(char column, int row) {
this.column = column;
this.row = row;
}

@Override
public String toString() {
return column + "" + row;
}

@Override
public boolean equals(Object obj) {
return ((ChessPosition) obj).column == column && ((ChessPosition) obj).row == row;
}