[LeetCode 51] N-Queens

Question

link

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

Stats

Frequency	3
Difficulty	4
Adjusted Difficulty	4
Time to use	----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is one of the most classic problems of NP (to be precise, NP-hard).

A lot of NP problems are be solved using similar approach, for example: Sudoku, Combinations, Combination Sum, Permutation, Work Break II, Palindrome Partitioning…

I posted my code below. It is very standard solution.

Solution

My solution is similar to the one written in this post.

My code

public class Solution {
    public List<String[]> solveNQueens(int n) {
        List<String[]> ans = new ArrayList<String[]>();
        if (n <= 0) {
            return ans;
        }
        int[] map = new int[n];
        helper(ans, map, 0, n);
        return ans;
    }

    private void helper(List<String[]> ans, int[] map, int row, int n) {
        if (row == n) {
            ans.add(convert(map, n));
            return;
        }
        for (int i = 0; i < n; i++) {
            map[row] = i;
            // check if map[row] conflicts with any row above
            boolean valid = true;
            for (int k = 0; k < row; k++) {
                if (Math.abs(map[k] - map[row]) == row - k || map[k] == map[row]) {
                    // not valid!
                    valid = false;
                    break;
                }
            }
            if (valid) {
                helper(ans, map, row + 1, n);
            }
        }
    }

    private String[] convert(int[] map, int n) {
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            StringBuilder str = new StringBuilder();
            for (int a = 0; a < map[i]; a++) {
                str.append('.');
            }
            str.append('Q');
            for (int a = map[i] + 1; a < n; a++) {
                str.append('.');
            }
            strs[i] = str.toString();
        }
        return strs;
    }
}