八皇后问题

最近接触到八皇后问题，看了下其中一种思路还挺简单，就是全排列然后筛选出斜边也满足的排列方法。比较麻烦的是全排列，特别是用List来存储结果。本来想新建一个List用=来复制原List，发现这样做对新List操作仍会影响原List，所以还是得新建空List再一个个元素添加。

本问题可拓展到N皇后。

全排列解法

public class Test1 {
    public List<List<String>> solveNQueens(int n) {
        
        
        List<Integer> l = new ArrayList<Integer>();
        for(int i = 0; i < n; i++){
            l.add(i);
        }
        
        List<List<Integer>> list = permutation(l,0);
      
        List<List<Integer>> filter = new ArrayList();
        for(int i = 0; i < list.size();i++){
            List<Integer> temp = list.get(i);
            if(valid(temp))filter.add(temp);
        }
    
        List<List<String>> res = new ArrayList<List<String>>();
        for(List<Integer> elem : filter){
            List<String> strList = new ArrayList<String>();
            for(int i = 0; i < elem.size(); i++){
                strList.add(generateStr(elem.size(),elem.get(i)));
            }
            res.add(strList);
        }
        
        return res;
     
    }
    
    public boolean valid(List<Integer> l){
        for(int i = 0; i <l.size() - 1; i++){
            for(int j = i + 1; j < l.size();j++){
                if(l.get(i) - l.get(j) == i - j || l.get(i) - l.get(j) == j - i){
                    return false;
                }
            }
        }
        return true;
    }


    public String generateStr(int n, int index){
        char[] str = new char[n];
        for(int i = 0; i < n; i++){
            str[i] = index == i ? 'Q':'.';
            }
            return new String(str);
    }
        
      
     public List<List<Integer>> combine(int first, List<List<Integer>> list){
            
        List<List<Integer>> res = new ArrayList();

        for(int i = 0; i < list.size(); i++){
            List<Integer> temp = new ArrayList(Arrays.asList(first));
            temp.addAll(list.get(i));
            res.add(temp);
        }

        return res;
    }
            
        
    public void swap(List<Integer> l, int i, int j){
        int temp = l.get(i);
        l.set(i,l.get(j));
        l.set(j,temp);
    }
 
    
    public List<List<Integer>> permutation(List<Integer> l, int from) {
        
        List<List<Integer>> res = new ArrayList();

        if(l.size() == from) return res;
        if(l.size() == from + 1){
            res.add(new ArrayList(Arrays.asList(l.get(from))));
            return res;
        }
        
        for(int i = from; i < l.size(); i++){
            swap(l,from,i);
            res.addAll(combine(l.get(from),permutation(l, from + 1)));
            swap(l,from,i);
        }
        
        return res;
    } 
}

这个时间复杂度比较高，在leetcode测试时N=9就会time limit exceeded。