Курсовая работа: Перебор с возвратом

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;

К-во Просмотров: 455
Бесплатно скачать Курсовая работа: Перебор с возвратом