Backtracking

[HastatusXXI]

Hola. He intentado resolver el problema del 15-puzzle del Juez de la UVa en Python mediante backtracking (el problema en cuestión es este: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=36&page=show_problem&problem=1122). El problema está en que se supone que cada solución está limitada a un máximo de 50 pasos, pero el vector solución crece hasta más de 140 pasos en la mayor parte de las iteraciones, por lo que el programa no encuentra la solución en un tiempo razonable. Adjunto el código del programa completo, pero solo es necesario mirar el método backtracking (sé que nadie va a estudiar un código tan largo, pero tampoco hace falta). Solo debería generarse un movimiento como máximo en cada llamada a backtracking, y si la rama no tiene más nodos intermedios debería volver al estado anterior y borrar del vector solución el último movimiento. La condición 

Código (python) [Seleccionar] Expandir

if(a[k] != mov_inv[c[i]]): sirve para evitar deshacer movimientos ¿Alguien puede decirme por qué el vector solución crece más allá de los 50 elementos? (Cabe decir, que efectivamente, k no sobrepasa nunca el valor 50).

Código (python) [Seleccionar] Expandir



moves = {0:('R','D'),1:('R','L','D'),2:('R','L','D'),3:('L','D'),4:('R','D','U'),5:('R','L','D','U'),
         6:('R','L','D','U'),7:('L','U','D'),8:('R','D','U'),9:('R','L','D','U'),10:('R','L','D','U'),
         11:('L','U','D'),12:('U','R'),13:('L','U','R'),14:('L','U','R'),15:('U','L')}

mov_inv = {'U':'D','D':'U','R':'L','L':'R'}


def backtracking(a,k,tab):
    c = []
    if is_solution(tab):
        process_solution(a)
    elif k < 51:
        print a
        c = construct_candidates(tab)
        for i in range(len(c)):
            if(a[k] != mov_inv[c[i]]):
                a.append(c[i])
                make_move(tab,a[k+1])
                backtracking(a,k+1,tab)
                unmake_move(tab,a[k+1])
                a = a[:-1]

def inversions(a):
    n_inv = 0
    a_copy = a[:]
    a_copy.remove(0)
   
    for i in range(len(a_copy)):
        for j in range(i,len(a_copy)):
            if a_copy[i] > a_copy[j]:
                n_inv = n_inv + 1
   
    return n_inv

def is_solvable(a):
    n_inv = inversions(a)
    if ((a.index(0) % 4) % 2) == 0 and n_inv % 2 == 0:
        return True
    if ((a.index(0) % 4) % 2) == 1 and n_inv % 2 == 1:
        return True
    return False


def construct_candidates(tab):
    i = tab.index(0)
    m = moves[i]
    c = []
    for j in range(len(m)):
        c.append(m[j])
    return c
   
def make_move(tab,m):
    i = tab.index(0)
    if m == 'U':
        c = tab[i-4]
        tab[i-4] = 0
        tab[i] = c
    elif m == 'D':
        c = tab[i+4]
        tab[i+4] = 0
        tab[i] = c
    elif m == 'L':
        c = tab[i-1]
        tab[i-1] = 0
        tab[i] = c
    elif m == 'R':
        c = tab[i+1]
        tab[i+1] = 0
        tab[i] = c
       
def unmake_move(tab,m):
    make_move(tab,mov_inv[m])

def is_solution(tab):
    if(tab[15] != 0):
        return False
    else:
        for i in range(len(tab)-1):
            if tab[i] != i+1:
                return False
    return True

def process_solution(a):
    print a

a = [-1]
tab = [2,3,4,0,
       1,5,7,8,
       9,6,10,12,
       13,14,11,15]


if not is_solvable(tab):
    print "This puzzle is not solvable"
else:
    backtracking(a,0,tab)