Backtracking – osem dám

// Príklad algoritmu sekvenčného vyhľadávania:

nájdené = -1;
hľadaj = Svet.načítajČíslo("Zadajte číslo…");

for (int i = 0; i < pole.length; ++i)
{
	if (hľadaj == pole[i])
	{
		nájdené = i;
		break;
	}
}

Obsah poľa šachovnice by sa dal najjednoduchšie (bez grafiky) zobraziť takto:

~

for (char[] riadok : šachovnica)
	Svet.vypíšRiadok(riadok);

Nižšie je uvedená úplná implementácia rodičovskej triedy kresliacej elegantnú grafickú šachovnicu.

~

import knižnica.*;

public class Šachovnica extends GRobot
{
	public final static int POČET_STĹPCOV = 8;
	public final static int POČET_RIADKOV = 8;
	public final static int ROZMER_ŠTVORCA = 45;
	public final static int MEDZERA = 8;
	public final static int ROZMER_DÁMY = 16;
	public final static int ROZMER_PREKÁŽKY = 12;

	protected char šachovnica[][] = new char[POČET_RIADKOV][POČET_STĹPCOV];

	public Šachovnica()
	{
		super((ROZMER_ŠTVORCA + MEDZERA) * (POČET_STĹPCOV + 1),
			(ROZMER_ŠTVORCA + MEDZERA) * (POČET_RIADKOV + 1));

		for (int riadok = 0; riadok < POČET_RIADKOV; ++riadok)
			for (int stĺpec = 0; stĺpec < POČET_STĹPCOV; ++stĺpec)
				šachovnica[riadok][stĺpec] = '.';

		hrúbkaČiary(2); skry();
	}

	public void vložPrekážku(int riadok, int stĺpec)
	{
		if (riadok >= 0 && riadok < šachovnica.length &&
			stĺpec >= 0 && stĺpec < šachovnica[riadok].length)
			šachovnica[riadok][stĺpec] = 'X';
	}

	public void nakresliŠachovnicu()
	{
		farba(tmavožltá);
		vyplňObdĺžnik(
			((ROZMER_ŠTVORCA + MEDZERA) * POČET_STĹPCOV + MEDZERA) / 2,
			((ROZMER_ŠTVORCA + MEDZERA) * POČET_RIADKOV + MEDZERA) / 2);

		farba(čierna);
		obdĺžnik(
			((ROZMER_ŠTVORCA + MEDZERA) * POČET_STĹPCOV + MEDZERA) / 2,
			((ROZMER_ŠTVORCA + MEDZERA) * POČET_RIADKOV + MEDZERA) / 2);

		skoč((-(ROZMER_ŠTVORCA + MEDZERA) * (POČET_STĹPCOV - 1)) / 2,
			((ROZMER_ŠTVORCA + MEDZERA) * (POČET_RIADKOV - 1)) / 2);


		for (int riadok = 0; riadok < POČET_RIADKOV; ++riadok)
		{
			for (int stĺpec = 0; stĺpec < POČET_STĹPCOV; ++stĺpec)
			{
				if (0 == (riadok + stĺpec) % 2)
					farba(hnedá);
				else
					farba(oranžová);
				vyplňŠtvorec(ROZMER_ŠTVORCA / 2);

				farba(čierna);
				štvorec(ROZMER_ŠTVORCA / 2);

				if (šachovnica[riadok][stĺpec] == 'O')
				{
					farba(biela);
					kruh(ROZMER_DÁMY);
					farba(čierna);
					kružnica(ROZMER_DÁMY);
					kružnica(ROZMER_DÁMY * 5 / 6);
					farba(svetlošedá);
					kruh(ROZMER_DÁMY * 1 / 4);
					farba(čierna);
					kružnica(ROZMER_DÁMY * 1 / 4);
				}
				else if (šachovnica[riadok][stĺpec] != '.')
				{
					farba(tmavošedá);
					kruh(ROZMER_PREKÁŽKY);
					farba(šedá);
					kruh(ROZMER_PREKÁŽKY * 2 / 3);
					farba(svetlošedá);
					kruh(ROZMER_PREKÁŽKY * 1 / 4);
					farba(čierna);
					kružnica(ROZMER_PREKÁŽKY);
				}

				skoč(ROZMER_ŠTVORCA + MEDZERA, 0);
			}
			skoč(-(ROZMER_ŠTVORCA + MEDZERA) * POČET_STĹPCOV,
				-ROZMER_ŠTVORCA - MEDZERA);
		}

		skoč(((ROZMER_ŠTVORCA + MEDZERA) * (POČET_STĹPCOV - 1)) / 2,
			((ROZMER_ŠTVORCA + MEDZERA) * (POČET_RIADKOV + 1)) / 2);
	}
}

Jedným z kľúčových použití vyhľadávacieho algoritmu je jeho použitie na overenie toho, či je práve ukladaná dáma v ohrození. Po krátkej úvahe sme zhodnotili, že bude postačovať overovať priestor nad dámou. Graficky sme si ho rozdelili na „červený“ a „oranžový“:

 

~

import knižnica.*;

public class Backtracking_OsemDám extends Šachovnica
{
	/**
	 * Táto metóda začína vykonávanie hľadania vhodnej pozície na riadku.
	 * Metóda umiestni prvú dámu na vhodné (t. j. voľné) miesto na riadku.
	 *
	 * @return Návratová hodnota značí, že sa akcia podarila.
	 */
	private boolean položDámuNaRiadok(int riadok)
	{
		// Nájdenie prvého voľného miesta na riadku
		// a vloženie dámy na to miesto:
		for (int stĺpec = 0; stĺpec < šachovnica[riadok].length; ++stĺpec)
		{
			if (šachovnica[riadok][stĺpec] == '.')
			{
				šachovnica[riadok][stĺpec] = 'O';
				return true;
			}
		}

		return false;
	}

	/**
	 * Táto metóda posúva dámu na riadku ďalej v prípade, že jej aktuálne
	 * umiestnenie nie je vyhovujúce. Metóda buď premiestni dámu na prvé voľné
	 * miesto na riadku vpravo od nej, alebo dámu z riadka odstráni úplne.
	 *
	 * @return Návratová hodnota značí, že sa akcia podarila.
	 */
	private boolean posuňDámuNaRiadkuĎalej(int riadok)
	{
		int stĺpec;

		// Vyhľadanie a zmazanie dámy na riadku:
		for (stĺpec = 0; stĺpec < šachovnica[riadok].length; ++stĺpec)
		{
			if (šachovnica[riadok][stĺpec] == 'O')
			{
				šachovnica[riadok][stĺpec] = '.';
				++stĺpec;
				break;
			}
		}

		// Vyhľadanie prvého voľného miesta a vloženie dámy na to miesto:
		for (; stĺpec < šachovnica[riadok].length; ++stĺpec)
		{
			if (šachovnica[riadok][stĺpec] == '.')
			{
				šachovnica[riadok][stĺpec] = 'O';
				return true;
			}
		}

		return false;
	}


	/**
	 * Táto metóda overuje, či je dáma na riadku umiestnená vo vhodnej polohe,
	 * to znamená, že ju neohrozuje žiadna iná z dám. Metóda predpokladá, že
	 * žiadna iná z dám nie je umiestnená na rovnakom riadku ako táto dáma, ani
	 * na riadku nižšie od nej. (Grafické znázornenie je v súbore na prevzatie
	 * vyššie.)
	 *
	 * @return Návratová hodnota značí, že dáma je ohrozená a je potrebné ju
	 *         presunúť.
	 */
	private boolean jeDámaNaRiadkuOhrozená(int riadok)
	{
		int stĺpec;

		// Hľadáme dámu na tomto riadku
		for (stĺpec = 0; stĺpec < šachovnica[riadok].length; ++stĺpec)
		{
			if (šachovnica[riadok][stĺpec] == 'O')
			{
				break;
			}
		}

		if (stĺpec >= šachovnica[riadok].length) return true;

		// Hľadáme dámy v „červenom“ priestore, pričom dávame pozor na to,
		// aby sme neskončili v „oranžovom“ priestore:
		for (int k = 1; k <= riadok; ++k)
		{
			// Hľadanie dámy v stĺpci:
			if (šachovnica[riadok - k][stĺpec] == 'O') return true;

			// Hľadanie dám na diagonálach:
			if ((stĺpec - k >= 0) &&
				šachovnica[riadok - k][stĺpec - k] == 'O') return true;

			if ((stĺpec + k < šachovnica[riadok].length) &&
				šachovnica[riadok - k][stĺpec + k] == 'O') return true;
		}

		return false;
	}


	/**
	 * Zlúčenie všetkých troch metód dohromady a rekurzívne nájdenie riešenia.
	 * Pochopenie vybudovania tejto metódy je kľúčové na pochopenie celého
	 * algoritmu. Opis jej zostavenia krok po kroku je uvedený nižšie.
	 */
	protected boolean hľadajBezpečnúPolohuDámyNaRiadku(int riadok)
	{
		if (!položDámuNaRiadok(riadok)) return false;

		boolean trebaOpakovať;
		do
		{
			trebaOpakovať = false;

			while (jeDámaNaRiadkuOhrozená(riadok))
			{
				if (!posuňDámuNaRiadkuĎalej(riadok)) return false;
			}

			if (riadok + 1 < šachovnica.length)
			{
				if (!hľadajBezpečnúPolohuDámyNaRiadku(riadok + 1))
				{
					if (!posuňDámuNaRiadkuĎalej(riadok)) return false;
					trebaOpakovať = true;
				}
			}
		}
		while (trebaOpakovať);

		return true;
	}
}

 

---

Jeden z možných spôsob „vybudovania“ metódy hľadajBezpečnúPolohuDámyNaRiadku

V celej nasledujúcej časti budeme pracovať len s telom uvedenej metódy, ktoré budeme postupne vylepšovať až do rozšírenia do konečného stavu.

Verzia 1

Najprv napíšme základný princíp, na ktorom bude metóda fungovať:

• položíme dámu na riadok,
• zistíme, či je ohrozená,
• keď je ohrozená, posunieme ju ďalej.

Zapísané v reči jazyka Java:

~

položDámuNaRiadok(riadok);

if (jeDámaNaRiadkuOhrozená(riadok))
	posuňDámuNaRiadkuĎalej(riadok);

Verzia 2

To nestačí. Posúvanie dámy musíme zopakovať, pretože si nemôžeme byť istí, že po posunutí doprava už dáma nie je ohrozená. V skutočnosti musíme posúvanie opakovať dovtedy, kým dáma nie je ohrozená. Zapísané v reči jazyka Java:

~

položDámuNaRiadok(riadok);

while (jeDámaNaRiadkuOhrozená(riadok))
	posuňDámuNaRiadkuĎalej(riadok);

Lenže pozor! Takto sme si práve vyrobili veľkú šancu na vznik nekonečného cyklu. Ak sa dáma už nemôže posúvať viac doprava, metóda jeDámaNaRiadkuOhrozená bude neustále vracať návratovú hodnotu false, čím vznikne nekonečný cyklus. Vždy musíme overiť, či sa dámu podarilo posunúť doprava. Presne o tom nás informuje návratová hodnota metódy posuňDámuNaRiadkuĎalej. Čiže cyklus upravíme takto:

~

while (jeDámaNaRiadkuOhrozená(riadok))
{
	if (!posuňDámuNaRiadkuĎalej(riadok)) return false;
}

Podobne by sme mali overiť aj návratovú hodnotu metódy položDámuNaRiadok (ktorej volanie je nad cyklom):

~

if (!položDámuNaRiadok(riadok)) return false;

Verzia 3

Po úspešnom skončení cyklu si môžeme byť istí, že dáma na tomto riadku nie je nikým ohrozovaná. Môžeme preto prejsť na spracovanie ďalšieho riadka. Využijeme rekurziu:

~

hľadajBezpečnúPolohuDámyNaRiadku(riadok + 1);

Musíme zabezpečiť, aby rekurzia nešla príliš hlboko. Musí sa skončiť na poslednom riadku šachovnice, čiže súčet riadok + 1 posledného rekurzívneho volania našej metódy musí byť menší než hodnota šachovnica.length, čo môžeme zapísať buď ako riadok + 1 < šachovnica.length, alebo ako riadok < šachovnica.length ­‑ 1 (záleží na tom, ktorý zápis komu lepšie vyhovuje):

~

if (riadok + 1 < šachovnica.length)
{
	hľadajBezpečnúPolohuDámyNaRiadku(riadok + 1);
}

Tiež musíme dbať na to, že ak sa volanie metódy neskončí úspechom, musíme vykonať prislúchajúce opatrenia! Dostávame príležitosť vykonať spätné trasovanie (backtracking), ktorého úplnú implementáciu dokončíme v ďalšom (poslednom) kroku (označenom verzia 4).

Telo celej metódy (vrátane úprav z predchádzajúceho kroku) bude teraz vyzerať takto:

~

if (!položDámuNaRiadok(riadok)) return false;

while (jeDámaNaRiadkuOhrozená(riadok))
{
	if (!posuňDámuNaRiadkuĎalej(riadok)) return false;
}

if (riadok + 1 < šachovnica.length)
{
	if (!hľadajBezpečnúPolohuDámyNaRiadku(riadok + 1))
	{
		// Miesto na vloženie niekoľkých príkazov zariaďujúcich časť
		// spätného trasovania – backtracking.
	}
}

Verzia 4

Po návrate z neúspešnej rekurzie (!hľadajBezpečnúPolohuDámyNaRiadku(riadok + 1)) nastáva prípad spätného trasovania. V takom prípade musíme dámu na aktuálne spracúvanom riadku posunúť ďalej s kontrolou úspechu, čiže použijeme rovnaký príkaz s podmieneným spracovaním ako v cykle while (vyššie):

~

if (!posuňDámuNaRiadkuĎalej(riadok)) return false;

Ďalej potrebujeme zariadiť, aby sa po úspešnom posunutí dámy ďalej vykonávanie metódy vrátilo na miesto za položením dámy, čiže presne na riadok s cyklom while, s pomocou ktorého kontrolujeme, či je dáma ohrozená. To sa dá zariadiť s pomocou uzavretia prislúchajúceho bloku do cyklu do­‑while, ktorého činnosť bude riadená pomocnou premennou trebaOpakovať.

Pomocnú premennú deklarujeme pred cyklom do­‑while. Vždy na začiatku vykonávania cyklu nastavíme jej hodnotu na false (čiže budeme predpokladať, že cyklus nebude potrebné opakovať). Na mieste vykonania spätného trasovania nastavíme hodnotu pomocnej premennej na true, čím zabezpečíme zopakovanie cyklu do­‑while a dokončenie celého algoritmu.

Nasledujúci neúplný kód obsahuje len riadky príkazov priamo súvisiace s cyklom do­‑while a jeho pomocnou premennou:

~

boolean trebaOpakovať;
do
{
	trebaOpakovať = false;

	// …

	if // …
	{
		// …
		trebaOpakovať = true;
	}
}
while (trebaOpakovať);

Ak sa vykonávanie metódy dostane na miesto za cyklom do­‑while znamená to, že hľadanie bolo úspešné a metóda môže skončiť s návratovou hodnotou true. Úplná definícia metódy hľadajBezpečnúPolohuDámyNaRiadku bude vyzerať takto:

~

protected boolean hľadajBezpečnúPolohuDámyNaRiadku(int riadok)
{
	if (!položDámuNaRiadok(riadok)) return false;

	boolean trebaOpakovať;
	do
	{
		trebaOpakovať = false;

		while (jeDámaNaRiadkuOhrozená(riadok))
		{
			if (!posuňDámuNaRiadkuĎalej(riadok)) return false;
		}

		if (riadok + 1 < šachovnica.length)
		{
			if (!hľadajBezpečnúPolohuDámyNaRiadku(riadok + 1))
			{
				if (!posuňDámuNaRiadkuĎalej(riadok)) return false;
				trebaOpakovať = true;
			}
		}
	}
	while (trebaOpakovať);

	return true;
}

~

import knižnica.*;

public class HlavnáTrieda extends Backtracking_OsemDám
{
	public void nájdiRiešenie()
	{
		if (!hľadajBezpečnúPolohuDámyNaRiadku(0))
		{
			Svet.farbaPozadia(čierna);
			skoč(0, -MEDZERA);
			nakresliŠachovnicu();
			skoč(0, 3 * MEDZERA +
				(ROZMER_ŠTVORCA + MEDZERA) * POČET_RIADKOV / 2);
			farba(svetločervená);
			text("Riešenie nejestvuje");
		}
		else
		{
			Svet.farbaPozadia(svetlomodrá);
			nakresliŠachovnicu();
		}
	}

	public static void main(String[] args)
	{
		Svet.použiKonfiguráciu();
		Svet.nekresli();
		new HlavnáTrieda().nájdiRiešenie();
		Svet.zbaľ();
		Svet.kresli();
	}
}

Ukážka riešenia:

Keď na šachovnicu vložíme niekoľko prekážok:

~

HlavnáTrieda riešiteľ = new HlavnáTrieda();
for (int i = 0; i < 3; ++i)
{
	riešiteľ.vložPrekážku(0, i);
	riešiteľ.vložPrekážku(7, 7 - i);
	riešiteľ.vložPrekážku(i, 0);
	riešiteľ.vložPrekážku(7 - i, 7);
}
riešiteľ.nájdiRiešenie();

Riešenie bude vyzerať takto:

Keď ich pridáme ešte viac:

~

HlavnáTrieda riešiteľ = new HlavnáTrieda();
for (int i = 0; i < 4; ++i)
{
	riešiteľ.vložPrekážku(0, i);
	riešiteľ.vložPrekážku(7, 7 - i);
	riešiteľ.vložPrekážku(i, 0);
	riešiteľ.vložPrekážku(7 - i, 7);
	riešiteľ.vložPrekážku(2 + i, 2 + i);
}
riešiteľ.nájdiRiešenie();

Riešenie nebude jestvovať: