fork download 
  1. #include <iostream>
  2.  
  3. void tryQueen(int col, int n, int* trace, bool* rowFlag, bool* pDiaFlag, bool* sDiaFlag, bool &found) {
  4.     if (col == n) {
  5.         std::cout << "Position of " << n << " queens (row, col): \n";
  6.         for (int c = 0; c < n; ++c) {
  7.             int r = trace[c];
  8.             std::cout << "(" << r << ", " << c << ")\n";
  9.         }
  10.         found = true;
  11.  
  12.         std::cout << "\nDrawing the board...\n";
  13.         int* traceRow = new int[n]();
  14.         for (int c = 0; c < n; ++c) {
  15.             traceRow[trace[c]] = c;
  16.         }
  17.         for (int r = 0; r < n; ++r) {
  18.             for (int c = 0; c < n; ++c) {
  19.                 std::cout << (traceRow[r] == c ? '*' : '.') << ' '; 
  20.             }
  21.             std::cout << '\n';
  22.         }
  23.         delete[] traceRow;
  24.  
  25.         return;
  26.     }
  27.     for (int row = 0; row < n; ++row) {
  28.         if (!rowFlag[row] && !pDiaFlag[n-1+(col-row)] && !sDiaFlag[n*2-2-(row+col)]) {
  29.             trace[col] = row;
  30.             rowFlag[row] = true;
  31.             pDiaFlag[n-1+(col-row)] = true;
  32.             sDiaFlag[n*2-2-(row+col)] = true;
  33.             tryQueen(col+1, n, trace, rowFlag, pDiaFlag, sDiaFlag, found);
  34.             rowFlag[row] = false;
  35.             pDiaFlag[n-1+(col-row)] = false;
  36.             sDiaFlag[n*2-2-(row+col)] = false;
  37.             if (found) {
  38.                 return;
  39.             }
  40.         }
  41.     }
  42. }
  43.  
  44. int main() {
  45.     int n;
  46.     std::cout << "Enter n: ";
  47.     std::cin >> n;
  48.  
  49.     int* trace = new int[n]();
  50.     bool* rowFlag = new bool[n]();
  51.     bool* pDiaFlag = new bool[n*2-1]();
  52.     bool* sDiaFlag = new bool[n*2-1]();
  53.     bool found = false;
  54.  
  55.     tryQueen(0, n, trace, rowFlag, pDiaFlag, sDiaFlag, found);
  56.  
  57.     if (!found) {
  58.         std::cout << "Solution not found!\n";
  59.     }
  60.  
  61.     delete[] trace;
  62.     delete[] rowFlag;
  63.     delete[] pDiaFlag;
  64.     delete[] sDiaFlag;
  65.  
  66.     return 0;
  67. }
Time limit exceeded #stdin #stdout 5s 6388KB
comments (?)
stdin 
Standard input is empty
stdout 
Enter n:
https://ideone.com/4W5zDO
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!