This is a classical backtracking exhaustive search problem. There no shortcuts, you have to brute force through the entire search space.The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

But there are some space optimizations that we can do. Normally a NxN board would be represented by an NxN matrix, but we can use a Nx1 matrix and assign the index of a value to the row (or column). E.g

Code: Select all

```
Q . .
. Q .
. . Q
```

Code: Select all

```
{0, 1, 2}
```

Code: Select all

```
int total = 0;
public int f(int[] board, int idx, int n) {
if (idx == n) {
total++;
return 1;
}
for(int i=0;i<n;i++) {
if (isValid(board, idx, i)) {
board[idx] = i;
int r = f(board, idx + 1,n);
}
}
return -1;
}
```

Code: Select all

```
public boolean isValid(int[] board, int idx, int col) {
for(int i=0;i<idx;i++) {
if (board[i] == col) return false;
if (Math.abs(i - idx) == Math.abs(board[i] - col)) {
return false;
}
}
return true
}
```