Air bags and the Lighthouse puzzle

Peg and I were visiting my Uncle Gerry in Marietta, Ohio the other day and he showed us a puzzle. It has nine square cards. The object is to arrange them in a 3 x 3 matrix such that the pictures on the cards line up with each other. Below is a picture of the cards. You can see that there are four different lighthouses, one made of brick, one with a spiral pattern, one with a ring or circle pattern and one with a diamond pattern. Each card has four pictures, each of either the top or bottom of one of the four lighthouses. Again, the object is to get the pictures to line up anywhere two cards abut.

Gerry and his kids and grandkids solved the puzzle, apparently after grinding on it for quite a while. It was the sort of thing that I looked at and thought, "how hard could this be?" The answer is "pretty hard".

Now, I am not much for puzzle solving, but I do enjoy programming and I thought this might be fun to work on. It so happens that I am in the midst of learning a new language, Python, because I want to do some projects using the Raspberry Pi single-board computer and Python is one of the most commonly used languages on that platform. Because of its design Python is not ideal for a compute-heavy project like this but as I said, I wanted some practice with it. There is so much processing though, I wrote the program on my desktop computer rather than a Raspberry Pi because a desktop is hundreds of times faster.

The way I figured to solve it is by brute force, that is, try every possible combination until I found the right one. The first thing I did was write some code to produce every possible permutation of the arrangement of the nine cards. That is, ignoring for the moment which edge of the card is up, but rather just every arrangement of which card goes in which position in the 3 x 3 matrix. There are, as it turns out 9! permutations. For those of you not familiar, that is not pronounced

9!

but rather "nine factorial" and is 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 362,880

For each of those 362,880 arrangements I then had to try every combination of how each card could be turned. That is to say, each card can be turned one of four ways. That gives 4 raised to the 9th power or 262,144 possibilities for each of the 362,880 card orderings or 95,126,814,720 possibilities.

At the speed of my computer, and the speed of the program I wrote, it would take about nine days to go through every combination. On average one would expect it to take about half that time but one never knows. My greatest concerns were two. First, I might have made a mistake in the program such that it didn't recognize a solution when it saw it, or two, Microsoft sends out some update and reboots my computer in the middle of the night.

Well, after 34 hours and 23 minutes, and on the 14,943,633,829th try it found a solution. If a human tried to solve the puzzle this way, which of course he or she would not, and tried one permutation every second, it would have taken more than 473 years. And we were lucky. We had only gotten through 15.7% of the possibilities.

OK, so what's the point? You might say it takes the fun out of the puzzle, at least if you like solving puzzles. I think the take-away is this. We all know computers are fast, but I think most of us don't realize how fast. A simple logic chip, available for about 10 cents, can switch in 7 nanoseconds. One nanosecond, a billionth of a second, is to one second as one second is to 30 years. Amazon will sell you a computer that runs at 3.5 billion cycles per second for less than $500. The import of this isn't that you can browse the web faster. Rather there is a whole new set of problem solutions, the Segway self balancing scooter, for instance. It detects when you are starting to fall over and moves the wheels to catch you. The computer is so fast that when it detects that you're falling over it has time to go to lunch, come back, call a meeting of the other computers, come up with several possible solutions, have the staff go away and research them and report back, and then decide which one works best and execute it, all before you realize you're falling. Fighter jets, like other airplanes, used to be designed so that they were stable in flight. The problem was that that stability made them slower to maneuver. Now they're intentionally made unstable, but the computer that the pilot uses to fly the plane detects deviations from the desired path and corrects for them so fast that the plane seems stable. Another example is this YouTube video showing a pair of quadcopters tossing a pole between them.

For computers, time moves so slowly that it requires a whole new mindset to even think of problems that can be solved this way. Air bags, Image stabilization in your camera, robots that can walk over uneven ground, compensation for variations in feedstock diameter for 3d printers, self driving cars, a device that detects when an old person is going to fall and catches him. Endless.

Addendum: In discussing the result with my uncle I realized that using this method there would actually be four solutions, each equivalent. They would effectively be looking at the one solution from each of the four sides of the puzzle, or to put it another way, all the cards would be in exactly the same places but the puzzle would be turned 90, 180, and 270 degrees. Thus I guess finding a solution after trying 15.7% of the possibilities isn't that lucky after all.