# 3D Edge matching puzzle generation

I have this weird idea for a puzzle/toy (or torture device, depending on how you look at it) I've been trying to make for years now. I happen to be worse at this kind of math as I thought; and I'd be delighted to get some help.

This puzzle is made of 64 cubes, with a peg or hole on each side (such as, you can connect them like Lego bricks). These pegs and holes have different shapes, call them, if you will, symbols (just bear in mind there's an "up" and "down" symbol pair on each connection). The goal of the puzzle is simple, build a solid $$4\times 4\times 4$$ cube, with no gaps in it.

The problem is, how can I generate a set of these cubes with a low number of possible solutions (Ideally just 1), while using the fewest amount of symbols?

P.S. Sorry if there was some weird grammar or tone here, I'm not a native speaker.

• Interesting question. Do you want the faces on the boundary of the big cube to be flat or to have unused pegs/holes? May 17, 2021 at 4:26
• I do want the faces on the boundary to have pegs and holes, due it's toy-like features (being able to build shapes, other than the intended solution). May 17, 2021 at 4:34
• If you are willing to ask a superior being for help, I'd first see what you get by starting from unique pegs, and joining randomly until a SAT solver reports two solutions after any additional peg joining. May 17, 2021 at 6:13
• Along the lines of Ville Salo's comment, see Marijn Heule's paper Solving edge-matching problems with satisfiability solvers. May 18, 2021 at 1:20
• If you take just one symbol with rotational symmetry of order 2 then there are 224 distinct cubes which can be made. A possible approach would be to assign symbol orientation and tab/slot at random to each of the 144 internal face pairs of the assembled $4\times 4\times 4$ puzzle; verify that the fully internal cubes are distinct; use bipartite matching to assign symbols to the external faces such that you get distinct cubes and no two corner cubes are interchangeable, and then try to verify the absence of phantom solutions with a SAT solver. May 19, 2021 at 13:44