Задача про розміщення ферзів Дерево пошуку та його обхід

Реферат на тему:

Задача про розміщення ферзів. Дерево пошуку та його обхід

Розглянемо шахівницю, що має розміри не 8´ 8, а n ´ n , де n >0. Як відомо, шаховий ферзь атакує всі клітини та фігури на одній з ним вертикалі, горизонталі та діагоналі. Будь-яке розташування кількох ферзів на шахівниці будемо називати їх розміщенням . Розміщення називається допустимим , якщо ферзі не атакують одне одного. Розміщення n ферзів на шахівниці n ´ n називається повним . Допустимі повні розміщення існують не при кожному значенні n . Наприклад, при n =2 або 3 їх немає. За n =4 їх лише 2 (рис.19.1), причому вони дзеркально відбивають одне одного.

Задача. Написати програму побудови всіх повних допустимих розміщень n ферзів, де 4£ n £ 20.

Для початку з'ясуємо деякі властивості допустимих розміщень. Очевидно, що в них кожний ферзь займає окрему вертикаль і горизонталь. Занумеруємо вертикалі й горизонталі номерами 1, … , n та позначимо через <H ₁ , H ₂ , ¼ , H_i > послідовність номерів горизонталей, зайнятих ферзями, що стоять у вертикалях 1, 2, ¼ , i , де 0£ i £ n . Випадок i =0 відповідає порожньому розміщенню <>.

Існує n способів розмістити ферзя в першій вертикалі, тобто перейти від порожнього розміщення до непорожнього. Цей перехід позначимо стрілкою (рис. 19.2(а)). За кожного з розміщень ферзя в першій вертикалі є n варіантів розміщення ферзя в другій вертикалі, але з них слід відкинути недопустимі. Відмітимо їх знаком '*' (рис.19.2(б)).

Узагалі, нехай зафіксовано розміщення ферзів у перших i -1вертикалях:

S (i -1)=<H ₁ ,¼ ,H_{i -1} >.

Для побудови всіх допустимих розміщень із початком S(i-1) треба перебрати всі допустимі розміщення S(i)з ферзем у i-й вертикалі та для кожного побудувати всі допустимі розміщення з початком S(i) .

Отже, маємо рекурсивний алгоритм побудови всіх допустимих розміщень, за яким пошук усіх допустимих заповнень ферзями останніх n -i +1вертикалей зводиться до пошуку заповнень n -i вертикалей.

Уточнимо цей алгоритм рекурсивною процедурою deps. Нехай розмір шахівниці не більше nm=20. Номери вертикалей та діагоналей містяться в діапазоні nums=1..nm, а розміщення зображається станом масиву H типу

arh = array [ nums ] of nums.

Процедура deps задає побудову розміщення, починаючи з i -ї вертикалі за фіксованих H [1], ¼ , H [i -1]. Підпрограми test та writs задають відповідно перевірку допустимості розміщення <H [1], … , H [i -1], H [i ]> та друкування повного розміщення. Вони викликаються у процедурі deps:

procedure deps ( var H : arh; n, i : nums);

var j, k : nums;

begin

for k := 1 to n do

begin

H[i] := k;

if test ( H, i) then

if i = n then writs ( H, n) {друкування повного розміщення }

else deps ( H, n, i+1 ) {рекурсивний виклик}

end

end

Функція test задає перевірку допустимості розміщення <H [1], ¼ , H [i -1], H [i ]> за умови, що <H [1], ¼ , H [i -1]> є допустимим:

function test ( var H : arh; i : nums ) : boolean;

var j : nums; flag : boolean;

begin

j := 1; flag := true ;

{перевірка, чи займається нова горизонталь і діагональ}

while ( j < i ) and flag do

begin

flag := ( H[i] <> H[j] ) and ( abs ( H[i]-H[j] ) <> i-j ); j := j+1

end ;

test := flag

end

Розробка процедури writs друкування повного розміщення залишається вправою.

Програма розв'язання задачі має такий вигляд:

program Queens ( input, output );

const nm = 20;

type nums = 1..nm;

arh = array [ nums ] of nums;

var H : arh; n : nums;

procedure writs ¼ end ;

function test ¼ end ;

procedure deps ¼ end ;

begin

writeln ('задайте розмір дошки: 4..20>'); readln ( n );

deps ( H, n, 1)

end .

2. Дерево пошуку та його обхід

Розміщення ферзів на шахівниці, що будуються в процесі виконання програми Queens, можна подати вузлами кореневого орієнтованого дерева (рис.19.3).

У цьому дереві кожний вузол <H [1], ¼ , H [i ]>, де 0£ i <n , має синів

<H [1], ¼ , H [i

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать