51 N-Queens

拼搏现实的明天。 2022-08-04 10:55 22阅读 0赞

public class Solution {
    
            public List<List<String>> solveNQueens(int n) {
    
                int[]a=new int[n];
    
            init(a);
    
            int i = 0, j = 0;
            List<List<String>>list=new ArrayList<List<String>>();
    
            while (i < a.length) {
                while (j < a.length) {
    
                    if (isValid(i, j, a)) {
                        a[i] = j;
                        j = 0;
                        break;
                    } else {
                        j++;
                    }
                }
                if (a[i] == -100) {     // 第i行没有找到放置皇后的位置
                    if (i == 0)             // 回溯到第一行，仍然无法找到可以放置皇后的位置，则说明已经找到所有的解，程序终止
                        break;
                    else {
                        i--;
                        j = a[i] + 1;       // 上一行皇后的位置向后移一列
                        a[i] = -100;        // 上一行皇后的位置清除
                        continue;   
                    }
                }
                if (i == (a.length - 1)) {  // 最后一行找到皇后位置，说明找到一个解
                    list.add(print(a));
                    j = a[i] + 1;
                    a[i] = -100;
                    continue;
                }
                i++;
            }
            return list;
        }  
    
        private static void init(int[] a) {
            for (int i = 0; i < a.length; i++) {
                a[i] = -100;
            }
        }
    
        private static boolean isValid(int row, int col, int[] a) {
    
            for (int i = 0; i < a.length; i++) {
                if (a[i] == col || Math.abs(i - row) == Math.abs(a[i] - col)) {
                    return false;
                }
            }
    
            return true;
        }
    
        private static List<String> print(int[] a) {
    
            List<String>res=new ArrayList<String>();
    
            String str="";
    
            for (int i = 0; i < a.length; i++) {
    
                str="";
    
                for (int j = 0; j < a.length; j++) {
    
                    if (a[i] != j)
                        str+=".";
                    else
                        str+="Q";
                }
                res.add(str);
            }
            return res;
        }
    }

参考[N皇后问题的两个最高效的算法][N]

[N]: http://blog.csdn.net/hackbuteer1/article/details/6657109