Square Colored Polyominoes



2015/11/17




Take a one-sided V-tromino with three squares. Using three colors there are 3^3 = 27 possible colorings of the squares if repetition of colors is allowed. Jared McComb asked for a Sudoku like 9x9 square made of theses pieces, where the number of same colored squares in each column, each row and each of the nine 3x3 subsquares is always 3. Computer solutions are immediately found and one solution is shown above. The pieces are made of hard foam with magnetic foil on the back to fix the pieces on an iron board.

What is the minimum number of preset pieces to get unique solutions?

The problem of Sudoku like squares can be generalized looking at other polyominoes. Since a one-sided I-tetromino is symmetric under 180 degree rotation there are only 1/2*(3^3+3^2) = 18 different colorings. With a total of 18*3 = 54 small squares you can't get a square. Therefore it seems to be better to take I-tetrominoes with fixed orientation getting 27 different pieces and a Sudoku like 9x9 square is possible.


With square colored tetrominoes you can also construct such squares. All pieces are one-sided and the O- and I-tetrominoes have a fixed orientation. The S-tetromino can't fill a square at all. For two or four colors the following tabel shows the results.

Tetromino Type Colors Pieces Square Size Same Colored Squares in Each Row Same Colored Squares in Each Row Subsquare Size Same Colored Squares in Each Subsquare
O-tetromino with Fixed Orientation 2 16 8x8 4 4 4x4 8
I-tetromino with Fixed Orientation 2 16 8x8 4 4 4x4 8
T-tetromino 2 16 8x8 4 4 4x4 8
L-tetromino 2 16 8x8 4 4 2x2 2
O-tetromino with Fixed Orientation 4 256 32x32 8 8 4x4 4
I-tetromino with Fixed Orientation 4 256 32x32 8 8 4x4 4
T-tetromino 4 256 32x32 8 8 4x4 4
L-tetromino 4 256 32x32 8 8 4x4 4

Two Colors

For the O- and T-tetrominoes you can't get a solution with 2x2 subsquares, because the uniformly colored pieces contribute four or three same colored squares to a 2x2 subsquare. For the I-tromino a solution is impossible, because the uniformly colored pieces must be placed into one column to meet the column condition. Otherwise they must be placed besided one another to meet the 2x2 square condition. This is a contradiction. Constructions with subsquares of size 4x4 are possible and each of th four subsqaures contains 8 squares of each color.



For the L-tetromino a construction even with 2x2 subsquares can be made.



Four Colors

If we use 4 colors, we have 256 pieces and can look for a 32x32 square. To reduce the problem we can divide the set. Let's take a special piece e.g. ABCC. Cyclic shift of colors produces the pieces BCDD, CDAA and DABB. This way we get 64 groups of 4 pieces each. Using only one piece of each group we can construct a 8x32 rectangle with 2 same colored squares in each row, 8 same colored squares in each column and 4 same colored squares in each 4x4 subsquare. With color shift we get three further 8x32 rectangles and the whole solution for the 32x32 square.









After the problems were solved I decided to make one set of 256 L-trominoes. The solution is shown on a 75cm x 75cm iron board. Even with the computer solution it took me some time to finish the construction, because it's difficult to spot the correct pieces in the large set. It's a good idea to divide the whole set into subsets due to the frequencies of the different colors .





Home