7
\$\begingroup\$

Update: It seems that the original question at math.SE was solved, there should be no 23 pieces solution.

The original problem is stated here over at math.SE

The task is writing a program that fits 22 copies (or perhaps 23) of the following pentacube into a 5x5x5 cube (back and front view).

enter image description here

The pentacube must be placed within the grid (no 45° orientations and shifts of 0.5 etc.) of the big cube and can be rotated around any of the x,y,z axes in 90° steps.

Known up to now:

According to the math.SE question there is a solution for 22 pieces, but it is unknown whether there is a solution for 23 pieces. (24 again seems to be impossible).

Winning criteria

Rotatation and mirroring of one solution count all as the same solution. Finding all solutions means that the program must show that the solutions provided are really all possible solutions. You will get (points will add up)

  • 10 points for finding any 22 piece solution
  • 20 points for finding two or more 22 piece solutions
  • 50 points for finding all 22 piece solution
  • 100 points for finding a 23 piece solution
  • 200 points for finding two or more 23 piece solutions
  • 500 points for finding all 23 piece solutions or showing that there is no 23 piece solution
  • 1 point per vote

If two people have the same amount of points the one that postet first will win. Please explain your approach and show the solution/s (at least one if there is one.) Please also include your score (except votes) and the runtime in your answer. I discourage hardcoding answers. If you find solutions 'by hand' or if you find a mathematical proof you can also submit them, but please state this explicitly if you do so.

UPDATE: In the original post in math.SE now 64 solutions for 22 pieces have been found (non exhausive, and perhaps some of them are rotations/mirrorings of others). So I discourage just copying these solutions - but as long as you found them on your own this is ok!

\$\endgroup\$
  • \$\begingroup\$ Thank you for pointing out all ambiguities! I'd also accept a mathematical proof or a packing that was found by hand, since the primary goal is solving the problem=) So I think the ouput 'format' should not be restricted. \$\endgroup\$ – flawr Aug 15 '14 at 22:49
  • \$\begingroup\$ That is a nice idea thank you again. (But I think it is unlikely that a tiebreaker will be needed.) \$\endgroup\$ – flawr Aug 15 '14 at 22:55
  • \$\begingroup\$ do you have any specific wish on how to visualise the solutions? \$\endgroup\$ – John Dvorak Aug 16 '14 at 6:34
  • 1
    \$\begingroup\$ Is it 20 points for finding a second 22-piece solution (cumulative with the 10 for the first), or 10 additional points for the second giving a total of 20? \$\endgroup\$ – Peter Taylor Aug 16 '14 at 12:31
  • 1
    \$\begingroup\$ It is adding up, so if you got two 22 piece solutions you will earn at least 30 points. \$\endgroup\$ – flawr Aug 16 '14 at 14:15
6
\$\begingroup\$

Plane-based analysis, 30+ points

The basic idea is explained in the comment at the top of the class. This runs for about 8 minutes on my desktop and finds 90560 22-tile solutions, possibly including symmetrical ones; since a cube has only 48 isometries, that corresponds to at least 1887 distinct solutions. However, it doesn't guarantee that there are no more: only that if there are any more, they don't have two opposite exterior faces which contain 3 cubies each of 8.

Two sample solutions:

ddbee dubb. ruut. rlktt llkk. 
adbbe aduee rrutt lrkjj lookj 
aa.ff qa.f. .q.vv ioov. iiojj 
ggchf qgcfh qqssv impnv mipnn 
gcchh gcssh ...s. .m.pn mmppn 


.ggff qqgf. .q.uu .llpu oolpp 
bgddf bgvdf qqvu. ooiup ollip 
bbdee rbdve rrvv. .mijj mmiij 
hhcea rhcae .rstt kmsnt mknjj 
hccaa hc.a. .sst. ks.nt kknn.

Checking for 23-tile solutions with the same principle is a matter of changing tilesInPlane2 to 7; it runs for about one minute and finds no solutions.

I suggest redirecting stdout to a file and watching the progress reports on stderr.

import java.util.*;

// Overall approach follows a strategy proposed by Ed Pegg.
// If we place one 8-tile board on plane 0 sticking into plane 1,
// and one 8-tile board on plane 4 sticking into plane 3,
// what can fit into plane 2 sticking into planes 1 and 3?
// Since an 8-tile plane occupies at least 16/25 of the adjacent plane, we're looking to fit 4/7 of the tiles from
// plane 2 into the gaps left by the tiles from plane 0, and then the remaining 3/7 into the gaps left
// by the tiles from plane 4.
public class CodeGolf36250 {
    // Bit mask: 25 bits indicating the "main" plane, 25 bits indicating the "adjacent" plane
    static final long mainPlane = (1L << 25) - 1;
    static final long adjPlane = ((1L << 25) - 1) << 25;

    static final int tilesInPlane2 = 6;
    static final int tilesInPlanes2_3 = (tilesInPlane2 + 1) / 2; // Half rounded up

    public static void main(String[] args) {
        Set<Long> primitives = new HashSet<Long>();
        for (int x = 0; x < 4; x++) {
            for (int y = 0; y < 4; y++) {
                int tl = x + y * 5;
                // We consider only positions where we put 3 cubies in the main plane and 2 in the adjacent plane.
                // Diagram format: main plane, adj plane
                // So we have
                //  c000 c100   c001 c101
                //  c010 c110   c011 c111
                long c000 = 1L << tl, c100 = c000 << 1, c010 = c000 << 5, c110 = c100 << 5;
                long c001 = c000 << 25, c101 = c100 << 25, c011 = c010 << 25, c111 = c110 << 25;
                // ##  .#  |  ##  #.  |  #.  #.  |  .#  .#
                // #.  #.  |  .#  .#  |  ##  .#  |  ##  #.
                primitives.add(c000 + c100 + c010 + c101 + c011);
                primitives.add(c000 + c100 + c110 + c001 + c111);
                primitives.add(c000 + c010 + c110 + c001 + c111);
                primitives.add(c100 + c010 + c110 + c101 + c011);
                // ##  .#  |  ##  ..  |  ##  #.  |  ##  ..
                // #.  .#  |  #.  ##  |  .#  #.  |  .#  ##
                primitives.add(c000 + c100 + c010 + c101 + c111);
                primitives.add(c000 + c100 + c010 + c011 + c111);
                primitives.add(c000 + c100 + c110 + c001 + c011);
                primitives.add(c000 + c100 + c110 + c011 + c111);
                // #.  .#  |  #.  ##  |  .#  #.  |  .#  ##
                // ##  .#  |  ##  ..  |  ##  #.  |  ##  ..
                primitives.add(c000 + c010 + c110 + c101 + c111);
                primitives.add(c000 + c010 + c110 + c001 + c101);
                primitives.add(c100 + c010 + c110 + c001 + c011);
                primitives.add(c100 + c010 + c110 + c001 + c101);
            }
        }

        // Building full sets of tiles in the two planes uses far too much memory in the intermediate numbers
        // (in particular, the 5-tile sets).
        // It's much more efficient to see what coverings of the main plane we get and then for the high-count
        // sets we care about, to expand them to the adjacent plane.
        List<Set<TileSet>> nTiles = new ArrayList<Set<TileSet>>();
        nTiles.add(new HashSet<TileSet>()); // 0 tiles
        nTiles.get(0).add(new TileSet());
        for (int n = 1; n < 9; n++) {
            Set<TileSet> next = new HashSet<TileSet>();
            for (TileSet board : nTiles.get(n - 1)) {
                for (long prim : primitives) {
                    if ((board.sum & prim) == 0) {
                        TileSet newBoard = new TileSet();
                        newBoard.addAll(board);
                        newBoard.add(prim & mainPlane);
                        next.add(newBoard);
                    }
                }
            }
            nTiles.add(next);
            System.err.println(n+" tiles: " + next.size());
        }

        // Needed for the expansion.
        Map<Long, Set<Long>> primsByMainPlane = new HashMap<Long, Set<Long>>();
        for (Long prim : primitives) {
            Set<Long> group = primsByMainPlane.get(prim & mainPlane);
            if (group == null) primsByMainPlane.put(prim & mainPlane, group = new HashSet<Long>());
            group.add(prim);
        }

        Map<Long, Set<TileSet>> boards8ByAdjGaps = new HashMap<Long, Set<TileSet>>();
        for (TileSet board8 : nTiles.get(8)) {
            for (TileSet expandedBoard8 : expand(board8, primsByMainPlane)) {
                long expansion = (~expandedBoard8.sum) & adjPlane;
                Set<TileSet> boards8 = boards8ByAdjGaps.get(expansion);
                if (boards8 == null) boards8ByAdjGaps.put(expansion, boards8 = new HashSet<TileSet>());
                boards8.add(expandedBoard8);
            }
        }
        System.err.println(boards8ByAdjGaps.size() + " distinct gap sets in plane next to full one");

        long solutions = 0;
        int progress = 0;
        for (TileSet board : nTiles.get(tilesInPlane2)) {
            // Each board is only expanded once, but we don't keep them all around so we save a lot of memory
            for (TileSet plane2 : expand(board, primsByMainPlane)) {
                for (Map.Entry<Long, Set<TileSet>> plane0 : boards8ByAdjGaps.entrySet()) {
                    solutions += countSolutions(plane0.getKey(), plane0.getValue(), plane2, boards8ByAdjGaps);
                }
            }

            progress++;
            // Progress reports are always good for long processes...
            if (progress % 1000 == 0) System.err.println("Progress: " + progress + "; solutions: " + solutions);
        }
    }

    private static Set<TileSet> expand(TileSet board, Map<Long, Set<Long>> primsByMainPlane) {
        Set<TileSet> bexps = new HashSet<TileSet>();
        bexps.add(new TileSet());
        for (Long tileBase : board) {
            Set<TileSet> nextBexps = new HashSet<TileSet>();
            for (TileSet bexp : bexps) {
                for (Long texp : primsByMainPlane.get(tileBase)) {
                    if ((bexp.sum & texp) == 0) {
                        TileSet nextBexp = new TileSet();
                        nextBexp.addAll(bexp);
                        nextBexp.add(texp);
                        nextBexps.add(nextBexp);
                    }
                }
            }
            bexps = nextBexps;
        }
        return bexps;
    }

    private static int countSolutions(long gaps1, Set<TileSet> planes0, TileSet plane2, Map<Long, Set<TileSet>> boards8ByAdjGaps) {
        int solutions = 0;
        int fitTiles = 0;
        long unfitTiles = 0;
        for (Long tile : plane2) {
            if ((tile & adjPlane) == (tile & gaps1)) fitTiles++;
            else unfitTiles |= tile;
        }

        if (fitTiles >= tilesInPlanes2_3) {
            for (Map.Entry<Long, Set<TileSet>> planes4 : boards8ByAdjGaps.entrySet()) {
                long gaps3 = planes4.getKey();
                if ((unfitTiles & adjPlane) == (unfitTiles & gaps3)) {
                    // The Cartesian product of planes0 and planes4.getValue() are all solutions with the same
                    // plane2
                    for (TileSet plane4 : planes4.getValue()) {
                        for (TileSet plane0 : planes0) {
                            printSolutions(plane0, plane2, unfitTiles, plane4);
                            solutions++;
                        }
                    }
                }
            }
        }

        return solutions;
    }

    private static void printSolutions(TileSet plane0, TileSet plane2, long unfitTiles, TileSet plane4) {
        char[][][] cube = new char[5][5][5];
        // plane0's main plane is 0
        char tileName = 'a';
        for (Long tile : plane0) {
            populatePlane(cube[0], tile & mainPlane, tileName);
            populatePlane(cube[1], tile >> 25, tileName);
            tileName++;
        }
        for (Long tile : plane4) {
            populatePlane(cube[4], tile & mainPlane, tileName);
            populatePlane(cube[3], tile >> 25, tileName);
            tileName++;
        }
        for (Long tile : plane2) {
            populatePlane(cube[2], tile & mainPlane, tileName);
            // The tricky bit: up or down? We look to unfitTiles.
            populatePlane(cube[(unfitTiles & tile) == 0 ? 1 : 3], tile >> 25, tileName);
            tileName++;
        }

        // Print as plane0 plane1 plane2 plane3 plane4
        for (int y = 0; y < 5; y++) {
            for (int z = 0; z < 5; z++) {
                for (int x = 0; x < 5; x++) {
                    System.out.print(cube[z][y][x] == 0 ? '.' : cube[z][y][x]);
                }
                System.out.print(' ');
            }
            System.out.println();
        }
        System.out.println();
        System.out.println();
    }

    private static void populatePlane(char[][] plane, long values, char tile) {
        for (int x = 0; x < 5; x++) {
            for (int y = 0; y < 5; y++) {
                if ((values & (1 << (x + 5*y))) != 0) {
                    if (plane[y][x] != 0) throw new IllegalStateException("Collision!");
                    plane[y][x] = tile;
                }
            }
        }
    }

    static class TileSet extends HashSet<Long> {
        private long sum = 0;

        @Override
        public boolean add(Long val) {
            if ((val & sum) != 0) throw new IllegalArgumentException();
            sum |= val;
            return super.add(val);
        }
    }
}
\$\endgroup\$

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.