# 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):

- (z, w) = (x +/- 3, y)
- (z, w) = (x, y +/- 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