N-queen Visualizer is a project where we try to put the queen in chess board. We can put the queens in such way that they can't attack each other.We know the queens can attack each other in same column, same row and in diagonal
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isSafe(int row, int col, vector<string>board, int n)
{
int dup_row = row;
int dup_col = col;
//left up corner
while (row >= 0 && col >= 0)
{
if (board[row][col] == 'Q') return false;
row--;
col--;
}
row = dup_row;
col = dup_col;
//left straight
while (col >= 0)
{
if (board[row][col] == 'Q') return false;
col--;
}
row = dup_row;
col = dup_col;
//left down corner
while (row < n && col >= 0)
{
if (board[row][col] == 'Q') return false;
row++;
col--;
}
return true;
}
void solve(int col, vector<string>&board, vector<vector<string>>&ans, int n)
{
if (col == n)
{
ans.push_back(board);
return;
}
for (int row = 0; row < n; row++)
{
if (isSafe(row, col, board, n))
{
board[row][col] = 'Q';
solve(col + 1, board, ans, n);
board[row][col] = '.';
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>>ans;
vector<string>board(n);
string s(n, '.');
for (int i = 0; i < n; i++)
{
board[i] = s;
}
solve(0, board, ans, n);
return ans;
}
};
int main()
{
Solution s;
int n;
cin >> n;
vector<vector<string>>ans = s.solveNQueens(n);
for (auto it : ans)
{
for (auto i : it)
{
cout << i << endl;
}
cout << "---------" << endl;
}
return 0;
}