Problém rozestavění osmi dam na šachovnici
Úloha č. 3 pro cvičení k předmětu Vybrané kapitoly z umělé inteligence
Zadání: Implementujte v libovolném programovacím jazyce heuristiku min-konflikt, zmíněnou na přednášce,
pro uspořádání osmi vzájemně se nenapadajících dam na šachovnici 8x8. Své řešení otestujte na příkladu uve-
deném v přednáškách a dále navrhněte ještě nějakou jinou testovací pozici (dle vlastního uvážení, nikoliv něco
triviálního--je nutno si vyzkoušet a ukázat funkčnost heuristiky). Nakonec se pokuste vyřešit několik pozic vy-
generovaných náhodně (na každém sloupci smí být ve výchozí pozici pouze jedna dáma a aspoň jedna dvojice
by se měla na začátku vzájemně napadat--zajímavé je zkusit heuristiku min-konflikt pro více vzájemně se
napadajících dvojic dam). Vyhodnoťte svá řešení--např. zjistěte průměrný počet kroků pro nalezení výsledku,
nárůst jejich počtu při výskytu 2, 3 nebo více konfliktů, apod..
Výsledek úlohy pošlete přes e-mail na adresu zizka@cba.muni.cz obdobně jako pro úlohy č. 1 a 2; subjekt
e-mailu bude obsahovat text 8-DAM a jméno a příjmení autora řešení (např. 8-DAM GARRY KASPAROV).
Další podmínky odevzdání, včetně procentového ohodnocení, jsou stejné jako u úloh č. 1 a 2; datum odevzdání
je jiné:
Termín je do půlnoci pondělí 5. prosince 2005.
V popisu svého řešení úlohy uveďte použité pozice dam na šachovnici (diagram, nebo lze např. použít běžnou
šachovou notaci--sloupce označované zleva doprava písmeny a, b, ..., h, řady zdola nahoru čísly 1, 2, ..., 8,
např. postavení v přednášce je Da7, Db4, Dc2, Dd5, De8, Df6, Dg3, Dh1; lze vynechat "D" označující figuru).
Dále uveďte, jaké kroky, v jakém pořadí a počtu heuristika vytvořila a zda předložené pozice vyřešila či ne.
Pokud ne, pokuste se neúspěch vysvětlit.
XABCDEFGHY
8-+-+q+-+(
7wq-+-+-+-'
6-+-+-wq-+&
5+-+q+-+-%
4-wq-+-+-+$
3+-+-+-wq-#
2-+q+-+-+"
1+-+-+-+q!
xabcdefghy
Pozice z přednášky s jednou
dvojicí napadajících se dam
(povinné)
XABCDEFGHY
8q+-+-+-+(
7+q+-+-+-'
6-+q+-+-+&
5+-+q+-+-%
4-+-+q+-+$
3+-+-+q+-#
2-+-+-+q+"
1+-+-+-+q!
xabcdefghy
Jedna z možných pozic s mnoha
napadajícími se dámami
(zájemci si mohou zkusit)
Pozn.: Heuristika min-konflikt se používá ve velmi mnoha reálných aplikacích, např. při automatizované podpo-
ře návrhu VLSI (very large-scale integration) obvodů na mikročipech. Při vytváření počátečních konfigurací
problémů je vhodné nepoužívat zcela náhodné generování (pozic dam, rozvrhu hodin, rozložení a propojení ele-
ktronických součástek, apod.), nýbrž se hned od začátku snažit vyhýbat se možným konfliktům (např. rozesta-
vovat dámy jako "konfliktní" jezdce, protože dáma neatakuje jako jezdec). Tím lze dosáhnout až pouze lineární
časové složitosti v odstraňování konfliktů z úvodní konfigurace.