14
$\begingroup$

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): Hexomino shapes are to be arranged, in groups of five, into seven shapes congruent to this one.

Sample shape

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.

$\endgroup$
  • 1
    $\begingroup$ In theory you could do anything without a computer $\endgroup$ – Meet Taraviya Dec 12 '17 at 13:28
  • $\begingroup$ 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. $\endgroup$ – Peter Taylor Dec 12 '17 at 13:39
  • $\begingroup$ 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. $\endgroup$ – BmyGuest Dec 17 '17 at 20:35
  • 1
    $\begingroup$ 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. $\endgroup$ – theonetruepath Dec 18 '17 at 0:09
  • 1
    $\begingroup$ 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. $\endgroup$ – theonetruepath Dec 18 '17 at 0:14
9
$\begingroup$

The 35 hexominos can be tiled like this:

hexomino layout

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – BmyGuest Dec 17 '17 at 20:29
  • $\begingroup$ 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! $\endgroup$ – BmyGuest Dec 17 '17 at 20:31
  • $\begingroup$ 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. $\endgroup$ – M Oehm Dec 17 '17 at 20:35
  • $\begingroup$ 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... $\endgroup$ – BmyGuest Dec 17 '17 at 20:37
  • $\begingroup$ @BmyGuest: My approach is a bit piecemeal. Do you think details of how each step was solved should go into the answer? $\endgroup$ – M Oehm Dec 17 '17 at 20:48
5
$\begingroup$

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<>();
            allBoards.add(boards);
            allParts.add(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)) {
            throw new AssertionError("Shape tiling not found.");
        }

        // 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);
                                allParts.get(i).add(bitSet);
                                allParts.get(j).add(bitSet);
                                allParts.get(k).add(bitSet);
                                allParts.get(l).add(bitSet);
                                allParts.get(m).add(bitSet);
                                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))
                    boards.add(newBoard2);
                // 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();
        }
    }
}
$\endgroup$
  • $\begingroup$ (before you ask: I was too lazy to write those nested loops recursively) $\endgroup$ – Glorfindel Dec 17 '17 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.