Given a chess board having cells (NxN), N number queens needs to placed on the board in such a way that no queen attacks any other queen.
Input:
The only line of input consists of a single integer denoting N.
Output:
If it is possible to place all the N queens in such a way that no queen attacks another queen, then print “YES” followed by N lines having N integers. The integer in line and column will denote the cell of the board and should be 1 if a queen is placed at otherwise 0. If there are more than way of placing queens print any of them. If it is not possible to place all N queens in the desired way, then print “FALSE” (without quotes).
Input 4 Output YES 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0
#include <iostream>
#include <vector>
using namespace std;
#define N 8
void print(vector<vector<int>>& board) {
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board.size(); j++) {
cout << board[i][j] << " ";
}
cout << endl;
}
}
bool isValid(vector<vector<int>>& board, int r, int c) {
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board.size(); j++) {
if (board[r][j] || board[i][c]) return false;
if ((i - j == r - c) || (i + j == r + c)) {
if (board[i][j]) return false;
}
}
}
return true;
}
bool NQueen(vector<vector<int>>& board, int n) {
if (n <= 0) return true;
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board.size(); j++) {
if (isValid(board, i, j)) {
board[i][j] = 1;
if (NQueen(board, n - 1)) return true;
board[i][j] = 0;
}
}
}
return false;
}
int main() {
vector<vector<int>> board(N, vector<int>(N, 0));
if (NQueen(board, N)) {
cout << "YES" << endl;
print(board);
} else
cout << "NO" << endl;
return 0;
}YES 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0
References