Lets Play Code Golf: Queens

/*
 * Filename     : queens.cpp
 * Author       : Kevin Folz <kevinfolz@gmail.com>
 * License      : CopyLeft, Feb 2017
 * Eight Queens : Find solutions which have N non-attacking queens placed on NxN chess board
 * Algorithm    : Rooted at 1,1 simultaneously add row and column to problem space
 *              : tracking the suitable queen locations in sets avail_x and avail_y
 *              : Each queen is validated for diagonal attacks prior to adding to 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://bit.ly/code_golf_queens
 * 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>
#include <cmath>
#include <vector>
#include <string>

using std::cout;
using std::vector;
using std::set;

// TODO: implement cli argument
const uint8_t BOARD_SIZE = 8;

struct queen_t {
    uint8_t x;
    uint8_t y;
};

static uint32_t num_recursions;

/* Forward declaration for validate_and_continue */
void find_more_solutions(vector<queen_t> &board, set<uint8_t> &avail_x,
    set<uint8_t> &avail_y, uint8_t cur_iteration,
    vector< vector<queen_t> > &solutions);

void print_board(const 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 rows */
    vector<std::string> rows = {" |"};
    for(int i=1; i <= BOARD_SIZE; i++){
        rows[0].append(std::to_string(i));
        rows.push_back(std::to_string(i) + "|" + std::string(BOARD_SIZE, 'x'));
    }

    /* Fill rows with queens */
    /* TODO: this produces incorrect results with n > 9 due to width of #| */
    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] << "\n";
    }
}

/*
 * 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, uint8_t cur_iteration,
        const queen_t first_queen, const queen_t second_queen,
        vector< vector<queen_t> > &solutions){

    /* 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 */
    find_more_solutions(new_board, new_avail_x, new_avail_y,
        cur_iteration + 1, solutions);
}

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

    //cout << "CurIter: " << static_cast<uint16_t>(cur_iteration) << \
        ", queens placed: " << board.size() << "\n";

    num_recursions ++;

    /* Completion conditions */
    uint8_t queens_left = BOARD_SIZE - board.size();
    if (cur_iteration > BOARD_SIZE){
        if (queens_left == 0 && avail_x.size() == 0 && avail_y.size() == 0) {
            //cout << "Adding solution, recursions so far: " << num_recursions << "\n";
            solutions.push_back(board);
        }

        return;
    }

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

    uint8_t rounds_left = BOARD_SIZE - cur_iteration + 1; // including this round
    uint8_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 <= std::min(queens_left, (uint8_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}, {}, solutions);
            });

            /* 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}, {}, solutions);
            });
            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) {
                /* Don't place a queen on a diagonal, would attack 2nd queen */
                if (cur_x == cur_iteration) {
                    return;
                }

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

                    /* Don't place a queen on a diagonal, would attack 1st queen */
                    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}, solutions);
                });
            });
            break;
        default:
            /* Place 0 queens this round, impossible >2 without collision */
            validate_and_continue(board, avail_x, avail_y, cur_iteration,
                {}, {}, solutions);
            break;
        }
    }
}

int main(){

    cout << "Calculating solutions...\n";

    vector< vector<queen_t> > solutions;
    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
    */
    find_more_solutions(board, avail_x, avail_y, 1, solutions);

    cout << "Found: " << solutions.size() << " solutions in: " <<
        ((double_t)(clock() - start_time)/CLOCKS_PER_SEC) <<
        " seconds using: " << num_recursions << " recursions\n";

    print_board(solutions.front());
}