DSA-Practice/N_Queens_1_Practice.cpp at main · TheMahirK/DSA-Practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <vector>
#include <string>
using namespace std;

void printBoards(vector<vector<string>> &boards)
{
    int count = 1;
    for (auto &board : boards)
    {
        cout << "Sol : " << count << endl;
        for (auto row : board)
        {
            cout << row << endl;
        }
        count++;
        cout << endl;
    }
}

bool isSafe(int row, int col, vector<string> &board)
{
    int dupl_row = row;
    int dupl_col = col;

    // for upper left diagonal
    while(row >= 0 && col >= 0)
    {
        if(board[row][col] == 'Q')
            return false;
        row--;
        col--;
    }

    // to reset row & col
    row = dupl_row;
    col = dupl_col;

    // for left diagonal
    while(col >= 0)
    {
        if(board[row][col] == 'Q')
            return false;
        col--;
    }

    col = dupl_col;

    // for lower left diagonal
    while(row < board.size() && col >= 0)
    {
        if(board[row][col] == 'Q')
            return false;
        row++;
        col--;
    }

    return true;

}

void solve(int col, vector<vector<string>> &result, vector<string> &board)
{
    if(col == board.size())
    {
        result.push_back(board);
    }

    for(int row=0; row<board.size(); row++)
    {
        if(isSafe(row,col,board))
        {
            board[row][col] = 'Q';
            solve(col+1,result,board);
            board[row][col] = '.';
        }
    }
}


vector<vector<string>> solveNQueens(int n)
{
    vector<vector<string>> result;
    vector<string> board(n);
    string s(n,'.');
    for(int i=0; i<n; i++)
    {
        board[i] = s;
    }

    solve(0,result,board);
    return result;

}

int main()
{

    int n = 4;

    vector<vector<string>> result;
    result = solveNQueens(n);

    printBoards(result);


    return 0;
}