(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:
| 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.
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
class State { State(int n){...} boolean isDefined(Pos pos){...} int get(Pos pos){...} void set(Pos pos, int h){...} void unset(Pos pos){...} }
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
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.
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.
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.
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.
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.
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:
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.
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:
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.
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.