Develop a typing game to improve keyboard skill as demonstrated in the following YouTube video.
At any moment ten random letters fall from the top of screen. When you hit a correct letter from keyboard, that letter disappears and is replaced by a new random letter dropping from the top. Also, your score will increase by 1. When you hit an incorrect letter, your score will decrease by 1.
Make these letters fall at random speeds and also let the speed increase gradually as time progresses. The game will end when a letter falls to the bottom of the screen.
You will need to use Turtle’s ontimer() and onkey() events to implement this project.
Source Code:
import turtle
import random
screen = turtle.Screen()
screen.setup(1000,1000)
screen.title('Typing Game - PythonTurtle.Academy')
screen.bgcolor('blue')
screen.tracer(0,0)
turtle.hideturtle()
turtle.up()
turtle.color('red')
score_turtle = turtle.Turtle()
score_turtle.color('red')
score_turtle.up()
score_turtle.hideturtle()
turtle.goto(350,400)
turtle.write('Score: ', align='center', font=('Courier',25,'normal'))
min_speed = 5
max_speed = 30
letters = []
speeds = []
pos = []
lts = []
n = 10
game_over = False
score = 0
def increase_difficulty():
global min_speed, max_speed
min_speed += 1
max_speed += 1
screen.ontimer(increase_difficulty,5000)
def draw_game_over():
turtle.goto(0,0)
turtle.color('red')
turtle.write('GAME OVER', align='center', font=('Courier',50,'normal'))
turtle.goto(0,-150)
turtle.color('orange')
turtle.write('Your Score is {}'.format(score), align='center', font=('Courier',40,'normal'))
screen.update()
def draw_score():
score_turtle.clear()
score_turtle.goto(420,400)
score_turtle.write('{}'.format(score),align='center',font=('Courier',25,'normal'))
screen.update()
def draw_letters():
global game_over
for i in range(len(letters)):
lts[i].clear()
lts[i].goto(pos[i])
lts[i].write(letters[i],align='center',font=('courier',20,'normal'))
pos[i][1] -= speeds[i]
if pos[i][1]<-500:
game_over = True
draw_game_over()
return
screen.update()
screen.ontimer(draw_letters,50)
def f(c): # handle keyboard press
global score
if c in letters:
score += 1
k = letters.index(c)
while True:
l = chr(ord('a')+random.randrange(26))
if l not in letters:
letters[k] = l
break
pos[k] = [random.randint(-450,450),500]
speeds[k] = random.randint(min_speed,max_speed)
else: score -= 1
draw_score()
for _ in range(n):
lts.append(turtle.Turtle())
while True:
l = chr(ord('a')+random.randrange(26))
if l not in letters:
letters.append(l)
break
speeds.append(random.randint(min_speed,max_speed))
pos.append([random.randint(-450,450),500])
for i in range(n):
lts[i].speed(0)
lts[i].hideturtle()
lts[i].up()
lts[i].color('yellow')
draw_letters()
increase_difficulty()
screen.onkey(lambda: f('a'), 'a')
screen.onkey(lambda: f('b'), 'b')
screen.onkey(lambda: f('c'), 'c')
screen.onkey(lambda: f('d'), 'd')
screen.onkey(lambda: f('e'), 'e')
screen.onkey(lambda: f('f'), 'f')
screen.onkey(lambda: f('g'), 'g')
screen.onkey(lambda: f('h'), 'h')
screen.onkey(lambda: f('i'), 'i')
screen.onkey(lambda: f('j'), 'j')
screen.onkey(lambda: f('k'), 'k')
screen.onkey(lambda: f('l'), 'l')
screen.onkey(lambda: f('m'), 'm')
screen.onkey(lambda: f('n'), 'n')
screen.onkey(lambda: f('o'), 'o')
screen.onkey(lambda: f('p'), 'p')
screen.onkey(lambda: f('q'), 'q')
screen.onkey(lambda: f('r'), 'r')
screen.onkey(lambda: f('s'), 's')
screen.onkey(lambda: f('t'), 't')
screen.onkey(lambda: f('u'), 'u')
screen.onkey(lambda: f('v'), 'v')
screen.onkey(lambda: f('w'), 'w')
screen.onkey(lambda: f('x'), 'x')
screen.onkey(lambda: f('y'), 'y')
screen.onkey(lambda: f('z'), 'z')
screen.listen()
screen.mainloop()
Use minimax tree search algorithm with alpha-beta pruning to write AI Tic-Tac-Toe player. You may also want to add randomness to your AI player so that it won’t play the same move every time. Here is more detail information on minimax tree and alpha-beta pruning. Your program should play against a human player. Therefore, you need to use onclick() function to handle mouse click events.
Source Code:
import turtle
import copy
import random
screen = turtle.Screen()
screen.setup(800,800)
screen.title("Tic Tac Toe - PythonTurtle.Academy")
screen.setworldcoordinates(-5,-5,5,5)
screen.bgcolor('light gray')
screen.tracer(0,0)
turtle.hideturtle()
def draw_board():
turtle.pencolor('green')
turtle.pensize(10)
turtle.up()
turtle.goto(-3,-1)
turtle.seth(0)
turtle.down()
turtle.fd(6)
turtle.up()
turtle.goto(-3,1)
turtle.seth(0)
turtle.down()
turtle.fd(6)
turtle.up()
turtle.goto(-1,-3)
turtle.seth(90)
turtle.down()
turtle.fd(6)
turtle.up()
turtle.goto(1,-3)
turtle.seth(90)
turtle.down()
turtle.fd(6)
def draw_circle(x,y):
turtle.up()
turtle.goto(x,y-0.75)
turtle.seth(0)
turtle.color('red')
turtle.down()
turtle.circle(0.75, steps=100)
def draw_x(x,y):
turtle.color('blue')
turtle.up()
turtle.goto(x-0.75,y-0.75)
turtle.down()
turtle.goto(x+0.75,y+0.75)
turtle.up()
turtle.goto(x-0.75,y+0.75)
turtle.down()
turtle.goto(x+0.75,y-0.75)
def draw_piece(i,j,p):
if p==0: return
x,y = 2*(j-1), -2*(i-1)
if p==1:
draw_x(x,y)
else:
draw_circle(x,y)
def draw(b):
draw_board()
for i in range(3):
for j in range(3):
draw_piece(i,j,b[i][j])
screen.update()
# return 1 if player 1 wins, 2 if player 2 wins, 3 if tie, 0 if game is not over
def gameover(b):
if b[0][0]>0 and b[0][0] == b[0][1] and b[0][1] == b[0][2]: return b[0][0]
if b[1][0]>0 and b[1][0] == b[1][1] and b[1][1] == b[1][2]: return b[1][0]
if b[2][0]>0 and b[2][0] == b[2][1] and b[2][1] == b[2][2]: return b[2][0]
if b[0][0]>0 and b[0][0] == b[1][0] and b[1][0] == b[2][0]: return b[0][0]
if b[0][1]>0 and b[0][1] == b[1][1] and b[1][1] == b[2][1]: return b[0][1]
if b[0][2]>0 and b[0][2] == b[1][2] and b[1][2] == b[2][2]: return b[0][2]
if b[0][0]>0 and b[0][0] == b[1][1] and b[1][1] == b[2][2]: return b[0][0]
if b[2][0]>0 and b[2][0] == b[1][1] and b[1][1] == b[0][2]: return b[2][0]
p = 0
for i in range(3):
for j in range(3):
p += (1 if b[i][j] > 0 else 0)
if p==9: return 3
else: return 0
def play(x,y):
global turn
if turn=='x': return
i = 3-int(y+5)//2
j = int(x+5)//2 - 1
if i>2 or j>2 or i<0 or j<0 or b[i][j]!=0: return
if turn == 'x': b[i][j], turn = 1, 'o'
else: b[i][j], turn = 2, 'x'
draw(b)
r = gameover(b)
if r==1:
screen.textinput("Game over!","X won!")
elif r==2:
screen.textinput("Game over!","O won!")
elif r==3:
screen.textinput("Game over!", "Tie!")
if r>0: turtle.bye()
_,move = max_node(b,-2,2)
b[move[0]][move[1]] = 1
draw(b)
r = gameover(b)
if r==1:
screen.textinput("Game over!","X won!")
elif r==2:
screen.textinput("Game over!","O won!")
elif r==3:
screen.textinput("Game over!", "Tie!")
if r>0: turtle.bye()
turn = 'o'
b = [ [ 0,0,0 ], [ 0,0,0 ], [ 0,0,0 ] ]
draw(b)
turn = 'x'
screen.onclick(play)
#turtle.mainloop()
def max_node(b,alpha,beta):
r = gameover(b)
if r==1: return 1,None
elif r==2: return -1,None
elif r==3: return 0,None
score = -2
# find all possible next moves
pm = list()
for i in range(3):
for j in range(3):
if b[i][j] == 0: pm.append((i,j))
random.shuffle(pm)
for (i,j) in pm:
if b[i][j] == 0:
nb = copy.deepcopy(b)
nb[i][j] = 1
cs,_ = min_node(nb,alpha,beta)
if score<cs:
score=cs
move = (i,j)
alpha = max(alpha,cs)
if alpha>=beta: return score,move
return score,move
def min_node(b,alpha,beta):
r = gameover(b)
if r==1: return 1,None
elif r==2: return -1,None
elif r==3: return 0,None
score = 2
# find all possible next moves
pm = list()
random.shuffle(pm)
for i in range(3):
for j in range(3):
if b[i][j] == 0: pm.append((i,j))
for (i,j) in pm:
if b[i][j] == 0:
nb = copy.deepcopy(b)
nb[i][j] = 2
cs,_ = max_node(nb,alpha,beta)
if score>cs:
score=cs
move = (i,j)
beta = min(beta,cs)
if alpha>=beta: return score,move
return score,move
_,move = max_node(b,-2,2)
b[move[0]][move[1]] = 1
draw(b)
turn = 1
screen.mainloop()
Write a connect 4 program with Python and Turtle graphics. Your game should be able to let two human players play against each other and declare winner or tie when the game ends. You need to use onclick() event to handle the mouse click.
Source Code:
import turtle
import time
screen = turtle.Screen()
screen.setup(800,800)
screen.setworldcoordinates(-500,-500,500,500)
screen.title("Connect 4 - PythonTurtle.Academy")
turtle.speed(0)
turtle.hideturtle()
screen.tracer(0,0)
score = turtle.Turtle()
score.up()
score.hideturtle()
ROWS = 6
COLS = 7
STARTX = -450
STARTY = -450*ROWS/COLS
WIDTH = -2*STARTX
HEIGHT = -2*STARTY
def draw_rectangle(x,y,w,h,color):
turtle.up()
turtle.goto(x,y)
turtle.seth(0)
turtle.down()
turtle.fillcolor(color)
turtle.begin_fill()
turtle.fd(w)
turtle.left(90)
turtle.fd(h)
turtle.left(90)
turtle.fd(w)
turtle.left(90)
turtle.fd(h)
turtle.left(90)
turtle.end_fill()
def draw_circle(x,y,r,color):
turtle.up()
turtle.goto(x,y-r)
turtle.seth(0)
turtle.down()
turtle.fillcolor(color)
turtle.begin_fill()
turtle.circle(r,360,150)
turtle.end_fill()
def draw_board():
draw_rectangle(STARTX,STARTY,WIDTH,HEIGHT,'light blue')
def draw_pieces():
global board
row_gap = HEIGHT/ROWS
col_gap = WIDTH/COLS
Y = STARTY + row_gap / 2;
for i in range(ROWS):
X = STARTX + col_gap/2
for j in range(COLS):
if board[i][j] == 0:
draw_circle(X,Y,row_gap/3,'white')
elif board[i][j] == 1:
draw_circle(X,Y,row_gap/3,'black')
else:
draw_circle(X,Y,row_gap/3,'red')
X += col_gap
Y += row_gap
def draw():
draw_board()
draw_pieces()
screen.update()
def game_over_lastmove(bb,turn,r,c):
# check horizontals
cnt = 1
i = c+1
while i<COLS and bb[r][i]==turn: cnt, i = cnt+1, i+1
i = c-1
while i>=0 and bb[r][i]==turn: cnt, i = cnt+1, i-1
if cnt>=4: return turn
# check vertical
if r>=3 and bb[r-1][c]==turn and bb[r-2][c]==turn and bb[r-3][c]==turn: return turn
# check diag 2
cnt = 1
i = 1
while r+i<ROWS and c+i<COLS and bb[r+i][c+i]==turn: cnt, i = cnt+1, i+1
i = -1
while r+i>=0 and c+i>=0 and bb[r+i][c+i]==turn: cnt, i = cnt+1, i-1
if cnt>=4: return turn
# check diag 1
cnt = 1
i = 1
while r+i<ROWS and c-i>=0 and bb[r+i][c-i]==turn: cnt, i = cnt+1, i+1
i = -1
while r+i>=0 and c-i<COLS and bb[r+i][c-i]==turn: cnt, i = cnt+1, i-1
if cnt>=4: return turn
for i in range(COLS):
if bb[ROWS-1][i] == 0:
return -2
return 0
# place piece in col for turn
def place_piece(bb,turn,col):
for i in range(ROWS):
if bb[i][col] == 0:
bb[i][col] = turn
return i
def init_board():
global board
for i in range(ROWS):
row = []
for j in range(COLS):
row.append(0)
board.append(row)
def place_piece_and_draw(bb,turn,col):
row = place_piece(bb,turn,col)
row_gap = HEIGHT/ROWS
col_gap = WIDTH/COLS
Y = STARTY + row_gap*row + row_gap / 2;
X = STARTX + col_gap*col + col_gap/2
i = row
j = col
if board[i][j] == 0:
draw_circle(X,Y,row_gap/3,'white')
elif board[i][j] == 1:
for k in range(5):
draw_circle(X,Y,row_gap/3,'white')
screen.update()
time.sleep(0.05)
draw_circle(X,Y,row_gap/3,'black')
screen.update()
time.sleep(0.05)
else:
for k in range(5):
draw_circle(X,Y,row_gap/3,'white')
screen.update()
time.sleep(0.05)
draw_circle(X,Y,row_gap/3,'red')
screen.update()
time.sleep(0.05)
return row
def play(x,y):
global turn,working
if working: return
working = True
cols = [ 900/7*i-450+900/14 for i in range(7) ]
for i in range(len(cols)):
if abs(x-cols[i]) < 900/14*2/3 and board[ROWS-1][i]==0:
rn = place_piece_and_draw(board,turn,i)
r = game_over_lastmove(board,turn,rn,i)
if r==0:
screen.textinput('Game over','tie')
elif r==1:
screen.textinput('Game over','player 1 won')
elif r==-1:
screen.textinput('Game over','player 2 won')
if r!=-2: screen.bye()
turn = -turn
working = False
board = []
init_board()
draw_board()
draw_pieces()
turn=1
working=False
screen.onclick(play)
screen.mainloop()
Game of SIM was invented in 1969 by Gustavus Simmons. In this two player (red and blue) game, each player takes turn to connect two vertices of a hexagon with the player’s color (either red or blue). The first player who draws all three sides of the triangle with the player’s color loses the game. There is always a winner for this game.
Write a Game of SIM with Python and Turtle graphics. Your game should be able to declare the winner when the game ends. You will need to use onclick() even of Turtle graphics.
Source Code:
import turtle
import math
screen = turtle.Screen()
screen.setup(800,800)
screen.title("Game of SIM - PythonTurtle.Academy")
screen.setworldcoordinates(-1.5,-1.5,1.5,1.5)
screen.tracer(0,0)
turtle.hideturtle()
def draw_dot(x,y,color):
turtle.up()
turtle.goto(x,y)
turtle.color(color)
turtle.dot(15)
def gen_dots():
r = []
for angle in range(0,360,60):
r.append((math.cos(math.radians(angle)),math.sin(math.radians(angle))))
return r
def draw_line(p1,p2,color):
turtle.up()
turtle.pensize(3)
turtle.goto(p1)
turtle.down()
turtle.color(color)
turtle.goto(p2)
def draw_board():
global selection
for i in range(len(dots)):
if i in selection: draw_dot(dots[i][0],dots[i][1],turn)
else: draw_dot(dots[i][0],dots[i][1],'dark gray')
def draw():
draw_board()
for i in range(len(red)):
draw_line((math.cos(math.radians(red[i][0]*60)),math.sin(math.radians(red[i][0]*60))),\
(math.cos(math.radians(red[i][1]*60)),math.sin(math.radians(red[i][1]*60))),\
'red')
for i in range(len(blue)):
draw_line((math.cos(math.radians(blue[i][0]*60)),math.sin(math.radians(blue[i][0]*60))),\
(math.cos(math.radians(blue[i][1]*60)),math.sin(math.radians(blue[i][1]*60))),\
'blue')
screen.update()
def play(x,y):
global selection,turn,red,blue
for i in range(len(dots)):
dist = (dots[i][0]-x)**2 + (dots[i][1]-y)**2
if dist<0.001:
if i in selection: selection.remove(i)
else: selection.append(i)
break
if len(selection)==2:
selection=(min(selection),max(selection))
if selection not in red and selection not in blue:
if turn=='red':
red.append(selection)
else:
blue.append(selection)
turn = 'red' if turn=='blue' else 'blue'
selection = []
draw()
r = gameover(red,blue)
if r!=0:
screen.textinput('game over',r+' won!')
turtle.bye()
def gameover(r,b):
if len(r)<3: return 0
r.sort()
for i in range(len(r)-2):
for j in range(i+1,len(r)-1):
for k in range(j+1,len(r)):
if r[i][0]==r[j][0] and r[i][1]==r[k][0] and r[j][1]==r[k][1]: return 'blue'
if len(b)<3: return 0
b.sort()
for i in range(len(b)-2):
for j in range(i+1,len(b)-1):
for k in range(j+1,len(b)):
if b[i][0]==b[j][0] and b[i][1]==b[k][0] and b[j][1]==b[k][1]: return 'red'
return 0
selection = []
turn = 'red'
dots = gen_dots()
red = [ ]
blue = [ ]
draw()
screen.onclick(play)
turtle.mainloop()
Design a two player tic-tac-toe game with Python Turtle. You will need to use onclick() event to let two human players play against each other.
Source Code:
import turtle
screen = turtle.Screen()
screen.setup(800,800)
screen.title("Tic Tac Toe - PythonTurtle.Academy")
screen.setworldcoordinates(-5,-5,5,5)
screen.bgcolor('light gray')
screen.tracer(0,0)
turtle.hideturtle()
def draw_board():
turtle.pencolor('green')
turtle.pensize(10)
turtle.up()
turtle.goto(-3,-1)
turtle.seth(0)
turtle.down()
turtle.fd(6)
turtle.up()
turtle.goto(-3,1)
turtle.seth(0)
turtle.down()
turtle.fd(6)
turtle.up()
turtle.goto(-1,-3)
turtle.seth(90)
turtle.down()
turtle.fd(6)
turtle.up()
turtle.goto(1,-3)
turtle.seth(90)
turtle.down()
turtle.fd(6)
def draw_circle(x,y):
turtle.up()
turtle.goto(x,y-0.75)
turtle.seth(0)
turtle.color('red')
turtle.down()
turtle.circle(0.75, steps=100)
def draw_x(x,y):
turtle.color('blue')
turtle.up()
turtle.goto(x-0.75,y-0.75)
turtle.down()
turtle.goto(x+0.75,y+0.75)
turtle.up()
turtle.goto(x-0.75,y+0.75)
turtle.down()
turtle.goto(x+0.75,y-0.75)
def draw_piece(i,j,p):
if p==0: return
x,y = 2*(j-1), -2*(i-1)
if p==1:
draw_x(x,y)
else:
draw_circle(x,y)
def draw(b):
draw_board()
for i in range(3):
for j in range(3):
draw_piece(i,j,b[i][j])
screen.update()
# return 1 if player 1 wins, 2 if player 2 wins, 3 if tie, 0 if game is not over
def gameover(b):
if b[0][0]>0 and b[0][0] == b[0][1] and b[0][1] == b[0][2]: return b[0][0]
if b[1][0]>0 and b[1][0] == b[1][1] and b[1][1] == b[1][2]: return b[1][0]
if b[2][0]>0 and b[2][0] == b[2][1] and b[2][1] == b[2][2]: return b[2][0]
if b[0][0]>0 and b[0][0] == b[1][0] and b[1][0] == b[2][0]: return b[0][0]
if b[0][1]>0 and b[0][1] == b[1][1] and b[1][1] == b[2][1]: return b[0][1]
if b[0][2]>0 and b[0][2] == b[1][2] and b[1][2] == b[2][2]: return b[0][2]
if b[0][0]>0 and b[0][0] == b[1][1] and b[1][1] == b[2][2]: return b[0][0]
if b[2][0]>0 and b[2][0] == b[1][1] and b[1][1] == b[0][2]: return b[2][0]
p = 0
for i in range(3):
for j in range(3):
p += (1 if b[i][j] > 0 else 0)
if p==9: return 3
else: return 0
def play(x,y):
global turn
i = 3-int(y+5)//2
j = int(x+5)//2 - 1
if i>2 or j>2 or i<0 or j<0 or b[i][j]!=0: return
if turn == 'x': b[i][j], turn = 1, 'o'
else: b[i][j], turn = 2, 'x'
draw(b)
r = gameover(b)
if r==1:
screen.textinput("Game over!","X won!")
elif r==2:
screen.textinput("Game over!","O won!")
elif r==3:
screen.textinput("Game over!", "Tie!")
b = [ [ 0,0,0 ], [ 0,0,0 ], [ 0,0,0 ] ]
draw(b)
turn = 'x'
screen.onclick(play)
turtle.mainloop()
Write a program that animates the move of a knight in a chess board from any source to any destination with the minimum number of steps. You may need to use Breadth First Search (BFS) with Queue data structure.
Source Code:
import turtle
import time
import sys
turtle.setup(800,800)
turtle.setworldcoordinates(-250,-250,250,250)
turtle.title("Knight's Minimum Moves - PythonTurtle.Academy")
def draw_square(x,y,size,color):
turtle.up()
turtle.goto(x,y)
turtle.seth(0)
turtle.down()
turtle.begin_fill()
turtle.fillcolor(color)
for i in range(4):
turtle.fd(size)
turtle.left(90)
turtle.end_fill()
def draw_board(src=(-2,-2),dest=(-2,-2), mlist=[]):
turtle.pencolor("black")
y = -200
piecesize = 50
startpiececolor = "darkgray"
for i in range(8):
x = -200
piececolor = startpiececolor
for j in range(8):
if (j+1,i+1)==src:
draw_square(x,y,piecesize,'light blue')
elif (j+1,i+1)==dest:
draw_square(x,y,piecesize,'pink')
elif (j+1,i+1) in mlist:
draw_square(x,y,piecesize,'light green')
else:
draw_square(x,y,piecesize,piececolor)
x += piecesize
if piececolor == "darkgray":
piececolor = "lightgray"
else:
piececolor = "darkgray"
y += piecesize
if startpiececolor == "darkgray":
startpiececolor = "lightgray"
else:
startpiececolor = "darkgray"
def draw_knight(pos):
xpos = 50*(pos[0]-1) - 175
ypos = 50*(pos[1]-1) - 195
turtle.up()
turtle.goto(xpos,ypos)
turtle.write('\u265e',align='center',font=('Arial',40,'normal'))
class node:
def __init__(self,val,nxt=None):
self.value=val
self.next=nxt
class LinkedList:
def __init__(self,it=None):
self.head = None
self.tail = None
self.length = 0
if it is None: return
for x in it:
self.insert_at_tail(x)
def insert_at_head(self,k):
if self.head is None:
self.head = node(k)
self.tail = self.head
else:
p = node(k,self.head)
self.head = p
self.length += 1
def insert_after(self,p,k):
if self.length < p or p < 0:
raise Exception('Linked List doesn\'t have position '+str(p))
if p==0:
self.insert_at_head(k)
return
q = self.head
for _ in range(p-1):
q = q.next
q.next = node(k,q.next)
def insert_at_tail(self,k):
if self.tail is None:
self.head = node(k)
self.tail = self.head
else:
self.tail.next = node(k)
self.tail = self.tail.next
self.length += 1
def __iter__(self):
p = self.head
while p is not None:
yield p.value
p = p.next
def __len__(self):
return self.length
def __str__(self):
s = ""
p = self.head
while p is not None:
s += str(p.value) + '->'
p = p.next
s += 'None'
return s
def delete_from_head(self):
if self.head is None: return
self.length -= 1
self.head = self.head.next
if self.head is None:
self.tail = None
def delete_from_tail(self):
if self.head is None: return
self.length -= 1
if self.head == self.tail: self.head = self.tail = None
p = self.head
while p.next != self.tail:
p = p.next
p.next = None
self.tail = p
class Queue:
def __init__(self):
self.ll = LinkedList()
self.length = len(self.ll)
def push(self,k):
self.ll.insert_at_tail(k)
def pop(self):
if len(self.ll)==0:
raise Exception('Queue is empty')
self.ll.delete_from_head()
def top(self):
if len(self.ll)==0:
raise Exception('Queue is empty')
return self.ll.head.value;
def empty(self):
return len(self.ll)==0
def __len__(self):
return len(self.ll)
class position:
def __init__(self,pos,dist,parent):
self.pos = pos
self.dist = dist
self.parent = parent
moves = [ (1,2), (1,-2), (-1,2),(-1,-2), (2,-1), (2,1), (-2,1), (-2,-1) ]
def valid_position(pos):
if pos[0] < 1 or pos[0] > 8 or pos[1] < 1 or pos[1] > 8: return False
return True
def minimum_knight_move(src, dest):
q = Queue()
s = set()
q.push(position(src,0,None))
s.add(src)
while not q.empty():
current = q.top()
pos = current.pos
dist = current.dist
q.pop()
# try all possible moves from here
for m in moves:
new_pos = (pos[0]+m[0],pos[1]+m[1])
if valid_position(new_pos) and new_pos not in s:
if new_pos == dest: return current
s.add(new_pos)
q.push(position(new_pos,dist+1,current))
return -1
if __name__=='__main__':
turtle.speed(0)
turtle.hideturtle()
turtle.tracer(0)
while True:
turtle.clear()
draw_board()
src = (-1,-1)
dest = (-1,-1)
while src[0] < 0 or src[0] > 8 or src[1] < 0 or src[1] > 8:
srctext=turtle.textinput("Begin Position","Please enter the starting position (e.g. 2 4):")
if srctext is None: sys.exit(0)
try:
src = tuple(map(int,srctext.split()))
except:
src = (-1,-1)
draw_board(src)
draw_knight(src)
while dest[0] < 0 or dest[0] > 8 or dest[1] < 0 or dest[1] > 8:
desttext=turtle.textinput("End Position","Please enter the target position (e.g. 8 5):")
if desttext is None: sys.exit(0)
try:
dest = tuple(map(int,desttext.split()))
except:
dest = (-1,-1)
draw_board(src,dest)
draw_knight(dest)
current = minimum_knight_move(src,dest)
s = LinkedList()
s.insert_at_head(dest)
mlist = list()
while current is not None:
s.insert_at_head(current.pos)
current = current.parent
for pos in s:
turtle.clear()
mlist.append(pos)
draw_board(src,dest,mlist)
draw_knight(pos)
time.sleep(1)
turtle.update()