# Hexominoes into 7 simultaneous congruent shapes

I came up with this puzzle 16 years ago, it was on Ed Pegg's Mathpuzzle site but nobody solved it AFAIK. The 35 hexominoes (which look like this): are to be arranged, in groups of five, into seven shapes congruent to this one.

The sample above is not a useful shortcut, if you start like this you won't be able to do all seven. In theory you could do this without a computer. In practice... I couldn't.

• In theory you could do anything without a computer Commented Dec 12, 2017 at 13:28
• I haven't checked, but I wouldn't be surprised if this is an exercise in the fascicle of Knuth's TAoCP which is currently in progress. Commented Dec 12, 2017 at 13:39
• I'd be interested to learn how you "came up with this" in a first place. Trying by chance? Or how did you find a shape you "knew" would work for at least one solution? It seems like coming up with this puzzle is at least as much work as solving it - without a guarantee there is a solution. Commented Dec 17, 2017 at 20:35
• Yes it was a fair bit of work to find the shape. In fact I was looking for an even better shape, one that gives a unique tiling for all seven individual tilings, but the one I found only has five of them unique, two have a 'flippable sub-rectangle'. But going back and trying again. I still can't find any shape that does as well as this one. This particular shape appears to be an outlier, and I was lucky to stumble on it. Well I found it by using a combination of trial-and-error and logic, but it is still an outlier. Commented Dec 18, 2017 at 0:09
• Method of finding this puzzle - basically the same as the method of solution given by two people below. 1. Find all piece sets that tile the shape using a tiling program I've been writing for many years. Takes about a second. 2. Feed them into a 'clique-solver' that I already wrote. This finds disjoint subsets, in this case the maximal disjoint subset ie a clique of seven groups of five pieces. This program is optimised and uses bitmaps and nasty #defines rather than recursion to speed things up. You've never seen an uglier chunk of code. But it finds this answer in less than a second. Commented Dec 18, 2017 at 0:14

The 35 hexominos can be tiled like this:

How did I find the tiling?

At first, I tried to find a solution without computer. I created the hexominoes in a graphics program and played with them. I could get up to five of the shapes filled, but for the last remaining shapes, I ended up with final gaps that required hexominoes that were already in use.

I then resorted to a computer approach. First, I determined which sets of five hexominoes can fill the given shape. Out of the C(35, 5) = 324,632 possible sets, only 2,664 can tile the given shape.

Then I tried to find an exact cover of these sets. I hope I haven't made a mistake, but my program tells me that the distribution above is the only one that solves the problem.

The exact tiling is a by-product of the first step, but I tiled the shapes by hand again — it's relaxing.

• Thanks for the link to the "exact cover" - it is always good to learn some new terms. However, did I miss something, or is it essentially just stating that you "tried to solve the original question"? (i.e. does the term add any information on how you solved it?) I'm seriously asking. Commented Dec 17, 2017 at 20:29
• And +1 just for the information that any one "by hand" has to play with (at least) 2664 sets... That gives one a nice perspective of the task at hand (and why it takes longer than one things it might.) Just finding those can be quite a task. I think anybody solving this puzzle "by hand" can indeed be very proud! Commented Dec 17, 2017 at 20:31
• You're right, the original question is also an exact cover problem. I just split it up into two parts to make the chunks manageable. Each of these two parts is also an exact cover problem, of course, so my description is misleading. Perhaps I had in mind that the second step is closer to the original description of exact cover as stated at the beginning of the Wikipedia article. Commented Dec 17, 2017 at 20:35
• Also: What type of algorithm did you do to find the solution? (Both steps). Just brute-force search of all possibilities or something more sophisticated? Always interesting to learn such things as well... Commented Dec 17, 2017 at 20:37
• @BmyGuest: My approach is a bit piecemeal. Do you think details of how each step was solved should go into the answer? Commented Dec 17, 2017 at 20:48

Just as I thought "this is a nice piece of work for Sunday" and was waiting for my code to finish, @MOehm came up with (of course) the same answer as I did, and we seemed to be using the same approach.

My Java code can be found here, or copied over from below. It takes 10 minutes to run on a 2013 MacBook Pro, so it should be within reach of most computers. It's a brute-force approach.

package nl.magnus.test;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public class Hex {
public static void main(String[] args) throws Exception {
// This is the image from the Puzzling.SE question.
// Hexominoes are numbered 0-34 (in the hexatridecimal number system)
String[] source = { //
" 022225555578AAAACCEEEEEFHHIIJKKMMMMOOORRRRTUUVVVVYY ",
"0021233466578888AACCDEFFFGHIJJKKLMMNOPORQSRTTUUWVVYYY",
"00111344467778999CCDDDDFFGHIIJKKLNNNOPPQQSSSTTUWWWWXY",
"011333446667999BBBBBBDGGGGHHIJJLLLLNNPPPQQQSSTUWXXXXX" };
int fixedCount = 0, oneSidedCount = 0;
for (int i = 0; i < freeCount; i++) {
// Determine character in source image
char c = (char)(i > 9 ? ('A' + i - 10) : ('0' + i));
List<Board> boards = new ArrayList<>();

// Find left-most and top-most occurrence of the character
int minIndex = Byte.MAX_VALUE, minRow = -1;
for (int row = 0; row < 4; row++) {
int index = source[row].indexOf(c);
if (index != -1) {
if (minRow == -1)
minRow = row;
if (index < minIndex)
minIndex = index;
}
}

// Board representation (original)
BitBoard board = new BitBoard();
for (int row = minRow; row < 4; row++) {
int index = minIndex;
do {
index = source[row].indexOf(c, index);
if (index == -1)
break;
board.set(row - minRow, index - minIndex);
index++;
} while (true);
}
oneSidedCount++;
fixedCount++;
determineShifts(board, boards);

// 90 degrees
BitBoard board90 = new BitBoard(board);
board90.rotate();
fixedCount++;
determineShifts(board90, boards);
// (cannot be identical to original with 6 tiles)

// 180 degrees
BitBoard board180 = new BitBoard(board90);
board180.rotate();
boolean hasRotationalSymmetry = board.equals(board180);
if (!hasRotationalSymmetry) {
fixedCount++;
determineShifts(board180, boards);
}

// 270 degrees
BitBoard board270 = new BitBoard(board180);
board270.rotate();
if (!hasRotationalSymmetry) {
fixedCount++;
determineShifts(board270, boards);
}

// Mirror
BitBoard mirror = new BitBoard(board);
mirror.mirror();
boolean hasMirrorSymmetry = board.equals(mirror) || board90.equals(mirror) || board180.equals(mirror)
|| board270.equals(mirror);
if (!hasMirrorSymmetry) {
oneSidedCount++;
fixedCount++;
determineShifts(mirror, boards);
}

// Mirror, 90 degrees
if (!hasMirrorSymmetry) {
BitBoard mirror90 = new BitBoard(mirror);
mirror90.rotate();
fixedCount++;
determineShifts(mirror90, boards);

if (!hasRotationalSymmetry) {
// Mirror, 180 degrees
BitBoard mirror180 = new BitBoard(mirror90);
mirror180.rotate();
fixedCount++;
determineShifts(mirror180, boards);

// Mirror, 270 degrees
BitBoard mirror270 = new BitBoard(mirror180);
mirror270.rotate();
fixedCount++;
determineShifts(mirror270, boards);
}
}
}

// Check algorithm, by comparing the one-sided and fixed counts with those from Wikipedia
if (oneSidedCount != 60 || fixedCount != 216) {
throw new AssertionError("Wrong one-sided / fixed counts.");
}

// Check tiling finder, by seeing if the shape tiling mentioned in the question can be found
if (!findTiling(new byte[] { 18, 7, 5, 8, 11 }, false)) {
}

// Find all possible tilings of the shape
long start = System.currentTimeMillis();
int shapeTilings = 0;
for (byte i = 0; i < freeCount; i++) {
for (byte j = (byte)(i + 1); j < freeCount; j++) {
for (byte k = (byte)(j + 1); k < freeCount; k++) {
for (byte l = (byte)(k + 1); l < freeCount; l++) {
for (byte m = (byte)(l + 1); m < freeCount; m++) {
if (findTiling(new byte[] { i, j, k, l, m }, false)) {
// Shape tiling possible, store it in a way which is convenient for later
BitSet bitSet = new BitSet(freeCount);
bitSet.set(i);
bitSet.set(j);
bitSet.set(k);
bitSet.set(l);
bitSet.set(m);
System.out.println(i + " " + j + " " + k + " " + l + " " + m);
shapeTilings++;
}
}
}
}
}
}
System.out.println("There are " + shapeTilings + " possible shape tilings (found in "
+ (System.currentTimeMillis() - start) / 1000 + " seconds)");

// Try to cover the entire range 0 .. 34 with parts for which a shape tiling exists
start = System.currentTimeMillis();
int step = 0, nextNumber = 0;
for (BitSet part : allParts.get(nextNumber)) {
usedBitSets[step] = part;
BitSet nextBitSet = (BitSet)part.clone();
// Find next not-covered number
nextCoverStep(nextBitSet, nextNumber, step + 1);
}
System.out.println("Cover search completed in " + (System.currentTimeMillis() - start) / 1000 + " seconds");
}

private static final int freeCount = 35; // found on Wikipedia
private static List<List<Board>> allBoards = new ArrayList<>();

private static List<List<BitSet>> allParts = new ArrayList<>();
private static BitSet[] usedBitSets = new BitSet[7];

private static boolean findTiling(byte[] tileNumbers, boolean showBoards) {
for (Board board0 : allBoards.get(tileNumbers[0])) {
Board boardAfter0 = (Board)board0.clone();
for (Board board1 : allBoards.get(tileNumbers[1])) {
if (board1.intersects(boardAfter0))
continue;
Board boardAfter1 = boardAfter0.union(board1);
for (Board board2 : allBoards.get(tileNumbers[2])) {
if (board2.intersects(boardAfter1))
continue;
Board boardAfter2 = boardAfter1.union(board2);
for (Board board3 : allBoards.get(tileNumbers[3])) {
if (board3.intersects(boardAfter2))
continue;
Board boardAfter3 = boardAfter2.union(board3);
for (Board board4 : allBoards.get(tileNumbers[4])) {
if (!board4.intersects(boardAfter3)) {
if (showBoards) {
System.out.println(board0);
System.out.println(board1);
System.out.println(board2);
System.out.println(board3);
System.out.println(board4);
}
return true;
}
}
}
}
}
}
return false;
}

private static void determineShifts(BitBoard bitBoard, List<Board> boards) {
Board board = new Board(bitBoard);
Board newBoard = board;
while (newBoard != null) {
Board newBoard2 = newBoard;
while (newBoard2 != null) {
if (!newBoard2.intersects(Board.SHAPE_TEMPLATE))
// Shift down
newBoard2 = newBoard2.shiftDown();
}
// Shift right
newBoard = newBoard.shiftRight();
}
}

private static void nextCoverStep(BitSet currentBitSet, int currentNumber, int step) {
int nextNumber = currentBitSet.nextClearBit(currentNumber + 1);
if (nextNumber == freeCount) {
// Complete tiling found, print it
for (int i = 0; i < 7; i++) {
System.out.println(usedBitSets[i]);
findTiling(getIndices(usedBitSets[i]), true);
}
return;
}
// Try all parts (for which a tiling has been found) containing the next free number
for (BitSet part : allParts.get(nextNumber)) {
if (part.intersects(currentBitSet))
continue;
usedBitSets[step] = part;
BitSet nextBitSet = (BitSet)currentBitSet.clone();
nextBitSet.or(part);
nextCoverStep(nextBitSet, nextNumber, step + 1);
}
}

private static byte[] getIndices(BitSet bitSet) {
byte[] indices = new byte[5];
int k = 0;
for (int j = bitSet.nextSetBit(0); j != -1; j = bitSet.nextSetBit(j + 1)) {
indices[k++] = (byte)j;
}
return indices;
}

/**
* Mutable board, storing everything as a boolean (so less efficient).
*/
static class BitBoard {
public BitBoard() {
board = new boolean[6][6];
}

public BitBoard(BitBoard bitBoard) {
boolean[][] newBoard = new boolean[6][6];
for (int row = 0; row < 6; row++) {
System.arraycopy(bitBoard.board[row], 0, newBoard[row], 0, 6);
}
board = newBoard;
}

private final boolean[][] board;

public void set(int row, int column) {
board[row][column] = true;
}

public boolean get(int row, int column) {
return board[row][column];
}

/**
* Rotates the board 90 degrees clockwise, and shifts the contents towards the origin.
*/
public void rotate() {
// Create temporary board
boolean[][] temporaryBoard = new boolean[11][11];

// Rotate
for (int y = 0; y < 6; y++) {
for (int x = 0; x < 6; x++) {
temporaryBoard[y][x] = board[5 - x][y];
}
}

// Determine shift values
int minX = -1, minY = -1;
for (int y = 0; y < 6; y++) {
for (int x = 0; x < 6; x++) {
if (temporaryBoard[y][x]) {
minY = y;
break;
}
}
if (minY != -1)
break;
}
if (minY == -1)
return; // empty board, so no changes
for (int x = 0; x < 6; x++) {
for (int y = 0; y < 6; y++) {
if (temporaryBoard[y][x]) {
minX = x;
break;
}
}
if (minX != -1)
break;
}

// Shift and copy to main board
for (int y = 0; y < 6; y++) {
for (int x = 0; x < 6; x++) {
board[y][x] = temporaryBoard[y + minY][x + minX];
}
}
}

/**
* Mirrors the board along the main diagonal.
*/
public void mirror() {
for (int x = 0; x < 6; x++) {
for (int y = x + 1; y < 6; y++) {
boolean temp = board[y][x];
board[y][x] = board[x][y];
board[x][y] = temp;
}
}
}

@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (int y = 0; y < 6; y++) {
for (int x = 0; x < 6; x++) {
builder.append(board[y][x] ? 'X' : '.');
}
builder.append('\n');
}
return builder.toString();
}

@Override
public boolean equals(Object object) {
if (this == object)
return true;
if (!(object instanceof BitBoard))
return false;
for (int y = 0; y < 6; y++) {
for (int x = 0; x < 6; x++) {
if (board[y][x] != ((BitBoard)object).board[y][x])
return false;
}
}
return true;
}
}

/**
* Immutable board, stored in the most efficient way.
*/
static class Board implements Cloneable {
public Board(BitBoard bitBoard) {
rows = new byte[6];
for (int y = 0; y < 6; y++) {
for (int x = 0; x < 6; x++) {
if (bitBoard.get(y, x)) {
rows[y] += (1 << x);
}
}
}
}

private Board(byte[] rows) {
this.rows = rows;
}

private final byte[] rows;

public static final Board SHAPE_TEMPLATE = new Board(new byte[] { 7, 3, 1, 0, 0, 0 });

/**
* Returns a board where everything is shifted one position to the right
*
* @return <code>null</code> if right shift is not possible.
*/
public Board shiftRight() {
byte[] newRows = new byte[6];
for (int row = 0; row < 6; row++) {
if (rows[row] >= 32)
// shift not possible
return null;
newRows[row] = (byte)(rows[row] * 2);
}
return new Board(newRows);
}

/**
* Returns a board where everything is shifted one position to the bottom
*
* @return <code>null</code> if right shift is not possible.
*/
public Board shiftDown() {
if (rows[5] != 0)
// shift not possible
return null;
byte[] newRows = new byte[6];
for (int row = 1; row < 6; row++) {
newRows[row] = rows[row - 1];
}
return new Board(newRows);
}

/**
* Check if two boards have a set bit in common.
*/
public boolean intersects(Board board) {
for (int row = 0; row < 6; row++) {
if ((rows[row] & board.rows[row]) != 0)
return true;
}
return false;
}

/**
* Overlays another board (but does not check for possible intersection).
*/
public Board union(Board board) {
byte[] newRows = new byte[6];
for (int row = 0; row < 6; row++) {
newRows[row] = (byte)(rows[row] | board.rows[row]);
}
return new Board(newRows);
}

@Override
public Object clone() {
byte[] newRows = new byte[6];
System.arraycopy(rows, 0, newRows, 0, 6);
return new Board(newRows);
}

@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (int y = 0; y < 6; y++) {
for (int x = 0; x < 6; x++) {
builder.append((rows[y] & (1 << x)) != 0 ? 'X' : '.');
}
builder.append('\n');
}
return builder.toString();
}
}
}

• (before you ask: I was too lazy to write those nested loops recursively) Commented Dec 17, 2017 at 23:05