回溯算法

框架

回溯问题算法框架
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

全排列问题

package fighting.algorithm.backtrack;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 全排列问题
 */
public class Sequence {

    public static int answer_num = 0;

    /**
     * 回溯
     *
     * @param numbers 用于排列的数字
     * @param track   路径
     */
    public static void backtrack(List<Integer> numbers, LinkedList<Integer> track) {
        if (numbers.size() == track.size()) {
            System.out.println(track);
            answer_num++;
            return;
        }

        for (int i : numbers) {
            // 如果该数已在路径中，忽略
            if (track.contains(i)) {
                continue;
            }
            // 做选择
            track.add(i);
            // 递归进入之后的选择
            backtrack(numbers, track);
            // 撤销选择
            track.removeLast();
        }
    }

    /**
     * 测试
     */
    public static void main(String ars[]) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(1);
        numbers.add(2);
        numbers.add(3);
        numbers.add(4);

        LinkedList<Integer> chooseList = new LinkedList<>();

        backtrack(numbers, chooseList);

        System.out.println(answer_num);
    }
}

N皇后问题

package fighting.algorithm.backtrack;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * N皇后问题
 */
public class Queen {

    public static final int QUEEN_NUM = 8;

    public static List<List<List<String>>> results = new ArrayList<>();

    public static void queen(List<List<String>> board, int row) {
        if (row >= QUEEN_NUM) {
            List<List<String>> boardCopy = initBoard();
            Collections.copy(boardCopy, board);
            results.add(boardCopy);
            return;
        }
        for (int column = 0; column < QUEEN_NUM; column++) {
            if (isValid(board, row, column)) {
                board.get(row).set(column, "Q");
                queen(board, row + 1);
                board.get(row).set(column, "");
            }
        }
    }

    public static boolean isValid(List<List<String>> board, int row, int column) {
        // false if q exists in the same column
        for (int i = 0; i < row; i++) {
            if (board.get(i).get(column).equals("Q")) {
                return false;
            }
        }

        for (int i = row - 1, j = column - 1; i >= 0 && j >= 0; i--, j--) {
            if (board.get(i).get(j).equals("Q")) {
                return false;
            }
        }

        for (int i = row - 1, j = column + 1; i >= 0 && j < QUEEN_NUM; i--, j++) {
            if (board.get(i).get(j).equals("Q")) {
                return false;
            }
        }

        return true;
    }

    public static List<List<String>> initBoard() {
        List<List<String>> board = new ArrayList<>();
        for (int i = 0; i < QUEEN_NUM; i++) {
            board.add(new ArrayList<>());
            for (int j = 0; j < QUEEN_NUM; j++) {
                board.get(i).add("");
            }
        }

        return board;
    }

    public static void printBoard(List<List<String>> board) {
        for (int i = 0; i < QUEEN_NUM; i++) {
            for (int j = 0; j < QUEEN_NUM; j++) {
                if (board.get(i).get(j).equals("Q")) {
                    System.out.print(" ● ");
                } else {
                    System.out.print(" ○ ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String args[]) {
        List<List<String>> board = initBoard();
        queen(board, 0);

        System.out.println(results.size());
    }
}