Colored Cubes

Time limit3sMemory limit128 MB

Summary
Given up to four cubes with colored faces, find the minimum number of face repaints so all cubes become identical under rotation.
Level

Medium6 of 10

Topics
Brute force, Simulation, Combinatorics
Solved
No attempts yet

Problem

There are several cubes, all of the same size. Every face of each cube is painted with a single color; two different faces of the same cube may or may not share a color.

Two cubes are identically colored if one of them can be rotated in space so that it looks exactly like the other, face for face. Only rigid rotations of the solid cube are allowed — you may never reflect a cube — so a cube and its mirror image are not necessarily identically colored. A set of cubes is identically colored when every pair of cubes in the set is identically colored.

You may repaint any face of any cube to any color you like. Given a set of cubes, determine the minimum total number of faces that must be repainted so that the whole set becomes identically colored.

Input

The input is a sequence of datasets. Each dataset starts with a line containing one integer nn (1≤n≤41 \le n \le 4), the number of cubes, followed by nn lines, one per cube.

Each cube line lists the colors of its six faces, in the fixed face order 1,2,3,4,5,61, 2, 3, 4, 5, 6, separated by single spaces. The faces are arranged so that faces 11 and 66 are opposite, faces 22 and 55 are opposite, and faces 33 and 44 are opposite; every cube uses this same numbering.

A color name is one or more words joined by hyphens (-), where each word is a nonempty string of lowercase English letters. Each color name is at most 2424 characters long, including any hyphens.

The end of the input is a line that contains a single 00; it is not a dataset.

Output

For each dataset, print one line with the minimum number of faces that must be repainted to make that set of cubes identically colored.

Examples5

  1. Example 1

    Input
    3
scarlet green blue yellow magenta cyan
blue pink green magenta cyan lemon
purple red blue yellow cyan green
2
red green blue yellow magenta cyan
cyan green blue yellow magenta red
2
red green gray gray magenta cyan
cyan green gray gray magenta red
2
red green blue yellow magenta cyan
magenta red blue yellow cyan green
3
red green blue yellow magenta cyan
cyan green blue yellow magenta red
magenta red blue yellow cyan green
3
blue green green green green blue
green blue blue green green green
green green green green green sea-green
3
red yellow red yellow red yellow
red red yellow yellow red yellow
red red red red red red
4
violet violet salmon salmon salmon salmon
violet salmon salmon salmon salmon violet
violet violet salmon salmon violet violet
violet violet violet violet salmon salmon
1
red green blue yellow magenta cyan
4
magenta pink red scarlet vermilion wine-red
aquamarine blue cyan indigo sky-blue turquoise-blue
blond cream chrome-yellow lemon olive yellow
chrome-green emerald-green green olive vilidian sky-blue
0
    Expected output
    4
2
0
0
2
3
4
4
0
16

  2. Example 2

    Input
    2
red green blue yellow magenta cyan
red green blue yellow magenta cyan
0
    Expected output
    0

  3. Example 3

    Input
    2
red red red red red red
blue blue blue blue blue blue
0
    Expected output
    6

  4. Example 4

    Input
    4
aaa aaa aaa aaa aaa aaa
bbb bbb bbb bbb bbb bbb
ccc ccc ccc ccc ccc ccc
ddd ddd ddd ddd ddd ddd
0
    Expected output
    18

  5. Example 5

    Input
    4
aa ab ac ad ae af
ba bb bc bd be bf
ca cb cc cd ce cf
da db dc dd de df
0
    Expected output
    18