Description
• Introduction
In this assignment, you are going to use Prolog in order to solve a basic hardware con guration task where you put hardware components into the sections of a computer box. You will be given the structure of the box and some constraints regarding the components. Your task is to nd a con guration of these hardware components so that the given constraints are satis ed.
• Hardware Con guration Task
This con guration task consists of assignments of the given computer hardware components to the given grid-like computer box. The computer box contains square shaped sections that are labeled. Two sections are adjacent if they share an edge. An example computer box sketch is given in Figure 1.
A
B
C
D
E
Figure 1: Example computer box with a plus-like shape. Each section is labeled with letters from A to E.
The task requires you to assign the given set of hardware components, like CPU, fan, RAM, HDD etc., to the sections of the given computer box. There will be two type of constraints regarding these components; (1) two components may be required to be close to each other and (2) a component may be required to have an outer edge. Your solution should nd all possible con gurations given these constraints.
• Speci cations
3.1 Hardware Representations
The list of sections and the structure of the computer box will be given in a le named hardware.pl.
1
3.1.1 sections/1 predicate
The list that contains the section labels is given as;
sections ( SECTION_LIST ) .
where SECTION LIST represents the list of the section labels given as atoms.
The fact can be read as \SECTION LIST is the list of the sections in the computer box”. There will be no duplicates in SECTION LIST.
There will be only one sections fact in the given hardware.pl le.
3.1.2 adjacent/2 predicate
The adjacency between two sections is given;
adjacent ( SECTION1 , SECTION2 ) .
where SECTION1 and SECTION2 represent the labels of the sections that are adjacent, i.e., sharing an edge.
The fact can be read as \SECTION1 is adjacent to SECTION2″.
SECTION1 and SECTION2 are members of SECTION LIST.
In the given adjacency facts, SECTION1 will NOT be equal to SECTION2.
This predicate represents a two way connection, that is, by the de nition, SECTION1 is adjacent to SECTION2 if and only if SECTION2 is adjacent to SECTION1. In the given hardware.pl, only one adjacency fact will be given for a pair of sections.
A section can be adjacent to at least one and at most four sections. That is, there is no disconnected section of the computer box, and a section can share at most four edges (due to the square shape).
3.1.3 outer edge/1 predicate
The constraint on a hardware component regarding having an outer edge is given as;
outer_edge ( COMPONENT ) .
where COMPONENT represents the hardware component that should be placed on a section with at least one outer edge, i.e. an edge which is not shared by any other section.
The fact can be read as \COMPONENT should have an outer edge in the con guration”.
COMPONENT is a member of the given COMPONENT LIST.
3.1.4 close to/2 predicate
The constraint on two hardware components regarding being close to each other is given as;
close_to ( COMPONENT1 , COMPONENT2 ) .
where COMPONENT1 and COMPONENT2 represent the two components that must be placed close to each other, that is, their assigned sections must share an edge.
2
The fact can be read as \COMPONENT1 should be placed close to COMPONENT2 in the con guration”.
COMPONENT1 and COMPONENT2 are members of the given COMPONENT LIST.
In the given closeness facts, COMPONENT1 will NOT be equal to COMPONENT2.
This predicate represents a two way connection, that is, if COMPONENT1 should be close to COMPONENT2, then, by the de nition, COMPONENT2 should also be close to COMPONENT1. In the given list of con-straints, only one closeness fact will be given for a pair of components.
3.1.5 put/2 predicate
A placement of a hardware component to a computer box section is represented as;
put ( COMPONENT , SECTION ) .
where COMPONENT and SECTION are the hardware component that is placed and the section place of this component in the computer box.
The fact can be read as \COMPONENT is put to SECTION in the con guration”.
COMPONENT is a member of the given COMPONENT LIST. SECTION is a member of SECTION LIST.
3.2 Task
You are going to write a predicate, configuration/3, that will nd a placement for the given set of hardware components onto the given computer box under the given constraints.
3.2.1 configuration/3 predicate
The predicate will take 3 arguments.
configuration ( COMPONENT_LIST , CONSTRAINT_LIST , PLACEMENT_LIST ) .
COMPONENT LIST contains the hardware components that are going to be placed into the sections. CONSTRAINT LIST is made of two types of constraints; outer edge/1 and close to/2 predicates,
de ned over the given components.
PLACEMENT LIST consists of the placements of each component into the sections of the computer box. The placements are represented with put/2 predicates.
COMPONENT LIST will NOT have any duplicates, i.e. no component can occur in the list more than once.
It is guaranteed that there will be at most one constraint regarding a component in the given CONSTRAINT LIST. That is, a component can only be seen in at most one constraint in the list.
It is guaranteed that COMPONENT LIST and CONSTRAINT LIST arguments will be provided in any kind of query.
A query missing PLACEMENT LIST should nd a con guration of the given components under the given constraints and unify PLACEMENT LIST.
In the nal PLACEMENT LIST, all the components must be placed to a section.
3
A query providing all of the arguments should evaluate as true if the given PLACEMENT LIST is a valid con guration of the given COMPONENT LIST under the given CONSTRAINT LIST.
If there is no valid con guration under the constraints, the predicate should evaluate as false. If the given COMPONENT LIST is empty, PLACEMENT LIST should also be empty.
When forced to backtrack, the predicate should be able to nd all valid con gurations. The order in the PLACEMENT LIST is NOT important.
3.3 An Example
3.3.1 Example Knowledge Base
An example hardware.pl le for the computer box given in Figure 1 is represented in Prolog as;
: module ( hardware , [ sections / 1 , adjacent / 2 ] ) .
sections ( [ sA , sB , sC , sD , sE ] ) .
adjacent ( sA , sC ) .
adjacent ( sB , sC ) .
adjacent ( sC , sD ) .
adjacent ( sC , sE ) .
where the sections are given by atoms as sA, sB, sC, sD, sE.
4
3.3.2
Example Runs for configuration/3
?
c o n f i g u r a t i o n ( [ ] , [ ] , P l a c e m e n t L i s t ) .
P l a c e m e n t L i s t = [ ] .
?
c o n f i g u r a t i o n ( [ c p u ] , [ ] , P l a c e m e n t L i s t ) .
P l a c e m e n t L i s t = [ p u t ( c p u ,
s A ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u ,
s B ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u ,
s C ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u ,
s D ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u ,
s E ) ] .
?
c o n f i g u r a t i o n ( [ f a n ] , [ o u t e r _ e d g e ( f a n ) ] , P l a c e m e n t L i s t ) .
P l a c e m e n t L i s t = [ p u t ( f a n , s A ) ] ;
P l a c e m e n t L i s t = [ p u t ( f a n , s B ) ] ;
P l a c e m e n t L i s t = [ p u t ( f a n , s D ) ] ;
P l a c e m e n t L i s t = [ p u t ( f a n , s E ) ] .
?
c o n f i g u r a t i o n ( [ c p u , r a m ] , [ c l o s e _ t o ( c p u , r a m ) ] , P l a c e m e n t L i s t ) .
P l a c e m e n t L i s t = [ p u t ( c p u , s A ) , p u t ( r a m , s C ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s B ) , p u t ( r a m , s C ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s B ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s A ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s E ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s D ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s D ) , p u t ( r a m , s C ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s E ) , p u t ( r a m , s C ) ] ;
f a l s e .
?
c o n f i g u r a t i o n ( [ c p u , r a m , s s d , h d d , f a n , g p u ] , [ ] , P l a c e m e n t L i s t ) .
f a l s e .
?
c o n f i g u r a t i o n ( [ c p u , r a m , s s d , h d d , f a n ] , [ o u t e r _ e d g e ( f a n ) , c l o s e _ t o ( c p u , r a m ) , c l o s e _ t o ( s s d , h d d ) ] ,
–
P l a c e m e n t L i s t ) .
f a l s e .
?
c o n f i g u r a t i o n ( [ c p u , r a m , s s d , h d d , f a n ] , [ o u t e r _ e d g e ( f a n ) , c l o s e _ t o ( c p u , r a m ) ] , P l a c e m e n t L i s t ) .
P l a c e m e n t L i s t = [ p u t ( c p u , s A ) , p u t ( r a m , s C ) , p u t ( s s d , s B ) , p u t ( h d d , s D ) , p u t ( f a n , s E ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s A ) , p u t ( r a m , s C ) , p u t ( s s d , s B ) , p u t ( h d d , s E ) , p u t ( f a n , s D ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s A ) , p u t ( r a m , s C ) , p u t ( s s d , s D ) , p u t ( h d d , s B ) , p u t ( f a n , s E ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s A ) , p u t ( r a m , s C ) , p u t ( s s d , s D ) , p u t ( h d d , s E ) , p u t ( f a n , s B ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s A ) , p u t ( r a m , s C ) , p u t ( s s d , s E ) , p u t ( h d d , s B ) , p u t ( f a n , s D ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s A ) , p u t ( r a m , s C ) , p u t ( s s d , s E ) , p u t ( h d d , s D ) , p u t ( f a n , s B ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s B ) , p u t ( r a m , s C ) , p u t ( s s d , s A ) , p u t ( h d d , s D ) , p u t ( f a n , s E ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s B ) , p u t ( r a m , s C ) , p u t ( s s d , s A ) , p u t ( h d d , s E ) , p u t ( f a n , s D ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s B ) , p u t ( r a m , s C ) , p u t ( s s d , s D ) , p u t ( h d d , s A ) , p u t ( f a n , s E ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s B ) , p u t ( r a m , s C ) , p u t ( s s d , s D ) , p u t ( h d d , s E ) , p u t ( f a n , s A ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s B ) , p u t ( r a m , s C ) , p u t ( s s d , s E ) , p u t ( h d d , s A ) , p u t ( f a n , s D ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s B ) , p u t ( r a m , s C ) , p u t ( s s d , s E ) , p u t ( h d d , s D ) , p u t ( f a n , s A ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s B ) , p u t ( s s d , s A ) , p u t ( h d d , s D ) , p u t ( f a n , s E ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s B ) , p u t ( s s d , s A ) , p u t ( h d d , s E ) , p u t ( f a n , s D ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s B ) , p u t ( s s d , s D ) , p u t ( h d d , s A ) , p u t ( f a n , s E ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s B ) , p u t ( s s d , s D ) , p u t ( h d d , s E ) , p u t ( f a n , s A ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s B ) , p u t ( s s d , s E ) , p u t ( h d d , s A ) , p u t ( f a n , s D ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s B ) , p u t ( s s d , s E ) , p u t ( h d d , s D ) , p u t ( f a n , s A ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s A ) , p u t ( s s d , s B ) , p u t ( h d d , s D ) , p u t ( f a n , s E ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s A ) , p u t ( s s d , s B ) , p u t ( h d d , s E ) , p u t ( f a n , s D ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s A ) , p u t ( s s d , s D ) , p u t ( h d d , s B ) , p u t ( f a n , s E ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s A ) , p u t ( s s d , s D ) , p u t ( h d d , s E ) , p u t ( f a n , s B ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s A ) , p u t ( s s d , s E ) , p u t ( h d d , s B ) , p u t ( f a n , s D ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s A ) , p u t ( s s d , s E ) , p u t ( h d d , s D ) , p u t ( f a n , s B ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s E ) , p u t ( s s d , s A ) , p u t ( h d d , s B ) , p u t ( f a n , s D ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s E ) , p u t ( s s d , s A ) , p u t ( h d d , s D ) , p u t ( f a n , s B ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s E ) , p u t ( s s d , s B ) , p u t ( h d d , s A ) , p u t ( f a n , s D ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s E ) , p u t ( s s d , s B ) , p u t ( h d d , s D ) , p u t ( f a n , s A ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s E ) , p u t ( s s d , s D ) , p u t ( h d d , s A ) , p u t ( f a n , s B ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s E ) , p u t ( s s d , s D ) , p u t ( h d d , s B ) , p u t ( f a n , s A ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s D ) , p u t ( s s d , s A ) , p u t ( h d d , s B ) , p u t ( f a n , s E ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s D ) , p u t ( s s d , s A ) , p u t ( h d d , s E ) , p u t ( f a n , s B ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s D ) , p u t ( s s d , s B ) , p u t ( h d d , s A ) , p u t ( f a n , s E ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s D ) , p u t ( s s d , s B ) , p u t ( h d d , s E ) , p u t ( f a n , s A ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s D ) , p u t ( s s d , s E ) , p u t ( h d d , s A ) , p u t ( f a n , s B ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s C ) , p u t ( r a m , s D ) , p u t ( s s d , s E ) , p u t ( h d d , s B ) , p u t ( f a n , s A ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s D ) , p u t ( r a m , s C ) , p u t ( s s d , s A ) , p u t ( h d d , s B ) , p u t ( f a n , s E ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s D ) , p u t ( r a m , s C ) , p u t ( s s d , s A ) , p u t ( h d d , s E ) , p u t ( f a n , s B ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s D ) , p u t ( r a m , s C ) , p u t ( s s d , s B ) , p u t ( h d d , s A ) , p u t ( f a n , s E ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s D ) , p u t ( r a m , s C ) , p u t ( s s d , s B ) , p u t ( h d d , s E ) , p u t ( f a n , s A ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s D ) , p u t ( r a m , s C ) , p u t ( s s d , s E ) , p u t ( h d d , s A ) , p u t ( f a n , s B ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s D ) , p u t ( r a m , s C ) , p u t ( s s d , s E ) , p u t ( h d d , s B ) , p u t ( f a n , s A ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s E ) , p u t ( r a m , s C ) , p u t ( s s d , s A ) , p u t ( h d d , s B ) , p u t ( f a n , s D ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s E ) , p u t ( r a m , s C ) , p u t ( s s d , s A ) , p u t ( h d d , s D ) , p u t ( f a n , s B ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s E ) , p u t ( r a m , s C ) , p u t ( s s d , s B ) , p u t ( h d d , s A ) , p u t ( f a n , s D ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s E ) , p u t ( r a m , s C ) , p u t ( s s d , s B ) , p u t ( h d d , s D ) , p u t ( f a n , s A ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s E ) , p u t ( r a m , s C ) , p u t ( s s d , s D ) , p u t ( h d d , s A ) , p u t ( f a n , s B ) ] ;
P l a c e m e n t L i s t = [ p u t ( c p u , s E ) , p u t ( r a m , s C ) , p u t ( s s d , s D ) , p u t ( h d d , s B ) , p u t ( f a n , s A ) ] ;
f a l s e .
?
c o n f i g u r a t i o n ( [ c p u , r a m , s s d , h d d , f a n ] , [ o u t e r _ e d g e ( f a n ) , c l o s e _ t o ( c p u , r a m ) ] , [ p u t ( c p u , s D ) , p u t ( r a m , s C ) , –
p u t ( s s d , s B ) , p u t ( h d d , s E ) , p u t ( f a n , s A ) ] ) .
t r u e .
5
• Regulations
1. Programming Language: You should write your code using SWI Prolog.
2. Late Submission: See the syllabus for the details.
3. Cheating: All the work should be done individually. We have zero tolerance policy for cheating. People involved in cheating will be punished according to the university regulations.
4. Newsgroup: You must follow the newsgroup (news.ceng.metu.edu.tr) for discussions and possible updates on a daily basis.
5. Evaluation: Your program will be evaluated automatically using \black-box” technique so make sure to obey the speci cations.
• Submission
Submission will be done via Ceng Class. Submit a single le called “hw5.pl” through the Ceng Class system. The le MUST start with the following lines.
• module ( hw5 , [ configuration / 3 ] ) .
• [ hardware ] .
6
