Untitled

mail@pastecode.io avatar
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;
}