NQueens

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.

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

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

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

Method:

Use the difference between rows and cols to decide if the queens are on the same diagonal.

Solution:

Time: O(n^n)
Space: O(n^n)

public class Solution {
    public ArrayList<ArrayList<String>> solveNQueens(int a) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> current = new ArrayList<>();
        helper(result, current, a);
        return generateBoards(result);
    }
    
    private void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> current, int a) {
        if (current.size() == a) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = 0; i < a; i ++) {
            if (isValid(current, i)) {
                current.add(i);
                helper(result, current, a);
                current.remove(current.size() - 1);
            }
        }
    }
    
    private boolean isValid(ArrayList<Integer> current, int col) {
        int row = current.size();
        for (int i = 0; i < current.size(); i ++) {
            int existingRow = i;
            int existingCol = current.get(i);
            if (existingRow == row) return false;
            if (existingCol == col) return false;
            if (Math.abs(existingRow - row) == Math.abs(existingCol - col)) {
                return false;
            }
        }
        
        return true;
    }
    
    private ArrayList<ArrayList<String>> generateBoards(ArrayList<ArrayList<Integer>> result) {
        ArrayList<ArrayList<String>> boards = new ArrayList<>();
        for (ArrayList<Integer> list : result) {
            ArrayList<String> board = new ArrayList<>();
            int size = list.size();
            for (int i = 0; i < size; i ++) {
                int queenCol = list.get(i);
                StringBuilder row = new StringBuilder();
                for (int j = 0; j < size; j ++) {
                    row.append(j == queenCol ? 'Q' : '.');
                }
                board.add(row.toString());
            }
            boards.add(board);
        }
        return boards;
    }
}