KenKen puzzle solver in 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.

KenKen is a number puzzle played on a square grid. I've added the setup for a 9x9 puzzle. The cells must be filled with the numbers 1-9 such that there are no duplicates in any row or column. An additional set of constraints involves a set of cages: groups of cells that must satisfy some arithmetical rule. For example: the values of the cells must equal 2 by division.

possibilities is a list of the numbers being considered as a solution for a given cell.

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)

Answer 1

@dataclass

The Cage abstraction is very nice; thank you for defining it.

Consider using a @dataclass decorator to make it a little more concise.

from dataclasses import dataclass
@dataclass
class Cage:
 indexes: list[int]
 operation: Callable[[list[float]], float]
 target: float

The OP def divide() admits of fractional results; consider doing int( ... ) on the result if puzzle targets are always integers.

class

There's a bunch of module-level globals, such as rows[] and possibilities[]. Consider defining class KenKen: so we can have e.g. a self.rows attribute.

parallel lists

Here's the biggest thing that really ought to be cleaned up:

indexes = [[0,1,9,10], [2,3], ... ]
 
operations = [multiplication, subtraction, ... ]
targets = [1344, 5, ... ] 

That's just kind of terrible -- humans are not good at seeing that an "18+" target is associated with the [69,70,71] cage. Prefer to list them as tuples:

puzzle = [
 ([0,1,9,10], multiplication, 1344),
 ([2,3], subtraction, 5),
 ... 
]

It might also be convenient to define the cage as the final tuple element; putting the variable length item at end of line makes it a little easier to visually scan through the puzzle definition.

Now the Cage(indexes[i], operations[i], targets[i]) expression gets turned into

for item in puzzle:
 cage = Cage(*item)
 ...

or

cages = list(map(lambda item: Cage(*item)))

rendering

To verify we have faithfully represented a given puzzle that appeared in a newspaper, it would be useful to add a function that dumps the internal representation to a tabular display format. Even if the initial version produces output that isn't pretty, it would still be a huge help for tracking down accidental typos.

branching factor

When exploring the graph of the solution space, the branching factor \$\beta\$ has a huge effect on elapsed running time. I didn't attempt any timing measurements, but I imagine this code runs on the slow side, as I didn't notice any comparisons on cage length.

You definitely want to lock in values for all the length-1 cages, as each of those is a "gimme". Then start exploring length-2 cages, in the hopes that you can find feasible candidates for both values, and finally explore the harder cages. This is just a matter of turning for cage in cages: into for cage in sorted(cages, key=cage_length):, with

def cage_length(cage: Cage) -> int:
 return len(cage.indexes)

As a tie-breaker, it might be helpful to tackle small {products, sums} first:

 return (len(cage.indexes), target)

Answer 2

Unused

The following line can be deleted:

from itertools import combinations

This was identified by lint tools

Layout

Move the class and functions to the top after the import lines. Having them in the middle of the code interrupts the natural flow of the code (from a human readability standpoint).

Naming

The PEP 8 style guide recommends capitalizing constants. For example, change

side = 9

to:

SIDE = 9

Portability

The versions of Python I am using show a syntax error on the first of these 2 lines:

if len(testColumn) == len(set(testColumn)) and len(testRow) 
 == len(set(testRow)):

Perhaps your version is more forgiving. Or, as commonly happens for users who are new to this site, maybe the code was not copied properly into the question.

The syntax error goes away when I add the second line to the end of the first:

if len(testColumn) == len(set(testColumn)) and len(testRow) == len(set(testRow)):

Comments

Many of the comments in the code are helpful.

However, this one can be deleted since it merely restates the code below it:

##define Cage class
class Cage:

Documentation

The PEP-8 guide recommends using a docstring for each class and function:

class Cage:
 """ Group of cells """
def multiplication(combination):
 """ Return the result of multiplying all input combinations """

Since combination is an array, it might be more helpful to pluralize it as combinations.

It would be helpful to document all function inputs and return values (types, expected ranges, etc.).

Simpler

It is common to use the special assignment operators for expressions like:

 result = result*n

It is simpler as:

 result *= n

Also:

i = i + 1

becomes:

i += 1

The following line:

indices = [i for i in range(side*side)]

can be simplified as:

indices = list(range(side ** 2))

The return keyword is conventionally used with out parentheses. Change:

return(result)

to:

return result