Перечислить все способы расстановки 8-ми ферзей на шахматной доске 8 на 8, при которых они не бьют друг друга. (Методом перебора с отходом назад)
ТЕСТЫ :) http://infallur.narod.ru/8queens.swf
Подсказки:
Очевидно, на каждой из 8 вертикалей должно стоять по ферзю. Каждую такую расстановку можно закодировать одномерным массивом
X[1],...,X[8],
где X[i] - номер горизонтали для i-го ферзя. Поскольку никакие два ферзя не могут стоять на одной горизонтали (тогда они бьют друг друга), то все X[i] различны, т.е. образуют перестановку из чисел 1..8. Можно, конечно, перебрать все 8! таких перестановок и выбрать среди них те ....., которые нас интересуют. Hо число 8!=40320 довольно большое.
МЕТОД ПЕРЕБОРА С ОТХОДОМ НАЗАД
Как вы уже поняли, перебор комбинаторных объектов - задача весьма трудоемкая даже для компьютера. Hапример, перестановок из восьми чисел будет 8! = 40320 - число немаленькое. Поэтому в любой переборной задаче главная цель состоит в СОКРАЩЕHИИ ПЕРЕБОРА, т.е. в исключении тех объектов, которые заведомо не могут стать решением задачи. Предположим, что нам требуется рассмотреть только те перестановки, для которых сумма |X[i]-i| равна 8. Понятно, что их будет гораздо меньше: например, все перестановки, начинающиеся на 8,7,... рассматривать не нужно! Как можно модифицировать наш переборный алгоритм в этом случае? Если на каком-то этапе сумма
|X[1]-1| + |X[2]-2| + ... + |X[k]-k|
уже больше 8, то рассматривать все перестановки, начинающиеся на X[1],...,X[k] уже не нужно - следует вернуться к X[k] и изменить его значение ("отойти назад" - отсюда название метода).
Для такой ситуации мы рассмотрим один общий метод, который почти всегда позволяет значительно сократить перебор. Пусть искомое решение находится среди последовательностей вида
X[1],...,X[N],
где каждое X[i] выбирается из некоторого множества вариантов A[i]. Предположим мы уже построили начало этой последовательности X[1],...,X[k] (k<N) и хотим продолжить его до решения.
Предположим также, что у нас есть некоторый простой метод P(X[1],...,X[k]), который позволяет получить ответ на вопрос: можно продолжить X[1],...,X[k] до решения (true) или нет (false). Заметим, что значение true еще HЕ ГАРАHТИРУЕТ существование такого продолжения, но зато значение false ГАРАHТИРУЕТ непродолжаемость ("не стоит дальше и пробовать"). Получаем простую рекурсивную процедуру ПЕРЕБОРА С ОТХОДОМ HАЗАД: procedure Backtracking(k);
begin
for (y in A[k]) do
if P(X[1],...,X[k-1],y) then
begin
X[k]:=y;
if k=N then {X[1],...,X[N] -решение}
Backtracking(k+1)
end
end;
begin
for (y in A[k]) do
if P(X[1],...,X[k-1],y) then
begin
X[k]:=y;
if k=N then {X[1],...,X[N] -решение}
Backtracking(k+1)
end
end;
