Untitled
unknown
plain_text
3 years ago
1.5 kB
13
Indexable
#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; }
Editor is loading...