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.|
Here are the eight pieces:
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.
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×47 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
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.