12.4. Visszalépéses programozás (Back-track)

A megoldás keresésének gyakori módszere a próbálgatás. Ha egy pontban már az összes lehetőséget kipróbáltuk, s egyik sem vezetett eredményre, akkor azt a lépést, mellyel idejutottunk, meg nem történtté kell nyilvánítani, s másfele próbálkozni. Erre a módszerre az egyik jellemző feladat az n vezér feladata, ahol az n × nes sakktáblára úgy kell felrakni az n vezért, hogy azok ne üthessék egymást. A vezérek pozícióját a T tömbben tároljuk, s megpróbáljuk lerakni az i-dik vezért. Ha ez sikerült, akkor próbáljuk lerakni a következőt is. Ellenkező esetben a vezért továbbtoljuk a következő pozícióra, hátha ott nagyobb sikerrel jár. Ha viszont ezzel leléptünk a tábláról, akkor ezt az utolsó vezért leszedjük a tábláról, s az utolsó előttinek keresünk jobb helyet.

Procedure N-VEZÉR(n) 
Input: n a tábla mérete 
Eredmény: T tömbben az állás 
1  i = 1 
2  j = 1 
3  while 0 ≤ i and i ≤ n do 
4     T[i] = j 
5     if j ≲ n then 
6        üti = HAMIS 
7        for k = 1 to n − 1 do 
8           if T[i] == T[k] or |T[i] − T[k]| == i − k then 
9              üti = IGAZ 
10          endif 
11       endfor 
12       if üti then 
13          j = j + 1 
14       else 
15          i = i + 1 
16          j = 1 
17       endif 
18    endif 
19    if j ≥ n then 
20       i = i − 1
21    endif 
22 endw 
23 if i ≥ 0 then 
24    j = T[i] + 1
25 endif