N-Queens Recursive Implementation in C++11

Question

I created a recursive, optimized, N-Queens implementation in CPP. Any suggestions for improvement?

/*
 * Filename     : queens.cpp
 * Author       : Kevin F. 
 * License      : CopyLeft, Feb 2017
 * Eight Queens : Print solutions which have N non-attacking queens placed on NxN chess board
 * Input        : Adjust BOARD_SIZE to change the size of the N
 * Output       : ASCII printed board and runtime statistics
 * Requires     : C++11
 * Compilation  : g++ -std=c++11 -O3 -o queens queens.cpp
 * Source       : http://pastebin.com/qy483BEi
 * Speed        : Found: 92 solutions in: 0.002582 seconds using: 2747 recursions
 * Without Opt  : Found: 92 solutions in: 0.132239 seconds using: 139049 recursions
*/

#include <algorithm>
#include <iostream>
#include <set>

#define BOARD_SIZE 8

using namespace std;

struct queen_t {
    uint8_t x;
    uint8_t y;
};

static vector< vector<queen_t> > _boards;
static uint32_t _num_recursions;

/* Forward declare for validate_and_continue */
void recurse(vector<queen_t> *board, set<uint8_t> *avail_x,
    set<uint8_t> *avail_y, uint16_t cur_iteration);

void print_board(vector<queen_t> *board){

    /* Sample Output
     *  |12345678
     * 1|xxxxxQxx
     * 2|xxxQxxxx
     * 3|xxxxxxQx
     * 4|Qxxxxxxx
     * 5|xxxxxxxQ
     * 6|xQxxxxxx
     * 7|xxxxQxxx
     * 8|xxQxxxxx
    */

    /* Generate empty board */
    vector<string> rows = {" |"};
    for(int i=1; i <= BOARD_SIZE; i++){
        rows[0].append(to_string(i));
        rows.push_back(to_string(i) + "|" + string(BOARD_SIZE, 'x'));
    }

    /* Fill boards with queens */
    for_each(board->begin(), board->end(), [&](const queen_t queen){
        rows[queen.y].replace(queen.x+1, 1, "Q"); // +1 to skip #|
    });

    for(int i=0; i <= BOARD_SIZE; i++){
        cout << rows[i] << endl;
    }
}

/*
 * Slope can be calculated as rise/run = (Y2-Y1)/(X2-X1)
 * A slope of 1 (perfect diagonal) implies (Y2-Y1) = (X2-X1)
*/
bool diagonal_slope(const queen_t *first_queen, const queen_t *second_queen){

    /* May be sent empty queens */
    if (first_queen->x == 0 || second_queen->x == 0){
        return false;
    }

    return abs(second_queen->y - first_queen->y) == abs(second_queen->x - first_queen->x);
}

/* Return true when new queen(s) trigger a diagonal attack */
bool can_attack(const vector<queen_t> *board, const queen_t *first_queen,
        const  queen_t *second_queen){

    for(const queen_t &queen : *board){
        if (diagonal_slope(first_queen, &queen) == true ||
                diagonal_slope(&queen, second_queen) == true){
            return true;
        }
    }

    return diagonal_slope(first_queen, second_queen);
}

/* If 0..2 queens added are valid, continue recursion */
void validate_and_continue(vector<queen_t> *board, set<uint8_t> *avail_x,
        set<uint8_t> *avail_y, uint16_t cur_iteration,
        queen_t first_queen, queen_t second_queen){

    /* Early prune any entries that produce diagonal attacks */
    if (can_attack(board, &first_queen, &second_queen) == true){
        return;
    }

    /* Update availability lists and create a new board */
    set<uint8_t> new_avail_x = *avail_x;
    set<uint8_t> new_avail_y = *avail_y;
    vector<queen_t> new_board = *board;

    if (first_queen.x != 0){
        new_avail_x.erase(first_queen.x);
        new_avail_y.erase(first_queen.y);
        new_board.push_back(first_queen);
    }

    if (second_queen.x != 0){
        new_avail_x.erase(second_queen.x);
        new_avail_y.erase(second_queen.y);
        new_board.push_back(second_queen);
    }

    /* Recurse with new modified copy of data */
    recurse(&new_board, &new_avail_x, &new_avail_y, cur_iteration + 1);
}

/* Iterate through 1..BOARD_SIZE queens based on X,Y availability lists */
void recurse(vector<queen_t> *board, set<uint8_t> *avail_x,
        set<uint8_t> *avail_y, uint16_t cur_iteration) {

    //cout << "CurIter: " << cur_iteration <<  ", queens placed: " << board->size() << endl;
    _num_recursions ++;

    /* Completion conditions */
    uint16_t queens_left = BOARD_SIZE - board->size();
    if (cur_iteration > BOARD_SIZE){
        if (queens_left == 0) {
            if (avail_x->size() != 0 || avail_y->size() != 0){
                cout << "ERROR: Board is full, but avail lists are non empty!" << endl;
                print_board(board);
                exit(1);
            }else{
                //cout << "Adding solution, recursions so far: " << _num_recursions << endl;
                _boards.push_back(*board);
            }
        }
        return;
    }

    /* Current iteration is now available for X and Y positions */
    avail_x->insert(cur_iteration);
    avail_y->insert(cur_iteration);

    uint16_t rounds_left = BOARD_SIZE - cur_iteration + 1; // including this round
    uint16_t queens_to_add = 0;
    if (queens_left >= (rounds_left * 2)) {
        /* Optimize for perfect 2 and skip 3+ saves ~5000 recursions */
        queens_to_add = ceil((double)queens_left / rounds_left);
    } else if (queens_left > ((rounds_left - 1) * 2)) {
        /* Avoid adding 0 queens this round saves ~500 recursions */
        queens_to_add = 1;
    }

    /* Add 0, 1, or 2 queens this round */
    for (queens_to_add; queens_to_add <= min(queens_left, (uint16_t)2); queens_to_add ++) {
        switch (queens_to_add) {
        case 1:
            /* Possible (X,cur_iteration) pairs */
            for_each(avail_x->begin(), avail_x->end(), [&](const uint8_t cur_x) {
                validate_and_continue(board, avail_x, avail_y,
                    cur_iteration, {cur_x, (uint8_t)cur_iteration}, {});
            });

            /* Possible (cur_iteration,Y) pairs */
            for_each(avail_y->begin(), avail_y->end(), [&](const uint8_t cur_y) {
                /* Equivalent to X = cur_iteration case above */
                if (cur_y == cur_iteration) {
                    return;
                }

                validate_and_continue(board, avail_x, avail_y,
                    cur_iteration, {(uint8_t)cur_iteration, cur_y}, {});
            });
            break;
        case 2:
            /*
             * Example outcomes for cur_iteration = 2
             * x = 1, y = 1... queens 1,2 and 2,1 ** valid
             * x = 1, y = 2....queens 1,2 and 2,2 ** skip in Y
             * x = 2, y = 1... queens 2,2 and 2,1 ** skip in X
             * x = 2, y = 2... queens 2,2 and 2,2 ** skip in X
            */

            for_each(avail_x->begin(), avail_x->end(), [&](const uint8_t cur_x) {
                /* First queen would generate a diagonal */
                if (cur_x == cur_iteration) {
                    return;
                }

                /* Possible (cur_iteration,Y) pairs */
                for_each(avail_y->begin(), avail_y->end(), [&](const uint8_t cur_y) {

                    /* Second queen would generate a diagonal */
                    if (cur_y == cur_iteration) {
                        return;
                    }

                    validate_and_continue(board,
                        avail_x, avail_y, cur_iteration,
                        {cur_x, (uint8_t)cur_iteration},
                        {(uint8_t)cur_iteration, cur_y});
                });
            });
            break;
        default:
            /* Place 0 queens this round, impossible >2 without collision */
            validate_and_continue(board, avail_x, avail_y,
                cur_iteration, {}, {});
            break;
        }
    }
}

int main(int argc, char *argv[]){

    cout << "Calculating solutions..." << endl;

    vector<queen_t> board;
    set<uint8_t> avail_x;
    set<uint8_t> avail_y;
    clock_t start_time = clock();

    /*
    * Recurse through possible outcomes that wont attack in row/column
    * Validate each placed queen against diagonal attacks via slope = 1
    */
    recurse(&board, &avail_x, &avail_y, 1);

    cout << "Found: " << _boards.size() << " solutions in: " <<
        ((double_t)(clock() - start_time)/CLOCKS_PER_SEC) <<
        " seconds using: " << _num_recursions << " recursions" << endl;

    print_board(&(*_boards.begin()));
}

On my fast workstation (vs slower HTPC), it completes in 0.001345 seconds (for Eight queens), so speed is not the concern. Code cohesiveness, clarity, code shrink, C++11isms, commenting, naming, optimizations, etc ? Can you get a lower number of recursions while maintaining the performance?

Thanks!

I updated the code per the link in title block, but left original here for readability of answers as per codereview.stackexchange.com policy.

I would suggest solving for a board of size 13x13 (or larger). Using an 8x8 board to determine performance isn't good because any program will solve that in much less than 1 second. I modified your program to solve a 13x13 board and it took 24.5 seconds. I took the program from my answer here to a recent n-queens question and it took 1 second. BTW your program used 9073263 recursions to solve 13x13 and the program I linked used 4601178 (around half). — JS1
– JS1, Commented Feb 22, 2017 at 21:07
interesting. thanks for the comparison. I notice the time it takes explodes around 12-14. It will be fun to narrow down the root cause. — Kevin
– Kevin, Commented Feb 22, 2017 at 23:39
Don't edit the code in your post after people have answered. If you want further review, you should post a new question, possibly linking back to this one for context. Please rollback the edit so that the answers make sense once again. — Toby Speight
– Toby Speight, Commented Feb 23, 2017 at 13:38
@Toby Speight thx for heads up. At least the updated code compiles :) — Kevin
– Kevin, Commented Feb 23, 2017 at 21:49

albert · Accepted Answer · 2018-12-16 14:28:58Z

Prefer references

Throughout your code you use vector* or queen_t*. Not once do you check whether they are nullptr. Prefer references instead of pointers, e.g.

bool diagonal_slope(const queen_t &first_queen, const queen_t &second_queen){

    if (first_queen.x == 0 || second_queen.x == 0){
        return false;
    }

    return std::abs(second_queen.y - first_queen.y) == abs(second_queen.x - first_queen.x);
}

In validate_and_continue, you can simply copy your std::sets.

Don't use an underscore on global scope names

An underscore at the start of an identifier at global scope is reserved and yields undefined behaviour.

Also, using namespace std; is considered bad practice.

Prefer range-based `for`-loops over `for_each`

Your for_each loop is not really easy too the eye:

        for_each(avail_x->begin(), avail_x->end(), [&](const uint8_t cur_x) {
            validate_and_continue(board, avail_x, avail_y,
                cur_iteration, {cur_x, (uint8_t)cur_iteration}, {});
        });

The range-based for loop which does the same doesn't need a lambda:

        for(auto cur_x : avail_x) {
            validate_and_continue(board, avail_x, avail_y,
                cur_iteration, {cur_x, (uint8_t)cur_iteration}, {});
        }

Prefer `const(expr) <integral type>` over `#define`

You currently define BOARD_SIZE as a macro:

#define BOARD_SIZE 8

This will replace BOARD_SIZE by 8 in your code, which is still better than a stray magic number. However, it can hinder debugging in some cases and doesn't provide a type to 8. Prefer a constexpr or a const, see here and here:

const uint16_t BOARD_SIZE = 8;

Other remarks

For loop parts can be empty

If you don't need to initialize something, just leave the initialization expression empty, or fill it with something useful:

// Do not
for (queens_to_add; queens_to_add <= min(queens_left, (uint16_t)2); queens_to_add ++) 

// Do
for (; queens_to_add <= min(queens_left, (uint16_t)2); queens_to_add ++)

Although note that you might call min in every iteration.

Documentation

If you want to follow a documentation quasi-standard, use doxygen. Also make sure to write down how your algorithm works, and why you use the variables you do. For example, why do you use avail_x and avail_y?

Global variables

Try to get rid of global variables. They make testing your functions a lot harder. If you want to know the number of recursions, either tag them along, or have recurse and validate_and_continue return the number of recursions.

Add missing includes

You're currently missing <vector> and <ctime>, as well as some others.

Better representation

For each row in a board, you only need to know the column of a queen in that board, e.g.

std::vector<unsigned> board = {1, 3, 0, 2};

// .Q..
// ...Q
// Q...
// ..Q.

Therefore, a std::vector<unsigned> is enough to store the location of the queens. The y-position is the index of your vector.

@knivil and that's why? You need for_each only if you don't want to traverse the whole range (begin() to end()), or if you need the functor. You also don't need a lambda/functor. So what's your reason not to prefer range-based for-loops in this case? — Zeta
– Zeta, Commented Feb 22, 2017 at 21:30
For me, they are equal. Non of them offer a clear quality advantage, e.g. readability. — knivil
– knivil, Commented Feb 22, 2017 at 21:47
I read this, stackoverflow.com/questions/2047414/… prior to my implementation, and indeed favoured range-based for ability to return early, but figured for_each was better practice? Seems like its personal preference — Kevin
– Kevin, Commented Feb 22, 2017 at 23:41

Community · Accepted Answer · 2017-05-23 12:40:52Z

Here are some things that may help you improve your code.

Don't abuse `using namespace std`

Putting using namespace std within your program is generally a bad habit that you'd do well to avoid.

Use the appropriate `#include`s

In order to compile and link, this code requires the following lines:

#include <cmath>
#include <vector>
#include <string>

For the program to be complete, these should be listed, too.

Fix the bug

OK, technically speaking, it's not actually a bug, but it's a useless statement and confusing to human readers. In particular, I'm referring to this line:

for (queens_to_add; queens_to_add <= min(queens_left, (uint16_t)2); queens_to_add ++) {

The first clause queens_to_add doesn't actually do anything. It caused me to wonder if it was intended to say queens_to_add=0 or something like that, but on deeper inspection, the value has already been set. I'd recommend leaving that clause empty instead.

Omit unused variables

Because argc and argv are unused, you could use the alternative form of main:

int main ()

Don't use `std::endl` if you don't really need it

The difference betweeen std::endl and '\n' is that '\n' just emits a newline character, while std::endl actually flushes the stream. This can be time-consuming in a program with a lot of I/O and is rarely actually needed. It's best to only use std::endl when you have some good reason to flush the stream and it's not very often needed for simple programs such as this one. Avoiding the habit of using std::endl when '\n' will do will pay dividends in the future as you write more complex programs with more I/O and where performance needs to be maximized.

Don't use leading underscores in names

Anything with a leading underscore is a reserved name in C++ (and in C). See this question for details.

Prefer references to raw pointers

In a number of places within the code, parameters are passed as raw pointers such as

void print_board(std::vector<queen_t> *board);

What you really want is a reference. The difference is that a reference cannot be nullptr and must actually point to an object, which is exactly the guarantee your code relies on anyway.

Use appropriate C++ idioms

The last line of main looks like this:

print_board(&(*_boards.begin()));

Instead of doing funny stuff like that with an iterator, why not just use front()? Combined with the suggestion above (to pass references), that would change that line instead to this:

print_board(_boards.front());

Use `const` where practical

In your print_board() routine, the passed board is never altered, which is just as it should be. You should indicate that fact by declaring it like this:

void print_board(const std::vector<queen_t> &board);

Note that this also incorporates the above two suggestions.

Prefer `const` or `constexpr` variables to `#define`

The BOARD_SIZE value should be declared as

constexpr std::size_t BOARD_SIZE{8};

The difference is that when constants are declared this way, they have a bit of additional type safety.

Eliminate global variables where possible

The _boards variable is global but should really be in main. If you move it to main, you can simply add an additional reference argument to recurse and to validate_and_continue.

Create a C++ object

Rather than passing the board vector around, it would seem to make more sense to me to have it be an actual object with most of the functions being member functions of that class. Itwould not only encapsulate the data and algorithms more neatly, but it would also make the code easier for humans to read and understand.

Use better naming

The can_attack() function is well named because it's easy to guess (correctly) what it does in this context. The recurse function, however, doesn't really say anything useful about what the function's purpose is; just a hint as to how it might function. A user of the function won't necessarily care what's inside, so the name should be more descriptive.

Return something useful from functions

Instead of void, why not return the recursion depth from recurse and pass the current depth as a parameter? That way you could eliminate another global variable.

Improving the algorithm

Reflections and translations of any given solution are also solutions. One could easily incorporate the generation of those within the program and eliminate some of the recursions.

Odd, I went through my program and removed all the extraneous headers... and it compiled fine without them. My machines are up-to-date Ubuntu 16.04, it seemed like the missing headers were being pulled from algorithm,etc. Thanks for the heads up :) — Kevin
– Kevin, Commented Feb 22, 2017 at 23:33
The problem with that approach is that some standard headers might include other standard headers. So that means that it compiles just find with that particular version of library and compiler, but it isn't portable and isn't reliable. So the best approach is, for each standard library call or template you use, include the documented #include per the standard. — Edward
– Edward, Commented Feb 22, 2017 at 23:38
unistd comes to mind... number of utilities at my company that were missing that header once we upgraded to Ubuntu 14.04... — Kevin
– Kevin, Commented Feb 22, 2017 at 23:45

knivil · Accepted Answer · 2017-02-22 21:20:32Z

-1

Including the appropriate header files to make this program compile, e.g. <vector>, <string> or <time.h>. Use clock functions from C++11. Do not use globals. Represent a board with a bitset where a set bit represents a position of a queen.

answered Feb 22, 2017 at 21:20

knivil

991 bronze badge

1

\$\begingroup\$ these sound like pretty actionable advice items. the only thing missing now is a justification... why? why should OP do this? \$\endgroup\$

Vogel612
– Vogel612

2017-02-22 22:40:12 +00:00
Commented Feb 22, 2017 at 22:40
\$\begingroup\$ 1.) Because the example does not compile on my machine. 2.) Because it is the prefered way (consistency) in C++11 (see question tags). 3.) Because globals are bad design. 4.) It is cool. \$\endgroup\$

knivil
– knivil

2017-02-22 22:51:39 +00:00
Commented Feb 22, 2017 at 22:51
\$\begingroup\$ A downvote because I do not spoon-feed every detail? \$\endgroup\$

knivil
– knivil

2017-02-23 09:28:33 +00:00
Commented Feb 23, 2017 at 9:28
\$\begingroup\$ Don't know why. Apart from the bitset, your points are valid. (didn't downvote you). \$\endgroup\$

Zeta
– Zeta

2017-02-23 23:37:45 +00:00
Commented Feb 23, 2017 at 23:37
\$\begingroup\$ I downvoted you but I don't know why - probably clicked by mistake \$\endgroup\$

nicholaswmin
– nicholaswmin

2017-11-15 17:14:27 +00:00
Commented Nov 15, 2017 at 17:14

| Show 1 more comment

Stack Exchange Network

N-Queens Recursive Implementation in C++11

3 Answers 3

Prefer references

Don't use an underscore on global scope names

Prefer range-based `for`-loops over `for_each`

Prefer `const(expr) <integral type>` over `#define`

Other remarks

For loop parts can be empty

Documentation

Global variables

Add missing includes

Better representation

Don't abuse `using namespace std`

Use the appropriate `#include`s

Fix the bug

Omit unused variables

Don't use `std::endl` if you don't really need it

Don't use leading underscores in names

Prefer references to raw pointers

Use appropriate C++ idioms

Use `const` where practical

Prefer `const` or `constexpr` variables to `#define`

Eliminate global variables where possible

Create a C++ object

Use better naming

Return something useful from functions

Improving the algorithm

You must log in to answer this question.

Linked

Hot Network Questions

N-Queens Recursive Implementation in C++11

3 Answers 3

Prefer references

Don't use an underscore on global scope names

Prefer range-based for-loops over for_each

Prefer const(expr) <integral type> over #define

Other remarks

For loop parts can be empty

Documentation

Global variables

Add missing includes

Better representation

Don't abuse using namespace std

Use the appropriate #includes

Fix the bug

Omit unused variables

Don't use std::endl if you don't really need it

Don't use leading underscores in names

Prefer references to raw pointers

Use appropriate C++ idioms

Use const where practical

Prefer const or constexpr variables to #define

Eliminate global variables where possible

Create a C++ object

Use better naming

Return something useful from functions

Improving the algorithm

You must log in to answer this question.

Linked

Related

Hot Network Questions

Prefer range-based `for`-loops over `for_each`

Prefer `const(expr) <integral type>` over `#define`

Don't abuse `using namespace std`

Use the appropriate `#include`s

Don't use `std::endl` if you don't really need it

Use `const` where practical

Prefer `const` or `constexpr` variables to `#define`