Button Board Solution

Voice Card  -  Volume 11  -  John Card Number 7  -  Sat, Dec 16, 1989 5:48 PM

As promised, here is the solution to the Amazing Button Board puzzle in last issue's Mr. Wizard.

To gain entry to his office, Professor Norgate usually pushes the buttons shown in the diagram at left.

"The puzzle is derived from an interesting and more general problem, called The All Ones Problem, studied by Klaus Sutner at the Stevens Institute of Technology in Hoboken, N.J.

"Sutner has shown that the problem has a solution for any n x n buttonboard. But he has gone much further than this. Replace the square lattice of adjacent buttons by any adjacency pattern whatever!

"Even in this general setting one can always find a solution. What is the minimum number of buttons one must press to turn on all the lights? Sutner has shown that this problem is computationally "hard". This means that we are unlikely ever to find an algorithm to solve such problems in a reasonable amount of time: one might as well go ahead and try every possible combination."

The above comments were taken from a newsletter called "Algorithm." Those of you who hadn't already solved the puzzle may want to return to the buttonboard and see what happens when the correct buttons are pushed!