Math major’s digital version of a classic puzzle hits the big time
William & Mary math student Robert Torrence is shedding some light on a decades-old game that continues to puzzle thousands each year.
Torrence ’15, along with his father Bruce Torrence, Garnett Professor of Mathematics at Randolph-Macon College, created an algorithm to solve larger and more challenging digital versions of the electronic game Lights Out, created in 1995 by Tiger Toys.
The New York Times recently published Torrence’s version to the game in Wordplay, the paper’s crossword blog section. Wordplay features a math-related puzzle every week in an ongoing section called Numberplay.
The Times included an online version of Lights Out for readers to try for themselves and see if they could come up with Torrence’s solution. At the end of the week, the paper published Torrence’s solution and explanation.
Lights Out is a game consisting of a network of switches that when turned on or off affect neighboring switches. Torrence explained that his puzzle was based on the generalized Petersen graph. The game consists of an inner and outer layer of switches. Players win the game by selecting the pattern of switches that will turn all the lights out in the smallest number of moves.
A quick search online offers strategies for a smaller 5x5 version, but Torrence realized no one had proved solutions to more complicated versions of the game. After studying the algorithm for the 5x5 game, Torrence and his father found a strategy that seemed to work for any initial set up of the game and more complicated versions as the number of switches increased. The next challenge was to prove that their solution could work for more complicated set-ups.
“A really good way of going about things sometimes in research is to discover an intuition for something, believe it’s true, and then once you think something’s true, developing a proof is a lot easier,” said Torrence.
Torrence and his father came up with what they call the “in-out” strategy. For the mathematically literate, here’s what they did: By moving all the lights either to the inner or outer ring and repeating the process four times, every solvable puzzle on the P(12,5) graphs can be solved. Torrence also noticed the puzzle worked on any solvable P(2n, n) graph, where 2n is the number of vertices in a Petersen graph with n vertices in each inner or outer circle.
The Lights-Out puzzle was a challenge for even the educated audience. Many readers of the New York Times article stumbled through the puzzle, but one commenter, “D-ferg”, was able to independently produce the Torrence solution.
Torrence went further with this discovery by proving that if you can solve the puzzle, you can solve it by only clicking lights that are already on. He credited the amount of time he spent just playing the game and trying different strategies for his success.
“One of the main reasons this kind of mathematics is great is that it’s so accessible in the front end,” said Torrence, “and in the back it has some nice mathematics!”
