Blinkenlights (solution)

by C. Scott Ananian

This is a recursively-constructed 4-bit maze. The goal is to turn off all the big lightbulbs. Each group of four bits has the following state diagram:

We can also look at the minimum number of steps required to reach 0000 from every step, and the number of transitions from each bit which are required in this shortest path:

StateTransitionsMin. Path Length
00000/0/0/00
00100/0/1/01
01100/1/1/02
11101/1/1/03
10111/1/1/14
10011/1/1/14
01111/1/1/14
11111/1/1/14
11011/2/1/15
11001/2/1/15
10101/1/2/15
00111/1/2/26
10002/1/2/27
00012/1/2/38
01012/2/2/39
01002/2/2/39

In addition, every group of 4 of these 4-bit mazes acts as a larger instance of the same maze: If any light in the group of four is on, then that bit in the “meta-maze” is set. When a bit in the “meta-maze” turns on, then the four lights it corresponds to reset to a specific starting state.

Why end there? Each group of 4 “meta-mazes” is a meta-meta-maze, and each group of four “meta-meta-mazes” forms a “meta-meta-meta-maze”. All told, there are 256 lightbulbs, forming 4 “64-bit mazes”, each of which is composed of 4 “16-bit mazes”, each composed of 4 4-bit mazes. For future reference, we are going to call these “M4”, “M16”, “M64”, and “M256” mazes, with each “bit” in an M16 maze comprising a group of four lightbulbs, etc.

In addition, there are a series of small lamps beneath each group of 16 lightbulbs, which simply count up the number of “steps” taken in that group of 16. There is also a message displayed at the top of the maze, which reveals new letters whenever at least one light is illuminated in a group of 8.

Once the solver has clicked around enough to figure out the construction, they can get down to solving in earnest. Extinguishing all the lights in the maze would take 952 steps, but we can shortcut the process analytically. Given the reset state of each M4/M16/M64/M256 puzzle we can deduce the end state; however, not all of the reset states are initially visible! So some clicking around will be necessary to get each meta-bit, meta-meta-bit, and meta-meta-meta bit to turn on at least once so that we can determine their reset state.

To begin, we recognize the initial state of the M256 puzzle is 1100. In order to get the final two meta-meta-meta bits to illuminate (to determine their reset state), we need to make the 1100 -> 1011 transition in the M256 puzzle. In order to do this, we need to solve the M64 puzzle corresponding to the second meta-meta-meta-bit of the M256 puzzle. This M64 puzzle is also initially in the 1100 state, so we need to make the 1100 -> 1011 transition by solving an M16 puzzle. The M16 puzzle is *also* in the 1100 state, as is the M4 puzzle corresponding to its second meta-bit. So we begin by toggling the following lights to solve the M4 puzzle: AA, A8, AB, AA, A9.

Now the M16 puzzle is in the 1011 state, so we need to toggle its final bit to make the 1011 -> 1110 transition. This M4 puzzle is initially in the 1110 state, and we solve it by clicking on: A3, A2, A1.

We continue in this fashion, recursively exploring the maze. We will eventually discover the following construction:

Maze level Lightbulbs Starting
state
Solve
Transitions
# Solve Steps Times Maze
Solved
Final Step Counter Value
M25600 - FF11001/2/1/1951* 1
M64C0 - FF00012/1/2/3298* 1
M16F0 - FF11001/2/1/140* 2= 80 = P
M4FC - FF00012/1/2/38* 2
M4F8 - FB00012/1/2/38* 4
M4F4 - F700012/1/2/38* 2
M4F0 - F300012/1/2/38* 2
M16E0 - EF01002/2/2/365* 1= 65 = A
M4EC - EF00012/1/2/38* 2
M4E8 - EB00012/1/2/38* 2
M4E4 - E711101/1/1/03* 2
M4E0 - E301012/2/2/39* 3
M16D0 - DF11001/2/1/142* 2= 84 = T
M4DC - DF00012/1/2/38* 2
M4D8 - DB01002/2/2/39* 4
M4D4 - D700012/1/2/38* 2
M4D0 - D300012/1/2/38* 2
M16C0 - CF11111/1/1/123* 3= 69 = E
M4CC - CF10111/1/1/14* 3
M4C8 - CB11011/2/1/15* 3
M4C4 - C700111/1/2/26* 3
M4C0 - C300012/1/2/38* 3
M6480 - BF11001/2/1/1122* 2
M16B0 - BF11001/2/1/139* 2= 78 = N
M4BC - BF01012/2/2/39* 2
M4B8 - BB01002/2/2/39* 4
M4B4 - B701012/2/2/39* 2
M4B0 - B311101/1/1/03* 2
M16A0 - AF11001/2/1/121* 4= 84 = T
M4AC - AF10011/1/1/14* 4
M4A8 - AB11001/2/1/15* 8
M4A4 - A701111/1/1/14* 4
M4A0 - A311101/1/1/03* 4
M1690 - 9F11111/1/1/116* 2= 32 =
M49C - 9F11111/1/1/14* 2
M498 - 9B10111/1/1/14* 2
M494 - 9710011/1/1/14* 2
M490 - 9301111/1/1/14* 2
M1680 - 8F11001/2/1/125* 2= 50 = 2
M48C - 8F10101/1/2/15* 2
M488 - 8B11011/2/1/15* 4
M484 - 8711001/2/1/15* 2
M480 - 8310101/1/2/15* 2
M6440 - 7F11001/2/1/1200* 1
M1670 - 7F11001/2/1/144* 1= 44 = ,
M47C - 7F01002/2/2/39* 1
M478 - 7B01012/2/2/39* 2
M474 - 7701002/2/2/39* 1
M470 - 7300012/1/2/38* 1
M1660 - 6F11001/2/1/126* 2= 52 = 4
M46C - 6F11011/2/1/15* 2
M468 - 6B11001/2/1/15* 4
M464 - 6710101/1/2/15* 2
M460 - 6300111/1/2/26* 2
M1650 - 5F00111/1/2/249* 1= 49 = 1
M45C - 5F00111/1/2/26* 1
M458 - 5B10002/1/2/27* 1
M454 - 5701012/2/2/39* 2
M450 - 5301002/2/2/39* 2
M1640 - 4F10002/1/2/255* 1= 55 = 7
M44C - 4F01012/2/2/39* 2
M448 - 4B00100/0/1/01* 1
M444 - 4701002/2/2/39* 2
M440 - 4301012/2/2/39* 2
M6400 - 3F10002/1/2/2209* 1
M1630 - 3F11001/2/1/122* 2= 44 = ,
M43C - 3F11011/2/1/15* 2
M438 - 3B11001/2/1/15* 4
M434 - 3710101/1/2/15* 2
M430 - 3301100/1/1/02* 2
M1620 - 2F10002/1/2/255* 1= 55 = 7
M42C - 2F01002/2/2/39* 2
M428 - 2B00100/0/1/01* 1
M424 - 2701012/2/2/39* 2
M420 - 2301002/2/2/39* 2
M1610 - 1F11001/2/1/128* 2= 56 = 8
M41C - 1F11011/2/1/15* 2
M418 - 1B11001/2/1/15* 4
M414 - 1710101/1/2/15* 2
M410 - 1300012/1/2/38* 2
M1600 - 0F11001/2/1/127* 2= 54 = 6
M40C - 0F11011/2/1/15* 2
M408 - 0B11001/2/1/15* 4
M404 - 0710101/1/2/15* 2
M400 - 0310002/1/2/27* 2

The message at the top of the page, which is gradually revealed as light bulbs are turned on in groups of 8, will say: “SolveRestThenPluralizeTitleWord4”. If you’ve taken the shortest path to the final end state (when all the lights are extinguished), the small lightbulbs which count the number of steps for each M16 puzzle will spell out “PATENT 2,417,786” in ASCII at the end.

Patent 2,417,786 is the U.S. Patent for “Pocket Shield or Protector”, one of the first pocket protector patents. The pluralized fourth word of its title, and the answer to this puzzle, is therefore: PROTECTORS.

Betsy Johnson
Betsy Johnson