fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void printAns(vector<vector<string>>& ans){
  5.     for(int i=0; i<ans.size(); i++){
  6.         for(int j=0; j<ans[i].size(); j++){
  7.             cout<<ans[i][j]<<'\n';
  8.         }
  9.     }
  10. }
  11.  
  12. bool isValid(int row, int col, int n, vector<string>& res){
  13.     for(int i=0; i<col; i++){
  14.         if(res[row][i]=='Q') return false;
  15.     }
  16.     for(int i=row-1; i>=0; i--){
  17.         for(int j=col-1; j>=0; j--){
  18.             if(res[i][j]=='Q') return false;
  19.         }
  20.     }
  21.     for(int i=row+1; i<n; i++){
  22.         for(int j=col-1; j>=0; j--){
  23.             if(res[i][j]=='Q') return false;
  24.         }
  25.     }
  26.     return true;
  27. }
  28.  
  29. void backTrack(int n, int col, vector<vector<string>>& ans, vector<string>& res){
  30.  
  31.     if(col>=n){
  32.         ans.push_back(res);
  33.         return;
  34.     }
  35.  
  36.     for(int i=0; i<n; i++){
  37.         if(isValid(i,col,n,res)){
  38.             res[i][col]='Q';
  39.             backTrack(n,col+1,ans,res);
  40.             res[i][col]='.';
  41.         }
  42.     }
  43.  
  44. }
  45.  
  46. int main(){
  47.  
  48.     ios::sync_with_stdio(false);
  49.     cin.tie(0);
  50.  
  51.     int n;
  52.     cin >> n;
  53.     vector<vector<string>> ans;
  54.     vector<string> res;
  55.  
  56.     for(int i=0; i<n; i++){
  57.         string s(n,'.');
  58.         res.push_back(s);
  59.     }
  60.  
  61.     backTrack(n,0,ans,res);
  62.     printAns(ans);
  63.  
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0s 4512KB
comments (?)
stdin
copy 
8
stdout
copy 
Standard output is empty
https://ideone.com/jmfChs
language:
C++14 (gcc 8.3)
created:
3 years 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!