
xxxxxxxxxx
#Connect Flow - www.101computing.net/connect-flow-backtracking-algorithm/
import turtle, time
SPEED = 1 #Change the speed of the animation from 0 (slow) to 1 (fast)
myPen = turtle.Turtle()
myPen.tracer(0)
myPen.speed(0)
myPen.hideturtle()
screen = turtle.Screen()
screen.bgcolor("#444444")
myPen.color("#222222")
topLeft_x=-150
topLeft_y=150
colors = ["#222222","#000000","red","yellow","blue","green","orange","magenta","purple","brown","darkgreen"]
dotsColors = ["#222222","#000000","darkred","orange","darkblue","darkgreen","red","purple","magenta","chocolate","green"]
##### Setting up the game...
grid=[]
grid = [[1,1,1,1,1,1,1,1,1,1]]
grid.append([1,0,0,2,0,0,0,0,0,1])
grid.append([1,0,0,3,4,5,0,0,0,1])
grid.append([1,0,0,6,0,0,0,0,0,1])
grid.append([1,0,0,0,0,0,6,0,4,1])
grid.append([1,0,0,0,2,0,3,0,0,1])
grid.append([1,5,0,7,0,0,7,8,0,1])
grid.append([1,9,0,0,0,8,0,0,0,1])
grid.append([1,0,0,9,0,0,0,0,0,1])
grid.append([1,1,1,1,1,1,1,1,1,1])
#Workout the size of the grid
ROWS = len(grid)
COLS = len(grid[0])
startNodes = {}
endNodes = {}
allNodes = []
distances = {}
#Let's analyse the initial grid to identify all starting and ending nodes that we will need to connect
for row in range (1,ROWS-1):
for column in range (1,COLS-1):
color = grid[row][column]
if color>0:
if color in startNodes:
endNodes[color] = [row,column]
distances[color] = abs(row-startNodes[color][0]) + abs(column-startNodes[color][1])
else:
startNodes[color] = [row,column]
allNodes.append([row,column,color])
#A procedure to draw the 2D grid using Python Turtle
def drawGrid(width):
global ROWS, COLS
myPen.penup()
myPen.setheading(0)
myPen.goto(topLeft_x,topLeft_y-width)
#myPen.pendown()
for row in range (1,ROWS-1):
for column in range (1,COLS-1):
square(width,grid[row][column])
myPen.forward(width)
myPen.setheading(270)
myPen.forward(width)
myPen.setheading(180)
myPen.forward(width*(COLS-2))
myPen.setheading(0)
#Add Starting and Ending Nodes to the grid...
for node in allNodes:
myPen.setheading(0)
myPen.goto(topLeft_x + node[1]*width - width//2, topLeft_y - node[0]*width + width//4)
myPen.fillcolor(dotsColors[node[2]])
myPen.begin_fill()
myPen.circle(width//4)
myPen.end_fill()
# This procedure draws a box by drawing each side of the square and using the fill function
def square(width,index):
myPen.fillcolor(colors[index])
myPen.begin_fill()
for i in range(0,4):
myPen.forward(width)
myPen.left(90)
myPen.end_fill()
myPen.setheading(0)
#A Function to check if the grid is valid! A grid that contains a cell of colour surrounded by other colours is invalid...
def checkGrid(grid):
for row in range (1,ROWS-1):
for column in range (1,COLS-1):
if grid[row][column]>0:
color = grid[row][column]
#A grid that contains a cell of colour surrounded by other colours is invalid...
if grid[row+1][column]>0 and grid[row+1][column]!=color:
if grid[row-1][column]>0 and grid[row-1][column]!=color:
if grid[row][column+1]>0 and grid[row][column+1]!=color:
if grid[row][column-1]>0 and grid[row][column-1]!=color:
return False
#A connection line that crosses with itself is invalid
if grid[row+1][column]==color and grid[row-1][column]==color and grid[row][column+1]==color:
return False
elif grid[row+1][column]==color and grid[row-1][column]==color and grid[row][column-1]==color:
return False
elif grid[row+1][column]==color and grid[row][column+1]==color and grid[row][column-1]==color:
return False
elif grid[row-1][column]==color and grid[row][column+1]==color and grid[row][column-1]==color:
return False
return True
#When all cells have been filled in, the puzzle should be solved!
def solved(grid):
global ROWS, COLS
for row in range (1,ROWS-1):
for column in range (1,COLS-1):
if grid[row][column]==0:
return False
return True
#Return the Absolute/positive difference between two numbers
def abs(a,b):
if a>b:
return a-b
else:
return b-a
#A recursive/backtracking function to check all possible moves and discard grids that will not lead to a solution
def solvePuzzle(grid):
drawGrid(30) #30 is the width of each square on the grid
myPen.getscreen().update()
time.sleep(1-SPEED)
#Applying heuristics to see ff the grid can be discarded at this stage, this will save a lot of steps
if checkGrid(grid)==False:
return False
#Is the grid fully solved?
if solved(grid):
return True
#Let's investigate the next move!
for color in startNodes:
startNode = startNodes[color]
endNode = endNodes[color]
#Check if the dots from this color are already connected
if (abs(endNode[0],startNode[0]) + abs(endNode[1],startNode[1])>1):
#If not let's find out in which direction to progress...
directions = []
if grid[startNode[0]][startNode[1]+1]==0:
directions.append("right") #Lower Priority!
if grid[startNode[0]][startNode[1]-1]==0:
directions.append("left") #Lower Priority!
if grid[startNode[0]+1][startNode[1]]==0:
directions.append("down") #Lower Priority!
if grid[startNode[0]-1][startNode[1]]==0:
directions.append("up") #Lower Priority!
if len(directions)==0:
return False
#Let's investigate possible moves in different directions...
for direction in directions:
if direction=="right":
startNode[1] += 1
grid[startNode[0]][startNode[1]]=color
if solvePuzzle(grid)==True:
return True
else:
#backtrack...
grid[startNode[0]][startNode[1]]=0
startNode[1] -= 1
elif direction=="left":
startNode[1] -= 1
grid[startNode[0]][startNode[1]]=color
if solvePuzzle(grid)==True:
return True
else:
#backtrack...
grid[startNode[0]][startNode[1]]=0
startNode[1] +=1
elif direction=="up":
startNode[0] -= 1
grid[startNode[0]][startNode[1]]=color
if solvePuzzle(grid)==True:
return True
else:
#backtrack...
grid[startNode[0]][startNode[1]]=0
startNode[0] +=1
elif direction=="down":
startNode[0] +=1
grid[startNode[0]][startNode[1]]=color
if solvePuzzle(grid)==True:
return True
else:
#backtrack...
grid[startNode[0]][startNode[1]]=0
startNode[0] -=1
#As none of the moves lead to a solution...
return False
drawGrid(30) #30 is the width of each square on the grid
myPen.getscreen().update()
time.sleep(3)
#Let's start the backtracking algorithm!
if solvePuzzle(grid):
print("Problem Solved!")
else:
print("This problem cannot be solved!")
task_alt