View difference between Paste ID: xxAHUmyp and qy483BEi

 /*
  * Filename     : queens.cpp
  * Author       : Kevin F
  * 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());
 }