n皇后问题的多种解法

问题

n-Queen 问题：在一个 n*n 的国际象棋棋盘上摆放 n 个皇后，使得所有皇后都是安全的（任意 2 个皇后不能出现在同一条直线或斜率为 1，-1 的斜线上）。每一个这样的棋盘成为一个解。

算法

PlanA：由于每列皇后只能存在一个，因此将每列皇后的位置穷举出来，并判断每个穷举出来的结果是否符合规则。例如 n=5，1 1 1 1 1 代表每列的皇后都在第一行的位置。这个算法的时间复杂度是 O(n^n)，空间复杂度是 O(n^n)。

PlanB：PlanA 中存在过度的计算，因为我们已知皇后不能在同行同列，因此我们可以生成排列，并判断这个排列是否符合规范。例如：n=5，1 5 4 3 2、1 3 2 5 4。这个算法的时间复杂度是 O(n!)，空间复杂度是 O(n!)

PlanC：由于 PlanB 是将全部的排列生成后，将这些排列一一判断，这个过程使用了大量的内存，因此我们采用 Pipe and Filter 策略，在每生成一个排列的时候，就将这个排列进行判断。同时采用一种内存占用较小的 JohnsonTrotter 算法来生成排列。算法时间复杂度 O(n!)，空间复杂度 O(1)（不考虑 JohnsonTrotter 的内存开销）

PlanD：可以发现 PlanC 中，对于所有当 n=5 的情况下，所有 1 2 开头的皇后排序方式都不可行，因为 1 2 在同一条斜线上，因此使用剪枝的方法，当存在此情况时，将整个子树删除不再计算。时间复杂度(最坏条件下)O(n!)。

PlanE：对于 PlanD 中，发现 CPU 占用不高，可能时因为 I/O 开销过大，因此采用 Shared Data 策略，使用多线程（n 线程，n 为皇后数），将不同开头的皇后分配给不同线程，例如第一列皇后处于第一行的在线程 1，处于第二行的在线程 2，以此类推。

算法测试

代码

1.main.java

import java.io.File;
import java.io.FileWriter;
import java.util.ArrayList;

public class main {
    static int n = 0;
    static int startTime = 1;

    static boolean WithoutAnswer = true;
    static int times = 20;

    public static void main(String[] args) throws Exception {
        //csv

        FileWriter fileWriter = new FileWriter(new File("result.csv"));

        fileWriter.write("n,PlanA,PlanB,PlanC,PlanD,PlanE\n");

        boolean isErrorHappened[] = new boolean[5];
        for (boolean i : isErrorHappened) {
            i = false;
        }

        for (int i = startTime; i <= times; i++) {
            System.out.println("Current n:" + i);
            main.n = i;
            Long A = null,B = null,C = null,D = null,E = null;
            if (!isErrorHappened[0]) {
                A = calculateTime(new PlanA());
                if (A != null) {
                    isErrorHappened[0] = false;
                } else {
                    isErrorHappened[0] = true;
                }
            }

            if (!isErrorHappened[1]) {
                B = calculateTime(new PlanB());
                if (B != null) {
                    isErrorHappened[1] = false;
                } else {
                    isErrorHappened[1] = true;
                }
            }

            if (!isErrorHappened[2]) {
                C = calculateTime(new PlanC());
                if (C != null) {
                    isErrorHappened[2] = false;
                } else {
                    isErrorHappened[2] = true;
                }
            }

            if (!isErrorHappened[3]) {
                D = calculateTime(new PlanD());
                if (D != null) {
                    isErrorHappened[3] = false;
                } else {
                    isErrorHappened[3] = true;
                }
            }

            if (!isErrorHappened[4]) {
                E = calculateTime(new PlanE());
                if (E != null) {
                    isErrorHappened[4] = false;
                } else {
                    isErrorHappened[4] = true;
                }
            }


            // writing to csv
            fileWriter.write(i + "," + ((A == null) ? ("Error") : (A.toString())) + "," + ((B == null) ? ("Error") : (B.toString())) + "," + ((C == null) ? ("Error") : (C.toString())) + "," + ((D == null) ? ("Error") : (D.toString())) + "," + ((E == null) ? ("Error") : (E.toString())) + "\n");

        }

        fileWriter.close();

    }

    final static boolean CANPRINT = false;

    public static void print(ArrayList<ArrayList<String>> result) {
        if (!CANPRINT) {
            return;
        }

        for (ArrayList<String> s : result) {
            for (String ss : s) {
                System.out.println(ss);
            }
            System.out.println();
        }
    }

    public static Long calculateTime(Plan p) {
        if (WithoutAnswer) {
            long start = System.currentTimeMillis();
            boolean fail = false;
            Integer result = 0;
            try {
                result = p.nQueenWithoutAnswer(n);

            } catch (Error e) {
                e.printStackTrace();
                fail = true;
            } catch (Exception e) {
                e.printStackTrace();
                fail = true;
            }
            long end = System.currentTimeMillis();

            System.out.println(p.getClass().getName() + "@n=" + n);
            System.out.println("Time:");
            System.out.println(end - start);
            System.out.println("Answer:");
            System.out.println(result);

            return fail ? null : (end - start);
        } else {
            long start = System.currentTimeMillis();
            boolean fail = false;
            ArrayList<ArrayList<String>> result = new ArrayList<>();
            try {
                result = p.nQueen(n);
                print(result);

            } catch (Error e) {
                e.printStackTrace();
                fail = true;
            } catch (Exception e) {
                e.printStackTrace();
                fail = true;
            }
            long end = System.currentTimeMillis();

            System.out.println(p.getClass().getName() + "@n=" + n);
            System.out.println("Time:");
            System.out.println(end - start);
            System.out.println("Answer:");
            System.out.println(result.size());

            return fail ? null : (end - start);
        }
    }


}

2.Plan.java

import java.util.ArrayList;

public abstract class Plan {
    public abstract ArrayList<ArrayList<String>> nQueen(int n);
    public abstract int nQueenWithoutAnswer(int n);
}

3.PlanA.java

import java.util.ArrayList;

public class PlanA extends Plan {

    @Override
    public ArrayList<ArrayList<String>> nQueen(int n) {
        // 将所有皇后的位置枚举出来
        // 由于皇后不能在同一行，所以每一行只能有一个皇后
        // 所以可以用一个一维数组来表示皇后的位置
        // 例如 1 1 1 1
        // 表示第一行的皇后在第一列，第二行的皇后在第一列，第三行的皇后在第一列，第四行的皇后在第一列

        ArrayList<ArrayList<Integer>> possible = generatePattern(n);
        ArrayList<ArrayList<String>> valid = new ArrayList<>();
        for (ArrayList<Integer> a : possible) {
            if (checkValid(a)) {
                ArrayList<String> temp = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    StringBuilder sb = new StringBuilder();
                    for (int j = 0; j < n; j++) {
                        if (j == a.get(i) - 1) {
                            sb.append("Q");
                        } else {
                            sb.append("#");
                        }
                    }
                    temp.add(sb.toString());
                }
                valid.add(temp);
            }
        }

        return valid;

    }
    @Override
    public int nQueenWithoutAnswer(int n) {
        // 将所有皇后的位置枚举出来
        // 由于皇后不能在同一行，所以每一行只能有一个皇后
        // 所以可以用一个一维数组来表示皇后的位置
        // 例如 1 1 1 1
        // 表示第一行的皇后在第一列，第二行的皇后在第一列，第三行的皇后在第一列，第四行的皇后在第一列

        ArrayList<ArrayList<Integer>> possible = generatePattern(n);
        Integer valid = 0;
        for (ArrayList<Integer> a : possible) {
            if (checkValid(a)) {
                valid++;
            }
        }

        return valid;

    }
    public ArrayList<ArrayList<Integer>> generatePattern(int n) {
        // 生成皇后所有可能的位置
        ArrayList<ArrayList<Integer>> result = helper(n, n);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        for (int i = 0; i < result.size(); i++) {
            ArrayList<Integer> temp = result.get(i);
            for (int j = 0; j < temp.size(); j++) {
                temp.set(j, temp.get(j) + 1);
            }
            res.add(temp);
        }
        return res;
    }

    ArrayList<ArrayList<Integer>> helper(int n, int l) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (l == 1) {
            for (int i = 1; i <= n; i++) {
                ArrayList<Integer> temp = new ArrayList<>();
                temp.add(i);
                result.add(temp);
            }
            return result;
        }
        ArrayList<ArrayList<Integer>> last = helper(n, l - 1);
        for (ArrayList<Integer> a : last) {
            for (int i = 1; i <= n; i++) {
                ArrayList<Integer> temp = new ArrayList<>(a);
                temp.add(i);
                result.add(temp);
            }
        }
        return result;
    }

    public boolean checkValid(ArrayList<Integer> plate) {
        for (int i = 0; i < plate.size(); i++) {
            for (int j = i + 1; j < plate.size(); j++) {
                if (plate.get(i).equals(plate.get(j))) {
                    return false;
                }
                if (Math.abs(plate.get(i) - plate.get(j)) == Math.abs(i - j)) {
                    return false;
                }
            }
        }
        return true;
    }
}

4.PlanB.java

import java.util.ArrayList;

public class PlanB extends Plan {
    @Override
    public ArrayList<ArrayList<String>> nQueen(int n) {
        // 将所有皇后的位置通过排列组合枚举出来
        // 然后检查是否合理

        ArrayList<ArrayList<Integer>> possible = generatePattern(n);
        ArrayList<ArrayList<String>> valid = new ArrayList<>();
        for (ArrayList<Integer> a : possible) {
            if (checkValid(a)) {
                ArrayList<String> temp = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    StringBuilder sb = new StringBuilder();
                    for (int j = 0; j < n; j++) {
                        if (j == a.get(i) - 1) {
                            sb.append("Q");
                        } else {
                            sb.append("#");
                        }
                    }
                    temp.add(sb.toString());
                }
                valid.add(temp);
            }
        }

        return valid;
    }
    @Override
    public int nQueenWithoutAnswer(int n) {
        // 将所有皇后的位置通过排列组合枚举出来
        // 然后检查是否合理

        ArrayList<ArrayList<Integer>> possible = generatePattern(n);
        Integer valid = 0;
        for (ArrayList<Integer> a : possible) {
            if (checkValid(a)) {
                valid++;
            }
        }

        return valid;
    }
    public ArrayList<ArrayList<Integer>> generatePattern(int n) {
        // 生成皇后所有可能的位置
        if (n == 1) {
            ArrayList<ArrayList<Integer>> temp = new ArrayList<>();
            ArrayList<Integer> t = new ArrayList<>();
            t.add(1);
            temp.add(t);
            return temp;
        }

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<ArrayList<Integer>> temp = generatePattern(n - 1);

        // 中间插入第n个数字
        for (ArrayList<Integer> t : temp) {
            for (int i = 0; i < n; i++) {
                ArrayList<Integer> tt = new ArrayList<>(t);
                tt.add(i, n);
                result.add(tt);
            }
        }
        return result;
    }



    public boolean checkValid(ArrayList<Integer> plate) {
        for (int i = 0; i < plate.size(); i++) {
            for (int j = i + 1; j < plate.size(); j++) {
                if (plate.get(i).equals(plate.get(j))) {
                    return false;
                }
                if (Math.abs(plate.get(i) - plate.get(j)) == Math.abs(i - j)) {
                    return false;
                }
            }
        }
        return true;
    }
}

5.PlanC.java

import java.util.ArrayList;

public class PlanC extends Plan {
    @Override
    public ArrayList<ArrayList<String>> nQueen(int n) {
        // 与PlanB相似，但是流式处理 防止内存溢出
        // 步骤：
        // 将所有皇后的位置通过排列组合枚举出来
        // 然后检查是否合理

        // 每生成一个排列 就立刻判断是否合法

        // 排列使用 JohnsonTrotter 算法
        // 算法代码来自:https://introcs.cs.princeton.edu/java/23recursion/JohnsonTrotter.java.html

        perm(n);
        return result;
    }


    @Override
    public int nQueenWithoutAnswer(int n) {
        // 与PlanB相似，但是流式处理 防止内存溢出
        // 步骤：
        // 将所有皇后的位置通过排列组合枚举出来
        // 然后检查是否合理

        // 每生成一个排列 就立刻判断是否合法

        // 排列使用 JohnsonTrotter 算法
        // 算法代码来自:https://introcs.cs.princeton.edu/java/23recursion/JohnsonTrotter.java.html

        permWithoutAnswer(n);
        return resultInt;
    }

    ArrayList<ArrayList<String>> result = new ArrayList<>();
    Integer resultInt = 0;

    public void perm(int n) {
        int[] p = new int[n]; // permutation
        int[] pi = new int[n]; // inverse permutation
        int[] dir = new int[n]; // direction = +1 or -1
        for (int i = 0; i < n; i++) {
            dir[i] = -1;
            p[i] = i;
            pi[i] = i;
        }
        perm(0, p, pi, dir);
    }

    public void permWithoutAnswer(int n) {
        int[] p = new int[n]; // permutation
        int[] pi = new int[n]; // inverse permutation
        int[] dir = new int[n]; // direction = +1 or -1
        for (int i = 0; i < n; i++) {
            dir[i] = -1;
            p[i] = i;
            pi[i] = i;
        }
        permWithoutAnswer(0, p, pi, dir);
    }

    public void permWithoutAnswer(int n, int[] p, int[] pi, int[] dir) {
        if (n >= p.length) {
            // 这里生成了一个排列
            // 检查一下这个排列是否合法
            // 如果合法则输出
            boolean valid = checkValid(p);
            if (valid) {
                resultInt++;
            }
            return;
        }
        permWithoutAnswer(n + 1, p, pi, dir);
        for (int i = 0; i <= n - 1; i++) {

            // swap
            int z = p[pi[n] + dir[n]];
            p[pi[n]] = z;
            p[pi[n] + dir[n]] = n;
            pi[z] = pi[n];
            pi[n] = pi[n] + dir[n];

            permWithoutAnswer(n + 1, p, pi, dir);
        }
        dir[n] = -dir[n];
    }

    public void perm(int n, int[] p, int[] pi, int[] dir) {
        if (n >= p.length) {
            // 这里生成了一个排列
            // 检查一下这个排列是否合法
            // 如果合法则输出
            boolean valid = checkValid(p);
            if (valid) {
                ArrayList<String> temp = new ArrayList<>();
                for (int j = 0; j < p.length; j++) {
                    StringBuilder sb = new StringBuilder();
                    for (int k = 0; k < p.length; k++) {
                        if (k == p[j]) {
                            sb.append("Q");
                        } else {
                            sb.append("#");
                        }
                    }
                    temp.add(sb.toString());
                }
                result.add(temp);
            }
            return;
        }
        perm(n + 1, p, pi, dir);
        for (int i = 0; i <= n - 1; i++) {

            // swap
            int z = p[pi[n] + dir[n]];
            p[pi[n]] = z;
            p[pi[n] + dir[n]] = n;
            pi[z] = pi[n];
            pi[n] = pi[n] + dir[n];

            perm(n + 1, p, pi, dir);
        }
        dir[n] = -dir[n];
    }

    public boolean checkValid(int[] plate) {
        for (int i = 0; i < plate.length; i++) {
            for (int j = i + 1; j < plate.length; j++) {
                if (plate[i] == plate[j]) {
                    return false;
                }
                if (Math.abs(plate[i] - plate[j]) == Math.abs(i - j)) {
                    return false;
                }
            }
        }
        return true;
    }

}

6.PlanD.java

import java.util.ArrayList;

public class PlanD extends Plan {
    @Override
    public ArrayList<ArrayList<String>> nQueen(int n) {
        // 采用剪枝方法进行优化
        return pruning(null, n, 1);

    }

    @Override
    public int nQueenWithoutAnswer(int n) {
        // 采用剪枝方法进行优化
        return pruningWithoutAnswer(null, n, 1);
    }

    public ArrayList<ArrayList<String>> pruning(ArrayList<Integer> plate, int n, int curr) {
        if (plate == null) {
            plate = new ArrayList<>();
        }
        ArrayList<Integer> plateExpand = new ArrayList<>(plate);
        ArrayList<ArrayList<String>> result = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            plateExpand.add(i);
            if (checkValid(plateExpand, n)) {
                if (curr == n) {
                    ArrayList<String> temp = new ArrayList<>();
                    for (int j = 0; j < n; j++) {
                        StringBuilder sb = new StringBuilder();
                        for (int k = 0; k < n; k++) {
                            if (k == plateExpand.get(j) - 1) {
                                sb.append("Q");
                            } else {
                                sb.append("#");
                            }
                        }
                        temp.add(sb.toString());
                    }
                    result.add(temp);
                } else {
                    result.addAll(pruning(plateExpand, n, curr + 1));
                }
            }
            plateExpand.remove(plateExpand.size() - 1);
        }

        return result;
    }

    public Integer pruningWithoutAnswer(ArrayList<Integer> plate, int n, int curr) {
        if (plate == null) {
            plate = new ArrayList<>();
        }
        ArrayList<Integer> plateExpand = new ArrayList<>(plate);
        Integer result = 0;
        for (int i = 1; i <= n; i++) {
            plateExpand.add(i);
            if (checkValid(plateExpand, n)) {
                if (curr == n) {
                    result++;
                } else {
                    result += pruningWithoutAnswer(plateExpand, n, curr + 1);
                }
            }
            plateExpand.remove(plateExpand.size() - 1);
        }

        return result;
    }

    public boolean checkValid(ArrayList<Integer> plate, int n) {
        for (int i = 0; i < plate.size() - 1; i++) {
            for (int j = i + 1; j < plate.size(); j++) {
                if (plate.get(i).equals(plate.get(j))) {
                    return false;
                }
                if (Math.abs(plate.get(i) - plate.get(j)) == Math.abs(i - j)) {
                    return false;
                }
            }
        }
        return true;
    }
}

7.PlanE.java

import java.util.ArrayList;

public class PlanE extends Plan {
    @Override
    public ArrayList<ArrayList<String>> nQueen(int n) {
        // 这个方案与PlanD相似
        // 不过增加了多线程的方案 使用Shared Data Pattern

        PlanE.n = n; // 提供多线程
        PlanE.result = new ArrayList<>(); // 清空结果
        ThreadToCalculate[] threads = new ThreadToCalculate[n];
        for (int i = 0; i < n; i++) {
            threads[i] = new ThreadToCalculate();
            threads[i].first = i + 1;
            threads[i].start();
        }


        // wait for all threads to finish
        for (int i = 0; i < n; i++) {
            try {
                threads[i].join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        return result;
    }

    @Override
    public int nQueenWithoutAnswer(int n) {
        // 这个方案与PlanD相似
        // 不过增加了多线程的方案 使用Shared Data Pattern
        PlanE.n = n;
        PlanE.resultWithoutAnswer = 0;
        ThreadToCalculateWithoutAnswer[] threads = new ThreadToCalculateWithoutAnswer[n];
        for (int i = 0; i < n; i++) {
            threads[i] = new ThreadToCalculateWithoutAnswer();
            threads[i].first = i + 1;
            threads[i].start();
        }

        for (int i = 0; i < n; i++) {
            try {
                threads[i].join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        return resultWithoutAnswer;
    }

    public static int n;
    public static ArrayList<ArrayList<String>> result = new ArrayList<>();
    public static int resultWithoutAnswer = 0;
}

class ThreadToCalculate extends Thread {

    public int first;

    @Override
    public void run() {
        ArrayList<Integer> r = new ArrayList<>();
        r.add(first);
        //this.pruning(r, PlanE.n, 2);
        PlanE.result.addAll(this.pruning(r, PlanE.n, 2));
    }

    public ArrayList<ArrayList<String>> pruning(ArrayList<Integer> plate, int n, int curr) {
        if (plate == null) {
            plate = new ArrayList<>();
        }
        ArrayList<Integer> plateExpand = new ArrayList<>(plate);
        ArrayList<ArrayList<String>> result = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            plateExpand.add(i);
            if (checkValid(plateExpand, n)) {
                if (curr == n) {
                    ArrayList<String> temp = new ArrayList<>();
                    for (int j = 0; j < n; j++) {
                        StringBuilder sb = new StringBuilder();
                        for (int k = 0; k < n; k++) {
                            if (k == plateExpand.get(j) - 1) {
                                sb.append("Q");
                            } else {
                                sb.append("#");
                            }
                        }
                        temp.add(sb.toString());
                    }
                    result.add(temp);
                } else {
                    result.addAll(pruning(plateExpand, n, curr + 1));
                }
            }
            plateExpand.remove(plateExpand.size() - 1);
        }
        return result;
    }

    public boolean checkValid(ArrayList<Integer> plate, int n) {
        for (int i = 0; i < plate.size() - 1; i++) {
            for (int j = i + 1; j < plate.size(); j++) {
                if (plate.get(i).equals(plate.get(j))) {
                    return false;
                }
                if (Math.abs(plate.get(i) - plate.get(j)) == Math.abs(i - j)) {
                    return false;
                }
            }
        }
        return true;
    }
}

class ThreadToCalculateWithoutAnswer extends Thread {
    public int first;

    @Override
    public void run() {
        ArrayList<Integer> r = new ArrayList<>();
        r.add(first);
        //this.pruning(r, PlanE.n, 2);
        PlanE.resultWithoutAnswer += this.pruningWithoutAnswer(r, PlanE.n, 2);
    }

    public Integer pruningWithoutAnswer(ArrayList<Integer> plate, int n, int curr) {
        if (plate == null) {
            plate = new ArrayList<>();
        }
        ArrayList<Integer> plateExpand = new ArrayList<>(plate);
        Integer result = 0;
        for (int i = 1; i <= n; i++) {
            plateExpand.add(i);
            if (checkValid(plateExpand, n)) {
                if (curr == n) {
                    result++;
                } else {
                    result += pruningWithoutAnswer(plateExpand, n, curr + 1);
                }
            }
            plateExpand.remove(plateExpand.size() - 1);
        }
        return result;
    }

    public boolean checkValid(ArrayList<Integer> plate, int n) {
        for (int i = 0; i < plate.size() - 1; i++) {
            for (int j = i + 1; j < plate.size(); j++) {
                if (plate.get(i).equals(plate.get(j))) {
                    return false;
                }
                if (Math.abs(plate.get(i) - plate.get(j)) == Math.abs(i - j)) {
                    return false;
                }
            }
        }
        return true;
    }
}