1995 BIO Round Two Question Two

Programming problem - Squares (1 hour 30 mins)

Languages available: Turbo Pascal 7.0, Turbo C++, QBasic

Given a 5x5 grid, the numbers 1 to 25 are to be placed without repetition in the grid. The placement rule is that given the number k occupying co-ordinates (x, y), 1 <= k < 25, the number k+1 can be placed in any unoccupied square on the board with the following co-ordinates (z, w):

1. (z, w) = (x +/- 3, y)
2. (z, w) = (x, y +/- 3)
3. (z, w) = (x +/- 2, y +/- 2)

For example, given the starting position of 1 at (1, 2), the number 2 can be placed in any of the squares marked with a *.

```+-------------------+
|   |   |   |   |   |
+-------------------+
| 1 |   |   | * |   |
+-------------------+
|   |   |   |   |   |
+-------------------+
|   |   | * |   |   |
+-------------------+
| * |   |   |   |   |
+-------------------+
```

Your program should repeatedly offer 3 options: A - Problem A; B - Problem B; X - exit program.

Problem A

You are given a starting position for the number 1. Print to the screen the list of all valid squares in which the number 2 can be placed according to the above rule. The order of this list is unimportant. Append a copy of this to the file 'BIO95R2.OUT'. A sample copy of this output is given below.

Input

```Starting square in format x y : 1 2
```

Output

```Valid positions starting from (1, 2):
(1, 5)
(4, 2)
(3, 4)
blank line
```

Problem B

You are again given a starting position in which the number 1 is placed. Evaluate and display the number of valid combinations which result in a complete grid. This means a grid in which all pieces 2 to 25 have been placed from the given starting position following the above rule. You should also give one example complete board. A copy of your output should be appended to the file 'BIO95R2.OUT'.

Input

```Starting square in format x y : 1 2
```

Output

```Total number of valid combinations starting from (1, 2): 548
Example grid:
16 24 10 17 25
1  13 21 2  12
9  18 5  8  19
15 23 11 14 22
4  7  20 3  6
blank line
```

Solution to the Squares Problem

squares.pas, the solution program.

Antony Rix
contact details