The 1997 British Informatics Olympiad

The British Informatics Olympiad
Sponsored by Data Connection.

Sample Paper: Solution to Question 3

This example solution is currently under development.

Question
statement

A domino is a 2x1 rectangle with 0, 1, 2, 3, 4, 5 or 6 written on each 1x1 half. A set of dominoes consists of the 28 unique dominoes. A domino with the same number on both halves is called a 'double'.

Sample run

3 (a)
[25 marks]

You are to write a program that will fit a set of dominoes onto a grid which is 7 squares high, and eight squares across. This is to be subject to restrictions, in the form of doubles in fixed positions, and to the rule that two touching squares can only be equal if they belong to the same domino. A square should only be considered to touch the four squares directly above, below, left or right. Dominoes may not overlap.

You should first read in input indicating where the fixed doubles are. For each double this will be in the form of an x co-ordinate and y co-ordinate for one of the halves of the domino, and a R or B to indicate whether the other half is to the right or below. The top left corner of the board is at (1,1). The list of doubles will terminate with the number -1.

Note that not all the doubles may be fixed, and that their value is left for you to decide.

Once you have read the list you should try and fit the other dominoes to the grid. You should then output a valid solution if there is one, or print 'Impossible'. Your program should then terminate.

8 3 B
4 1 R
5 7 R
-1

0-1 0 1-1 0-3 0
    |         |
5-0 2 0-6 1-2 4
1-3 1-4 1-5 1 0
            | |
3-2 4-2 5-2 6 0
2-6 3-4 3-5 3-6
4-5 4-6 5-6 5-5
6-6 3-3 2-2 4-4

3 (b)
[4 marks]

Suppose you are given some double restrictions, and a valid solution to the problem. Can you guarantee (or not) that there are any other solutions?

3 (c)
[8 marks]

Without any restrictions on doubles or the values on touching dominoes, how many ways can 28 dominoes be placed on the 7x8 board?

The 1997 British Informatics Olympiad