N-Queens Recursive Implementation in C++11

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

#define BOARD_SIZE 8

using namespace std;

struct queen_t {
uint8_t x;
uint8_t y;
};

static vector > _boards;
static uint32_t _num_recursions;

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

void print_board(vector *board){

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

/ Generate empty board /
vector rows = {" |"};
for(int i=1; i begin(), board->end(), &{
rows[queen.y].replace(queen.x+1, 1, "Q"); // +1 to skip #|
});

for(int i=0; i 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 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;

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) 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 ` and , 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 board = {1, 3, 0, 2};

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

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

StackExchange Code Review Q#156050, answer score: 5