Due to a problem with turtle, this program slows down as time goes on. I'm trying to fix that issue, but it should work otherwise. I know that changes need to be made in def play(), but I'm not exactly sure how. I'm trying to find a quicker way to run this and any and all feedback is much appreciated!
import math
import turtle
import random
class Puzzle:
def __init__(self, sideLength, x, y, col):
self.cells = [[1, 2, 3],[4, 5, 6],[7, 8, 0]]
self.SIZE = 100
self.posX = 0
self.posY = 0
self.t = turtle.Turtle()
turtle.delay(0)
turtle.tracer(0,0)
self.SIZE = sideLength
self.posX = x
self.posY = y
self.t.width = 4
self.t.hideturtle()
self.t.speed(0)
self.t.color(col,'white')
self.t.penup()
self.t.goto(0,0)
self.t.pendown()
def drawSquare(self, t, side):
[x,y] = self.t.position()
self.t.pendown()
self.t.begin_fill()
self.t.begin_poly()
for s in range(4):
self.t.forward(side)
self.t.right(90)
self.t.end_poly()
self.t.end_fill()
self.t.penup()
self.t.goto(x,y)
self.t.pendown()
def isGoal(self):
temp = []
for row in range(3):
for col in range(3):
temp.append(self.cells[row][col])
if temp[0]==0:
for i in range(8):
if temp[i]>temp[i+1]:
return False
return True
if temp[-1]==0:
for i in range(7):
if temp[i]>temp[i+1]:
return False
return True
else:
return False
def solvable(self):
temp = []
for row in range(3):
for col in range(3):
temp.append(self.cells[row][col])
inv_count = 0;
for i in range(len(temp)):
for j in range(i+1,len(temp)):
if temp[j]!=0 and temp[i]!=0 and temp[i] > temp[j]:
inv_count += 1
return (inv_count%2==0)
def shuffle(self):
temp = []
for row in range(3):
for col in range(3):
temp.append(self.cells[row][col])
for i in range(len(temp)):
r = random.randint(0, len(temp)-1)
t = temp[i]
temp[i] = temp[r]
temp[r] = t
for i in range(len(temp)):
self.cells[i//3][i%3] = temp[i]
def utility(self):
manhattan_dist = 0
for row in range(3):
for col in range(3):
tile = self.cells[row][col]
if tile == 0:
continue
finalRow = (tile-1)//3
finalCol = (tile-1)%3
manhattan_dist += abs(row-finalRow)+abs(col-finalCol)
return manhattan_dist
def display(self):
print(self.cells)
def up(self, visible):
found = False
for row in range(3):
for col in range(3):
if self.cells[row][col]==0:
found = True
break
if found:
break
if row==2:
return False
else:
self.cells[row][col] = self.cells[row+1][col]
self.cells[row+1][col] = 0
if visible:
self.updateBoard(row+1, col, row, col)
return True
def down(self, visible):
found = False
for row in range(3):
for col in range(3):
if self.cells[row][col]==0:
found = True
break
if found:
break
if row==0:
return False
else:
self.cells[row][col] = self.cells[row-1][col]
self.cells[row-1][col] = 0
if visible:
self.updateBoard(row-1, col, row, col)
return True
def left(self, visible):
found = False
for row in range(3):
for col in range(3):
if self.cells[row][col]==0:
found = True
break
if found:
break
if col==2:
return False
else:
self.cells[row][col] = self.cells[row][col+1]
self.cells[row][col+1] = 0
if visible:
self.updateBoard(row, col+1, row, col)
return True
def right(self, visible):
found = False
for row in range(3):
for col in range(3):
if self.cells[row][col]==0:
found = True
break
if found:
break
if col==0:
return False
else:
self.cells[row][col] = self.cells[row][col-1]
self.cells[row][col-1] = 0
if visible:
self.updateBoard(row, col-1, row, col)
return True
def displayWin(self, count):
self.t.penup()
outputX = self.posX
outputY = self.posY - 5 *self.SIZE
self.t.goto(outputX, outputY)
self.t.pendown()
self.t.write("Solved in " + str(count) + " moves!", move=False, align="center", font=("Arial", int(0.75*self.SIZE), "normal"))
def updateBoard(self, row1, col1, row2, col2):
self.t.penup()
topLeftX = self.posX + col1*self.SIZE
topLeftY = self.posY - row1*self.SIZE
self.t.goto(topLeftX, topLeftY)
self.t.pendown()
self.drawSquare(self.t, self.SIZE)
self.t.penup()
self.t.right(90)
self.t.forward(self.SIZE)
self.t.left(90)
self.t.forward(self.SIZE/2)
self.t.pendown()
if self.cells[row1][col1] != 0:
self.t.write(self.cells[row1][col1], move=False, align="center", font=("Arial", int(0.75*self.SIZE), "normal"))
self.t.penup()
topLeftX = self.posX + col2*self.SIZE
topLeftY = self.posY - row2*self.SIZE
self.t.goto(topLeftX, topLeftY)
self.t.pendown()
self.drawSquare(self.t, self.SIZE)
self.t.penup()
self.t.right(90)
self.t.forward(self.SIZE)
self.t.left(90)
self.t.forward(self.SIZE/2)
self.t.pendown()
if self.cells[row2][col2] != 0:
self.t.write(self.cells[row2][col2], move=False, align="center", font=("Arial", int(0.75*self.SIZE), "normal"))
self.t.penup()
self.t.goto(0,0)
self.t.pendown()
def drawBoard(self):
for row in range(3):
for col in range(3):
self.t.penup()
topLeftX = self.posX + col*self.SIZE
topLeftY = self.posY - row*self.SIZE
self.t.goto(topLeftX, topLeftY)
self.drawSquare(self.t, self.SIZE)
self.t.penup()
self.t.goto(topLeftX, topLeftY)
self.t.right(90)
self.t.forward(self.SIZE)
self.t.left(90)
self.t.forward(self.SIZE/2)
self.t.pendown()
if self.cells[row][col] != 0:
self.t.write(self.cells[row][col], move=False, align="center", font=("Arial", int(0.75*self.SIZE), "normal"))
self.t.penup()
self.t.goto(0,0)
self.t.pendown()
def play():
p = Puzzle(50, 0, 0, 'blue')
p.shuffle()
while(not p.solvable()):
p.shuffle()
p.display()
p.drawBoard()
prevMove = 1
count = 0
while (not p.isGoal()):
#Create a new puzzle and copy the current state to it
q = Puzzle(30,-200,200, 'red')
#p.display()
for row in range(3):
for col in range(3):
q.cells[row][col] = p.cells[row][col]
# Disable this next line if you don't want to display this board
q.drawBoard()
bestMove = 0
minimum = 1000
validMoves = []
# Try out all possible moves on the new puzzle and choose the one that leads to the lowest utility
# Make the q method calls with False if you don't want to display this board
if q.down(True):
validMoves.append(0)
bestMove = 0
minimum = q.utility()
q.up(True)
if q.right(True):
validMoves.append(1)
if q.utility()<minimum:
minimum = q.utility()
bestMove = 1
q.left(True)
if q.up(True):
validMoves.append(2)
if q.utility()<minimum:
minimum = q.utility()
bestMove = 2
q.down(True)
if q.left(True):
validMoves.append(3)
if q.utility()<minimum:
minimum = q.utility()
bestMove = 3
q.right(True)
# If the best move is the opposite of the one just taken...
if(abs(bestMove - prevMove)==2): #UP and DOWN, LEFT and RIGHT are numbered 2 values apart
#... flip a coin and if it is heads...
r = random.randint(1,2)
#... remove the best move from the list of valid moves...
validMoves.remove(bestMove)
if r == 1:
# Randomly choose one of the other valid moves
index = random.randint(0, len(validMoves)-1)
bestMove = validMoves[index]
# If the coin shows tails, then allow the solver to backtrack over the last move
if bestMove==0:
p.down(True)
print('down',p.utility())
count += 1
elif bestMove==1:
p.right(True)
print('right', p.utility())
count += 1
elif bestMove==2:
p.up(True)
print('up', p.utility())
count += 1
else:
p.left(True)
print('left', p.utility())
count += 1
prevMove = bestMove;
print(count)
print('Solved in ' + str(count) + ' moves')
p.displayWin(count)
#mov = input()
play()
Since graphics are your bottleneck, make sure at runtime, the graphics do as little work as possible. In your code, at runtime, you move the turtle to the correct location, draw a new square with a white interior, adjust the position slightly, and draw a number. Instead, let's leave the grid alone and create a matrix of turtles all at the correct locations to clear and draw a new number:
from turtle import Turtle, Screen
import random
class Puzzle:
def __init__(self, sideLength, x, y, color):
self.cells = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
self.markers = [[None, None, None], [None, None, None], [None, None, None]]
self.t = Turtle(visible=False)
self.s = Screen()
self.s.tracer(False)
self.SIZE = sideLength
self.font = ("Arial", int(0.75 * self.SIZE), "normal")
self.posX, self.posY = x, y
self.t.width = 4
self.t.speed('fastest')
self.t.color(color, 'white')
def drawSquare(self, side):
position = self.t.position()
self.t.pendown()
for _ in range(4):
self.t.forward(side)
self.t.right(90)
self.t.penup()
self.t.goto(position)
self.t.pendown()
def isGoal(self):
temp = []
for row in range(3):
for col in range(3):
temp.append(self.cells[row][col])
if temp[0] == 0:
for i in range(8):
if temp[i] > temp[i + 1]:
return False
return True
if temp[-1] == 0:
for i in range(7):
if temp[i] > temp[i + 1]:
return False
return True
return False
def solvable(self):
temp = []
for row in range(3):
for col in range(3):
temp.append(self.cells[row][col])
inv_count = 0
for i in range(len(temp)):
for j in range(i + 1, len(temp)):
if temp[j] != 0 and temp[i] != 0 and temp[i] > temp[j]:
inv_count += 1
return inv_count % 2 == 0
def shuffle(self):
temp = []
for row in range(3):
for col in range(3):
temp.append(self.cells[row][col])
for i in range(len(temp)):
r = random.randint(0, len(temp) - 1)
t = temp[i]
temp[i] = temp[r]
temp[r] = t
for i in range(len(temp)):
self.cells[i // 3][i % 3] = temp[i]
def utility(self):
manhattan_dist = 0
for row in range(3):
for col in range(3):
tile = self.cells[row][col]
if tile == 0:
continue
finalRow = (tile - 1) // 3
finalCol = (tile - 1) % 3
manhattan_dist += abs(row - finalRow) + abs(col - finalCol)
return manhattan_dist
def display(self):
print(self.cells)
def up(self, visible):
found = False
row, col = 0, 0
for row in range(3):
for col in range(3):
if self.cells[row][col] == 0:
found = True
break
if found:
break
if row == 2:
return False
self.cells[row][col] = self.cells[row + 1][col]
self.cells[row + 1][col] = 0
if visible:
self.updateBoard(row + 1, col, row, col)
return True
def down(self, visible):
found = False
row, col = 0, 0
for row in range(3):
for col in range(3):
if self.cells[row][col] == 0:
found = True
break
if found:
break
if row == 0:
return False
self.cells[row][col] = self.cells[row - 1][col]
self.cells[row-1][col] = 0
if visible:
self.updateBoard(row - 1, col, row, col)
return True
def left(self, visible):
found = False
row, col = 0, 0
for row in range(3):
for col in range(3):
if self.cells[row][col] == 0:
found = True
break
if found:
break
if col == 2:
return False
self.cells[row][col] = self.cells[row][col + 1]
self.cells[row][col + 1] = 0
if visible:
self.updateBoard(row, col + 1, row, col)
return True
def right(self, visible):
found = False
row, col = 0, 0
for row in range(3):
for col in range(3):
if self.cells[row][col] == 0:
found = True
break
if found:
break
if col == 0:
return False
self.cells[row][col] = self.cells[row][col - 1]
self.cells[row][col - 1] = 0
if visible:
self.updateBoard(row, col - 1, row, col)
return True
def displayWin(self, count):
self.t.penup()
outputX = self.posX
outputY = self.posY - 5 * self.SIZE
self.t.goto(outputX, outputY)
self.t.pendown()
self.t.write("Solved in " + str(count) + " moves!", move=False, align="center", font=self.font)
def updateBoard(self, row1, col1, row2, col2):
data = self.cells[row1][col1] or ''
marker = self.markers[row1][col1]
marker.undo()
marker.write(data, align="center", font=self.font)
self.s.update() # don't rely on this happening as a side effect of other turtle functions
data = self.cells[row2][col2] or ''
marker = self.markers[row2][col2]
marker.undo()
marker.write(data, align="center", font=self.font)
self.s.update()
def drawBoard(self):
for row in range(3):
for col in range(3):
self.t.penup()
topLeftX = self.posX + col * self.SIZE
topLeftY = self.posY - row * self.SIZE
self.t.goto(topLeftX, topLeftY)
self.drawSquare(self.SIZE)
self.t.penup()
self.t.goto(topLeftX, topLeftY)
self.t.right(90)
self.t.forward(self.SIZE)
self.t.left(90)
self.t.forward(self.SIZE / 2)
data = self.cells[row][col] if self.cells[row][col] != 0 else ''
marker = self.t.clone()
marker.write(data, align="center", font=self.font)
self.markers[row][col] = marker
self.t.penup()
self.t.goto(0, 0)
self.t.pendown()
def play():
p = Puzzle(50, 0, 0, 'blue')
p.shuffle()
while not p.solvable():
p.shuffle()
p.display()
p.drawBoard()
prevMove = 1
count = 0
q = Puzzle(30, -200, 200, 'red')
q.drawBoard()
while not p.isGoal():
# Copy the current state to new puzzle (probably should be a method)
for row in range(3):
for col in range(3):
q.cells[row][col] = p.cells[row][col]
data = q.cells[row][col] or ''
marker = q.markers[row][col]
marker.undo()
marker.write(data, align="center", font=q.font)
q.s.update()
bestMove = 0
minimum = 1000
validMoves = []
# Try out all possible moves on the new puzzle and choose the one that leads to the lowest utility
# Make the q method calls with False if you don't want to display this board
if q.down(True):
validMoves.append(0)
bestMove = 0
minimum = q.utility()
q.up(True)
if q.right(True):
validMoves.append(1)
if q.utility() < minimum:
minimum = q.utility()
bestMove = 1
q.left(True)
if q.up(True):
validMoves.append(2)
if q.utility() < minimum:
minimum = q.utility()
bestMove = 2
q.down(True)
if q.left(True):
validMoves.append(3)
if q.utility() < minimum:
minimum = q.utility()
bestMove = 3
q.right(True)
# If the best move is the opposite of the one just taken...
if abs(bestMove - prevMove) == 2: # UP and DOWN, LEFT and RIGHT are numbered 2 values apart
#... flip a coin and if it is heads...
r = random.randint(False, True)
#... remove the best move from the list of valid moves...
validMoves.remove(bestMove)
if r:
# Randomly choose one of the other valid moves
index = random.randint(0, len(validMoves) - 1)
bestMove = validMoves[index]
# If the coin shows tails, then allow the solver to backtrack over the last move
if bestMove == 0:
p.down(True)
print('down', p.utility())
count += 1
elif bestMove == 1:
p.right(True)
print('right', p.utility())
count += 1
elif bestMove == 2:
p.up(True)
print('up', p.utility())
count += 1
else:
p.left(True)
print('left', p.utility())
count += 1
prevMove = bestMove
print(count)
print('Solved in ' + str(count) + ' moves')
p.displayWin(count)
play()
I've also done some other code cleanup as well, that may, or may not, affect performance.