Objectives: For this assignment, you'll learn how to use Prolog to write recursive programs with lists and backtracking.

Problem: There are three parts to this assignment. They are all related.

Part I) (see the included file "chess.pl")

Consider the problem of chess moves of a Knight on a 5x5 chess board. (For now, we shall simplify our problem to just a 5x5 chess board. The solution is the same when we expand it to a 8x8 chess board.)

Starting at position A (3,3), a Knight can move to any position B. Its rule is that a Knight can move 1 step in the x-direction and 2 steps in the y-direction in one move, or 2-step in the x-direction and 1 step in the y-direction.

The predicate "move1( (X1,Y1), (X2,Y2) )" holds if a Knight can move from the position (X1,Y1) to the position (X2,Y2) in a single move. (See the file "chess.pl" for details.)

Your problem for part (I) is to define a new predicate "path( (X1,Y1), (X2,Y2) , N, P )" which holds if there exists a non-cyclic path P from (X1,Y1) to (X2,Y2) in less than N moves.

Part II) Using your solution to part (I), you are required to define a predicate "shortest( (X1,Y1), (X2,Y2) , P )" which holds if P is a shortest path from position (X1,Y1) to (X2,Y2).

Part III) Finally, you are required to define a predicate "visit ( (X,Y), P, N )" which holds if P is a path starting from (X,Y) from which a Knight can move and that the path ends in exactly N moves.

Attachment:- chess-in-prolog.zip