# Pieces of a polyomino puzzle.

Pieces of a polyomino puzzle

Polyominoes, which are the basis for thousands of mathematical puzzles, are shapes that cover connected squares on a checkerboard. One of the most intriguing of such puzzles involves proving that polyominoes of a certain shape can be laid down to form a complete rectangle. Recently, software engineer Karl A. Dahlke of AT&T Bell Laboratories in Naperville, Ill., combining perseverance with clever computer programming, managed to solve two particularly perplexing versions of this problem--ones that for nearly 20 years had defeated the best efforts of scores of amateur and professional mathematicians (SN: 9/20/86, p.186).

"I was amazed,' says mathematician Solomon W. Golomb of the University of Southern California in Los Angeles, who in 1954 introduced the term "polyomino.' Golomb has been exploring polyomino properties and proposing polyomino puzzles ever since. "A lot of very bright people have worked on [the problem],' he says. "This is a noteworthy accomplishment.'

Dahlke, who is blind, first learned of the puzzles earlier this year in an audio edition of SCIENCE NEWS. Dahlke spent several months working on the puzzles in his spare time. First, he tried proving that the problem has no solution. Because that approach didn't seem to lead anywhere, he started looking for an answer but kept running into dead ends. "I took so many different avenues,' he says.

Finally, Dahlke decided to program his personal computer to search for an answer systematically. Dahlke's computer is equipped with a speech synthesizer that converts the computer's output into sound. It took the addition of several programming tricks designed to circumvent time-consuming situations, in which the computer was trapped in endlessly repeating patterns, before Dahlke found his two minimum-area rectangles (see illustrations).

"It turns out that the size of the solutions is clearly a little bit beyond what people could easily do by hand,' says Golomb, "but fortunately, it's within the range of what you can find on a personal computer.'

"I'm no Einstein,' says Dahlke. "Maybe anyone with a micro, some perseverance and a little bit of geometric knowledge could have done it. But I did it, and it's a pretty thing.' Dahlke is ready to try more polyomino puzzles. He also dreams of the day when he'll get a chance to go back to college to study mathematics at the graduate level.

Photo: Karl Dahlke

Photo: Solving a tiling problem.

Polyominoes, which are the basis for thousands of mathematical puzzles, are shapes that cover connected squares on a checkerboard. One of the most intriguing of such puzzles involves proving that polyominoes of a certain shape can be laid down to form a complete rectangle. Recently, software engineer Karl A. Dahlke of AT&T Bell Laboratories in Naperville, Ill., combining perseverance with clever computer programming, managed to solve two particularly perplexing versions of this problem--ones that for nearly 20 years had defeated the best efforts of scores of amateur and professional mathematicians (SN: 9/20/86, p.186).

"I was amazed,' says mathematician Solomon W. Golomb of the University of Southern California in Los Angeles, who in 1954 introduced the term "polyomino.' Golomb has been exploring polyomino properties and proposing polyomino puzzles ever since. "A lot of very bright people have worked on [the problem],' he says. "This is a noteworthy accomplishment.'

Dahlke, who is blind, first learned of the puzzles earlier this year in an audio edition of SCIENCE NEWS. Dahlke spent several months working on the puzzles in his spare time. First, he tried proving that the problem has no solution. Because that approach didn't seem to lead anywhere, he started looking for an answer but kept running into dead ends. "I took so many different avenues,' he says.

Finally, Dahlke decided to program his personal computer to search for an answer systematically. Dahlke's computer is equipped with a speech synthesizer that converts the computer's output into sound. It took the addition of several programming tricks designed to circumvent time-consuming situations, in which the computer was trapped in endlessly repeating patterns, before Dahlke found his two minimum-area rectangles (see illustrations).

"It turns out that the size of the solutions is clearly a little bit beyond what people could easily do by hand,' says Golomb, "but fortunately, it's within the range of what you can find on a personal computer.'

"I'm no Einstein,' says Dahlke. "Maybe anyone with a micro, some perseverance and a little bit of geometric knowledge could have done it. But I did it, and it's a pretty thing.' Dahlke is ready to try more polyomino puzzles. He also dreams of the day when he'll get a chance to go back to college to study mathematics at the graduate level.

Photo: Karl Dahlke

Photo: Solving a tiling problem.

Printer friendly Cite/link Email Feedback | |

Author: | Peterson, Ivars |
---|---|

Publication: | Science News |

Date: | Nov 14, 1987 |

Words: | 396 |

Previous Article: | Fossil skeleton gets seabird size record. |

Next Article: | Huge ice cube in Antarctic waters. |

Topics: |