Részletesen leírná valaki hogy a következő backtrack pszeudókódban az egyes sorok mit csinálnak? Mondjuk a 8 királynő problémára lefordítva.

Első válaszoló vagyok.

A lényegét kell megérteni, vizsgán sem azt kérik hogy az előadás vázlattal minél több százalékban pontosan megegyezzen amit vizsgára írsz , hanem hogy helyes legyen.

Az életbe is a lényegét kell megérteni a backtrack-nek. Számtalan helyes pszeudó kódot lehetne írni konkrétan a 8 királynő-re, meg általánosan is a visszalépéses keresésre.

Most ugyan azt tudnám leírni ami ott van, ha pontosan a kérdésre válaszolnék. E helyett leírom a saját szavaimmal hogy működik a backtrack a 8 királynőre, most elvonatkoztatva kicsit az óravázalttól, az alapelv tulajdonképpen ugyan az. Itt ott pongyolán fogok fogalmazni azért mert az a tapasztalatom hogy így könnyebb így megérteni, mintha végig precízen/ formálisan írnám.

Vegyük a 8 királynő problémáját ahol a cél egy sakktáblán van 8 királynőt úgy elhelyezni hogy (a sakk szabályainak megfelelően) egyik sem üti a másikat.

Első megközelítésbe van egy nagyon nagy problématerünk, de ezt lehet csökkenteni pl egy sorba csak egy bábú lehet ezért elég csak 8 számot tárolni ami az egyes sorokra vonatkozik hogy hol van a bábú az adott sorba.Továbbá megállapíthatjuk hogy föntről le haladva a táblán már a 2. sor nem stimmel akkor kár a további sorokba próbálkozni előbb az 1. és 2. sornak kell stimmelni aztán jöhet a 3. sor és így tovább. Vagyis az n-edik sorba lévő bábút csak akkor rakjuk le ha a szabálynak megfelel az 1. sortól az n-1-ik sorig. Elő fordulhat hogy nem rakhatunk sehova az n-edik sorba de az n-1-ik sorba még a szabálynak megfelel, akkor vegyük a következő megoldást az n-1 sorra és most próbáljuk meg az n-ik sorba rakni.

Az n-1-ik sorig sem közvetlenül oldjuk meg hanem ugyan így. Vissza vezetjük a problémát n-2 sorra, ezt n-3 sorra egészen addig vezetjük vissza egyre kisebb részproblémáig amíg közvetlenül meg tudjuk oldani, vagyis visszavertjük egészen addig amíg csak 1 sor van vagyis a táblának vesszük a 8x1-es részét, itt bárhogy is rakunk 1-et az jó lesz. Majd vesszük a 8x2-es részét stb ahogy már leírtam.

Nem kell mereven ragaszkodni az általánosan felírt pszeudó kódhoz, az alapelvéhez igen.

A 8 királynő pszedó kódja:

probal(i){

--for j= 1 to 8 do

----if eddig_jo(j) then

--------{

-------------tabla[i]:=j;

-------------if i<8 then probal(i+1) else{

---------------kiír(tabla)

---------------{kilépés a programból}

--------------}

--------}

}

A probal(1) függvényhívással kell meghívni, ha elhagyjuk a {kilépés a programból} sort akkor az összes megoldást kiírja. A sok - jel azért van hogy megmaradjon az indentáció. Ha jól tévedek akkor ez jó pszeudo kód, impelentáld a 8 királynőt ez alapján. Impelmentáld a sudokut is teljesen egyedül és több visszalépéses kereséssel megoldható problémát is ezeken kívül! Gondolkozz közbe,lényegébe mást nem is kell tenni! Majd nézd meg a jegyzetet és világos lesz mint a nap! :)