Harvey Mudd College
Computer Science 60
Assignment 9, Due Thursday, November 11, by midnight

Prolog

Part 1: Food Knowledge Base for Local Restaurants

This problem entails coding queries into predicate logic using Prolog. Your file should be a program which will load and run in Prolog named prolog.pl. (That file will also have the prolog clauses for Part 2 of this assignment.) The names of constants and predicates are in lower-case for convenience in working with Prolog; to capitalize them would require that we include them in single quotes. The following predicates about local restaurants have been pre-coded in Prolog. Your program should access this code by including the following line in your prolog.pl source:

serves predicate:

american restaurants serve 
	salad, steak, sandwiches, burgers, and fried chicken.
burger_place restaurants serve 
	burgers, fries, and salad.
cajun restaurants serve
	rice, beans, gumbo, and sausage.
chinese restaurants serve 
	eggrolls, rice, shrimp, soup, and noodles. 
indian restaurants serve 
	papadam, bagan_bharta, rice, tandoori, and naan.
italian restaurants serve 
	salad, pasta, cioppino, snapper, and bread.
japanese restaurants serve 
	sashimi, rice, tempura, and noodles. 
mediterranean restaurants serve
	gyros, humus, pita, and falafel. 
mexican restaurants serve 
	tacos, beans, rice, enchiladas, and snapper. 
pizza_place restaurants serve 
	pizza, salad, garlic_bread
seafood_place restaurants serve
	salad, shrimp, snapper, bouillabaisse, and clams. 
thai restaurants serve 
	eggrolls, rice, noodles, and pad_thai. 

Note: There are two ways in which you can define a predicate such as serves: One on hand, you can enumerate each relationship:

etc.

A more concise way is to use lists in an auxiliary predicate, in conjunction with the built-in member predicate that enumerates the relationships.

servesAll(american, [salad, steak, sandwiches, burgers, fried_chicken]).

serves(Kind, Dish) :- servesAll(Kind, Dishes), member(Dish, Dishes).

This is the technique used in foodkb.pl.

(end of note)

dish predicate:

vegetarian dishes:
	beans, bagan_bharta, enchiladas, falafel, humus, 
	pizza, salad, soup, tempura, and all starch dishes 
meat dishes:
	burgers, enchiladas, gyros, pad_thai, pizza, steak, sandwiches, 
	fried_chicken, tacos, tandoori
seafood dishes:
	eggrolls, snapper, cioppino, sashimi, shrimp, bouillabaisse, tempura 
starch dishes:
	naan, papadam, bread, rice, noodles, pita, garlic_bread, pasta, fries

cuisine and location predicates:

arrufos is an italian restaurant in claremont.
bamboo_yuan is a chinese restaurant in claremont.
bombay is an indian restaurant in ontario.
chilis is an american restaurant in laverne. 
don_salsa is a mexican restaurant in claremont. 
el_gato is a mexican restaurant in upland. 
full_house is a chinese restaurant in upland. 
islands is a burger place in montclair. 
kishi is a japanese restaurant in upland. 
nirvana is an indian restaurant in montclair. 
nogi is a japanese restaurant in claremont. 
orchid_garden is a thai restaurant in laverne. 
pizza_n_such is a pizza_place restaurant in claremont. 
rosas is an italian restaurant in ontario. 
sacas is a mediterranean restaurant in claremont. 
sanamluang_cafe is a thai restaurant in pomona. 
shrimp_house is a seafood_place restaurant in claremont. 
tutti_mangia is an italian restaurant in claremont. 
warehouse is a pizza_place restaurant in laverne. 
yiannis is a mediterranean restaurant in claremont. 

county predicate:

claremont is in los_angeles_county. 
laverne is in los_angeles_county. 
montclair is in san_bernardino_county. 
ontario is in san_bernardino_county. 
pomona is in los_angeles_county. 
upland is in san_bernardino_county. 

Problem:

Code the following queries in Prolog. Include in your code a comment with each query that shows the answer to that query. (See the example below.) In some cases, you may find it helpful to define auxiliary predicates to assist.

1. Which restaurants are in claremont?
2. Which restaurants have italian cuisine?
3. Which restaurants serve bouillabaisse?
4. Where can you get served rice in claremont?
5. Where can you get served a vegetarian dish in montclair?
6. Which restaurants serve both vegetarian and meat dishes?
7. Which cities have both a chinese restaurant and a mexican restaurant?
8. Which restaurants in claremont or upland serve meat dishes?
9. Which restaurants in san_bernardino_county serve vegetarian dishes?
10. Which restaurants in claremont don't serve snapper?
11. Which cities have more than one restaurant of some type of cuisine?
12. Which cities have more than one restaurant serving noodles?

Each answer should be encoded as a predicate which gives the whole set of entities as a list. The following is an example of how this would be done for the first query:

/* 1. Which restaurants are in claremont? */

/* inClaremont(Restaurant) is true iff Restaurant is in claremont */

inClaremont(Restaurant) :- restaurant(Restaurant, _, claremont).


/* ans1(Restaurants) gives the set of restaurants in claremont */

ans1(Restaurants) :- setof(Restaurant, inClaremont(Restaurant), Restaurants).

/*
The answer to the query ans1(X) is

X = [arrufos,bamboo_yuan,don_salsa,nogi,pizza_n_such,sacas,shrimp_house,
     tutti_mangia,yiannis]
*/

Part 2: Problem encoding and solving

The problem

This problem exploits Prolog's problem solving abilities to solve a non-obvious state-transition puzzle. In chapter 6, a puzzle involving pegs was presented, as shown here:

The objective of this puzzle is to completely reverse the colors of the pegs by a restricted form of moves, namely a light peg can move right into an empty hole or can jump to the right over a single adjacent peg of either color, while a dark peg can move left into an empty hole or can jump to the left over an adjacent peg. Thus light pegs move only to the right and dark ones only to the left. Jumped pieces are not removed from the game.

Your program should print out a sequence of moves for solving this puzzle. Each move is one of the following:

The solution will show the move sequence as a list, something like the following:

The name of the predicate that produces the solution sequence should be called solve4 (for the puzzle with 4 pegs of each color). It should have one argument, the solution of which is the sequence.

Extra Credit:

For 10 points extra credit, generalize the predicate to a two-argument predicate solve, where solve(N, M) solves an N-peg puzzle (N > 0).

Represent the state of the puzzle as two lists, one representing the pegs from the left of the hole in reverse order, and one representing the pegs on the right of the hole in regular order. This is similar, by the way, to the way rex represents a Turing machine tape in the text. The reason for this representation is so that manipulation of pegs on either side of the hole is easy.

Consider defining a 5-ary predicate, say pegs, where pegs(L, R, FL, FR, M) means that M is a sequence of moves that will take the state L, R into the state FL, FR. In fact, you can pretend M is specified to drive the puzzle from one state to another, and if your rules are done carefully, specifying the beginning and ending state will generate the sequence M for you, which is the objective. This clearly shows off Prolog's problem solving ability.

As always, get advice from the instructor or grutor when you need help with Prolog specifies.

Reading

Predicate Logic and prolog is covered in Chapter 10 of the text. States and transitions are covered in Chapter 6.

Submission

Include both parts in the same prolog.pl source file in the usual way, i.e., by running

% cs60submit prolog.pl

You will be asked to input the assignment number (9).