EECS-3401 Introduction to AI
For Q1 through Q7, build Prolog procedures for SWI Prolog that work as specified.
Dr. Dogfurry has designed the following binary-tree data-structure in Prolog. A “node” term looks like
- [bt(integer, binary_tree_node, binary_tree_node)] or
- []
The latter represents an empty tree. The former, a tree; the second and third arguments are binary-tree nodes. Call the first argument, an integer, the node's key.
A binary-tree node can have a left-child binary tree (the second argument) or a right-child binary tree (the third argument), or both. (If it does not have one or the other, an empty binary tree, [], is placed there.)
E.g., [bt(5, [], [bt(7, [], [])])]
For the forllowing, you may assume any term argument that you are passed is a proper binary tree, apropos Dr. Dogfurry's representation:
- it is finite (that is, does not contain circular “pointers”);
- if it is not the empty binary tree, that the first argument is an integer, and the next two arguments are proper binary trees (maybe empty); and
- that it is ground.
Q1. [5pt] empty_bintree/1
Write a procedure for empty_bintree/1 that takes an argument Tree. It should return true if this is an empty binary tree, apropos Dr. Dogfurry's representation; and false (fail), otherwise.
The procedure should return true — with the appropriate additional behaviour — with an unbound variable for its argument.
Q2. [5pt] bintree_contains/2
Write a procedure for bintree_contains/2 that takes two arguments, Key and Tree, in that order. The latter argument is input.
The procedure should evaluate true iff Key is equal to the key of any node in the binary tree Tree. If Key is a variable on the call, it should unify to the key of a node in Tree. And unify to each key of each node in Tree via backtracking.
Q3. [5pt] bintree_sum/2
Write a procedure for bintree_sum/2 that takes two arguments, Tree and Sum, in that order. The former argument is input, the latter output or input. Sum should be unified to the sum of the keys of the nodes in Tree.
Q4. [5pt] is_bintree_ordered/1
Write a procedure for is_bintree_ordered/1 that takes one argument Tree. It should evaluate true iff the Tree has the property of being ordered. That is, if one did a left-to-right in-order traversal of Tree, the keys are in order ascending, allowing for duplicate key values.
Recall the 15 puzzle. There are tiles numbered 1 through 15 arranged on a 4 by 4 grid. This leaves one slot on the grid empty. The solved puzzle then looks like:
A tile adjacent to the blank slot can be slid over, effectively swapping the the tile and the blank. Making a number of moves like that can leave the puzzle pretty scrambled. E.g.,
Number the slots in the 4 by 4 grid the same as the tiles as when the puzzle is solved, with the blank slot as 16.
We can represent a state of the puzzle simply as a list of lists: each inner list is a list of the slots in that row; the outer list is a list of rows. A number in a list represents that the tile of that number is in that position. Let us use the number 0 as a stand in for the blank. Thus, the solved state is:
[[ 1, 2, 3, 4],
[ 5, 6, 7, 8],
[ 9, 10, 11, 12],
[13, 14, 15, 0]]
And for the scrambled state above:
[[12, 1, 2, 15],
[11, 6, 5, 8],
[ 7, 10, 9, 4],
[ 0, 13, 14, 3]]
Q5. [5pt] is_legal_15/1
Write a procedure for is_legal_15/1 that takes an argument State. It should evaluate as true if State represents a legal state of the 15 Puzzle, apropos our chosen representation above. You may assume that State must be ground to be legal.
Q6. [5pt] move_15/2
Write a procedure for move_15/2 that takes two arguments, In_state_ and Out_state, in that order. The former is input, the latter output.
You may assume that In_state is a legal state of the 15 Puzzle, apropos our chosen representation above. The procedure should return a legal state via Out_state that is one move different from the In_state. One move different is that the blank has been exchanged with an adjacent tile.
Your procedure should be backtrackable through all new states reachable from In_state in one move.
Q7. [5pt] manhattan_15/2
Write a procedure manhattan_15/2 that takes two arguments, State and Distance, in that order. The former is input, the latter output. You may assume that State is a legal state of the 15 Puzzle, apropos our chosen representation above. Distance should be the manhattan distance the State is from the solved state. That is, the sum of the manhattan distances of each tile from where the tile is and where it should be. (Note that “0” is not a tile and is not included here in the sum.)
Q8. [5pt] Is manhattan_15/2 a monotonic heuristic?
Assume that one move is a cost of one. Prove or disprove that manhattan_15/2 is a monotonic heuristic as per A*.
Your proof or disproof needs to be clear and convincing. It does not need to be in formal style.
Q. For Q5, is_legal_15/1, do we need to determine too that the state is reachable from the solved state? (Not all configurations of 0, …, 16 matched to the slots are reachable!)
Or do we just need to determine that State is a list of four lists, each sub-list of length four, and that 0, …, 16 are each represented? (In other words, that the State is just syntactically correct.)
A. The latter. You do not need to be detecting that State is reachable.
Q. Help! Where to start?
A. Look over the various Prolog code that we have developed over the term. You should find that there are procedures from our various examples that match closely to things you are looking to implement here.
For instance, in word trail, we needed to be able to swap two letters in a list. Here, you need to be able to swap two adjacent “tiles” in a list of lists, for the 15 Puzzle.
- Have a Prolog program named widgets.pl that contains your procedures for Q1 through Q7.
- Have a text file (ASCII or utf-8), name it
manhattan.txt, for your answer to Q8.
Submit your two files.
% submit 3401 two widgets.pl manhattan.txt