fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //Store in vector queens positions
  5. //Check for attaks to return 0 or start searching for best positions
  6. //Mark each position, diagonals, row and columns
  7. //Only one queen per row/column/diagonal
  8.  
  9. //Time complexity -> O(n!)
  10. //Space -> O(n)
  11.  
  12. bool backtrack(int row, int queens, bool col[8], bool diag1[15], bool diag2[15], vector<pair<int,int>>& positions) {
  13.     if(queens == 8) return true;
  14.     if(row >= 8) return false;
  15.  
  16.     bool hasQueen = false;
  17.     for(auto &p : positions){
  18.         if(p.first == row){
  19.             hasQueen = true;
  20.             break;
  21.         }
  22.     }
  23.     if(hasQueen) return backtrack(row + 1, queens, col, diag1, diag2, positions);
  24.  
  25.     for(int c = 0; c < 8; c++){
  26.         if(!col[c] && !diag1[row + c] && !diag2[row - c + 7]){
  27.             col[c] = diag1[row + c] = diag2[row - c + 7] = true;
  28.             positions.push_back({row, c});
  29.             if(backtrack(row + 1, queens + 1, col, diag1, diag2, positions)) return true;
  30.             col[c] = diag1[row + c] = diag2[row - c + 7] = false;
  31.             positions.pop_back();
  32.         }
  33.     }
  34.  
  35.     return false;
  36. }
  37.  
  38. int main() {
  39.     int n;
  40.     cin >> n;
  41.  
  42.     vector<pair<int,int>> positions;
  43.     bool col[8] = {false};
  44.     bool diag1[15] = {false};
  45.     bool diag2[15] = {false};
  46.  
  47.     for(int i = 0; i < n; i++){
  48.         int x, y;
  49.         cin >> x >> y;
  50.         x--; y--;
  51.         if(col[y] || diag1[x + y] || diag2[x - y + 7]){
  52.             cout << 0;
  53.             return 0;
  54.         }
  55.         positions.push_back({x, y});
  56.         col[y] = true;
  57.         diag1[x + y] = true;
  58.         diag2[x - y + 7] = true;
  59.     }
  60.  
  61.     if(!backtrack(0, n, col, diag1, diag2, positions)){
  62.         cout << 0;
  63.         return 0;
  64.     }
  65.  
  66.     for(auto &p : positions){
  67.         cout << p.first + 1 << " " << p.second + 1 << endl;
  68.     }
  69.  
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
2
1 4
7 1
stdout
copy 
1 4
7 1
2 2
3 7
4 3
5 6
6 8
8 5
https://ideone.com/gVCxHf
language:
C++ (gcc 8.3)
created:
8 hours ago
visibility:
public

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!