hacktoberfest/n-Queen-Problem at master · Outlooker007/hacktoberfest · 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
#include <bits/stdc++.h>

using namespace std;
/*********--------- n Queen Problem ---------********* */
#define m 4
#define n 4

bool isSafe(int i, int j, int arr[][m])
{
    int n1 = i, m1 = j;
    // row
    for (int k = i - 1; k >= 0; k--)
    {
        if (arr[k][j] == 1)
            return false;
    }

    // left- daigonal
    while (i >= 0 && j >= 0)
    {
        if (arr[i][j] == 1)
            return false;
        i--;
        j--;
    }
    i = n1;
    j = m1;
    // left- daigonal
    while (i >= 0 && j <= n-1)
    {
        if (arr[i][j] == 1)
            return false;
        i--;
        j++;
    }
    return true;
}

bool maxNumofQueens(int i, int arr[][m])
{
    if (i == n)
    {

        cout << " resultant array : " << endl;
        for (int k = 0; k < n; k++)
        {
            for (int l = 0; l < m; l++)
            {
                if(arr[k][l] == 1){
                    cout<<"Q ";
                }else{
                    cout<<"_ ";
                }
            }
            cout << endl;
        }
        cout << endl;
        return false;
    }

    for (int j = 0; j < n; j++)
    {
        if (isSafe(i, j, arr))
        {
            arr[i][j] = 1;

            bool isPlace = maxNumofQueens(i + 1, arr);

            if (isPlace)
            {
                return true;
            }
            arr[i][j] = 0;
        }
    }
    return false;
}

int main()
{
    int arr[n][m] = {0};

    bool ans = maxNumofQueens(0, arr);
}