eightSolver.py

class Game:
    def __init__(self,arr):
        self.arr=arr
        self.history=[]
    def isGameOver(self):
        i=0
        for line in self.arr:
            for number in line:
                i+=1
                if number!=i:
                    return False
        return True
    def getXY(self,i):
        for y,line in enumerate(self.arr):
            for x,c in enumerate(line):
                if c==i:
                    return (x,y)
        return None
    def getAllPossibilities(self):
        ret=[]
        x,y=self.getXY(9)
        allTuples=((x+1,y),(x-1,y),(x,y+1),(x,y-1))
        for t in allTuples:
            if (3 > t[0] > -1) and (3 > t[1] > -1):
                ret.append(self.arr[t[1]][t[0]])
        return ret
    def play(self,i):
        x,y=self.getXY(9)
        allTuples=((x+1,y),(x-1,y),(x,y+1),(x,y-1))
        for t in allTuples:
            if (t[0]<0) or (t[0]>2) or (t[1]<0) or (t[1]>2):
                continue
            if self.arr[t[1]][t[0]]==i:
                self.arr[t[1]][t[0]]=9
                self.arr[y][x]=i
                self.history.append(i)
                return
    def unplay(self):
        self.play(self.history[-1])
        self.history.pop()
        self.history.pop()

def solve (game, steps):
    #print("solve("+str(id(game))+','+str(steps)+')')
    if game.isGameOver():
        return game
    if steps==0:
        return None
    for p in game.getAllPossibilities():
        if len(game.history):
            if p==game.history[-1]:
                continue
        game.play(p)
        g2=solve(game,steps-1)
        if g2:
            return g2
        else:
            game.unplay()
    return None

def main():
    arr=[]
    for _ in range(3):
        s=input()
        l=[]
        arr.append(l)
        for c in s:
            if c==" ":
                l.append(9)
            else:
                l.append(int(c))
    game=Game(arr)
    game=solve(game,81)
    if game:
        print(game.history)
    else:
        print("Impossible")

main()