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.

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.

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 #includes

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.

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.