kenken solver, python

Question

I have written a series of functions to solve kenkens. The general strategy is to eliminate possibilities until only one remains for each cell. This first function eliminates all possibilities that can't be used to satisfy the operation and target constraints.

I'm interested in any feedback concerning style and efficiency.

from itertools import product
from itertools import combinations

#set size of square board
side = 9

#each cell of the grid is identified by an index        
indices = [i for i in range(side*side)]

#each cell is located in a row and in a column
addresses = []
index2row = []
index2column = []
for x in range(side):
    for y in range(side):
        addresses.append([x,y])
        index2row.append(x)
        index2column.append(y)

#each row and column is a list of indices
rows = []
a = 0
b = side
for r in range(side):
    row = []
    for i in indices[a:b]:
        row.append(i)
    rows.append(row)
    a = b
    b = b+side

columns = []
for c in range(side):
    column = []
    a = c
    for i in range(side):
        column.append(a)
        a = a + side
    columns.append(column)

#initially each cell can be any number from 1 to the number side
possibilities = []
for i in range(side*side):
    lp = []
    for n in range(1, side+1):
        lp.append(n)
    possibilities.append(lp)

#initially the solution for each cell is set at 0
values = [0 for i in range(side * side)]



##define Cage class
class Cage:
    def __init__(self, indexes, operation, target):

        self.indexes = indexes #cells in cage
        self.operation = operation #arithmetic operation
        self.target = target #result of operation e.g. 2 by division


##operation functions       
def multiplication(combination):
    result = 1
    for n in combination:
        result = result*n
    return(result)

def subtraction(pair):
    return(abs(pair[0] - pair[1]))

def division(pair):
    return(max([pair[0]/pair[1], pair[1]/pair[0]]))

def addition(combination):
    return(sum(combination))

def equals(combination):
    return(combination[0])

#sample puzzle, indices, operations and targets for each cage
indexes = [[0,1,9,10],[2,3],[4,12,13],[5,14],[6,7],[8,17,26],[11,20],[15,24],[16,25],[18,27,36,45],
           [19,28,37],[21,22,31],[23,32,41,50,59],[29,38],[30,39],[33,42],[34,43,52],[35,44],[40,49],
           [46,54,55],[47,48],[51,60],[53,62],[56,57],[58,67,68,77],[61],[63,72],[64,73,74],[65],
           [66,75,76],[69,70,71],[78,79,80]]



operations = [multiplication,subtraction,addition,division,addition,multiplication,
              multiplication,division,subtraction,
              multiplication,addition,multiplication,addition,
              multiplication,division,subtraction,multiplication,subtraction,
              addition,addition,division,addition,addition,
              subtraction,addition,equals,
              subtraction,addition,equals,multiplication,addition,multiplication]

targets = [1344,5,20,2,15,15,24,2,2,648,14,120,35,56,4,5,18,5,6,12,3,11,13,1,16,8,3,19,1,48,18,210]                            
#assemble indexes, operations and targets for all cages into list 'cages'
cages = []
for i in range(len(targets)):
    cage = Cage(indexes[i], operations[i], targets[i])
    cages.append(cage)


##1 remove numbers that can't be used to produce target
##e.g. 2 by division eliminates 5,7,9 
## 8 by subtraction leaves only 1 and 9, 2-8 are eliminated
def cullPossibilities(possibilities):
    for cage in cages:
        if all([possibilities[i] == [] for i in cage.indexes]):
            continue #test if all cells in cage have been solved, if so move to 
                     #next cage
        listsPossibilities = [] #assemble list of possibilities from cage cells
        for index in cage.indexes:
            if possibilities[index] != []:
                listsPossibilities.append(possibilities[index])
            else:
                listsPossibilities.append([values[index]])
        combinations = list(product(*listsPossibilities)) 
        #generate combinations of possibilities from cells in cage
        combinations = [list(combination) for combination in combinations] 
        #test which satisfy target
        targetCombinations = []
        for combination in combinations:
            if cage.operation(combination) == cage.target:
             #check for duplicates using set and length of list
                if len(combination) == len(set(combination)):
                    targetCombinations.append(combination)
                else:
                    rowAddresses = [index2row[index] for index in cage.indexes]
                    testRow = list(zip(combination, rowAddresses))
                    columnAddresses = [index2column[index] for index in 
                         cage.indexes]
                    testColumn = list(zip(combination, columnAddresses))
                    if len(testColumn) == len(set(testColumn)) and len(testRow) 
                                                  == len(set(testRow)):
                        targetCombinations.append(combination)
        # if target is satisfied and there are no duplicates add to new list of
         #possibilities which replaces original list of possibilities           
        i = 0
        for index in cage.indexes:
            newPossibilities = [targetCombination[i] for targetCombination in targetCombinations]
            if possibilities[index] != []:
                possibilities[index] = list(set(newPossibilities))
            i = i + 1

    return(possibilities)