Program Implementation Description: The files included are lisp programs written to solve the Missionaries-Cannibals problem (MC) as well as the 8-puzzle problem (EightPuzzle). Solutions to both programs are found using A* search. The programs were successfully tested on Windows 10 and Ubuntu 16.04. To run the programs Clisp needs to be installed on your machine. Once Clisp is installed open the command prompt (Windows) or terminal (Linux). Change directory to the location of the program files and type “clisp” hit enter and then type ‘ (load “MC.lisp”) ‘ to run the Missionaries-Cannibals problem or ‘ (load “EightPuzzle.lisp”) ‘ to run the Eight Puzzle problem type. Hit enter.
Missionary-Cannibal Program: Typing ‘(MC)’ in Clisp runs the code to solve the Missionary-Cannibal problem. The program asks and receives a user’s input for the number of missionaries, number of cannibals and the max capacity of the boat. Since the number of cannibals cannot outnumber the number of missionaries, the users input is checked to see if it is valid. After receiving the user’s input, the program creates a search tree and uses A* search algorithm to search the tree and find the optimal path to the goal. A* is a search algorithm that uses a heuristic function and a path cost function. The heuristic function chosen for this program is the sum of missionaries and cannibals at a specific node in the search tree. The path cost function is equal to the current depth of the node in the tree. The optimal path is the least amount of steps to reach the goal state. The goal state is when all the missionaries, cannibals and the boat are on the other side of the river. The code returns an array that represents the values of missionaries, cannibals and boat location for each step in the search path. For example (3,3,1) represents 3 missionaries, 3 cannibals on the starting side of the river with the boat located on the starting side as well. And (2,2,0) represents 2 missionaries, 2 cannibals on the starting side of the river with the boat located on the goal side. Thus, the goal state would be (0,0,0). The code is written with the assumption that a missionary or cannibal in the boat at the shore but not on the shore counts as being be itself. The code was tested with missionary and cannibal values up to 24 and boat capacity up to 6. The larger the values of missionaries and cannibals the onger the program will take.
8 -Puzzle Program Typing ‘(8P)’ in Clisp runs the code to solve the 8-Puzzle problem. The program asks and receives a user’s input for each square in the 8-Puzzle problem. The empty square is represented by 0. The user’s input is checked to see if it is a feasible puzzle to be solved. This is done by checking the number of inversions (values are in reverse order of where they are in goal state)., since it is not possible to solve the 8-Puzzle with an odd number of inversions. After receiving the user’s input, the program uses A* search algorithm to search the tree and find goal state ((1,2,3),(4,5,6),(7,8,E)). The heuristic function chosen for this program is the number of mismatched tiles from the goal state. The path cost function is equal to the current depth of the node in the tree. Once finished the program outputs all of the nodes that were expanded during the search. The program also shows the optimal path to a solution. In the optimal path, the heuristic, depth, state and parent node are displayed for each node. The program was tested for the valid input ((E,1,3),(4,2,5),(7,8,6)) and the infeasible input ((8,1,2),(E,4,3),(7,6,5)). Figure 6 show terminal script of the program running for the start state ((E,1,3),(4,2,5),(7,8,6)) and Figure 7 show terminal script of an infeasible puzzle.