Курсовая работа: Перебор с возвратом
end;
end
elsebegin
Inc(S);{счетчик числа решений, глобальная переменная}
Print;{выводрешения}
end;
end;
Поиск только не симметричных решений. Для доски 8*8 ответ 12.
Эта модификация требует предварительных разъяснений. Из каждого решения задачи о ферзях можно получить ряд других при помощи вращений доски на 90о , 180о и 270о и зеркальных отражений относительно линий , разделяющих доску пополам (система координат фиксирована). Доказано, что в общем случае для доски N*N (N>1) для любой допустимой расстановки N ферзей возможны три ситуации:
· при одном отражении доски возникает новая расстановка ферзей, а при поворотах и других отражениях новых решений не получается;
· новое решение при повороте на 90о и ее отражения дают еще две расстановки;
· три поворота и четыре отражения дают новые расстановки.
Для отсечения симметричных решений на всем множестве решений требуется определить некоторое отношение порядка. Представим решение в виде вектора длиной N, координатами которого являются числа от 1 до N. Для ферзя, стоящего в i-й строке, координатой его столбца является i-я координата вектора. Для того, чтобы не учитывать симметричные решения, будем определять минимальный вектор среди всех векторов, получаемых в результате симметрий. Процедуры Sim1, Sim2, Sim3 выполняют зеркальные отображения вектора решения относительно горизонтальной, вертикальной и одной из диагональных осей. Известно (из геометрии), что композиция этих симметрий дает все определенные выше симметрии шахматной доски, причем не принципиально, в какой последовательности выполняются эти процедуры для каждой конкретной композиции. Проверка «на минимальность» решения производится функцией Cmp, которая возвращает значение true в том случае, когда одно из симметричных решений строго меньше текущего.
{не лучший вариант реализации - отсечение на выводе решений}
type Tarray=array[1..N] of integer;
procedure Sim1(var X:Tarray);
var i:integer;
begin
for i:=1 to N do X[i]:=N-X[i]+1;
end;
procedure Sim2(var X:Tarray);
var i,r:integer;
begin
for i:=1 to N do begin
r:=X[i]; X[i]:=X[N-i+1];X[N-i+1]:=r;
end;
end;
procedure Sim3(var X:Tarray);
var Y:Tarray;