#### Maze solution ( algorithm of backtracking)

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