P7 − ACM SPPC 1 of 2 Saturday, 20/09/2003
PROBLEM 7 − COLOUR GRIDS
You are given a number of plastic tiles, all of the same size, and a target pattern.
Your task is to assemble the tiles into a pile so that, looking from the top, it matches
the target pattern. Each tile is composed of 16 squares of transparent or coloured
plastic (opaque and identically coloured on both faces), arranged in a 4x4 grid. The
target pattern is also a grid of colours, similar to a tile, but without transparencies.
The tiles can be rotated clockwise through multiples of 90° and/or flipped about a
horizontal axis. This leads to 8 possible transformations − rotated 0, 1, 2 or 3 times,
or a flip followed by the same sequence of rotations. These transformations, in the
above order, are numbered 0 to 7. The following diagrams provide an example, with
colours denoted by upper case letters, and dots (‘.’) representing transparency:
Transform #0
(original)
Transform #1
Transform #2
Transform #3
R R G G
R R . G
Y Y B B
Y Y B B
Y Y R R
Y Y R R
B B . G
B B G G
B B Y Y
B B Y Y
G . R R
G G R R
G G B B
G . B B
R R Y Y
R R Y Y
Transform #4
Transform #5
Transform #6
Transform #7
Y Y B B
Y Y B B
R R . G
R R G G
R R Y Y
R R Y Y
G . B B
G G B B
G G R R
G . R R
B B Y Y
B B Y Y
B B G G
B B . G
Y Y R R
Y Y R R
Write a program that will read in a sequence of tiles and a target pattern and
determine whether the target pattern can be made by some arrangement of all or
some of the input tiles.
o If there are several ways of achieving the target, then choose the pile with
fewest tiles.
o If there are still several ways of achieving the target, then at every point in the
pile, in a top–down order, choose first the lowest numbered appropriate tile
and, if still needed, the lowest numbered appropriate transformation.
