定义
回溯是所有编程语言中使用的一种方法，用于探索问题的所有可能结果。
它可以应用于解决迷宫中寻找路径、解决 n 皇后问题、数独等问题。
为什么有用？
为什么回溯对于开发者来说很有价值？
想象一下有多种可能结果可供探索的情况。我们有时间手动检查每一种可能性吗？显然不是。
我们可能会考虑创建一个大循环来遍历所有潜在的解决方案。但每台机器的能力都能处理如此繁重的工作吗？再说一次，不。
这就是回溯派上用场的地方。带着这个理念，我们系统地尝试每一种可能的解决方案。如果一种解决方案不起作用，我们会返回并尝试另一种解决方案，直到满足我们定义的成功条件为止。
类比
以数独为例：
每行必须包含 1 到 9 的数字。
每列必须包含 1 到 9 的数字。
9个子网格（3*3）中的每一个都必须包含从1到9的数字。
解决数独谜题时，需要填充空白区域。解决方法：
- 我们创建一个函数来检查一个数字是否满足所有规则。
- 确认是否可以输入号码后，我们继续检查剩余空位的可能性。
- 如果输入的数字稍后会导致无效的解决方案，我们会回溯，尝试另一个数字，然后重复该过程。
这会一直持续，直到所有空格都被正确填充并解决谜题。
回溯的主要步骤
- 选择：找出每一步所有可能的解决方案，并一一检查。
- 约束：根据规则验证解是否有效。
- 目标：确定解决方案是否满足所有条件。
- 后退：当解决方案失败时回溯并探索其他选项。
示例代码：使用 javascript 通过回溯求解数独
//We start with a partially filled Sudoku board (for empty cells) and we want to find the possible numbers that can be used to fill the board
const board = [
["5", "3", ".", "6", "7", "8", "9", "1", "2"],
["6", "7", "2", "1", "9", "5", "3", "4", "8"],
["1", "9", "8", "3", "4", "2", "5", "6", "7"],
["8", "5", "9", "7", "6", "1", "4", "2", "3"],
["4", "2", "6", "8", ".", "3", "7", "9", "1"],
["7", "1", "3", "9", "2", "4", "8", "5", "6"],
["9", "6", "1", "5", "3", "7", "2", "8", "4"],
["2", "8", "7", "4", "1", "9", "6", "3", "5"],
["3", "4", "5", "2", "8", "6", "1", ".", "9"]
];
//'.' represents an empty cell
// Possible numbers for Sudoku
const possibleNumbers = ["1", "2", "3", "4", "5", "6", "7", "8", "9"];
// Function to check if placing a number is valid
function isValid(number, row, col, board) {
// Check row and column
for (let i = 0; i < board.length; i++) {
if (board[row][i] === number || board[i][col] === number) {
return false;
}
}
// Check the 3x3 sub-grid
let startRow = Math.floor(row / 3) * 3;
let startCol = Math.floor(col / 3) * 3;
for (let i = startRow; i < startRow + 3; i++) {
for (let j = startCol; j < startCol + 3; j++) {
if (board[i][j] === number) {
return false;
}
}
}
return true; // The number is valid for this position
}
// Function to solve the Sudoku board
function solveSudoku(board) {
const emptySpaces = [];
// Find all empty spaces on the board
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (board[i][j] === ".") {
emptySpaces.push({ row: i, col: j });
}
}
}
// Recursive function to fill empty spaces
function recurse(emptySpaceIndex) {
if (emptySpaceIndex >= emptySpaces.length) {
return true; // All spaces filled successfully
}
const { row, col } = emptySpaces[emptySpaceIndex];
for (let i = 0; i < possibleNumbers.length; i++) {
const num = possibleNumbers[i];
if (isValid(num, row, col, board)) {
board[row][col] = num; // Place the number
if (recurse(emptySpaceIndex + 1)) {
return true; // Solution found
}
// Backtrack if placing the number doesn't lead to a solution
board[row][col] = ".";
}
}
return false; // No valid number found for this position
}
recurse(0); // Start solving from the first empty space
return board;
}
// Solve the Sudoku puzzle
solveSudoku(board);
console.log(board);
要点
回溯系统地探索所有可能性，同时遵守约束。
它对于解决基于约束的问题（例如数独、n 皇后等）特别有用。
回溯的递归性质使我们能够在解决方案失败时后退一步并尝试替代路径。
希望您对我的文章感到满意。我会在那里回答您可能提出的所有问题。
如果满意的话就留下一个♥️（其实意义很大）
图片：图片来自 freepik 上的 storyset
