in java only , and please make sure code is running

The game of chess is played on an 88 grid of squares. A knight can move either two squares horizontally and one square vertically, or one square horizontally and two squares vertically: For the purposes of simplicity, we will label the rows and columns 18, so that the bottom left square is ( 1 , 1) and the top right is (8,8). Then the picture above shows that at square (4,4), the knight can move to squares (2,3),(3,2),(5,2),(6,3),(6,5),(5,6),(3,6), and (2,5). In this project, we will suppose that the chessboard is completely empty except for a single knight which is placed by the user. Project You are to write a Java program which asks the user to input in a starting position (a starting row and a starting column) and an ending position (a destination row and a destination column), and output a sequence of positions that the knight can visit to get from the starting to the ending position. You should then output the length of the path (the number of moves it takes). For this project, you are only allowed to use the basic programming structures that we learned about in class so far: - Variables (orimitive tvoes, Strines) You are to write a Java program which asks the user to input in a starting position (a starting row and a starting column) and an ending position (a destination row and a destination column), and output a sequence of positions that the knight can visit to get from the starting to the ending position. You should then output the length of the path (the number of moves it takes). For this project, you are only allowed to use the basic programming structures that we learned about in class so far: - Variables (primitive types, Strings) - Scanner class for input - If statements - Loops - Arrays - Methods (we are learning about these this week) In particular, you are not allowed to use any higher-order abstractions on this project! Examples Here are some examples of output: Example 1: Enter in a starting row: 2 Enter in a starting column: 1 Enter in a destination row: 2 Enter in a destination coluan: 2 Steps: (2,1) (4,2) (3,4) (2,2) 3 moves. Example 2: Enter in a starting row: 1 Enter in a starting column: 1 Enter in a destination row: 8 Enter in a destination column: 8 Steps: (1,1) (2,3) (3,5) (4,7) (6,8) (7,6) (8,8) 6 moves. Your goal is to always find the optimum path: that is, the shortest path between the two positions that is valid. Note that you can never travel out of bounds: the row and column must each be between 1 and 8 . If you are unable to find an optimum path, at least find any valid path (there is always a path from one square to another on an empty chessboard). In fact, there is always a path from one square to another in at most 6 moves: you will get some credit (in between "valid" and "optimum") for paths that are shorter than 10 moves. Your program should never crash. That includes when the user types in invalid positions (like row 9 or 1, or a non-integer string): in those cases, the program should output an error message and exit the program