I have tried tirelessly to make a maze solver in python. I have used all my resources such as friends, the internet, and stack. I have adapted my code a lot from stack questions previous to mine, but still can not come to an answer EVEN WHEN COMPLETELY COPYING CODE (which I don't like doing).
The maze/input file (nested list):
[['*', '*', '*', '*', '*'],
['*', ' ', '*', ' ', '*'],
['*', ' ', ' ', ' ', '*'],
['*', ' ', '*', ' ', 'E'],
['*', 'S', '*', '*', '*']]
This function keeps looping over the same points in the maze. My start point "S" is (4,1), with the output:
(4,1)
(4,0)
(3,1)
The above output is from the print statement I used to debug the function. It just prints the above in that order until it hits the recursive limit.Below is my solve function:
already_visited=[]
def solve(x,y):
global already_visited
matrix = draw(load())
print (x,y)
#base cases
if matrix[x][y] == "E":
for row in matrix:
row = str(row)[1:-1]
print row
return True
if matrix[x][y] == "*":
return False
if matrix[x][y] == "x":
return False
matrix[x][y] = "x"
#---------------------
if (x,y) in already_visited: #check if we have already been here
return False
already_visited.append((x,y)) #add position to list
#---------------------
# recursive cases (matrix traversal)
if (x < len(matrix)-1 and solve1(x+1,y)):
return True
elif (y > 0 and solve1(x,y-1)):
return True
elif (x > 0 and solve1(x-1,y)):
return True
elif (y < len(matrix)-1 and solve1(x,y+1)):
return True
else:
return False
All I am entering into the function for x
and y
are starting indices, S, as seen in the maze posted above. Any help is extremely appreciated!
Replacing the start of your function with the correct constraint check makes it work without running into the IndexError
. First you need to assure that x
is in range of your matrix row count. Then you need to check the same for the column count. Here the value given by len()
is the first out of range.
Additionally your reloading the matrix in every call of the solver. You should only operate on one matrix to have persistent changes. For that add it as an argument to the function:
def solve2(matrix,x,y):
print (x,y)
if x >= len(matrix) or y >= len(matrix[x]):
return False
[...]
Then call it like solve2(draw(load()),4,1)
on the first run and replace every recursing call with equivalents of solve2(matrix,x,y-1))
. The same works for solve1()
as well.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments