Puzzle Passion Powers Research Paper

Fern, kiwi, map,  ­sheep, NZ. And… go.

Keith Brandt, Ph.D., professor of mathematics at Rockhurst University, knows those themes well – they’re the keys to the so-called “New Zealand puzzle.”

In the newest issue of British-based mathematical education journal “Mathematical Spectrum,” Brandt details how he and an undergraduate student spent months developing and refining computer programs that would be able to solve the New Zealand puzzle – according to the box, it’s one of the world’s hardest puzzles, with millions of potential placements. Then they set out to make it harder.

It’s a process that started when Brandt received the New Zealand puzzle as a gift from a friend. The concept of the puzzle is simple – place tiles containing the five different themes on the four-by-four printed grid in the bottom of the box such that no two identical tiles are placed next to each other or atop an identical spot on the bottom of the printed grid.

“I fiddled with it off and on for a couple of years,” he said. “The challenge of this puzzle is that there are just too many things to try.”

By Brandt’s own calculations, there are 1.407 times 10 to the 22nd power possible ways a player could set the pieces on the board. So Brandt, whose interests have ranged from computer programming to combinatorics (the study of finite patterns), approached solving the puzzle as a research opportunity. He enlisted the help of Serge Nevsky, ’12, who at the time was looking for ways to marry his passion for computer science to his education.

“I tried to take a tech-oriented approach to as many of my classes as I could,” Nevsky said. “Still, I never had an opportunity to write a useful program. So when Dr. Brandt offered a project to solve the puzzle with a computer, I happily jumped on the opportunity.”

Nevsky said they would brainstorm ways to program a computer to solve the puzzle separately, then meet periodically to share and try out their ideas and hash out what worked and what didn’t over coffee.

Both worked in programming language Python for the first time for the project, and through a lot of troubleshooting and trial and error developed a program that could run simulations of the puzzle in about five minutes to find a solution.

After finding the first solution, Nevsky and Brandt found there were more than 14,000 additional solutions to the original puzzle.

“We were shocked by that,” Brandt said.

It the opening of the proverbial Pandora’s box, Brandt said.

“The more familiar we became with the puzzle, the more enticing it became to think bigger and to solve more difficult problems in the same vein,” Nevsky said.

Adding more variables, like another one of each of the theme tiles or more spaces on the grid, made solving more difficult and added more potential solutions. So Brandt and Nevsky devised more programs that would not only solve iterations of the puzzle, but be able to come up with new variations on the board according to those additional criteria. Another program culled the new variations to remove any fundamentally identical boards. All told, Nevksy and Brandt discovered 950 unique new arrangements for the New Zealand puzzle.

The pair enlisted the help of John Koelzer, Ph.D., emeritus professor of mathematics, to run programs day and night on different computers in order to cut down the amount of time needed to find all of the solutions.

“We had an exciting week or so where we divided up the boards and ran the programs constantly,” Brandt said.

Eventually, they came up with a list of every possible solution to every possible board of the New Zealand puzzle. Brandt said the experience was a fun exercise, but one that illustrates the importance of recursive backtracking programs, which are commonly used to solve problems in computer science. Brandt said similar concepts could be used to solve large-scale problems like managing air traffic for airports or telecommunications companies managing call loads on cellular towers.

“There’s tons of situations where’s there’s just too much information and it would just take too long for humans to calculate it by hand,” Brandt said.

The project also gave Brandt ­– and Nevsky, who used the research as the basis for a senior research project and who draws on the experience in his current career as a software engineer – an inside look at the process of solving those complex problems, piece by piece.