Maze solution ( algorithm of backtracking)

  backtracking, maze, python

I’m trying to create a maze solution (The maze is the Prim function).
But I don’t understand why my backtracking algorithm doesn’t work.
Can anyone help me ?

import numpy as np
from numpy.random import randint as rand
import matplotlib.pyplot as pyplot

def Laby_mur(x,y):
    M = np.ones((2*x+1,2*y+1))
    return(M)

def Prim(x,y):
    M = Laby_mur(x,y)
    (X,Y) = np.shape(M)
    a, b = 2*rand(x)+1, 2*rand(y)+1
    M[a][b] = 0
    V1 = []
    V = [[(a-2, b),(a,b)],[(a, b-2),(a,b)],[(a+2, b),(a,b)],[(a, b+2),(a,b)]]
    for i in V:
        i0 = i[0]
        if 0<i0[0]<X-1 and 0<i0[1]<Y-1:
            M[i[0],i[1]] = 2
            V1 += [i]
    V = V1
    V1 = []
    while V != []:
        c = rand(len(V))
        [a,b] = V[c]
        del V[c]
        M[a[0],a[1]] = 0
        M[b[0]+(a[0]-b[0])//2,b[1]+(a[1]-b[1])//2]=0    
        d = a[0]
        e = a[1]
        V += [[(d,e+2),(d,e)],[(d-2,e),(d,e)],[(d,e-2),(d,e)],[(d+2,e),(d,e)]]
        for i in V :
            i0 = i[0]
            if  0<i0[0]<X-1 and 0<i0[1]<Y-1 and M[i0[0],i0[1]] != 0:
                M[i0[0],i0[1]]=2
                V1+=[i] 
        V=V1
        V1=[]
    M[0,1]=0
    M[X-2, Y-1]=0
    return(M,(a,b), V)

So this is my function to create a maze.
Now, this is my backtracking algorithm.
I have to go East as often as possible.

    
def initialisation(laby):
    laby[0][1]=0.5
    P = [(0,1)]
    return(laby,P)

print(initialisation(Prim(2,2))[0])
    
def  Vers_Est(laby, i, j, P):
    if laby[i][j] == 0:
        P += [(i,j+1)]
        laby[i][j+1] = 0.5
        i = i
        j = j+1
        return(True, laby, P)
    else :
        return(False, laby, P)
        
def  Vers_Ouest(laby, i, j, P):
    if laby[i][j] == 0:
        P += [(i,j-1)]
        laby[i][j-1] = 0.5
        i = i
        j = j-1
        return(True, laby, P)
    else :
        return(False, laby, P)

def  Vers_Sud(laby, i, j, P):
    if laby[i][j] == 0:
        P += [(i+1,j)]
        laby[i+1][j] = 0.5
        i = i+1
        j = j
        return(True, laby, P)
    else :
        return(False, laby, P)
    
def  Vers_Nord(laby, i, j, P):
    if laby[i][j] == 0:
        P += [(i-1,j)]
        laby[i-1][j] = 0.5
        i = i-1
        j = j
        return(True, laby, P)
    else :
        return(False, laby, P)
    

Each function (Vers_Est, Vers_Ouest…) associate with 4 inputs (maze in its matrix form, i, j, P which is a list describing the way to get out of the maze), a triplet : (True if a move can be made to the East / West / South / North, laby who is the maze after the move, P with the coordinates of the displacement).


def Demi_tour_Est(laby, i, j, P):
    if Vers_Est(laby,i,j,P)[0] == False :
        if Vers_Ouest(laby,i,j,P)[0] == False:
            if Vers_Sud(laby,i,j,P)[0] == False :
                if Vers_Nord(laby, i, j, P)[0] == False:
                    if laby[i][j+1] == 0.5 :
                        P.remove[(i,j)]
                        laby[i][j] = 0.2
                        return(True,laby,P)
                    else :
                        return(False, laby, P)
                    
def Demi_tour_Ouest(laby, i, j, P):
    if Vers_Est(laby,i,j,P)[0] == False :
        if Vers_Ouest(laby,i,j,P)[0] == False:
            if Vers_Sud(laby,i,j,P)[0] == False :
                if Vers_Nord(laby, i, j, P)[0] == False:
                    if laby[i][j-1] == 0.5 :
                        P.remove[(i,j)]
                        laby[i][j] = 0.2
                        return(True,laby,P)
                    else :
                        return(False, laby, P)
        
def Demi_tour_Sud(laby, i, j, P):
    if Vers_Est(laby,i,j,P)[0] == False :
        if Vers_Ouest(laby,i,j,P)[0] == False:
            if Vers_Sud(laby,i,j,P)[0] == False :
                if Vers_Nord(laby, i, j, P)[0] == False:
                    if laby[i+1][j] == 0.5 :
                        P.remove[(i,j)]
                        laby[i][j] = 0.2
                        return(True,laby,P)
                    else :
                        return(False, laby, P)
                    
def Demi_tour_Nord(laby, i, j, P):
    if Vers_Est(laby,i,j,P)[0] == False :
        if Vers_Ouest(laby,i,j,P)[0] == False:
            if Vers_Sud(laby,i,j,P)[0] == False :
                if Vers_Nord(laby, i, j, P)[0] == False:
                    if laby[i-1][j] == 0.5 :
                        P.remove[(i,j)]
                        laby[i][j] = 0.2
                        return(True,laby,P)
                    else :
                        return(False, laby, P)

Each function (Demi_tour_Est, Demi_tour_Ouest …) allows to turn around if no coordinates are empty around the place laby[i][j].


def backtracking(laby):
    M = initialisation(laby)[0]
    i = 0
    j = 1
    (X,Y) = np.shape(M)
    P = initialisation(laby)[1]
    while M[i][j] != M[X-2][Y-1] :
        if Vers_Est(laby, i, j, P)[0] :
            Vers_Est(laby, i, j, P)
        elif Vers_Ouest(laby, i, j, P)[0]:
            Vers_Ouest(laby, i, j, P)
        elif Vers_Sud(laby, i, j, P)[0]:
            Vers_Sud(laby, i, j, P)[0]
        elif Vers_Nord(laby, i, j, P)[0]:
            Vers_Nord(laby, i, j, P)[0]
        else :
            if Demi_tour_Est(laby, i, j, P)[0]:
                Demi_tour_Est(laby, i, j, P)
            elif Demi_tour_Ouest(laby, i, j, P)[0]:
                Demi_tour_Ouest(laby, i, j, P)
            elif Demi_tour_Sud(laby, i, j, P)[0]:
                Demi_tour_Sud(laby, i, j, P)
            elif Demi_tour_Nord(laby, i, j, P)[0]:
                Demi_tour_Nord(laby, i, j, P)
    return(laby,P)

print(backtracking(Prim(3,3)))

I don’t understand what’s wrong.

In the function Backtracking, I want to put in relation these functions to try to solve the labyrinth.

Can anyone help me ?

Source: Python Questions

LEAVE A COMMENT