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.

8-queens

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

还是DFS递归题,每次处理一行,往这一行里添加Queen,然后检查是否valid。

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);
        }
        else{
            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++){
                s[i].append('.');
            }
            
        }
        for(int i = 0; i < n; i++){
            s[i].setCharAt(sol[i], 'Q');
            res[i] = s[i].toString();
        }
        
        ret.add(res);
    }
}
Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s