fork download
copy 
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. bool isSafe(int board[][10], int i, int j, int n){
  5.     //you can check for column
  6.     for(int row=0;row<i;row++){
  7.         if(board[row][j]==1){
  8.             return false;
  9.         }
  10.     }
  11.  
  12.     //you can check for left diagonl
  13.     int x = i;
  14.     int y = j;
  15.     while(x>=0 && y>=0)
  16.     {
  17.         if(board[x][y]==1){
  18.             return false;
  19.         }
  20.        x--;
  21.        y--;
  22.     }
  23.  
  24.     //you can check for right diagonal
  25.     x = i;
  26.     y = j;
  27.     while(x>=0 && y<n)
  28.     {
  29.         if(board[x][y]==1){
  30.             return false;
  31.         }
  32.        x--;
  33.        y++;
  34.     }
  35.     //the position is now safe, column and diagonals
  36.     return true;
  37. }
  38. bool solveNQueen(int board[][10],int i, int n){
  39.     //base case
  40.     if(i==n){
  41.         //you hav successfully place queens in n rows( 0,....,n-1);
  42.         //print the board;
  43.         for(int i=0;i<n;i++){
  44.             for(int j=0;j<n;j++){
  45.                 if(board[i][j]==1){
  46.                     cout<<"Q";
  47.                 }
  48.                 else{
  49.                     cout<<"_ ";
  50.                 }
  51.             }
  52.             cout<<endl;
  53.         }
  54.             return true;
  55.     }
  56.     //rec case
  57.     //try to place the queen in the current row and call on the remaining mart which will b done by recursion
  58.     for(int j=0;j<n;j++){
  59.         //i hav to check if i,j th position is safe to place the  queen or not
  60.         if(isSafe(board,i,j,n)){
  61.             //place the queen - assuming i,j is the correct position
  62.             board[i][j]=1;
  63.  
  64.             bool nextQueenRakhPaye = solveNQueen(board,i+1,n);
  65.             if(nextQueenRakhPaye){
  66.                 return true;
  67.             }
  68.            //means i,j if not the correct position - Assumption is wrong
  69.            board[i][j]=0;//backtrack
  70.         }
  71.     }
  72.     //you hav tried all positions in a current row but couldn't place the queen
  73.     return true;
  74. }
  75.  
  76. int main(){
  77.     int n;
  78.     cin>>n;
  79.     int board[10][10] = {0};
  80.  
  81.     solveNQueen(board,0,n);
  82. return 0;}
  83.  
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/54UYFQ
language:
C++ (gcc 8.3)
created:
6 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!