8 Jun 2014

Knight's Shortest Path

Problem Statement:
          Given a Source and Destination , find the minimum number of moves required to move a knight from Source to Destination.


Fig: Movement of Knight from Source to Destination
Download Source Code
Solution: 

To find the minimum moves from Source to Destination, I have used the BFS ( Breadth First Search) technique, once the Destination is reached print the Solution


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**
  * BFS to find the minimum moves to reach the destination
  * @return return number of hops if solution is availale else -1
  */
 public static int path(int[][] board, int startRow, int startCol, int endRow, int endCol) {
  queue = new LinkedList<Coordinate>();
  queue.add(new Coordinate(startRow, startCol));
  queue.add(null);  //this acts a delimiter
  board[startRow][startCol] = 0;
  int hops=0;

  while (!queue.isEmpty()) {
   Coordinate popedItem = queue.poll();

   if (popedItem == null) {
    hops++;
    queue.offer(null);
    //System.out.println("======");
    continue;
   } 
   
    int r = popedItem.row;
    int c = popedItem.col;

    board[r][c] = hops;
    
    //System.out.println(hops + " " + r + " " + c);
    
    if(r==endRow && c==endCol)
    {
     printSol(board);
     return hops;
    }
     

    Coordinate[] points = validCoordinates(board, r, c);

    for (Coordinate o : points) {
     if (o != null)
      queue.add(o);
    }
  }
  return -1;
 }

 private static boolean isValid(int[][] board, int row, int col) {
  if (row >= 0 && row < colLen && col >= 0 && col < rowLen
    && board[row][col] == BLANK)
   return true;
  return false;
 }

 public static Coordinate[] validCoordinates(int[][] board, int row, int col) {
  Coordinate[] points = new Coordinate[8];

  if (isValid(board, row + 2, col + 1))
   points[0] = new Coordinate(row + 2, col + 1);

  if (isValid(board, row + 1, col + 2))
   points[1] = new Coordinate(row + 1, col + 2);

  if (isValid(board, row - 1, col + 2))
   points[2] = new Coordinate(row - 1, col + 2);

  if (isValid(board, row - 2, col + 1))
   points[3] = new Coordinate(row - 2, col + 1);

  if (isValid(board, row - 2, col - 1))
   points[4] = new Coordinate(row - 2, col - 1);

  if (isValid(board, row - 1, col - 2))
   points[5] = new Coordinate(row - 1, col - 2);

  if (isValid(board, row + 1, col - 2))
   points[6] = new Coordinate(row + 1, col - 2);

  if (isValid(board, row + 2, col - 1))
   points[7] = new Coordinate(row + 2, col - 1);

  return points;
 }
 
 private static void printSol(int[][] board) {
  for(int i=0;i<colLen;i++)
  {
   for(int j=0;j<rowLen;j++)
   {
    System.out.print(board[i][j]+ "   ");
   }
   System.out.println();
  }
 }

Please post your suggestions and comments.
Happy Coding !! :)

1 comment: