Cool Circuits

I came across a particular kind of puzzle, the design of which is really fascinating to me.

I wanted to get my son some electronics toys for his last birthday.  I had one of those 100-in-1 electronics kits when I was a kid but he's still a bit young for the complex wiring, or at least that's what I thought.  I ended up picking Snap Circuits, which he loves.  I had to pick one more thing because you never know with kids, it's safer to get a couple of smaller things than one big one, so I tossed in Cool Circuits, because it had a similar name, and I think Amazon suggested it or something.  He also loved that one.  It's not really about electronics, it's just a puzzle game, but I've come to realize it's a very cleverly-made one.

A cool circuit in progress.

Here's how it works: the board has 25 pegs, arranged in a kind of diagonal grid.  There are 8 serpentine pieces which can fit in between the pegs, and each has a unique shape.  For each puzzle you are given some constraints (e.g. part of the circuit must travel along this path) and you must put the pieces on the board in a way that meets the constraints.  The one universal constraint is that the pieces must form a single loop.  In the toy, that triggers some mechanism which lights up the board and plays some music, but I've found that feature to be pretty finicky.

It's pretty tough to make a circuit from scratch, so the constraints tend to help more than hurt, and the more of them there are the easier the puzzle.

At first I thought the shapes of the pieces were arbitrary, but there's a mathematical beauty and completeness to them that took some pondering to discover.

As a font, it would not be easy to read.

Each piece is made of a sequence of five quarter-circles.  The manual describes them as "J", "U", "V", "E", "N", "I", "L", and "S".  So if you're looking at a given piece, starting from one end, you might describe it by listing the chirality of each segment.  For instance the "V" piece would be: turn right, left, left, right, left.  Or maybe clockwise, counter-clockwise, etc..  But that's a terrible description because the same piece would be described differently if you started from the other end, or flipped it over.

Math!

We can normalize the description for flipping by listing not the turns themselves, but the changes.  So if it starts out in one direction, we just say whether the next turn is the same as the previous one or different.  The "V" piece would then be different-same-different-different.  Now imagine same as 0 and different as 1 (e.g. 1011).  Each piece is described by four bits.  But some pieces have a different description if we start from the other end.  To correct for that, for each piece we'll pick the description that has the smallest number when treated as binary.

Here are the eight pieces:

Letter	Description	Flipped
J	0011	1100
U	1001	(same)
V	1011	1101
E	0110	(same)
N	0101	1010
I	1111	(same)
L	0111	1110
S	0010	0100

In this scheme, you can't have three zeros in a row, because that would make the piece intersect itself.  So 0000, 0000, and 1000 are out.  That means every workable bit sequence is represented.  These aren't arbitrary shapes at all, it's all possible unique shapes of length 5!  At length 4, there are 6 possible pieces.  At length 6, there would be 15.

All possible locations for the first piece.
Testing just the blue ones is enough.

So how many circuits are there? Let's start with an upper bound. For now let's say the first piece we put down can go in any point, in any direction, flipped or not. There are 224 possible first points (red and blue arrows in the diagram to the right).  However, some of those are equivalent to one another, because we could just rotate or "flip" the board itself.  So we'll cut that down to 28 (blue arrows only).

Suppose each piece can fit two ways at one of the blue arrows.  Actually, some pieces fit fewer ways than that, and sometimes they won't fit at all, but let's not work out those details yet.  After that first piece, we choose a next piece and fit it on in one of four ways.  This overestimated upper bound says there are fewer than 28×8!×2×4⁷ paths (36,993,761,280). That's pretty high.  Luckily, many of the paths terminate quickly, either running off the board or crossing and earlier section of the path, so we're not going to need to search them all just to find the complete circuits.

I wrote a program to brute force all the paths.  It found 17,473 paths, starting from those blue-arrow positions, that used all 8 pieces without self-intersection or running off the board.  Of those, 1,520 ended up where they started, forming (possibly cool) circuits.

We're overcounting with that number though, because for any given unique solution, we're seeing it 16 different ways (counting reflection and cycling through the 8 pieces as starting pieces).  Now I very well may have made a mistake (or several) here, but I think the final answer, the number of unique solutions to this puzzle, the number of Cool Circuits, is 95 (no, see UPDATE below).

Cool Circuits at ScienceWiz

Solver Source Code

UPDATE 4/27: I found a mistake.  I didn't account for some solutions that fit so tightly that they leave four empty pegs all along one side of the board.  Those solutions are double counted in my initial number because they can be translated into another solution.  I was accounting for rotation and reflection, but not translation.  There are apparently 11 solutions like that, so my final answer (today) is 84.