speeding up help.. probably deepcopy()...

[eugene kim]

http://gotofreegames.com/IQGame/free_peg_game.htm

i am trying to make a program to solve the game in above page.
It works fine.. but it's still finding solutions with 45 mins run time.
lol

and i have newbie question ..
is always pass by reference in python?
(in java, it's always pass by value..afaik)
It seems like scoping rules changed with new python.


thank you
--
I store 14balls information and pass it as I move one ball until there's no 
possible move
--

#!/usr/local/bin/python

import copy

class Ball:
    def __init__(self):
        self.a = None
        self.b = None
        self.c = None
        self.d = None
        self.e = None
        self.f = None
        self.adjacent_balls = []
        self.empty = 0

    def __repr__(self):
        result = ""
        for adjacent_ball in self.adjacent_balls:
            if adjacent_ball == None or adjacent_ball.empty:
                result = result + "0"
            else:
                result = result + "1"

        return result
                
    def assign(self, a = None, b= None,c=None,d=None,e=None,f=None):
        self.a =a
        self.b =b
        self.c =c
        self.d =d
        self.e =e
        self.f =f
        self.adjacent_balls = [self.a,self.b,self.c,self.d,self.e,self.f]


balls = []
for i in range(15):
    tmp_ball = Ball()
    exec "balls.append(tmp_ball)"

balls[0].assign(e=balls[2], f= balls[1])
balls[1].assign(c=balls[0], d=balls[2],e=balls[4],f=balls[3])
balls[2].assign(a=balls[1], b=balls[0], e=balls[5], f=balls[4])
balls[3].assign(c=balls[1], d=balls[4], e=balls[7], f=balls[6])
balls[4].assign(a=balls[3], b=balls[1], c=balls[2], d=balls[5], e=balls[8], 
f=balls[7])
balls[5].assign(a=balls[4],b=balls[2], e=balls[9], f=balls[8])
balls[6].assign(c=balls[3], d=balls[7], e=balls[11], f=balls[10])
balls[7].assign(balls[6], balls[3], balls[4], balls[8], balls[12], 
balls[11])
balls[8].assign(balls[7], balls[4], balls[5], balls[9], balls[13], 
balls[12])
balls[9].assign(a=balls[8], b= balls[5], e=balls[14], f=balls[13])

balls[10].assign(None, None, balls[6], balls[11], None,None)
balls[11].assign(balls[10],balls[6],balls[7], balls[12], None, None)
balls[12].assign(balls[11], balls[7], balls[8], balls[13], None, None)
balls[13].assign(balls[12], balls[8], balls[9], balls[14], None, None)
balls[14].assign(balls[13], balls[9], None, None, None, None)

balls[8].empty = 1

def find(tmp_balls):


    sol = []
    human_sol = []
    for i in range(len(tmp_balls)):
        tmp_balls2 = copy.deepcopy(tmp_balls)
        ball = tmp_balls2[i]
        for j in range(len(ball.adjacent_balls)):
            adjacent_ball = ball.adjacent_balls[j]
            if (not ball.empty) and adjacent_ball != None and (not 
adjacent_ball.empty) and adjacent_ball.adjacent_balls[j] != None and 
adjacent_ball.adjacent_balls[j].empty:

                ball.empty = 1
                adjacent_ball.empty=1
                adjacent_ball.adjacent_balls[j].empty = 0

                sol.append(tmp_balls2)
                one_human_sol = []
                one_human_sol.append(i)
                one_human_sol.append(j)
                human_sol.append(one_human_sol)


    return [sol,human_sol]

next_balls = find(balls)

sol_count = 0

def func(next_balls, path):
    balls = next_balls[0]
    human_sol = next_balls[1]
    for i in range(len(balls)):
        aState = balls[i]
        aHSol = human_sol[i]

        next_balls = find(aState)
        if len(next_balls[0]) == 0:
            global sol_count
            sol_count = sol_count + 1
            count = 0
            for ball in aState :
                if not ball.empty:
                    count = count +1
            if count == 1:
                print aState, count
                print
                print path + [aHSol]
                print
        else:
            func(next_balls, path+[aHSol])

            
func(next_balls, [])            
        

print "# of solution with 1 left:", sol_count