Что такое откат?

Возврат — это общий алгоритм поиска всех (или некоторых) решений проблемы путем постепенного построения решения и отмены (возврата) хода, если он признан неверным. Он используется для решения таких задач, как поиск всех возможных комбинаций или перестановок набора элементов или поиск кратчайшего пути через лабиринт. Поиск с возвратом часто реализуется с использованием рекурсии, и его можно рассматривать как поиск в глубину дерева возможных решений.

Пример в JavaScript:

Одним из примеров проблемы, которую можно решить с помощью поиска с возвратом, является «задача N ферзей», которая состоит в том, чтобы разместить N ферзей на шахматной доске размером NxN таким образом, чтобы никакие два ферзя не атаковали друг друга (т. е. никакие два ферзя не находились в одном ряду, столбец или диагональ).

Вот пример функции JavaScript, которая решает проблему N-Queens с помощью поиска с возвратом:

function solveNQueens(n) {
  let solutions = [];
  let queens = Array(n).fill(-1);

  function placeQueens(row) {
    if (row === n) {
      solutions.push(queens.slice());
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        queens[row] = col;
        placeQueens(row + 1);
        queens[row] = -1;
      }
    }
  }

  function isSafe(row, col) {
    for (let i = 0; i < row; i++) {
      if (queens[i] === col || // same column
          queens[i] - i === col - row || // same diagonal
          queens[i] + i === col + row) { // same diagonal
        return false;
      }
    }
    return true;
  }

  placeQueens(0);
  return solutions;
}

В этом примере функция placeQueens является алгоритмом поиска с возвратом. Он начинается с первой строки и пытается разместить ферзя в каждом столбце. Если он находит безопасную позицию, он ставит ферзя и переходит к следующему ряду. Если он достигает строки, в которой не может найти безопасную позицию, он возвращается к предыдущей строке и пробует следующий столбец. После того, как все ферзи размещены на доске без каких-либо конфликтов, конфигурация доски передается в массив решений.

Эта функция вернет массив всех возможных решений, где каждый элемент массива представляет собой массив, представляющий столбец каждого ферзя в этом решении.

Например:

solveNQueens(4)

вернется

[
  [1, 3, 0, 2],
  [2, 0, 3, 1]
]

Это всего лишь один пример, поиск с возвратом может быть применен ко многим задачам, таким как задача перестановки и комбинации, судоку, решение лабиринта и т. д.