Leetcode: N-Queens

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

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

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

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

Understand the problem:
It is a classic N-queue problem. The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an n×n chessboard, where solutions exist for all natural numbers n with the exception of n=2 or n=3. 

Solution:
This is again a classic permutation and combination problem. So we can still apply the same recursive approach. 

Code (Java):

?

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

public class Solution {     public List<String[]> solveNQueens(int n) {         List<String[]> result = new ArrayList<String[]>();                   if (n == 0 || n == 2 || n == 3) {             return result;         }                   solveNqueensHelper(n, 0, new int[n], result);                   return result;     }           private void solveNqueensHelper(int n, int row, int[] cols, List<String[]> result) {         if (row == n) {             String[] solution = new String[n];             for (int i = 0; i < n; i++) {                 StringBuilder temp = new StringBuilder();                 for (int j = 0; j < n; j++) {                     if (cols[i] == j) {                         temp.append('Q');                     } else {                         temp.append('.');                     }                 }                 solution[i] = temp.toString();             }             result.add(solution);             return;         }                   for (int j = 0; j < n; j++) {             if (isValid(j, row, cols) == true) {                 cols[row] = j;                 solveNqueensHelper(n, row + 1, cols, result);             }         }     }           private boolean isValid(int col, int row, int[] cols) {         for (int i = 0; i < row; i++) {             if (col == cols[i] || row - i == Math.abs(col - cols[i])) {                 return false;             }         }         return true;     } }