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**