Recursive maze solver with a twist - Python

Question

I am trying to solve the following problem: a die (dice?) rolls over an empty grid, giving every cell it passes the value of the number of eyes of the die (top side). There's a given starting and exit cell. I want to find a route that passes over every cell, ending up in the exit. 1 solution is enough. The program should return that route and the grid with all the numbered cells following the rules of a rolling die.

I started from a DFS maze solver script with an empty 'maze', and made changes according to the extra rules. I got it to find a route that covers every cell. And I got a script working (I think) that generates the correct number value for any given X or Y movement of the die. But trying to combine those 2 melts my brain. I am not a programmer by any means, so the recursion is killing me here.

edit: I think I managed to pull it off! I replaced my dice rolling script with yours and had to work around some other issues, but as far as I can tell it is working now! Thank you so much! This is not the end of my adventure though, there's another layer of complexity I need to implement, but I'll see if I manage to solve it on my own first.

Here's the updated code:

def roll(die, old_dir, new_dir):
    return dict(zip(new_dir, [die[s] for s in old_dir]))

def roll_north(die):
    return roll(die, 'TBNESW', 'NSBETW')

def roll_west(die):
    return roll(die, 'TBNESW', 'WENTSB')

def roll_south(die):
    return roll(die, 'TBNESW', 'SNTEBW')

def roll_east(die):
    return roll(die, 'TBNESW', 'EWNBST')

def DFS(x,y,maze,dice,c,dir):
    global Map
    Map=maze
    if ((Map[x][y]=="exit") & (c==35)):                 #check if we're at the exit
        return [(x,y)]                                  #if so then we solved it so return this spot
    if (Map[x][y]!="path"):                             #if it's not a path, we can't try this spot
        return []
    stat = Map[x][y]
    c += 1
    Map[x][y] = dice['T']                               #make this spot explored so we don't try again

    poss = [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]
    for dir in range(0, 4):                               #new spots to try
        if(dir == 0):
            dice = roll_south(dice)
        elif(dir == 1):
            dice = roll_north(dice)
        elif(dir == 2):
            dice = roll_east(dice)
        elif(dir == 3):
            dice = roll_west(dice)

        result = DFS(poss[dir][0],poss[dir][1],Map,dice,c,dir)       #recursively call itself
        if (dir == 0):
            dice = roll_north(dice)
        elif (dir == 1):
            dice = roll_south(dice)
        elif (dir == 2):
            dice = roll_west(dice)
        elif (dir == 3):
            dice = roll_east(dice)
        if len(result)>0:                                    #if the result had at least one element, it found a correct path, otherwise it failed
            result.append((x,y))                             #if it found a correct path then return the path plus this spot
            return result
    Map[x][y] = stat
    c -= 1
    return []                                                #return the empty list since we couldn't find any paths from here

def GetMap():
    return [
        ["wall","wall","wall","wall","wall","wall","wall","wall"],
        ["wall","path","path","path","path","path","path","wall"],
        ["wall","path","path","path","path","path","path","wall"],
        ["wall","path","path","path","path","path","path","wall"],
        ["wall","path","exit","path","path","path","path","wall"],
        ["wall","path","path","path","path","path","path","wall"],
        ["wall","path","path","path","path","path","path","wall"],
        ["wall","wall","wall","wall","wall","wall","wall","wall"]
    ]

def DrawMap(Map,path):
    cntr = 0
    for x in range(0,len(Map)):
        for y in range(0,len(Map[x])):
            if ((x,y) in path):
                if (Map[x][y] == 1):
                    print("1 ", end="")
                elif (Map[x][y] == 2):
                    print("2 ", end="")
                elif (Map[x][y] == 3):
                    print("3 ", end="")
                elif (Map[x][y] == 4):
                    print("4 ", end="")
                elif (Map[x][y] == 5):
                    print("5 ", end="")
                elif (Map[x][y] == 6):
                    print("6 ", end="")
                elif (Map[x][y] == "exit"):
                    print("e ", end="")
            elif (Map[x][y]=="wall"):
                print("# ",end="")

            else:
                print('  ',end="")
            cntr += 1
        print()
    if path:
        print("\nPATH:")
        path.reverse()
        print(path)

initial_die = dict(zip('TBNESW', [6,1,5,4,2,3]))

print("Solved with DFS:")
res = DFS(2,3,GetMap(),initial_die,0,0)
DrawMap(Map,res)
print("path is",len(DFS(2,3,GetMap(),initial_die,0,0))-1,"steps long\n")
print("\n")

And this is the output:

Solved with DFS:
# # # # # # # # 
# 1 2 6 5 1 2 # 
# 4 2 6 3 1 4 # 
# 4 6 5 5 5 5 # 
# 5 e 1 4 6 3 # 
# 3 3 2 2 2 2 # 
# 2 6 6 3 1 4 # 
# # # # # # # # 

PATH:
[(2, 3), (3, 3), (4, 3), (5, 3), (6, 3), (6, 4), (5, 4), (4, 4), (3, 4), (2, 4), (2, 5), (3, 5), (4, 5), (5, 5), (6, 5), (6, 6), (5, 6), (4, 6), (3, 6), (2, 6), (1, 6), (1, 5), (1, 4), (1, 3), (1, 2), (1, 1), (2, 1), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (6, 1), (6, 2), (5, 2), (4, 2)]
path is 35 steps long

Answer 1

I suggest a much simpler way to handle the die.

• The die is a dictionary that maps a direction (T, B, N, E, S, W) to a number (1,2,3,4,5,6);
• There are four functions roll_north, roll_south, roll_west, roll_east that take as input a die, and return a new die, with the six directions permuted to reflect the roll.

The face on top of the die can be accessed simply as die['T'].

initial_die = dict(zip('TBNESW', [6,1,5,4,2,3]))

def roll(die, old_dir, new_dir):
    return dict(zip(new_dir, [die[s] for s in old_dir]))

def roll_north(die):
    return roll(die, 'TBNESW', 'NSBETW')

def roll_west(die):
    return roll(die, 'TBNESW', 'WENTSB')

def roll_south(die):
    return roll(die, 'TBNESW', 'SNTEBW')

def roll_east(die):
    return roll(die, 'TBNESW', 'EWNBST')

Testing:

d = initial_die
print(d['T'], d)
for r in roll_north, roll_east, roll_south, roll_west:
    d = r(d)
    print(d['T'], d)

# OUTPUT
6 {'T': 6, 'B': 1, 'N': 5, 'E': 4, 'S': 2, 'W': 3}
2 {'N': 6, 'S': 1, 'B': 5, 'E': 4, 'T': 2, 'W': 3}
3 {'E': 2, 'W': 5, 'N': 6, 'B': 4, 'S': 1, 'T': 3}
6 {'S': 3, 'N': 4, 'T': 6, 'E': 2, 'B': 1, 'W': 5}
2 {'W': 6, 'E': 1, 'N': 4, 'T': 2, 'S': 3, 'B': 5}