Untitled

unknown
plain_text
2 years ago
1.5 kB
10
Indexable
Never
```#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 4

bool canBePlacedQueen(char mat[][N], int currRow, int currCol){

// column - return false if two queens are placed in the same column
for(int i=0; i<currRow; i++){
if(mat[i][currCol] == 'Q') {
return false;
}
}

// left diagonal

int currI = currRow, currJ = currCol;
while(currI >= 0 && currJ >= 0){

if(mat[currI][currJ] == 'Q'){
return false;
}
currI--;
currJ--;
}

// right diagonal

currI = currRow, currJ = currCol;
while(currI >= 0 && currJ < N){

if(mat[currI][currJ] == 'Q'){
return false;
}
currI--;
currJ++;
}

return true;
}

void printMatrix(char mat[][N]){
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
cout << mat[i][j] << " ";
}
cout << endl;
}
}

void fillNQueens(char mat[][N], int currRow){

if(currRow == N){
printMatrix(mat);
cout << "===========" << endl;
return;
}

// i will start placing my queen row by row

for(int currCol = 0; currCol < N; currCol++){

bool value = canBePlacedQueen(mat, currRow, currCol);

if(value){

mat[currRow][currCol] = 'Q';

fillNQueens(mat, currRow + 1);

mat[currRow][currCol] = '*';

}

}
}

int main() {

char mat[N][N];

// initialise it with all the *
memset(mat, '*', sizeof(mat));

// printMatrix(mat);

int currRow = 0;
fillNQueens(mat, currRow);
return 0;
}```