Algorisme de backtracking

El backtracking és una tècnica algorísmica per trobar solucions a problemes a base de provar totes les possibles solucions.

Aplicacions típiques del backtracking son els laberints i el Sudoku.

Exemple del laberint

Podem fer una ullada a l'exemple d'aquesta web on surt el típic laberint i on s'expliquen dos algorismes per solucionar-ho: el recursiu (backtrack) i el A* (que ve a ser una optimització).

http://www.laurentluce.com/posts/solving-mazes-using-python-simple-recursivity-and-a-search/

Assumim que tenim un objecte Laberint com s'indica, amb un mètode backtrack (entre d'altres) que retorni la llista de cel·les que ens porten des de l'inici (I) fins el final (F):

class Laberint():
    lab = None # matriu del laberint
    ...
    def backtrack(self,fila,col):
        ...

L'algorisme RECURSIU que ens ho resol seria aquest:

    # backtrack recursiu
    # retornem
    #   false si no hi ha sortida
    #   la llista de cel·les recorregudes quan arribem al final
    def backtrack(lab,fila,col):
        if lab[fila][col]=="F":
            # final: engeguem la llista que s'anirà omplint amb el recorregut bo
            return [(fila,col)]
        elif lab[fila][col]=="*":
            # mur, per aquí no podem
            return False
        elif lab[fila][col]=="v":
            # cel·la visitada, passem a la següent
            return False

        # se suposa que és una cela "I" o ".""
        assert lab[fila][col]=="I" or lab[fila][col]=="." , "cel·la desconeguda"

        if lab[fila][col]==".":
            # marquem com a cel·la visitada
            lab[fila][col] = "v"

        # direccions = dreta, amunt, esq, avall
        direccions = [(0,1),(1,0),(0,-1),(-1,0)]

        # avançem: provem per cadascuna per les diferents direccions
        for d in direccions:
            fila_seg = fila + d[0]
            col_seg = col + d[1]
            # controlem de no sortir del laberint (matriu)
            if fila_seg<0 or fila_seg>=len(lab) or col_seg<0 or col_seg>=len(lab[0]):
                pass
            else:
                # seguim al seguent pas
                cami = backtrack(lab,fila_seg,col_seg)
                # hem arribat al final (retorna llista):
                if cami:
                    cami.append( (fila,col) )
                    return cami
        # si arribem aquí és que hem esgotat totes les possibles direccions
        return False

Exemple del Sudoku

...ja arribarà...