n_queen

PHOTO EMBED

Fri Jul 02 2021 18:33:06 GMT+0000 (UTC)

Saved by @zs #c++

#include<iostream>
using namespace std;
bool issafe(int** arr,int x,int y,int n){
    for(int row=0;row<x;row++){
        if(arr[row][y]==1) return false;
    }
    int row=x-1;
    int col=y-1;
    while(row>=0 && col>=0){
        if(arr[row][col]==1)return false;
        row--;
        col--;
    }
     row=x-1;
     col=y+1;
    while(row>=0 && col<n){
        if(arr[row][col]==1)  return false;
        row--;
        col++;
    }
    return true ;
}
bool nqueen(int** arr,int n,int x=0){
    if(x>=n) return true;
    for(int col=0;col<n;col++){
        if(issafe(arr,x,col,n)){
            arr[x][col]=1;
            if(nqueen(arr,n,x+1)) return true;
            arr[x][col]=0;  //backtracking
        }
    }
    return false;
}
int main(){
    int n;
    cin>>n;
    int **arr=new int*[n];
    for(int i=0;i<n;i++){
        arr[i]=new int[n];
        for(int j=0;j<n;j++) arr[i][j]=0;
    }
    if(nqueen(arr,n)){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++) cout<<arr[i][j]<<" ";
            cout<<endl;
        }
    }
    return 0;
}
content_copyCOPY