Chess aficionados know that the game is one of exponential complexity. The first three moves yield more than 9 million possible board positions and there are nearly 319 billion possible ways to play the first four moves on both sides. That makes solving chess problems unimaginably difficult.

That’s one reason the game has long captured the fancy of computer scientists. It’s impossible for even the world’s fastest computer to run through all 10¹²⁰ possible permutations of a chess game, but can algorithms be devised to achieve the same outcome with far less effort?

Now a team of researchers at Scotland’s University of St Andrews has demonstrated that in the case of at least one famous chess problem, it can’t. If their proof holds up, it would put to rest a nearly 170-year-old debate over the so-called n-Queens problem. On the other hand, anyone who can prove them wrong would be eligible for a $1 million cash prize announced Thursday — and probably a fast track to building the next Microsoft Corp.

A problem of queens

One of the 92 n-Queens solutions Image: Wikipedia

The n­-Queens problem is to place n number of chess queens on an n by n chessboard so that no two queens can attack each other, meaning that they don’t share the same row, column or diagonal. Coming up with an algorithm that solves the problem is a lot harder than it sounds. On a standard eight-by-eight chessboard, there are 4.4 billion possible arrangements of eight queens but only 92 solutions that have been identified. As the board gets larger, the problem grows exponentially more difficult.

St Andrews Computer Scientist Professor Ian Gent and colleagues Christopher Jefferson and Peter Nightingale actually set out to address a variation of n­-Queens called n­-Queens Completion that has greater commercial relevance. In that version, one or more queens have already been placed on the board and the challenge is to place the rest. The problem is analogous to one that a commercial package delivery firm, for example, might confront in optimizing routes around a set of distribution centers.

The original n­-Queens problem was proposed in 1848 and has fascinated mathematicians and computer scientists ever since. It has been the subject of an ongoing debate over its value as a benchmark for artificial intelligence, meaning that an algorithm that could solve n-Queens at scale would be, by definition, intelligent. No one ever has solved it at scale, though, and Gent and his colleagues believe it’s unlikely anyone ever will.

Their paper, published in the most recent edition of the Journal of Artificial Intelligence Research, offers a proof that n-Queens Completion is “NP-complete” (NP stands for “nondeterministic polynomial”). Basically, that means that it’s possible to verify a solution to the problem, but impossible to figure out how to get to the solution in the first place.

Development of an algorithm that solves n-Queens Completion would have broad applications across other areas. “If you could solve one [NP-Completion] problem very quickly, you could automatically solve all the others,” Gent said in an interview with SiliconANGLE. For example, Major League Baseball could use it to optimize a season’s worth of schedules of all 30 teams. Airlines could plan the most fuel-efficient routes for an entire global fleet. Colleges could use it to optimize roommate compatibility in dorm room assignments.

A $1 million solution

Those potential applications are one reason why Clay Mathematics Institute includes NP problems in the list of challenges for which it offers $1 million for a solution. “[O]ne of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure,” the institute writes on its website.

Gent’s interest in n-Queens was sparked by a challenge a colleague posted on Facebook on New Year’s Day 2015. “What attracted me personally is that it has a long history and many people have worked on different ways of solving it,” he said. Google Scholar lists more than 6,500 references to n-Queen in its database.

The researchers’ 34-page paper documents with scores of formulas only a mathematician could comprehend the results of three solvers they created to either find a solution or confirm that there was none. If their proof holds up, they would technically be eligible for the Clay Institute Prize, but Gent isn’t holding his breath. “You have to get your paper published in a reputable, peer-reviewed journal and then wait two years in case a challenge comes up,” he said.

Why is a paper that proves something isn’t possible such a big deal? Basically, so researchers can stop beating their heads against a wall and focus on something else. “When you show that something is NP-complete, you usually stop trying to solve it,” Gent said. “Instead of trying to crack it with a hammer, you chip pieces off.”

That would help them avoid sinking into an eternal struggle like the fictional Deep Thought supercomputer in “Hitchhiker’s Guide to the Galaxy,” which took seven-and-a-half million years to provide an answer to the meaning of everything.

Image: Pixabay