# 51. N-Queens

### Description

 The *n*-queens puzzle is the problem of placing *n* queens on an *n*×*n* chessboard such that no two queens attack each other.

![](https://1091135627-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmU-aGQcUvtjjAH8_3%2F-MFBzZRe3btsM9_ILW-I%2F-MFBzuJuZYMz3bzn9dX0%2Fimage.png?alt=media\&token=ed3be0c3-dd12-4b31-98ee-8f8b67c63df9)

Given an integer *n*, return all distinct solutions to the *n*-queens puzzle.

Each solution contains a distinct board configuration of the *n*-queens' placement, where `'Q'` and `'.'` both indicate a queen and an empty space respectively.

### Constraints

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/n-queens/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** 4

**Output:** 

\[

// Solution 1

\[ ".Q..", "...Q", "Q...", "..Q." ],

// Solution 2

\[ "..Q.", "Q...", "...Q", ".Q.." ]

]

**Explanation:** There exist two distinct solutions to the 4-queens puzzle as shown above.
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(N!). There is N possibilities to put the first queen, 
 *    not more than N (N - 2) to put the second one, not more than N(N-2)(N-4) 
 *    for the third one etc. In total that results in O(N!) time complexity.
 * Space complexity : O(N) to keep an information about diagonals and rows.
 */

class Solution {
    private Set<Integer> col = new HashSet<>();
    private Set<Integer> hill = new HashSet<>();
    private Set<Integer> dale = new HashSet<>();
    
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> resultList = new ArrayList<>();
        backtrack(resultList, new ArrayList<String>(), 0, n);
        return resultList;
    }
    
    private void backtrack(List<List<String>> resultList,
                           List<String> currList,
                           int row,
                           int n) {
        if(row == n) {
            resultList.add(new ArrayList(currList));
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if(col.contains(i) || 
                hill.contains(row+i) || 
                dale.contains(row-i)) {
                continue;
            }

            char[] rowArr = new char[n];
            Arrays.fill(rowArr, '.');
            rowArr[i] = 'Q';
            String rowStr = new String(rowArr);

            currList.add(rowStr);
            col.add(i);
            hill.add(row+i);
            dale.add(row-i);

            backtrack(resultList, currList, row+1, n);

            currList.remove(currList.size()-1);
            col.remove(i);
            hill.remove(row+i);
            dale.remove(row-i);
        }
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private boolean[] cols;
    private boolean[] hills;
    private boolean[] dales;
    
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> resultList = new ArrayList<>();
        if(n == 0) resultList.add(new ArrayList<>());
        if(n == 1) resultList.add(List.of("Q"));
        if(n > 3) {
            cols = new boolean[n];
            hills = new boolean[n*2 - 1];
            dales = new boolean[n*2 - 1];
            char[][] board = new char[n][n];
            for(char[] arr: board) {
                Arrays.fill(arr, '.');
            }
            backtrack(resultList, board, 0, n);
        }
        return resultList;
    }
    
    private void backtrack(List<List<String>> resultList,
                           char[][] board,
                           int row,
                           int n) {
        if(row == n) {
            ArrayList<String> tempList = new ArrayList();
            for(char[] arr: board) {
                tempList.add(new String(arr));
            }
            resultList.add(tempList);
            return;
        }
        
        for(int col = 0; col < n; col++) {
            if(cols[col] || hills[row+col] || dales[row-col+n-1]) {
                continue;
            }

            board[row][col] = 'Q';
            cols[col] = true;
            hills[row+col] = true;
            dales[row-col+n-1] = true;

            backtrack(resultList, board, row+1, n);

            board[row][col] = '.';
            cols[col] = false;
            hills[row+col] = false;
            dales[row-col+n-1] = false;
        }
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

* Check if a Queen can attack a given cell on chessboard - [GFG](https://www.geeksforgeeks.org/check-if-a-queen-can-attack-a-given-cell-on-chessboard/)
* Check if the given chessboard is valid or not - [GFG](https://www.geeksforgeeks.org/check-if-the-given-chessboard-is-valid-or-not/)
* Job Sequencing Problem - [GFG](https://www.geeksforgeeks.org/job-sequencing-problem/)