Java数据结构与算法(回溯算法)

前言

回溯算法是一种通过构建问题的解树（或解图）来逐步构建候选解的通用算法。它尝试通过一系列选择来解决问题，选择可能包括移动、添加一个元素到当前解、决定一个解的某部分等。当发现某个选择无法导致一个有效解时，算法会回退（即回溯），撤销该选择，并尝试其他选择。回溯算法通常用于解决组合优化问题、排列问题、子集问题、图的着色问题、数独等。

实现原理

回溯算法主要包括以下几个步骤：

1. 选择：在当前步骤，尝试所有可能的选择。
2. 约束：检查选择是否满足问题的约束条件。
3. 递归：如果选择满足约束条件，则向前推进到下一步（递归调用）。
4. 回溯：如果选择不满足约束条件，或者当前选择导致无法得到解，则撤销该选择（回溯），并尝试其他选择。

具体代码实现(N皇后)

要求在一个 N x N 的棋盘上放置 N 个皇后，使得每个皇后都无法攻击到其他任何一个皇后。

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

public class NQueens {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>();
        int[] queens = new int[n]; // 用一维数组表示棋盘，queens[i]表示第i行皇后所在的列
        solve(0, n, queens, solutions);
        return solutions;
    }

    private void solve(int row, int n, int[] queens, List<List<String>> solutions) {
        if (row == n) {
            solutions.add(generateBoard(queens, n));
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isValid(row, col, queens)) {
                queens[row] = col;
                solve(row + 1, n, queens, solutions);
                queens[row] = -1; // 回溯
            }
        }
    }

    private boolean isValid(int row, int col, int[] queens) {
        for (int i = 0; i < row; i++) {
            if (queens[i] == col || Math.abs(queens[i] - col) == Math.abs(i - row)) {
                return false;
            }
        }
        return true;
    }

    private List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            for (int j = 0; j < n; j++) {
                row[j] = '.';
            }
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }

    public static void main(String[] args) {
        NQueens nQueens = new NQueens();
        int n = 4;
        List<List<String>> solutions = nQueens.solveNQueens(n);
        for (List<String> solution : solutions) {
            for (String row : solution) {
                System.out.println(row);
            }
            System.out.println();
        }
    }
}

QA:待定