Uživatelská dokumentace

Program je demonstrační aplet pro metodu prohledávání s návratem. Jeho úkolem je nalézt řešení problému vzájemného ohrožení, kdy je nutno najít takovou kombinaci 8 šachových dam na šachovnici tak, aby se navzájem neohrožovaly.

Prohledávání s návratem spočívá v postupném kladení figur na šachovnici a ověřování jejich ohrožení. Pokud je dáma ohrožena jinou již položenou, odebere se a hledá se další volné pole. Pokud není dáma ohrožena, pokračuje se pokládáním další dámy. Pokud pro dámu neexistuje již další volná pozice, dáma se odebere a hledá se nová pozice předcházející dámy. Pokud je položeno 8 dam, které se neohrožují, je tato kombinace řešením. Pro účely apletu byly vynechány z důvodu pomalého vykreslování pozice dam, kdy se dámy ohrožují vertikálně či horizontálně (tato ohrožení jsou zřejmě viditelná). Množství pokusů i potřebný čas k provedení se tak znatelně zmenšily.

Spouští se hlavní třída Damy v balíku semestr bez parametrů, tedy např.: "java semestr/Damy". Po spuštění se vytvoří okno, do kterého se průběh algoritmu vykresluje. Zeleně se vykreslují dámy, které byly správně položeny, tj. nejsou ohroženy. Červeně jsou vyznačeny špatné pokusy. Modře se vykreslí každé konečné řešení. Počet pokusů i řešení se nasčítávají v okně. Všechna konečná řešení se vypisují do konzole v podobě souřadnic reálné šachovnice.

Program končí po vyprázdnění šachovnice. Okno s grafikou lze pak zavřít.

Dokumentace jednotlivých tříd

public class Sachovnice

Reprezentuje informace o rozložení dam na šachovnici, umožňuje operace s nimi a kontrolu ohrožení.

Políčko šachovnice v celém apletu lze identifikovat buď pomocí souřadnic x,y (0-7,0-7) nebo pro zjednodušení některých cyklů pomocí pořadového čísla (0-63) po řádcích s počátkem v levém horním rohu. Metody vyžadující zadání políčka jsou vždy deklarovány ve dvou verzích přetěžováním parametrů. Převod z čísla na souřadnice je realizován pomocí statických metod getx, gety třídy Sachovnice.

private boolean[][] pole

Pole obsahuje informace o položených dámách - true = položena. Při spuštění je celé nastaveno na false.

public void poloz(int x, int y)
public void poloz(int cislo)
public void zvedni(int x, int y)
public void zvedni(int cislo)

Položí/zvedne dámu - Nastaví proměnnou pole[x][y] na true/false.

public boolean je_tam (int cislo)
public boolean je_tam (int x, int y)

Vrátí true, pokud je na políčku dáma (obsah proměnné pole[x][y])

public boolean check_horizontal (int cislo)
public boolean check_horizontal (int ix, int iy)
public boolean check_vertical (int cislo)
public boolean check_vertical (int ix, int iy)
public boolean check_diag1 (int cislo)
public boolean check_diag1 (int ix, int iy)
public boolean check_diag2 (int cislo)
public boolean check_diag2 (int ix,int iy)

Tyto metody provádějí test, zda je zadané políčko šachovnice ohrožené v horizontálním, vertikálním a obou diagonálních směrech. Pokud je pole volné, vrací true, pokud je ohrožené tak false.

public boolean check(int cislo)
public boolean check(int ix, int iy)

Provede test na všechny směry. Vrací true, pokud je pole volné

public String toString()

Implicitní převod na String, vrátí pozice všech momentálně položených figurek v souřadnicích reálné šachovnice. Využito při výpisu řešení do konzole.

public class Kresleni

Tato třída zprostředkovává grafický výstup šachovnice. Využívá existujícího objektu třídy Sachovnice, který je předán pomocí parametru konstruktoru třídy. Vytvoření nového objektu této třídy způsobí otevření nového okna pro grafiku.

public boolean poloz_a_kontroluj(int cislo)
public boolean poloz_a_kontroluj(int x, int y)

Vrátí true, pokud je zadané políčko neohroženo, položí dámu a vykreslí ji zeleně.
Vrátí false, pokud je zadané políčko ohroženo, vykreslí dámu červeně a po prodlevě ji smaže.

public void zvedni_a_smaz(int cislo)
public void zvedni_a_smaz(int x, int y)

Odstraní figurku z proměnné objektu sachovnice a smaže ji z displeje.

public void zvyrazni_reseni()

Všechny položené dámy vykreslí modře a po prodlevě je opět překreslí zeleně. Slouží pro zvýraznění každého konečného řešení na šachovnici.

public class Damy

Hlavní třída projektu. Provádí vlastní algoritmus hledání řešení.

static Kresleni kresleni;
static Sachovnice sachovnice;

Statické proměnné objektů tříd Sachovnice a Kreslení

static void dalsi (int uroven)

Provede pokusy o položení další dámy na šachovnici.
Aby byla zaručena neohroženost v horizontálním směru, pokládají se figurky jen do řádku určeného parametrem uroven. Tedy např. úroveň 0 na 0.tý řádek (z 0-7). Pokud by se nějaký řádek vynechal, určitě by při počtu 8mi dam musely být dvě na stejném řádku. Pokud je zjištěno svislé ohrožení vybraného políčka, vykreslení se přeskočí z důvodu rychlosti vykreslování apletu. Následně je volána metoda poloz_a_zkontroluj. Pokud políčko není ohroženo, volá se metoda dalsi s parametrem uroven+1. V případě, že aktuální úroveň je 7, provede se zvýraznění řešení a jeho výpis do konzole. V případě že jsou vyčerpány všechny možnosti v řádku, metoda skončí a přejde se na předchozí úroveň, vybere se další políčko této úrovně atd.

Martin Plicka, plickm1@fel.cvut.cz, 4.1.2005