SHARE
TWEET

Untitled

a guest Sep 17th, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. bool is_valid(const vector<int>& cols, int row) {
  8.     for (int i=0; i<row; ++i) {
  9.         if (cols[i] == cols[row] || abs(cols[i]-cols[row]) == row-i)
  10.             return false;  //clash horizontal or diagonal
  11.     }
  12.     return true;
  13. }
  14.  
  15. vector<vector<string>> solveNQueens(int n) {
  16.     //using backtracking iteratively
  17.     vector<vector<string>> ret;
  18.     vector<int> cols(n, 0);
  19.     int row = 0;
  20.  
  21.     while (true) {
  22.         if (row == n) {  //valid complete board
  23.             //compose string vector for board and add to ret
  24.             vector<string> board;
  25.             string line(n, '.');
  26.             for (int pos : cols) {
  27.                 line[pos] = 'Q';
  28.                 board.push_back(line);
  29.                 line[pos] = '.';
  30.             }
  31.             ret.push_back(board);
  32.             //continue search by going to last row and incrementing last queen
  33.             cols[--row]++;
  34.         }
  35.         else if (cols[row] == n) {  //end of row
  36.             cols[row--] = 0;  //reset queen position and move back one row
  37.             if (row == -1) break;  //finished. let's break out
  38.             cols[row]++;  //move queen forward one position.
  39.         }
  40.         else if (!is_valid(cols, row))
  41.             cols[row]++;  //not valid, so move queen forward one position
  42.         else
  43.             row++;   //valid, so go to next row.        
  44.     }
  45.     return ret;
  46. }
  47.  
  48. void print_grids(const vector<vector<string>>& grids) {
  49.     for (const vector<string>& grid : grids) {
  50.         for (const string& line : grid)
  51.             cout << line << "\n";
  52.         cout << "\n";
  53.     }
  54. }
  55.  
  56. int main() {
  57.     auto grids = solveNQueens(5);
  58.     cout << "calculated " << grids.size() << " boards:\n\n";
  59.     print_grids(grids);
  60.  
  61.     return 0;
  62. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top