Pairwise matching of tiles

Question

Recently in a coding competition I came across this question.

We have a 1000 tiles where each tile is a 3x3 matrix. Each cell in the matrix has an integer value from 0 to 9 which signifies the elevation of the cell. The problem was to find the maximum pairs of tiles such that they fit in perfectly. The tiles may be rotated to fit in. By fit in it means that for tile A and tile B

A[i]+B[i]=const for i=0 to 8

The approach I thought for this problem was that I could maintain a hash value corresponding to each tile. Then I would find the possible combinations of tiles that would be a possible fit and look it up in the hashtable.

Ex. For the tile below

5 3 2                   4 6 7                           5 7 8
4 8 9  matches with     5 1 0   for const = 9  & with   6 2 1  for const=10
1 4 5                   8 5 4                           9 6 5

for this tile the 'const' would range from 9(adding 0 to the maximum element) to 10(adding 9 to the minimum element). So I would get two possible combinations for tiles which i would look up in the table.

But this method is greedy and does not give the desired answer and also I was unable to think of a proper hash function which would consider of all possible rotations.

So what would be a good approach for solving this problem?

I am sure there is a brute force way to solve this problem but I was actually wondering whether a viable solution to the problem exists on the lines of "pairwise equal to k" problem.

Answer 1

For n=1000 I would stick with the O(n^2) brute force solution. However an O(n log n) algorithm is described below.

The lexicographicalish ordering is defined by the following less-than operator:

Given two matrices M1, M2, define M1' as M1 if M1[1] is positive and -M1 if M1[1] is negative, and likewise or M2'. We say that M1<M2 if M1'[1]<M2'[1], or if M1'[1] == M2'[1] and M1'[2] < M2'[2], or if M1'[1] == M2'[1] and M1'[2] == M2'[2] and M1'[3] < M2'[3] etc.

1. Subtract the middle element of each matrix from the rest of the elements of the matrix i.e. A'[5] = A[5] and A'[i] = A[i] - A[5]. Then A' fits with B' if A'[i] +B'[i] = 0 for i!=5, and the elevation is A'[5] + B'[5].

2. Create an array of matrices and a dictionary. Rotate each matrix so that the top left corner has minimal absolute value before adding it to the array. If there are multiple corners with the same absolute value then duplicate the matrix and store both rotations in the array.

   If some rotation of a matrix fits with itself and i,j are indices of rotations of this matrix, add the key-value pairs (i,j) and (j, i) to the dictionary.

3. Create an array S of indices 1,2... and sort S using the lexicographicalish ordering.

4. Instead of needing O(n^2) operations to check all possible pairs of matrices, it is only necessary to check all pairs of matrices with indices are S_i and S_(i+1). If a pair of matrices fits, use the dictionary to check that the two matrices are not rotations of the same original matrix before calculating the elevation of the pair.