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:

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){...}
}
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:

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.

Upload the file Naive.java.

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.

Upload the file EarlyChecks.java.

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:

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:

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.

Upload the file Action.java.

Upload the file SmartEarlyChecks.java.

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:

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:

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

Upload the file Action.java.

Upload the file Propagation.java.

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.

Upload the file SmartArchitects.java.