About Geoffrey De Smet

Geoffrey De Smet (Red Hat) is the lead and founder of OptaPlanner. Before joining Red Hat in 2010, he was formerly employed as a Java consultant, an A.I. researcher and an enterprise application project lead.

Cheating on the N Queens benchmark

Many Solver distributions include an N Queens example, in which n queens need to be placed on a n*n sized chessboard, with no attack opportunities. So when you’re looking for the fastest Solver, it’s tempting to use the N Queens example as a benchmark to compare those solvers. That’s a tragic mistake, because the N Queens problem is solvable in polynomial time, which means there’s a way to cheat.

That being said, OptaPlanner solves the 1 000 000 queens problem in less than 3 seconds. Here’s a log to prove it (with time spent in milliseconds):
 
 
 

INFO  Opened: data/nqueens/unsolved/10000queens.xml
INFO  Solving ended: time spent (23), best score (0), ...

INFO  Opened: data/nqueens/unsolved/100000queens.xml
INFO  Solving ended: time spent (159), best score (0), ...

INFO  Opened: data/nqueens/unsolved/1000000queens.xml
INFO  Solving ended: time spent (2981), best score (0), ...

How to cheat on the N Queens problem

The N Queens problem is not NP-complete, nor NP-hard. That is math speak for stating that there’s a perfect algorithm to solve this problem: the Explicits Solutions algorithm. Implemented with a CustomSolverPhaseCommand in OptaPlanner it looks like this:

public class CheatingNQueensPhaseCommand implements CustomSolverPhaseCommand {

    public void changeWorkingSolution(ScoreDirector scoreDirector) {
        NQueens nQueens = (NQueens) scoreDirector.getWorkingSolution();
        int n = nQueens.getN();
        List<Queen> queenList = nQueens.getQueenList();
        List<Row> rowList = nQueens.getRowList();

        if (n % 2 == 1) {
            Queen a = queenList.get(n - 1);
            scoreDirector.beforeVariableChanged(a, "row");
            a.setRow(rowList.get(n - 1));
            scoreDirector.afterVariableChanged(a, "row");
            n--;
        }
        int halfN = n / 2;
        if (n % 6 != 2) {
            for (int i = 0; i < halfN; i++) {
                Queen a = queenList.get(i);
                scoreDirector.beforeVariableChanged(a, "row");
                a.setRow(rowList.get((2 * i) + 1));
                scoreDirector.afterVariableChanged(a, "row");

                Queen b = queenList.get(halfN + i);
                scoreDirector.beforeVariableChanged(b, "row");
                b.setRow(rowList.get(2 * i));
                scoreDirector.afterVariableChanged(b, "row");
            }
        } else {
            for (int i = 0; i < halfN; i++) {
                Queen a = queenList.get(i);
                scoreDirector.beforeVariableChanged(a, "row");
                a.setRow(rowList.get((halfN + (2 * i) - 1) % n));
                scoreDirector.afterVariableChanged(a, "row");

                Queen b = queenList.get(n - i - 1);
                scoreDirector.beforeVariableChanged(b, "row");
                b.setRow(rowList.get(n - 1 - ((halfN + (2 * i) - 1) % n)));
                scoreDirector.afterVariableChanged(b, "row");
            }
        }

    }

}

Now, one could argue that this implementation doesn’t use any of OptaPlanner’s algorithms (such as the Construction Heuristics or Local Search). But it’s straightforward to mimic this approach in a Construction Heuristic (or even a Local Search). So, in a benchmark, any Solver which simulates that approach the most, is guaranteed to win when scaling out.

Why doesn’t that work for other planning problems?

This algorithm is perfect for N Queens, so why don’t we use a perfect algorithm on other planning problems? Well, simply because there are none!

Most planning problems, such as vehicle routing, employee rostering, cloud optimization, bin packing, … are proven to be NP-complete (or NP-hard). This means that these problems are in essence the same: a perfect algorithm for one, would work for all of them. But no human has ever found such an algorithm (and most experts believe no such algorithm exists).

Note: There are a few notable exceptions of planning problems that are not NP-complete, nor NP-hard. For example, finding the shortest distance between 2 points can be solved in polynomial time with A*-Search. But their scope is narrow: finding the shortest distance to visit n points (TSP), on the other hand, is not solvable in polynomial time.

Because N Queens differs intrinsically from real planning problems, is a terrible use case to benchmark.

Conclusion

Benchmarks on the N Queens problem are meaningless. Instead, benchmark implementations of a realistic competition. A realistic competition is an official, independent competition:

  1. that clearly defines a real-word use case
  2. with real-world constraints
  3. with multiple, real-world datasets
  4. that expects reproducible results within a specific time limit on specific hardware
  5. that has had serious participation from the academic and/or enterprise Operations Research community

OptaPlanner‘s examples implement several cases of realistic competitions.

Reference: Cheating on the N Queens benchmark from our JCG partner Geoffrey De Smet at the OptaPlanner blog.
Related Whitepaper:

Software Architecture

This guide will introduce you to the world of Software Architecture!

This 162 page guide will cover topics within the field of software architecture including: software architecture as a solution balancing the concerns of different stakeholders, quality assurance, methods to describe and evaluate architectures, the influence of architecture on reuse, and the life cycle of a system and its architecture. This guide concludes with a comparison between the professions of software architect and software engineer.

Get it Now!  

Leave a Reply


× seven = 49



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use | Privacy Policy
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.

Sign up for our Newsletter

20,709 insiders are already enjoying weekly updates and complimentary whitepapers! Join them now to gain exclusive access to the latest news in the Java world, as well as insights about Android, Scala, Groovy and other related technologies.

As an extra bonus, by joining you will get our brand new e-books, published by Java Code Geeks and their JCG partners for your reading pleasure! Enter your info and stay on top of things,

  • Fresh trends
  • Cases and examples
  • Research and insights
  • Two complimentary e-books