51. N-Queens

N-Queens

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

Solution

public class Solution {
      public List<List<String>> solveNQueens(int n) {
        List<List<Integer>> result = new ArrayList<>();
        solve(new ArrayList<>(), n, result);
        List<List<String>> finalResult = result.stream().map(item -> draw(item, n)).collect(Collectors.toList());
        return finalResult;
    }

    private List<String> draw(List<Integer> one, int n) {
        List<String> result = new ArrayList<>();
        for(Integer i: one) {
            StringBuffer sb = new StringBuffer();
            for(int x = 0; x < n; x ++) {
                if (i == x) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            result.add(sb.toString());
        }
        return result;
    }

    private void solve(List<Integer> columns, int n, List<List<Integer>> result) {
        if (columns.size() == n) {
            result.add(new ArrayList<>(columns));
            return;
        }

        for(int i = 0; i < n; i ++) {
            if (checkValid(columns, i)) {
                columns.add(i);
                solve(columns, n, result);
                columns.remove(columns.size()-1);
            }
        }
    }

    private boolean checkValid(List<Integer> columns, int nextColumn) {
        int currentRow = columns.size();
        for(int i = 0; i < columns.size(); i ++) {
            if (columns.get(i) == nextColumn) {
                return false;
            }

            int left = Math.abs(currentRow - i);
            int right = Math.abs(nextColumn - columns.get(i));
            if (left == right) {
                return false;
            }
        }

        return true;
    }

}