Advertisement
kevinf28

Lets Play Code Golf: Queens

Feb 21st, 2017
190
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.54 KB | None | 0 0
  1. /*
  2.  * Filename     : queens.cpp
  3.  * Author       : Kevin Folz <kevinfolz@gmail.com>
  4.  * License      : CopyLeft, Feb 2017
  5.  * Eight Queens : Find solutions which have N non-attacking queens placed on NxN chess board
  6.  * Algorithm    : Rooted at 1,1 simultaneously add row and column to problem space
  7.  *              : tracking the suitable queen locations in sets avail_x and avail_y
  8.  *              : Each queen is validated for diagonal attacks prior to adding to board
  9.  * Input        : Adjust BOARD_SIZE to change the size of the N
  10.  * Output       : ASCII printed board and runtime statistics
  11.  * Requires     : C++11
  12.  * Compilation  : g++ -std=c++11 -O3 -o queens queens.cpp
  13.  * Source       : http://bit.ly/code_golf_queens
  14.  * Speed        : Found: 92 solutions in: 0.002582 seconds using: 2747 recursions
  15.  * Without Opt  : Found: 92 solutions in: 0.132239 seconds using: 139049 recursions
  16. */
  17.  
  18. #include <algorithm>
  19. #include <iostream>
  20. #include <set>
  21. #include <cmath>
  22. #include <vector>
  23. #include <string>
  24.  
  25. using std::cout;
  26. using std::vector;
  27. using std::set;
  28.  
  29. const uint8_t BOARD_SIZE = 8;
  30.  
  31. struct queen_t {
  32.     uint8_t x;
  33.     uint8_t y;
  34. };
  35.  
  36. static uint32_t num_recursions;
  37.  
  38. /* Forward declaration for validate_and_continue */
  39. void find_more_solutions(vector<queen_t> &board, set<uint8_t> &avail_x,
  40.     set<uint8_t> &avail_y, uint8_t cur_iteration,
  41.     vector< vector<queen_t> > &solutions);
  42.  
  43. void print_board(const vector<queen_t> &board){
  44.  
  45.     /* Sample Output
  46.      *  |12345678
  47.      * 1|xxxxxQxx
  48.      * 2|xxxQxxxx
  49.      * 3|xxxxxxQx
  50.      * 4|Qxxxxxxx
  51.      * 5|xxxxxxxQ
  52.      * 6|xQxxxxxx
  53.      * 7|xxxxQxxx
  54.      * 8|xxQxxxxx
  55.     */
  56.  
  57.     /* Generate empty rows */
  58.     vector<std::string> rows = {" |"};
  59.     for(int i=1; i <= BOARD_SIZE; i++){
  60.         rows[0].append(std::to_string(i));
  61.         rows.push_back(std::to_string(i) + "|" + std::string(BOARD_SIZE, 'x'));
  62.     }
  63.  
  64.     /* Fill rows with queens */
  65.     /* TODO: this produces incorrect results with n > 9 due to width of #| */
  66.     for_each(board.begin(), board.end(), [&](const queen_t queen){
  67.         rows[queen.y].replace(queen.x+1, 1, "Q"); // +1 to skip #|
  68.     });
  69.  
  70.     for(int i=0; i <= BOARD_SIZE; i++){
  71.         cout << rows[i] << "\n";
  72.     }
  73. }
  74.  
  75. /*
  76.  * Slope can be calculated as rise/run = (Y2-Y1)/(X2-X1)
  77.  * A slope of 1 (perfect diagonal) implies (Y2-Y1) = (X2-X1)
  78. */
  79. bool diagonal_slope(const queen_t &first_queen, const queen_t &second_queen){
  80.  
  81.     /* May be sent empty queens */
  82.     if (first_queen.x == 0 || second_queen.x == 0){
  83.         return false;
  84.     }
  85.  
  86.     return abs(second_queen.y - first_queen.y) == abs(second_queen.x - first_queen.x);
  87. }
  88.  
  89. /* Return true when new queen(s) trigger a diagonal attack */
  90. bool can_attack(const vector<queen_t> &board, const queen_t &first_queen,
  91.         const queen_t &second_queen){
  92.  
  93.     for(const queen_t &queen : board){
  94.         if (diagonal_slope(first_queen, queen) == true ||
  95.                 diagonal_slope(queen, second_queen) == true){
  96.             return true;
  97.         }
  98.     }
  99.  
  100.     return diagonal_slope(first_queen, second_queen);
  101. }
  102.  
  103. /* If 0..2 queens added are valid, continue recursion */
  104. void validate_and_continue(vector<queen_t> &board, set<uint8_t> &avail_x,
  105.         set<uint8_t> &avail_y, uint8_t cur_iteration,
  106.         const queen_t first_queen, const queen_t second_queen,
  107.         vector< vector<queen_t> > &solutions){
  108.  
  109.     /* Early prune any entries that produce diagonal attacks */
  110.     if (can_attack(board, first_queen, second_queen) == true){
  111.         return;
  112.     }
  113.  
  114.     /* Update availability lists and create a new board */
  115.     set<uint8_t> new_avail_x = avail_x;
  116.     set<uint8_t> new_avail_y = avail_y;
  117.     vector<queen_t> new_board = board;
  118.  
  119.     if (first_queen.x != 0){
  120.         new_avail_x.erase(first_queen.x);
  121.         new_avail_y.erase(first_queen.y);
  122.         new_board.push_back(first_queen);
  123.     }
  124.  
  125.     if (second_queen.x != 0){
  126.         new_avail_x.erase(second_queen.x);
  127.         new_avail_y.erase(second_queen.y);
  128.         new_board.push_back(second_queen);
  129.     }
  130.  
  131.     /* Recurse with new modified copy of data */
  132.     find_more_solutions(new_board, new_avail_x, new_avail_y,
  133.         cur_iteration + 1, solutions);
  134. }
  135.  
  136. /* Iterate through 1..BOARD_SIZE queens based on X,Y availability lists */
  137. void find_more_solutions(vector<queen_t> &board, set<uint8_t> &avail_x,
  138.         set<uint8_t> &avail_y, uint8_t cur_iteration,
  139.         vector< vector<queen_t> > &solutions) {
  140.  
  141.     //cout << "CurIter: " << static_cast<uint16_t>(cur_iteration) << \
  142.         ", queens placed: " << board.size() << "\n";
  143.  
  144.     num_recursions ++;
  145.  
  146.     /* Completion conditions */
  147.     uint8_t queens_left = BOARD_SIZE - board.size();
  148.     if (cur_iteration > BOARD_SIZE){
  149.         if (queens_left == 0 && avail_x.size() == 0 && avail_y.size() == 0) {
  150.             //cout << "Adding solution, recursions so far: " << num_recursions << "\n";
  151.             solutions.push_back(board);
  152.         }
  153.  
  154.         return;
  155.     }
  156.  
  157.     /* Current iteration is now available for X and Y positions */
  158.     avail_x.insert(cur_iteration);
  159.     avail_y.insert(cur_iteration);
  160.  
  161.     uint8_t rounds_left = BOARD_SIZE - cur_iteration + 1; // including this round
  162.     uint8_t queens_to_add = 0;
  163.     if (queens_left >= (rounds_left * 2)) {
  164.         /* Optimize for perfect 2 and skip 3+ saves ~5000 recursions */
  165.         queens_to_add = ceil((double)queens_left / rounds_left);
  166.     } else if (queens_left > ((rounds_left - 1) * 2)) {
  167.         /* Avoid adding 0 queens this round saves ~500 recursions */
  168.         queens_to_add = 1;
  169.     }
  170.  
  171.     /* Add 0, 1, or 2 queens this round */
  172.     for (; queens_to_add <= std::min(queens_left, (uint8_t)2); queens_to_add ++) {
  173.         switch (queens_to_add) {
  174.         case 1:
  175.             /* Possible (X,cur_iteration) pairs */
  176.             for_each(avail_x.begin(), avail_x.end(), [&](const uint8_t cur_x) {
  177.                 validate_and_continue(board, avail_x, avail_y, cur_iteration,
  178.                 {cur_x, (uint8_t)cur_iteration}, {}, solutions);
  179.             });
  180.  
  181.             /* Possible (cur_iteration,Y) pairs */
  182.             for_each(avail_y.begin(), avail_y.end(), [&](const uint8_t cur_y) {
  183.                 /* Equivalent to X = cur_iteration case above */
  184.                 if (cur_y == cur_iteration) {
  185.                     return;
  186.                 }
  187.  
  188.                 validate_and_continue(board, avail_x, avail_y, cur_iteration,
  189.                     {(uint8_t)cur_iteration, cur_y}, {}, solutions);
  190.             });
  191.             break;
  192.         case 2:
  193.             /*
  194.              * Example outcomes for cur_iteration = 2
  195.              * x = 1, y = 1... queens 1,2 and 2,1 ** valid
  196.              * x = 1, y = 2....queens 1,2 and 2,2 ** skip in Y
  197.              * x = 2, y = 1... queens 2,2 and 2,1 ** skip in X
  198.              * x = 2, y = 2... queens 2,2 and 2,2 ** skip in X
  199.             */
  200.  
  201.             for_each(avail_x.begin(), avail_x.end(), [&](const uint8_t cur_x) {
  202.                 /* Don't place a queen on a diagonal, would attack 2nd queen */
  203.                 if (cur_x == cur_iteration) {
  204.                     return;
  205.                 }
  206.  
  207.                 /* Possible (cur_iteration,Y) pairs */
  208.                 for_each(avail_y.begin(), avail_y.end(), [&](const uint8_t cur_y) {
  209.  
  210.                     /* Don't place a queen on a diagonal, would attack 1st queen */
  211.                     if (cur_y == cur_iteration) {
  212.                         return;
  213.                     }
  214.  
  215.                     validate_and_continue(board,
  216.                         avail_x, avail_y, cur_iteration,
  217.                         {cur_x, (uint8_t)cur_iteration},
  218.                         {(uint8_t)cur_iteration, cur_y}, solutions);
  219.                 });
  220.             });
  221.             break;
  222.         default:
  223.             /* Place 0 queens this round, impossible >2 without collision */
  224.             validate_and_continue(board, avail_x, avail_y, cur_iteration,
  225.                 {}, {}, solutions);
  226.             break;
  227.         }
  228.     }
  229. }
  230.  
  231. int main(){
  232.  
  233.     cout << "Calculating solutions...\n";
  234.  
  235.     vector< vector<queen_t> > solutions;
  236.     vector<queen_t> board;
  237.     set<uint8_t> avail_x;
  238.     set<uint8_t> avail_y;
  239.     clock_t start_time = clock();
  240.  
  241.     /*
  242.     * Recurse through possible outcomes that wont attack in row/column
  243.     * Validate each placed queen against diagonal attacks via slope = 1
  244.     */
  245.     find_more_solutions(board, avail_x, avail_y, 1, solutions);
  246.  
  247.     cout << "Found: " << solutions.size() << " solutions in: " <<
  248.         ((double_t)(clock() - start_time)/CLOCKS_PER_SEC) <<
  249.         " seconds using: " << num_recursions << " recursions\n";
  250.  
  251.     print_board(solutions.front());
  252. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement