stables.py

#!/usr/bin/python3

initial = [-1,1,2,3,4,0,6,7,8,9]


def makenewstable(stable, frm, to):
	newstable = stable[:]
	temp = newstable[to]
	newstable[to] = newstable[frm]
	newstable[frm] = temp
	return newstable

def checkgoal(stable):
	for i in range(1,5):
		if stable[i] < 5:
			return False
	for i in range(6,10):
		if stable[i] > 5:
			return False
	return True

solution = []

def solve(stable, turn):	
	for i in range(1,10):		
		if stable[i] >= 6 and stable[i] <= 9:			
			if i > 2 and stable[i-2] == 0 and stable[i] != i-2:
				newstable1 = makenewstable(stable, i, i-2)
				if checkgoal(newstable1) or solve(newstable1, turn+1):
					print(stable[i], i-2)
					solution.insert(0, stable[i]*10+i-2)
					return True				
			if i > 1 and stable[i-1] == 0 and stable[i] != i-1:
				newstable2 = makenewstable(stable, i, i-1)
				if checkgoal(newstable2) or solve(newstable2, turn+1):
					print(stable[i], i-1)
					solution.insert(0, stable[i]*10+i-1)
					return True				
		elif stable[i] >= 1 and stable[i] <= 4 and turn != 0:
			if i < 8 and stable[i+2] == 0 and stable[i] != i+2:
				newstable3 = makenewstable(stable, i, i+2)
				if checkgoal(newstable3) or solve(newstable3, turn+1):
					print(stable[i], i+2)
					solution.insert(0, stable[i]*10+i+2)
					return True				
			if i < 9 and stable[i+1] == 0 and stable[i] != i+1:
				newstable4 = makenewstable(stable, i, i+1)
				if checkgoal(newstable4) or solve(newstable4, turn+1):
					print(stable[i], i+1)
					solution.insert(0, stable[i]*10+i+1)
					return True
	return False

solve(initial,0)
print(solution)