Game simulator: two teams change seats

gistfile1.py

#!/bin/env python
from turtle import *

N = 5 #how may seats each side

Positions = list(range(N*2+1))

Positions[N] = None #empty place

AllXY = {N:(100,280)}

class Person(object):
	global Positions, AllXY
	def __init__(self, side, idx):
		self.side = side
		self.idx = idx
		if self.side == 1:
			self.pos = self.side*N + 1 + idx
		else:
			self.pos = idx
		Positions[self.pos] = self
		self.tt = Turtle()
		if side == 0:
			self.tt.penup()
			self.tt.shape('square')
			self.tt.goto(0, 50* idx)
			AllXY[self.pos] = (0, 50*idx)
		elif side == 1:
			self.tt.penup()
			self.tt.color('red')
			self.tt.shape('circle')
			self.tt.goto(200,50*(N-1-idx))
			AllXY[self.pos] = (200, 50*(N-1-idx))

	def goto(self, x, y):
		self.tt.goto(x,y)

	def __repr__(self):
		return str((self.side, self.idx))

	def try_forward(self):
		maybe_pos = None
		if self.side == 0:
			if self.pos+1<len(Positions) and Positions[self.pos + 1] == None:
				maybe_pos = self.pos + 1
			elif self.pos+2<len(Positions) and Positions[self.pos + 2] == None:
				maybe_pos = self.pos + 2
		elif self.side == 1:
			if self.pos-1>=0 and Positions[self.pos-1] == None:
				maybe_pos = self.pos - 1
			elif self.pos-2>=0 and Positions[self.pos -2] == None:
				maybe_pos = self.pos - 2
		return maybe_pos

	def forward(self, new_pos):
		old_pos = self.pos
		self.pos = new_pos
		Positions[old_pos] = None
		Positions[new_pos] =  self		
		return old_pos

def is_found():
	s = sum([p.side for p in Positions[:N] if p!=None])		
	if s == N and Positions[N] == None:
		return True
	return False

def dfs(path):
	#print(Positions)
	if is_found():
		return True
	for person in Positions:
		if person == None:
			continue
		maybe_pos = person.try_forward()
		if maybe_pos != None:
			print("maybe", person, maybe_pos)
			path.append((person, maybe_pos))
			#print(path)
			old_pos = person.forward(maybe_pos)
			fixed = dfs(path)
			if not fixed:
				person.forward(old_pos)	
				del path[-1]
			else:
				return True
	return False

if __name__ == "__main__":
	for i in range(N):
		Person(0,i)
		Person(1,i)
	path = []
	print(Positions)
	dfs(path)
	print(Positions)
	print(len(path), path)
	print(AllXY)
	for person, pos in path:
		x, y = AllXY[pos]
		person.tt.speed(1)
		person.goto(x,y)
	
	mainloop()