N-Queens, Leetcode 解题笔记

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.”, // Solution 2


public class Solution {
    ArrayList<String[]> ret = new ArrayList<String[]>();
    public ArrayList<String[]> solveNQueens(int n) {
        int[] sol = new int[n];
        Arrays.fill(sol, -1);
        placeQ(sol, 0, n);
        return ret;
    public void placeQ(int[] sol, int cur, int n){
        if(cur == n){           
            generateA(sol, n);
            for(int i = 0; i < n; i++){
                sol[cur] = i;
                if(check(sol, cur, n)){
                    placeQ(sol, cur+1, n);
    public boolean check(int[] sol, int cur, int n){
        for(int i = 0; i < cur; i++){
            if(sol[cur] == sol[i] || Math.abs(sol[cur] - sol[i]) == cur - i){
                return false;
        return true;
    public void generateA(int[] sol, int n){
        String [] res = new String[n];
        StringBuilder[] s = new StringBuilder[n];
        for(int i = 0; i < n; i++){
            s[i] = new StringBuilder();
            for(int j = 0; j < n; j++){
        for(int i = 0; i < n; i++){
            s[i].setCharAt(sol[i], 'Q');
            res[i] = s[i].toString();

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s