Poor performance on the nqueens min-conflic search

Question

I am implementing the nqueens min-conflict search as mentioned by

Norvig, S., & Peter, J. R. and. (2014). Artificial Intelligence A Modern Approach. In Pearson (Vol. 58, Issue 12).

The authors mention this heuristic alone is super efficient:

Yet when I implement it I cannot solve an over 5000 in less than a min. While the authors speed of million-queens in 50 iterations, my implementation often goes over the 1000 iterations for 5000-queens. Another question mentions similar result.

Any ideas on what I am doing wrong? Is it algorithmic or am I using a loop where I shouldn't?

update() is the main method by the way.

    list<unsigned> rowsInConflict(const unsigned currentState[]) {
        list<unsigned> rowsInConflict; //TODO change to map

        for (unsigned row = 0; row < boardSize; row++) {
            for (unsigned otherRow = 0; otherRow < boardSize; otherRow++) {
                if (isConflict(row, currentState[row], otherRow, currentState[otherRow])) {
                    rowsInConflict.push_front(row);
                    debug("row in conflict " + to_string(row));
                    rowsInConflict.push_front(otherRow);
                    //return rowsInConflict;
                }
            }
        }

        return rowsInConflict;
    }

    bool update(unsigned currentState[]) {
                unsigned randomRow, column;

        list<unsigned> conflictRows = rowsInConflict(currentState);
        if (conflictRows.empty()) {
            return true;
        }

        list<unsigned>::iterator it = conflictRows.begin();
        std::advance(it, rand() % conflictRows.size());
        randomRow = (unsigned) *it;

        column = getMinConflictColumn(currentState, randomRow);
        placeQueen(currentState, randomRow, column);


        return false;

    }



    void solve_nqueen(unsigned size, bool isVerbose) {

        unsigned rowSpace[size];






        while (!update(rowSpace)) {

            if (iterations >= 1000) {
                cout << "Random restart." << endl;
                intialize(rowSpace);
                iterations = 0;
            }
            iterations++;
        }
        printBoard(rowSpace);




    }

};

Answer 1

As I said in the comments, if you're trying to minimize the number of swaps, it's crucial to start with a good initial configuration. In my nQueens implementation, I have 3 different methods for generating the initial row for each queen:

1. For each queen, select a random row
2. Create a permutation of the numbers in 1..n corresponding to each queen's row number
3. Place each queen on the row with the least conflicts, breaking ties randomly

All of these approaches restrict each queen to a single column. The third method reuses the function I use find a new destination row when performing swaps.

Here are some sample runs on 5000 queens for each of the initial configurations:

# Board initialized by random rows
Number of queens = 5000, 100 reps
Average time per board: 1.57167
Average number of swaps: 3160.87

# Board initialized by shuffle
Number of queens = 5000, 100 reps
Average time per board: 1.17037
Average number of swaps: 2445.96

# Board initialized by min-conflict
Number of queens = 5000, 100 reps
Average time per board: 1.23296
Average number of swaps: 49.97

As you can see, method 3 gives us our target number of swaps, while the others require a lot more. In fact, the number of swaps required for this method is consistent from about 1000 queens on up.

Interestingly, the total time taken by each method does not vary nearly as much as the number of swaps. (All times include both setting up the initial board and moving the queens.)