Algorithm-Analysis-Design-Lab/nqueens(backtracking).cpp at main · Hazrat-Ali9/Algorithm-Analysis-Design-Lab · 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
#include <iostream>
#define n 5
using namespace std;

class nqueens
{
    public:
        void Queen(int board[n][n], int col);
        bool place(int board[n][n], int row, int col);
        void display(int board[n][n]);
};
void nqueens::Queen(int board[n][n], int col)
{

    if (col >= n)
    {
        display(board);
        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (place(board, i, col))
        {
            board[i][col] = 1;
            Queen(board, col + 1);
            board[i][col] = 0;
        }
    }
}

bool nqueens::place(int board[n][n], int row, int col)
{
    int i, j;

    for (i = 0; i < col; i++)
        if (board[row][i])
            return false;

    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j])
            return false;

    for (i = row, j = col; j >= 0 && i < n; i++, j--)
        if (board[i][j])
            return false;

    return true;
}

void nqueens::display(int board[n][n])
{
    cout << "\n";
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << "   " << board[i][j];
        cout << "\n";
    }
}

int main()
{
    nqueens nq;
    int board[n][n] = {{0, 0, 0, 0},
                       {0, 0, 0, 0},
                       {0, 0, 0, 0},
                       {0, 0, 0, 0},
                       {0, 0, 0, 0}};

    nq.Queen(board, 0);
    return 0;
}

/*OUTPUT
D:\Data\Downloads\DAA Codes>g++ nqueens.cpp
D:\Data\Downloads\DAA Codes>a
0   0   1   0
1   0   0   0
0   0   0   1
0   1   0   0

0   1   0   0
0   0   0   1
1   0   0   0
0   0   1   0
*/