4
\$\begingroup\$

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)
\$\endgroup\$
9
  • \$\begingroup\$ Welcome to CR! Could you post how this function is to be called and show a sample input/output? I'm not sure what possibilities is supposed to look like. Thanks. \$\endgroup\$ – ggorlen May 11 '20 at 16:09
  • \$\begingroup\$ possibilities is a list of the numbers being considered as a solution for a given cell. \$\endgroup\$ – Dan May 12 '20 at 16:03
  • 1
    \$\begingroup\$ Please make this part of your question, comments are just for discussion. See the above link to get a sense of what a solid, answerable post looks like. Without a bit more context, the post might remain unanswered, or answers that do arrive will be cursory and unsatisfying for you. \$\endgroup\$ – ggorlen May 12 '20 at 16:33
  • 1
    \$\begingroup\$ I've added annotation to try to convey my thought process. \$\endgroup\$ – Dan May 12 '20 at 21:57
  • 1
    \$\begingroup\$ the referenced KenKen post was very helpful. Thank you. \$\endgroup\$ – Dan May 13 '20 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.