# N Queens

## Question

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 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.

Have you met this question in a real interview? Yes

Example

There exist two distinct solutions to the 4-queens puzzle:

``````[
// Solution 1
[".Q..",
"...Q",
"Q...",
"..Q."
],
// Solution 2
["..Q.",
"Q...",
"...Q",
".Q.."
]
]``````

Challenge Can you do it without recursion?

## Solution

``````import java.util.Arrays;
import java.util.ArrayList;

class Solution {
/**
* Get all distinct N-Queen solutions
* @param n: The number of queens
* @return: All distinct solutions
* For example, A string '...Q' shows a queen on forth position
*/
ArrayList<ArrayList<String>> solveNQueens(int n) {
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
String[] nQueens = new String[n];
char[] init = new char[n];
Arrays.fill(init, '.');
Arrays.fill(nQueens, String.valueOf(Arrays.copyOf(init, n)));
search(n, 0, nQueens, result);
return result;
}

private void search(int n, int row, String[] nQueens, ArrayList<ArrayList<String>> result) {
if (row == n) {
return;
}

for (int col = 0; col < n; col++) {
if (isValid(nQueens, row, col, n)) {
char[] chars;
chars = nQueens[row].toCharArray();
chars[col] = 'Q';
nQueens[row] = String.valueOf(chars);
// nQueens[row][col] = 'Q';
search(n, row + 1, nQueens, result);
chars = nQueens[row].toCharArray();
chars[col] = '.';
nQueens[row] = String.valueOf(chars);
// nQueens[row][col] = '.';
}
}
}

private boolean isValid(String[] nQueens, int row, int col, int n) {
char[] chars;
for (int i = 0; i < row; i++) {
chars = nQueens[i].toCharArray();
if (chars[col] == 'Q') {
return false;
}
}

for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
chars = nQueens[i].toCharArray();
if (chars[j] == 'Q') {
return false;
}
}

for (int  i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
chars = nQueens[i].toCharArray();
if (chars[j] == 'Q') {
return false;
}
}
return true;
}

public static void main(String[] args) {
Solution s = new Solution();
ArrayList<ArrayList<String>> res = s.solveNQueens(Integer.valueOf(args[0]));
// java Solution 4
System.out.println(res);
//[[.Q.., ...Q, Q..., ..Q.], [..Q., Q..., ...Q, .Q..]]
}
};``````

Last updated