全排列问题

package com.test.clickhouse.config;
import java.util.LinkedList;
import java.util.List;
/**
 * @author jia
 * @since 2022-04-13 12:01
 */
public class Permute {
    public static void main(String[] args) {
        List<List<Integer>> permute = permute(new int[]{1, 2, 3});
        System.out.println(permute);
    }
    public static List<List<Integer>> permute(int[] arr) {
        List<List<Integer>> resList = new LinkedList<>();
        LinkedList<Integer> res = new LinkedList<>();
        boolean [] used = new boolean[arr.length];
        backtrack(arr, used,  res, resList);
        return resList;
    }
    private static void backtrack(int[] arr, boolean[] used, LinkedList<Integer> res,
                                  List<List<Integer>> resList) {
        if (res.size() == arr.length) {
            resList.add(new LinkedList<>(res));
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (used[i]) {
                continue;
            }
            // 做选择
            res.add(arr[i]);
            used[i] = true;
            backtrack(arr, used, res, resList);
            // 取消选择
            res.removeLast();
            used[i] = false;
        }
    }
}

n皇后问题

package com.test.clickhouse.config;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
/**
 * @author jia
 * @since 2022-04-13 12:01
 */
public class Permute {
    public static void main(String[] args) {
        List<String[][]> permute = queens(4);
        List<List<String>> collect = permute.stream().map(Permute::parse).collect(Collectors.toList());
        System.out.println(collect);
    }
    private static List<String> parse(String[][] arr) {
        List<String> list = new ArrayList<>();
        for (String[] strings : arr) {
            list.add(String.join("", strings));
        }
        return list;
    }
    private static List<String[][]> queens(int n) {
        String[][] arr = new String[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = ".";
            }
        }
        List<String[][]> res = new LinkedList<>();
        backtrack(0, arr, res);
        return res;
    }
    private static void backtrack(int row, String[][] arr, List<String[][]> res) {
        if (arr.length == row) {
            res.add(copy(arr));
            return;
        }
        for (int col = 0; col < arr[row].length; col++) {
            if (!isValid(arr, row, col)) {
                continue;
            }
            // 做选择
            arr[row][col] = "Q";
            backtrack(row + 1, arr, res);
            // 取消选择
            arr[row][col] = ".";
        }
    }
    private static boolean isValid(String[][] arr, int row, int col) {
        int n = arr.length;
        // 判断左上
        for (int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--) {
            if (arr[i][j].equals("Q")) {
                return false;
            }
        }
        // 判断上
        for (int i = row-1; i >= 0; i--) {
            if (arr[i][col].equals("Q")) {
                return false;
            }
        }
        // 判断右上
        for (int i = row-1, j = col+1; i >= 0 && j < n; i--, j++) {
            if (arr[i][j].equals("Q")) {
                return false;
            }
        }
        return true;
    }
    private static String[][] copy(String[][] arr) {
        int length = arr.length;
        String[][] arrRes = new String[length][length];
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                arrRes[i][j] = arr[i][j];
            }
        }
        return arrRes;
    }
}