Skyscrapers
by Stéphane Graham-Lengrand and Karthikeyan Bhargavan

Login :  Mot de passe :

# Skyscrapers

(The French version of this TD is available here.)

Skyscrapers is a puzzle-style game based on the following premise. A set of urban planners and architects are given the job of planning a new neighbourhood in a city. The neighbourhood is to be laid out as a square of n*n buildings of varying heights. Furthermore, the planners must obey two constraints:

• on each east-west row (resp. north-south column), they must construct n buildings that all have different heights (number of floors) between 1 and n (inclusive);
• on each east-west row (resp. north-south column), a specific number of buildings should be visible from the west (resp. the south) and a specific number of buildings must be visible from the east (resp. the north).
For example, consider the following provisional plan that encodes one set of planning constraints:
``` | 4 3 2 1 |
-+---------+-
4|         |1
3|         |2
2|         |2
1|         |2
-+---------+-
| 1 2 2 2 |
```
The plan requires that on the first row, 4 buildings must be visible from the west and only 1 is visible from the east; on the third column, 2 buildings must be visible from the north, and 2 must be visbile from the south, etc. The idea is that a if a tall building is in front of a small building (when seen from some direction), the small building is not visible when seen from that direction.

The following complete plan meet these specifications:

``` | 4 3 2 1 |
-+---------+-
4| 1 2 3 4 |1
3| 2 3 4 1 |2
2| 3 4 1 2 |2
1| 4 1 2 3 |2
-+---------+-
| 1 2 2 2 |
```

Conversely, the following provision plan is unrealizable:

``` | 3 2 1 |
-+-------+-
3|       |1
2|       |2
1|       |3
-+-------+-
| 1 2 3 |
```

In this TD, we will write a program that given a set of planning constraints as a provisional plan, computes a solution if there exists one. The program must explore the space of possibilities, backtracking when stuck, at each step making decisions of the form: at position (x,y) of the grid, we will place a building of height h floors.

# Structures de données

Download the archive td_8.tar.gz and unzip it within the source directory of a new eclipse project. Inside you will find a package skyscrapers, a folder that contains example input files, and a class Test (in Test.java) for testing your code in each exercise. We will run each test by editing the method main in Test to call the test corresponding to each exercise.

The class Post (in package skyscrapers) implements the coordinates (x,y) of a position on the grid (for a grid of length n, each coordinate is between 0 and n-1):

```class Pos{
final int x, y;
Pos(int x,int y){
this.x=x;
this.y=y;
}
...
}```

A state of our search algorithm will be a map of the grid, which may be fully determined (a building height has been decided for each position in the grid, which may represent a solution found by the algorithm), or it may be fully undetermined (no height has been decided for any position, which is the initial state), or it may be partially determined (an intermediate state of the algorithm). To uniformly represent all of these states, we will use an object of the class State (given in the file State.java), which implements the following methods:

```class State {
State(int n){...}
boolean isDefined(Pos pos){...}
int get(Pos pos){...}
void set(Pos pos, int h){...}
void unset(Pos pos){...}
}
```
• The constructor State(int n) constructs an initial state for an (n*n) grid, where none of the positions have been decided.
• The method isDefined indicates whether the height of the building at position pos has been decided.
• get returns the height of the building at position pos if it has been decided (it raises a runtime exception if the position is still undecided).
To raise exceptions, we use the class DecisionException (fichier DecisionException.java). (It extends the builtin Java exception class RuntimeException, and so it does not need to be declared in the signatures of the methods.)
• set modified the state and records the decision to place a building of height p at the position post (it raises a DecisionException if this position had already been decided).
• unset annuls the decision for the position pos and returns it to the undecided state (it raises a DecisionException if this position is currently undecided).
These methods permit the planners to read and edit a building plan, and notably to verify that the current state respects the initial constraints.

To test that the code you have been given has been installed correctly, call the function test0 within the method main in the Test class. You should obtain:

`test0 seems ok`

# Exploration

From this point onwards, we will program various alorithms that search for a solution to the skyscrapers game, and try to make them more and more efficient. Each algorithm will be implemented in its own class, and for ease of testing, all these classes will extend a single abstract class Exploration (file Exploration.java) that contains the initial planning constraints as an object archi of the class Architects:

```Architects archi;
```
We shall discuss the methods of the Architects class gradually in the following exercises. In each exercise, we shall implement a search algorithm as two methods:
```boolean search();
State getState();
```
The first method search must return true if there exists a solution that satisfies the planning constraints, and it must return false otherwise. In the first case, a subsequent call to getState should return the solution. The constraints can be accessed using the field archi inherited from Exploration.

## Naive Exploration

In the class Architects (file Architects.java), you will find in particular a method:

`boolean checkState(State cs)`
that returns true if the state cs satisfies the constraints and returns false otherwise. Note that this semantics only makes sense if the state has been completely decided. For now, ignore the rest of the class Architects.

Implement, in the class Naive (file Naive.java), a naive exploration alogorithm, by completing the skeleton of the method search.

For this exercise, it will be wise to save as a field in the class Naive the current state, initialized in the constructor (using the State constructor), and refined little by little by the recursive calls to search. The precise specification of the method search is to to return true if the current (potentially incomplete) state can be completed into a final plan that satisfies the constraints, otherwise it must return false.

The naive search for the solution works as follows: it enumerates all the possible states that can result from completing the current state, and verifies whether any of them satisfies the constraints. To perform this enumeration, you can use the methods of the State class as follows:

• choose any position that is still undecided (i.e. by checking that isDefined returns false);
• pour each possible height h,
set the value for the current position to the value h, and recursively call search to see if there exists a solution that completes the new current state; if there is a solution, we are done; otherwise, we annul this decision by calling unset and continue with the other remaining heights h; if no heights are left, there is no solution and so we return false.

In the first step, to choose an undecided position, the class State provides you with a method Pos selectUndefinedPos(){...}. If a decision has already been made for all the positions in the grid, the the current state represents a proposed solution and this method returns null. Note that this method has a complexity of O(n^2) (where n is the width and height of the grid); as an extra question can you find a better solution by choosing a different data structure to represent the state?

In the second step, to iterate through all possible heights, we recommend that you obtain an enumerable set of heights by calling the method ISet getPossibilities(Pos p) from the class State: an object of the class ISet (implementing a set of integers) can be enumerated (like any Iterable class) using the for statement as follows:

```for (int h:state.getPossibilities(pos)){...}
```
Test your naive algorithm using test1 in Test.java. Your algorithm should return a solution for problems of size 3. Conversely, it will probably not find a solution in a reasonable time for problems of size 4.

## Viability of partial states

We would now like to do better than the naive solution, and avoid exploring the search space when it is clear that no solution can be found: we must prune the tree fo possibilities.

The first thing to do is to check whether the current state, even if it is partially decided, is viable, that is if it has any chance of leading to a solution. Note that since we only explore viable states, it is not necessary to reverify the full state at each step: if we know that the state was viable before the last modification, and if the last position modified was (i,j), then only the row i and the column j could potentially violate any constraints and only these need to be checked.

You will find in the class Architects a method

`boolean viable(State cs,Pos p)`
that verifies only that the row and column of p satisfy the constraints. Since cs may only be a partially decided state, the method returns false only if we can be sure that cs cannot be completed to a final state that satisfies the constraints; if any such completion is possible or if it is too costly to determine at this stage, the method returns true. In other words, true and false correspond respectively to the responses "Yes, maybe" and "Certainly not" to the question "can the state cs be completed to a solution of the problem?".

Implement, in the class EarlyChecks (file EarlyChecks.java), a recursive exploration algorithm, by completing the skeleton of the method search. This method assumes that the current state is viable; it takes a decision for some undecided position, and then calls viable to verify the row and column of the newly decided position, before recursively calling search until the state is completely determined. If the new state is not viable, it tries a different height for the undecided position; if no other heights remain, then search returns false.

Test your code using test2. Your algorithm should quickly find solutions for problems of size 3, 4, 5, 6, 7; it will take a little more time for problems of size 8. It will probably not terminate in a reasonable time for problems of size 9.

# Constraint Propagation

Now, we improve the algorithm further by maintaining for each position (i,j) the set of values (heights) that remain possible for that position. We will reduce this set dynamically over the during our search. To maintain this additional state, you are given a new class SmartState (file SmartState.java), that extends State with a more sophisticated data structure: at each position, it stores a set of integers (an object of the class ISET) that can be read and modified by the following methods:

```ISet getPossibilities(Pos p)
void setPossibilities(Pos p,ISet possib)
```
Recall that in State each position was associated with at most one value. In SmartState we say that a position has been decided if its ISet is a singleton set (has exactly one member); if a position has more than one element in its ISet, it is still undecided; if a position has an empty ISet then there is no remaining value for this position.

## Actions

In the place of the methods set and unset of State, we will use a different technique to modify objects of the class SmartState. SmartState includes a method:
`Action createSetAction(Pos p,int h){...}`
This method returns an object of class Action (file Action.java) that represents a state modification operation (which has not yet been performed.) The class Action has the methods:
```boolean perform()
void undo()
```
that are analogous to the methods set et unset. Actually, createSetAction(Pos p,int h) returns a particular type of action, an object of the class ToSet that extends Action.
Later, we will use other types of actions implemented by other subclasses of Action.

You will find in the class Action the fields Pos p (the position to modify), int h (the height to set at position p), SmartState cs (the state to modify), ISet backup (that stores a copy of the possibilities at position p just before its height was set), and an implementation of the method undo() (that reverts the value for the position p position to the previous backup copy).

You must implement the method boolean perform() in the class ToSet (file Action.java), according to the following specification:

• unlike set (which returns null), perform must return false if the action is impossible (that is, h is not a member of the possible values for pistion p), and true otherwise ;
• if the action is possible, the ISet of the position p must be modified to contain the singleton h before perform returns;
• if the ISet at position p has been modified by the action, and only in this case, perform should save the old ISet in the field backup.
You will need to use the methods boolean contains(int x), ISet add(int x), and boolean isSingleton(), from the class ISet, and the constructor ISet() that creates an empty set of integers.

Now complete the class SmartEarlyChecks (fichier SmartEarlyChecks.java), by adapting EarlyChecks as follows:

• the current state is now a SmartState, not a State;
• we use the methods perform and undo rather than set and unset to perform actions.

Test your code with test3. Your algorithm will probably be slower than the previous question, because our algorithm does not reduce the set of possible values for different position; the set of possible values for each position stays {1..n} until it is replaced by a singleton. Effectively, the algorithm is the same as the previous question but maintaining an ISet for each position costs us a certain factor of speed.

## Using an action queue

We will now implement a new kind of action: ``it is forbidden to have a building of height h at the position p''.

Complete the class ToForbid (file Action.java), which extends Action, by implementing its method perform according to the following specification:

• perform removes the value h from the ISet at the position p (if the value h was not in the ISet, then perform does nothing);
• if the ISet at the position p has been modified by the action, and only in this case, perform should save the old ISet in the field backup.
• the boolean returned by perform indicates whether there are still some possible valuees remaining at position p.
You may utilize the methods ISet remove(int x) and boolean isEmpty() from the class ISet.

Now complete the class Propagation (file Propagation.java). It is advisable to write two methods that call each other:

```boolean search()
boolean propagateAndSearch(Pos p,Queue<Action> todo)```

The method propagateAndSearch takes as its argument a position p that has just been modified (we have not yet verified the viability of this modification, and we have not yet determined it consequences), and a Queue todo of actions to perform.

The method search is the same as in the previous question, except that instead of directly verifying the viability of the state before making a recursive call, it calls propagateAndSearch and passes to it the position where one decision has just been made, ad an empty Queue of actions (an empty LinkedList<Action> created using new LinkedList<Action>() will do).

The method propagateAndSearch proceeds as follows:

• in the case where p is not the pointer null, verify the viability of the state by calling the method boolean viable(State cs,Pos p,Queue<Action> todo) from the class Architects (we pass in the queue todo so that when checking the viability, the method viable can also fill up the queue with the consequences of the modification of the state at p);
• then it calls search if there are no more actions to perform in the queue todo, and otherwise
• it performs the first action of todo ;
• if the action returns false, it undo-es the action and returns false (the action is not possible);
• otherwise, it recursively calls itself to determine if a solution to the problem exists after this action (for the recursive call, the position that has been modified by an action can be recovered by the method Pos needsChecking() in the classe Action) ;
• if there is no solition it undo-es the action and returns false.

Test your code using test4. Your algorithm must have the same behavior as the previous question.

## Permutation Constraints

So far, none of your code takes advantage of the action queue todo, and this is what we will address in this exercise. Specifically, when verifying partial states, it becomes clear that certain actions are a direct consequence of the previous modification and can therefore be placed in the queue todo. We will need a class Architects that is more intelligent, and in particulat, contains a method

`boolean isPermutation(State cs, Pos p, boolean b,Queue<Action> todo)`
that determines if the row or the column of p still has a chance of being completed by a permutation (buildings of all distinct heights). If b is true, it will verify the row of p, otherwise its column.

In the class Architects this method does not touch todo. To extend this method so that it adds actions in todo, we will redefine the method in a subclass SmartArchitects (file SmartArchitects.java) of the class Architects.

The new version of isPermutation(State cs, Pos p, boolean b,Queue<Action> todo) first calls the same method in its superclass to verify the current state, and it returns false if the method returns false. Conversely, if the row or column is viable, and if we decide that the building at position p has a height h, we will revisit every other position in the same line and column as p and try to remove h from the possible values of these positions. We will not remove this value immediately, but we will place in the queue todo the actions ToForbid that will perform this removal. To create these ToForbid actions, you can use the following method from the class SmartState:

`Action createForbidAction(Pos p,int h)`

Finally, to explore a row or a column, we will build on the loop used in the method of the superclass, and the usage of the constructor

`Pos(int n, Pos p, int j, boolean b)`
where n is the width/height of the grid, p is the position for which we are considering the row or column, j is the number of the position in the current row or column (between 0 and n-1), and b determines whether we are speaking of the row or the column of p.

Test your code with test5. Your algorithm must have better performance than the previous question.