Project 5 – Prolog Programming

Introduction

For this project you will need to implement a number of functions in Prolog that together can be used to find solutions for mazes. This project will provide experience dealing with logic, recursion, lists, and other features in Prolog.

Getting Started

Download the following archive file p5.zip and extract its contents.

Along with files used to make direct submissions to the submit server (submit.jar, .submit, submit.rb), you will find the following project files:

• Your Prolog program – logic.pl
• Public tests
  • publicRecursion1.pl
  • publicRecursion2.pl
  • publicRecursion3.pl
  • publicMaze1.pl
  • publicMaze2.pl
• Expected outputs for public tests
  • publicRecursion1.out
  • publicRecursion2.out
  • publicRecursion3.out
  • publicMaze1.out
  • publicMaze2.out
• Public test driver – goTest.pl

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.pl 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_ackermann
• public_prod
• public_fill
• public_genN
• public_genXY
• public_flat
• public_isprime
• public_inlang
• public_stats
• public_validPath
• public_findDistance
• public_solve

Here’s an example of how to run a public test manually:

swipl                                 % start prolog
?- working_directory(C,'path to p5'). % go to p5 directory
                        % start here if using swipl-win.exe
?- ['logic.pl'].                      % load your code
?- ['publicMaze1.pl'].                % load public test
?- maze1_public.                    % run public test
etc...

On Windows machines, opening the logic.pl file with swipl-win.exe will bring up a window running the Prolog interpreter in the directory containing logic.pl, so it is not necessary to start swipl or call the function working_directory manually.

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 p5'). % go to p5 directory
?- ['goTest.pl'].                     % load test driver
                        % start here if using swipl-win.exe
?- run.                               % run all public tests

Prolog Library Functions Allowed

For this project you should write most code yourself, and only use Prolog’s built-in and library functions where absolutely necessary. You are not allowed to use any library or built-in functions unless they are explicitly listed as permitted functions. The only built-in function that you are allowed to use for this project are:

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:

   S -> T | V
   T -> UU
   U -> aUb | ab
   V -> aVb | aWb
   W -> bWa | ba

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 atoms u, d, l, and r, 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.
  • The Wts component of the fact indicates the weights granted to paths following the respective direction. That is, each element in Dirs has a corresponding weight in Wts.

  As an example, the fact cell(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 named N (a string) through the maze starting at position SX,SY and following the directions given by Dirs. For example, the fact path(‘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.

This is obviously a terse description; if you have further questions (once you have completed the rest of the assignment), ask the course staff.

Hints

• Unlike previous projects, you may be able to rely on Prolog’s backtracking to find multiple possible solutions through multiple queries.
• The Prolog functions findall will collect all results from a function using backtracking. The functionsetof will, in addition, sort the result and remove duplicates. These functions are used in the public tests.

Submission

You can submit your project in two ways:

• Submit your file logic.ml directly to the submit server by clicking on the submit link in the column “web submission”.