Project 4  Maze Solver in Prolog
For this project you will need to implement a number of functions in Prolog that together can be used to find solutions for mazes and evaluating boolean formulae.
This project will provide experience dealing with logic, recursion, lists, and other features in Prolog.
Getting Started
Download the following archive file p4.zip
and extract its contents.
You will find the following project files:
 Your Prolog program 
logic.pl
 Public tests
publicRecursion1.pl
publicRecursion2.pl
publicMaze1.pl
publicMaze2.pl
publicEval.pl
 Expected outputs for public tests
publicRecursion1.out
publicRecursion2.out
publicMaze1.out
publicMaze2.out
 Public test driver 
goTest.pl
Maze Converter convertMaze.rb
The logic.pl
file you downloaded contains a number of utility functions, and comments describing the functions you are required to implement.
Note that you must implement your functions with the exact parameters specified, or else the submit server tests will fail.
Running Public Tests
The public tests are set up as a number of Prolog programs that will call functions from your logic.ml code and test them with different inputs. To execute a public test, you need to load both logic.pl and the public test file into the Prolog interpreter, then call the appropriate public test function for each logic.pl function you were required to implement. The public test functions are:
public_prod
public_fill
public_genN
public_genXY
public_flat
public_stats
public_validPath
public_findDistance
public_solve
Here’s an example of how to run a public test manually:
swipl % start prolog
? ['logic.pl']. % load your code
? ['publicMaze1.pl']. % load public test
? maze1_public. % run public test
etc...
If you are having trouble making the public tests run, you may have to change the working directory of Prolog using the working_directory(C,'path to p6')
command.
Alternatively, you may run all of the public tests at once using the goTest.pl
public test driver provided. It will load logic.pl and all the public tests, then run all public tests at once.
swipl % start prolog
? working_directory(C,'path to p6'). % go to p6 directory
? ['goTest.pl']. % load test driver
? run. % run all public tests
Prolog Library Functions Allowed
For this project you should write most code yourself, and only use Prolog’s builtin and library functions where absolutely necessary. You are not allowed to use any library or builtin functions unless they are explicitly listed as permitted functions. The only builtin function that you are allowed to use for this project are:
Type  Builtin Functions 
Arithmetic  +, , *, div, mod, <, =<, >, >=, is, =:= 
Logic  ==, =, \==, \=, \+ 
Lists  [HT], [H1,H2T], [H1,H2,H3T], etc. 
List Utilities  member(X,L), append(X,Y,R), sort(X,R) 
Cut  ! 
Collecting Solutions  findall(X,Y,R), setof(X,Y,R) 
Since many functions you need to implement are similar to those from previous projects, you may find it useful to examine your previous solutions when writing your solution in Prolog.
Part 1: Recursion
Write the following recursive functions:
prod(L,R)
L
=list of intsR
=product of elements ofL
 R=1 if L=[]
 L will always be given
? prod([1,2,3],R).
givesR=6
? prod([],R).
givesR=1
fill(N,X,R)
N
=intX
=intR
=list containing N copies of XR=[]
if N=0 N will always be given
 Either X or R will be given
? fill(4,2,R).
givesR=[2,2,2,2]
? fill(4,X,[2,2,2,2]).
givesX=2
genN(N,R)
N
=nonzero positive intR
=int values between 0 and N1, inclusive, in ascending order N will always be given
? genN(2,R).
givesR=0;R=1
.
genXY(N,R)
N
=nonzero positive intR
=pairs [X,Y], where X & Y are values between 0 and N1, inclusive, generated in ascending lexicographic order.N
will always be given? genXY(2,R).
R=[0,0];R=[0,1];R=[1,0];R=[1,1].
flat(L,R)
 L=list
 R=elements of L concatenated together, preserving relative order, first placing nonlist elements in a list if necessary
 R=[] if L=[]
 L will always be given
 Only removes one level of list, unlike flatten/2
? flat([[1],[2,3]],R).
R=[1,2,3].
? flat([1,[2,3]],R).
R=[1,2,3].
? flat([[1,[2]],3],R).
R=[1,[2],3].
Part 2: Maze solver
Maze descriptions
For this project, the mazes you will compute with will be given as Prolog databases. In particular, you will be given three kinds of facts
maze(N,SX,SY,EX,EY).
This fact indicates that: The height and width of the maze is N cells,
 The default starting position is SX,SY, and
 The ending position is EX,EY.

cell(X,Y,Dirs,Wts)
A fact of this form describes a cell in the maze. In particular, it says that the cell at position X,Y, has open walls as described by Dirs, the list of directions. More precisely:
The list
Dirs
will contain at most one of each of the atomsu
,d
,l
, andr
, which designate openings going up, down, left, or right, respectively. Recall from project one that the coordinate system places
0,0
in the upper left corner of the maze.
 Recall from project one that the coordinate system places

The
Wts
component of the fact indicates the weights granted to paths following the respective direction. That is, each element inDirs
has a corresponding weight inWts
. As an example, the factcell(1,0,['r','d'],[16.6, 0.89])
indicates that the cell at 1,0 has two open walls: one leading to the right (to cell 2,0) with weight 16.6, and one leading down (to cell 1,1) with weight 0.89. 
path(N,SX,SY,Dirs)
This fact describes a path namedN
(a string) through the maze starting at positionSX,SY
and following the directions given by Dirs. For example, the factpath('path1',0,3,[u,r,u,l,u])
indicates that there is a path ‘path1’ that starts at 0,3 and follows the given directions to end up at position 0,0.

Based on these maze facts, you need to implement the following functions for solving a maze.
stats(U,D,L,R)
U,D,L,R
=number of cells with openings up, down, left, and right.? stats(U,D,L,R).
U = D, D = 8, L = R, R = 7.
validPath(N,W)
N
=name of valid path (only goes through openings)W
=float value for weight of path (rounded to 4 decimal places) Return valid paths in same order as in database
 Use round4(X,Y) : T1 is X*10000, T2 is round(T1), Y is T2/10000.

Apply round4() to final float weight, not intermediate sums.
? validPath(N,W).
N = path1, W = 99.9958; N = path2, W = 103.779.
findDistance(L)
L
=list of coordinates of cells at distance D from maze start Elements of L are in form [D, [[X1,Y2],[X2,Y2],…]]
 Values of D range from 0 to D, in ascending order
 D=distance of cell furthest from start
 Cell coordinates [X,Y] are in lexicographic order

? findDistance(L).
L = [[0, [[0, 3]]], [1, [[0, 2]]], [2, [[1, 2]]], [3, [[1, 1],[2,2]], ..., [6, [[3, 2]]].
solve
 True if maze is solvable, fails otherwise.
? solve.
true.
The maze converter program convertMaze.rb
may be used to convert simple maze files from Project 1 into Prolog for use as test cases. Run it as ruby convertMaze.rb simpleMazeN.in > prologMazeN.pl
.
Submission
Submit your file logic.ml
directly to the submit server by clicking on the submit link in the column “web submission.”