# # This is modified version. # # If you want to run it in SoloLearn, # please give an input less than 10, # or it would cause TLE or Memory limit. # # I recommend you to copy the code to # other IDE to see how it completely runs. # Line 251, 252 is used to see the progress # when the required size is big and you # wouldn't know if it's still working. # # I have created a 3D-direction class # and is useful to deal with 3D directions. # # This code contains a 3D-direction system, # a maze generator, which not only give the # map but also its solution, and an # algorithm to solve a 3D maze. # # # '18/05/20 # Flandre Scarlet(雨宮桜) # import random class Direction: # 3D direction system def __init__(self,front,right): # 0E 1N 2U 3W 4S 5D self.f = front self.r = right def turn(self,dir): dir %= 6 # 0r 1f 2u 3l 4b 5d def Up(f,r): transform = [[0,5,1],[2,1,3],[4,0,2]] if f%6<3: return (transform[f%6][r%3] + r%6//3*3%6)%6 else: return Up(f%3,(r+3)%6) if dir==0: self.f, self.r = self.r, (self.f+3)%6 elif dir==1: # do nothing self.f elif dir==2: self.f = Up(self.f, self.r) elif dir==3: self.f, self.r = (self.r+3)%6, self.f elif dir==4: self.f = (self.f+3)%6 self.r = (self.r+3)%6 elif dir==5: self.f = Up(self.f+3, self.r) def getRel(self, dir): if dir==self.r: # right return 0 elif dir==self.f: # front return 1 elif dir==(self.r+3)%6: # left return 3 elif dir==(self.f+3)%6: # back return 4 elif dir == self.getDirection(2).f: return 2 # up else: return 5 # down def turnTo(self, dir): rel = self.getRel(dir) if rel in [0,3,4]: self.turn(rel) else: self.f = dir def next(self,num=1): # N/E - U/N - W/U - S/W - D/S - E/D self.f = (self.f+num)%6 self.r = (self.r+num)%6 def getDirection(self, dir=1): newDir = Direction(self.f, self.r) newDir.turn(dir) return newDir def show(self): # front only return ["E","N","U","W","S","D"][self.f] def showFull(self): # front, right ds = ["E","N","U","W","S","D"] return [ds[self.f],ds[self.r]] def createMap(w,d,h): # width, depth, height maps = [] for p in range(w): surface = [] for q in range(d): line = [] for r in range(h): line.append([1,1,1]) surface.append(line) maps.append(surface) return maps def getGrid(grid, dir=None): if dir == None: return [grid[0],grid[1],grid[2]] elif dir == 0: return [grid[0]+1,grid[1],grid[2]] elif dir == 1: return [grid[0],grid[1]+1,grid[2]] elif dir == 2: return [grid[0],grid[1],grid[2]+1] elif dir == 3: return [grid[0]-1,grid[1],grid[2]] elif dir == 4: return [grid[0],grid[1]-1,grid[2]] elif dir == 5: return [grid[0],grid[1],grid[2]-1] def open(maps, grid, dir): a, b, c = grid if dir <3: maps[a][b][c][dir] = 0 elif dir == 3: maps[a-1][b][c][0] = 0 elif dir == 4: maps[a][b-1][c][1] = 0 elif dir == 5: maps[a][b][c-1][2] = 0 def same(p1,p2): for cor in range(3): if p1[cor]!=p2[cor]: return False return True def isIn(arr,test): for item in arr: if same(item,test): return True return False def noWay(maps,grid): a, b, c = grid #print(grid) if a0 and not isUsed(maps,[a-1,b,c]): #print(a-1,b,c,"0 =1") return False elif b>0 and not isUsed(maps,[a,b-1,c]): #print(a,b-1,c,"1 =1") return False elif c>0 and not isUsed(maps,[a,b,c-1]): #print(a,b,c-1,"2 =1") return False else: #print("No way") return True def isUsed(maps,grid): a, b, c = grid if 0 in maps[a][b][c]: return True elif a>0 and maps[a-1][b][c][0]==0: return True elif b>0 and maps[a][b-1][c][1]==0: return True elif c>0 and maps[a][b][c-1][2]==0: return True else: return False def avail(w,d,h,grid,dir=None): tmp = getGrid(grid,dir) if tmp[0]<0 or tmp[0]==w: del tmp return False elif tmp[1]<0 or tmp[1]==d: del tmp return False elif tmp[2]<0 or tmp[2]==h: del tmp return False else: del tmp return True def printWalls(maps, grid): a, b, c = grid w = [] for p in maps[a][b][c]: w.append(p) w.append(1 if a==0 else maps[a-1][b][c][0]) w.append(1 if b==0 else maps[a][b-1][c][1]) w.append(1 if c==0 else maps[a][b][c-1][2]) return w def createPuzzle(w,d,h): maps = createMap(w,d,h) size = w*d*h used = 1 #rec = [[0,0,0]] sol = [[0,0,0]] index = 0 pos = sol[index] end = [w-1,d-1,h-1] progressChecker = 1 #print(maps) while used=progressChecker: progressChecker += 1 print(int(used/(size/100)),"% completed") while not same(sol[-1],end): del sol[-1] return [maps,sol] # solve def solMap(w,d,h): solmaps = [] for p in range(w): surface = [] for q in range(d): line = [] for r in range(h): line.append(0) surface.append(line) solmaps.append(surface) return solmaps def isWalked(maps,grid,direc): a, b, c = grid if direc==0: return maps[a+1][b][c]==1 elif direc==1: return maps[a][b+1][c]==1 elif direc==2: return maps[a][b][c+1]==1 elif direc==3: return maps[a-1][b][c]==1 elif direc==4: return maps[a][b-1][c]==1 else: return maps[a][b][c-1]==1 def printWalked(maps, grid): a, b, c = grid w = [] w.append(-1 if a==len(maps)-1 else maps[a+1][b][c]) w.append(-1 if b==len(maps[0])-1 else maps[a][b+1][c]) w.append(-1 if c==len(maps[0][0])-1 else maps[a][b][c+1]) w.append(-1 if a==0 else maps[a-1][b][c]) w.append(-1 if b==0 else maps[a][b-1][c]) w.append(-1 if c==0 else maps[a][b][c-1]) return w def isWall(maps, grid, direc): a, b, c = grid[0],grid[1],grid[2] #print("maps",[a,b,c],":",maps[a][b][c]) #print("direc:",direc) if direc<3: return maps[a][b][c][direc]==1 elif direc==3: return maps[a-1][b][c][0]==1 elif direc==4: return maps[a][b-1][c][1]==1 elif direc==5: return maps[a][b][c-1][2]==1 def getDirec(grid1, grid2): for p in range(3): if grid2[p]>grid1[p]: return p for p in range(3): if grid2[p] get back for p in range(5): if not avail(a,b,c,pos,tempdir) or isWall(maps, pos, tempdir) or isWalked(solrec,pos,tempdir): #print(pos,tempdir,"no") #if not avail(a,b,c,pos,tempdir): #print(pos,tempdir,"not avail") #elif isWall(maps, pos, tempdir): #print(pos,tempdir,"isWall",printWalls(maps,pos)) #elif isWalked(solrec,pos,tempdir): #else: #print(pos,tempdir,"isWalked",printWalked(solrec,pos)) tempdir = (tempdir+1)%6 else: break #input() if tempdir==(direc.f+3)%6: #print("del",path[-1]) if path[-1] in sol: #print("in sol?:",path[-1] in sol) #print("next:",sol[sol.index(path[-1])+1]) if input()==" ": printMap(solrec) input() del path[-1] direc.turnTo(getDirec(path[-2],path[-1])) length -= 1 pos = path[-1] #print(pos,direc) print("*",length,"/".join(direc.showFull()),"back",pos,"*") else: pos = getGrid(pos, tempdir) length += 1 tempDirec = direc.getDirection() direc.turnTo(tempdir) print(length,"/".join(direc.showFull()),["right","front","up ","left ","b","down "][tempDirec.getRel(tempdir)],pos) #print("add",pos) solrec[pos[0]][pos[1]][pos[2]] = 1 path.append(pos) #input() return path con = "y" while con.lower()=="y": print("Game start, please set the maze size first") try: x = int(input("width:\n")) except: x = 30 try: y = int(input("depth:\n")) except: y = x try: z = int(input("height:\n")) except: z = y #directions = [0,1,2,3,4,5] # +x, +y, +z, -x, -y, -z maps = createPuzzle(x,y,z) # 0 is map, 1 is solution print() print("Map size:",x*y*z) print("Solution length:",len(maps[1])) try: input("\nwaiting to check solution\n"); except: print() # automatically solving sol = solve(maps[0],maps[1]) #[print(p+1,sol[p]) for p in range(len(sol))] print() print("Auto-Solving correct" if checkSolution(maps[1],sol) else "Solution failed") print() try: con = input("Do you want to play once more?(y/n)") except: con = "n" print() print("Thank you for playing my game.")

3D Maze Generator and Solver