backtracking*

Método de aproximacións con busca en retroceso que se emprega para resolver problemas probando varias combinacións de movementos ata que se atopa unha combinación que teña resultados. Funciona como segue: primeiro selecciónase un movemento posible e realízase; logo, continúase desde aí seleccionando outro movemento posible e así sucesivamente, ata que se atopa unha solución. Se se alcanza un lugar no que só se atopou unha solución pero non hai máis movementos posibles, retrocédese ata a alternativa máis recente sen probar. É dicir, desfanse un ou máis movementos ata que se retrocede a unha alternativa que non se seguiu. Séguese esa opción diferente para ver se a solución se atopa nesa dirección. Se non é así, séguese retrocedendo ata que se atope o que se está buscando; se é necesario esgotando todos os movementos posibles.