labyrinthe = [
    [1, 0, 1, 1],
    [1, 1, 1, 1],
    [0, 1, 0, 1],
    [1, 1, 1, 1]
]

chemins_valides = []

def explorer(lab, dim, chemin, yd, xd, yf, xf):
    global chemin_valide
    
    if (xd == xf and yd == yf):
        chemins_valides.append(chemin.copy())
        return 
    
    for (dx,dy) in [(1,0), (-1,0), (0,1), (0,-1)]:
        x = xd + dx
        y = yd + dy

        if (y,x) in chemin:
            continue
        
        if (0 <= x < dim) and (0 <= y < dim):
            if lab[y][x] == 1:
                chemin.append((y, x))
                explorer(lab, dim, chemin, y, x, yf, xf)
                chemin.pop()

def main(): 
    global chemin_valide  
    
    explorer(labyrinthe, 4, [(0,0)], 0, 0, 3, 3)
    for chemin in chemins_valides:
        print(chemin)
    
if __name__ == "__main__":
    main()