N-Queens Leetcode

Here is the reference:
http://blog.csdn.net/u011095253/article/details/9158473

I like the idea of chopping the problems into several pieces.

首先我们弄清楚一下输出，最终输出是ArrayList<String[]>，每一个解是String[], 每一个解的每一行是String

我们当然可以采用上一题，Word Search里更新board内容的方法，不过更新来更新去比较麻烦，这一题我们换个思路

我们把这一题分成几个小问题

1. 传统的dfs递归

2. 验证放置Queen的地方是否合法

3. 输出Board结果

这么做的好处就是，一开始，我们不用建立一个庞大的Board，我们选用一个数组对应Board里面的每一行，数组每一个值对应这一行放置Queen的列号

比如： int[ ] {3,1,4,2} 代表放置的地点分别为[1,3], [2,1], [3,4], [2,4] 这么一来，我们用很简单的用数组表示了整个Board，而且在isValid函数里判断的时候会非常简洁，而且把输出Board单独隔离了出来

public List<String[]> solveNQueens(int n) {
        List<String[]> res = new ArrayList<>();
        int[] loc = new int[n];
        dfs(res, loc, 0, n);
        return res;
    }
   
    private void dfs(List<String[]> res, int[] loc, int curr, int n) {
        if (curr==n) {
            printBoard(res, loc, n);
        } else {
            for (int i=0; i<n; i++) {
                loc[curr] = i;
                if (isValid(loc, curr)) {
                    dfs(res, loc, curr+1, n);
                }
            }
        }
    }
   
    private boolean isValid(int[] loc, int curr) {
        for (int i=0; i<curr; i++) {
            //first condition for column and second condition for diagnal (no need check the row)
            if (loc[i]== loc[curr] || Math.abs(loc[curr]-loc[i]) == (curr-i)) {
                return false;
            }
        }
        return true;
    }
   
    private void printBoard(List<String[]> res, int[] loc, int n) {
        String[] ans = new String[n];
        for (int i=0; i<n; i++) {
            String row = new String();
            for (int j=0; j<n; j++) {
                if (j==loc[i]) {
                    row += "Q";
                } else {
                    row += ".";
                }
            }
            ans[i] = row;
        }
        res.add(ans);
    }