Printer Friendly

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.
COPYRIGHT 1987 Science Service, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 1987, Gale Group. All rights reserved. Gale Group is a Thomson Corporation Company.

Article Details
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:


Related Articles
Children's computers.
The jigsaw puzzle as a metaphor for knowledge.
Items of Interest.
AMERICAN LEAGUE: AROUND THE HORN A'S TAKE THEIR PLACE IN AL WEST.
Patriotic pieces proclaim hope.
HENDERSON HOPING FOR NEW HOME.
ANGELS NOTEBOOK: ECKSTEIN SHINES AS LEADING MAN.
Scramble Square puzzles.

Terms of use | Copyright © 2017 Farlex, Inc. | Feedback | For webmasters