5 Cut und Not, Backtracking
Solutions
5.1 A Tennis Tournament
On a sunny afternoon Adam, Bob, Carlo and Daniel play some tennis matches. The results are recorded as Prolog facts:
beats( adam, bob).
beats( adam, carlo).
beats( bob, daniel).
beats( carlo, daniel).
The players agree to be classified in 3 categories:
category( S, 1)
/* S won all matches */
category( S, 2)
/* S won some matches and lost some matches */
category( S, 3)
/* S lost all matches */
Implement the predicate category( Player, Category) in two ways: once using only cut, and once using only not. Test your implementations using the queries:
- What is the category of Adam?
- Which players belong to the category 2?
- Does Adam belong to the category 1? Does he belong to the category 2? Does he belong to the (nonexisting) category 4?
- What is the category of (non-playing) Thomas?
- Who played and in which category?
Note: Both implementations cannot answer all queries correctly.
Solution 5.1
5.2 Three Friends
The three friends Bill, Daniel und Michael live in different cities and have different jobs. Each year they meet in Zurich, where one of them lives, and take part in the Silvester run. This time Michael was faster than his friend from Bern and Daniel was faster than the officer. The fastest was the sport teacher as always. Daniel lives in Basel, and Michael is a doctor.
Who is who ?
Solution 5.2
5.3 The N Queens Problem
N queens should be positioned on a NxN chessboard so that none of them can hit any other in one move. In chess, a queen can move as far as she pleases, horizontally, vertically, or diagonally.
5.3.1 Generate and Test
The most straigtforward (but inefficient) solution is the "Generate and Test" method, that can be implemented in Prolog in general as follows:
solve( Problem, Solution) :-
generate( Problem, Solution),
test( Solution).
In the case of the N queens this would be:
solve( N, Position) :-
generate( N, Position),
test( Position).
The predicate generate generates by backtracking all possible positions of the queens and the predicate test tests whether these positions are admissible.
A position can be represented e.g. as [p(1,D1), p(2,D2), ..., p(N,DN)]. The structure p(1,D1) means that a queen is in the column 1 and in the row D1, etc. The possible values for D1, D2, ..., DN correspond to the permutations of the numbers 1, 2, ...N.
5.3.2 Stepwise Generate and Test
The problem can be solved more efficiently by placing the queens in the columns step by step and immediately testing whether the placement is admissible. If the placement is not admissible, the backtracking in the columns is performed to get an admissible placement and only afterwards a new column is tried. Try to implement this method.
A partial solution with admissible queens in the columns 1, 2, …, k is represented by two lists: a list B with occupied rows and a list F with free rows.
Example: N = 5, k = 3, B = [1, 3, 5], F = [2, 4].