The Confused Bricklayer Robot Problem
A robot able to perform bricklaying operations is sent to a construction site and supposed to tile a floor. The tiles are 30cm x 30cm, the room is square and 3m x 3m. A hundred tiles have been delivered to the construction site, of which 53 are black and the remainder white. The architect was supposed to leave a plan specifying the pattern in which the tiles should be layed, but unfortunately had forgotten to do so. In an emergency phone call, he delivers the following information:
For simplicity, I will tell you only the number of black tiles in each row and column. The black tiles are to be layed such that they build perfect rectangles with a minimum side length of 2 tiles in each direction. The rectangle do not touch each other, not even at corners.
The black tiles in the columns, from left to right, are 3, 7, 4, 6, 6, 2, 7, 5, 8, 5. The black tiles in the rows, from top to bottom, are 7, 7, 7, 4, 4, 6, 2, 8, 6, 2.
Please answer the questions and perform the tasks as follows:
1. Draw a picture to illustrate the initial problem situation.
2. How can you describe a possible solution?
3. Try to manually solve the problem with a "hand-on"/guessing approach. Could you solve the problem in less than 10 minutes?
4. If you succeeded in solving the problem, reflect on your solution approach and try to write it down as some variation of pseudocode. Is the approach generalizable and suitable for implementation in software?
5. If you could not solve the problem by hand, try to think of a way how you (and later the computer) could generate possible solutions systematically and then check whether they satisfy all conditions or not.
6. Assuming that, no matter what approach you have decided for, the algorithm will require some searching for a solution, determine the size of the search space and describe a systematic method of enumerating all possibilities you have to test. Is it reasonable to expect good runtime performance from a software implementation?
7. Reflect on your current approach and the problem and check, whether you are already exploiting all information and knowledge that is provided in the problem description. If this is not the case, think of possibilities how you could use this knowledge to improve your algorithm.
8. Implement the algorithm and make a nice demo!