The queen of all puzzles.
FACED WITH SEEMINGLY UNSOLVABLE PROBLEMS, historically, people get creative, whether a sword through the Gordian Knot or the threat of one through a disputed baby. But a seemingly “simple” chess problem will require a sharper solution—so sharp, in fact, that researchers at the University of St. Andrews in Scotland believe it could earn its master one of the $1 million Millennium Prizes, from the Clay Mathematics Institute.The riddle is based on what is known as the Queens Puzzle, first devised in 1850. Eight queens must be placed on a standard chessboard so that no two pieces can take one another. According to a release from the university, “This means putting one queen each row, so that no two queens are in the same column, and no two queens in the same diagonal.” Solutions are not hard to imagine, but the problem becomes more complex when the chessboard grows—say 100 queens on a 100-by-100 chessboard.
New research from computer science professors Ian P. Gent, Christopher Jefferson, and Peter Nightingale refers to a still more challenging variant in which the board is even larger, but some queens have already been placed. In an interview with the Clay Mathematics Institute, Gent said this problem, technically known as the “n-Queens Completion Problem,” falls into a class of high-level math puzzles known as “NP-Complete.” Any algorithm that could solve it, Gent said, could therefore be used indirectly to solve others in the class—and be a contender for the Millennium Prize.A program of this sort would be far more powerful than anything we currently have, said Gent. “If you could write a computer program that could solve the problem really fast, you could adapt it to solve many of the most important problems that affect us all daily.” This program, he said, would be able to decrypt even the toughest online security, something that would take current software thousands of years to unravel, by scrolling through and then discarding an almost infinite number of solutions until one works. Nightingale, his colleague, questioned whether this is even be possible.“What our research has shown is that—for all practical purposes—it can’t be done,” he said....MORE
