# N-Queens

## Problem

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.

## 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?

## Code - Java

class Solution {

private ArrayList<ArrayList<String>> result;

/**
* 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) {
result = new ArrayList<ArrayList<String>>();
placeQueen(new int[n], 0, n);
return result;
}

private void placeQueen(int[] board, int row, int nQueens) {
if (row == nQueens) {
return;
}

for (int i = 0; i < nQueens; i++) {
board[row] = i;
if (isValid(board, row)) {
placeQueen(board, row + 1, nQueens);
}
}
}

private boolean isValid(int[] board, int row) {
for (int i = 0; i < row; i++) {
if (board[i] == board[row] || row - i == Math.abs(board[i] - board[row])) {
return false;
}
}
return true;
}

private void addToResult(int[] board) {
ArrayList<String> solution = new ArrayList<>();
for (int i = 0; i < board.length; i++) {
String s = "";
for (int j = 0; j < board.length; j++) {
if (board[i] == j) {
s += 'Q';
} else {
s += '.';
}
}
};