I solved the first puzzle in short order, and found it fun.
Even more fun was the realization that writing a solver for kenken in Python would also be fun, and once I had done that I concluded that this could serve as a starting program for a new project of mine, how to teach programming in Python to students in k12. I’ll be writing about that project in a forthcoming post.
Puzzles are described in a simple text format. You can read the code to figure out the encoding. Here is the first 4×4 puzzle published in the New York Times:
first 4x4 puzzle from NY Times, published on Friday 02/13/09 4 8 * 0 0 rr 1 - 0 3 d 3 - 1 0 d 3 = 1 1 7 + 1 2 dl 2 / 2 3 d 1 - 3 0 r 1 = 3 2
Below you can find a simple kenken solver written in python. It reads the puzzle definition from standard input:
# Copyright (C) 2009, David Shields # Licensed under "License Dave Shields for Software" available at https://daveshields.wordpress.com/about/#license # # v1 is with puzzle definition in the program # v2 is with puzzle definition read from standard input, with cage as list of cells # v3 is with puzzle read from standard input, with each cage represented by line and set of moves # v4 fixes a bug in multiply() # v5 uses prettyprint to format output # v5 adds special handling for triples # A puzzle is represented by a list [title-string, puzzle-size, cage-list] # where # title-string is a string identifying the puzzle # puzzle-size is an integer giving the number of rows (and also columns) # cage-list is a list of cages # A cage is a list (result-value, operator, cell-list) # where # result-value is the value of the operator applied to the values in the cells in the cell-list # operator is a string, one of '+', '-', '*', '/' and '=' # cell-list is a list of cells # A cell is a list (row, column) # By convention, the first cell in the cell-list is the topmost, leftmost cell, but this is not required. # # An assignment is a list of cages and assignments of values for the cells in each cage: [cage, values] # # A solution is a list of assignments to cages that satisfies the non-duplication requirement import copy import pprint import string import sys def add(size, cage): # ways to get result res with puzzle size size and length length # if length is two and since must add at least one, then just look at values less than result result, operator, cells = cage length = len(cells) r =  if result == 0: return r if length < 2: return r if length == 2: for i in range(size): n = i+1 if result - n <= size: r.append([n, result - n]) # if result -n != n: # append complentary choice if it is different # r.append([result - n, n]) else: # try all the possibilities for first cell, and then look for alternatives in the remaining cells for i in range(size-1): n = i+1 tail = [result - n, '+', cells[1:]] others = add(size, tail) t = [n] for o in others: r.append([n] + o) if length == 3: # remove obvious incorrect possibilities trim3(cage, r) return r def adjacent(cell0, cell1): r0, c0 = cell0 r1, c1 = cell1 if r0 == r1 or c0 == c1: return True return False def choices(puzzle): title,size,cages = puzzle res =  for cage in cages: result, operator, cells = cage length = len(cells) if operator == '=': possible = [[result]] elif operator == '+': possible = add(size, cage) elif operator == '-': possible = subtract(size, cage) elif operator == '*': possible = multiply(size, cage) elif operator == '/': possible = divide(size, cage) else: print "error, unknown operator",operator if possible == None or len(possible) == 0: print "no solution for cage ", result, operator, cells print " ", 1 / 0 res.append(possible) return res def classify(cells): #classify triple, returning center if len(cells) != 3: return None cell0, cell1, cell2 = cells if adjacent(cell0, cell1) and adjacent(cell0, cell2): return 0 if adjacent(cell1, cell0) and adjacent(cell1, cell2): return 1 if adjacent(cell2, cell0) and adjacent(cell2, cell1): return 2 return  def divide(size, cage): result = cage r =  if result > size: print "error, impossible division", result,size else: for i in range(size): n = i + 1 if n * result <= size: r.append([n, n*result]) r.append([n*result, n]) return r def multiply(size, cage): # ways to get -result- by multiplying -length- numbers for puzzle of given -size- r =  result, operator, cells = cage length = len(cells) if result == 1: # here if want result of 1, so add appropriate number of 1's t =  for i in range(length): t.append(1) r.append(t) return r if length == 2: for i in range(size): n = i + 1 # trial divisor (quot, rem) = divmod(result, n) if rem == 0: if quot <= size: r.append([quot, result // quot]) return r; # here if more than two numbers for i in range(result): n = i+1 if n == 1: continue # have already dealt with this case if n > size: break # if too big (quot,rem) = divmod(result, n) if rem: continue # not a divisor # have possible choice for first now = [quot, size, cage[1:]] others = multiply(size, now) for o in others: t = [n] t.extend(o) r.append(t) if len == 3: # remove obvious incorrect possibilities trim3(cage, r) return r def printsolution(puzzle, solution): #choices, guess): # solution is list of form [row,col, value] title, size, cages = puzzle cells =  * (size * size) for s in range(len(solution)): row, col, value = solution[s] cells[col*size + row] = value for row in range(size): for col in range(size): print " ", cells[col*size + row], " ", print "" def readpuzzle(): # read puzzle from standard input text = "" lines = sys.stdin.readlines() cages =  nlines = 0 for line in lines: words = line.split() # break line into words separated by whitespace if len(words) == 0: continue # ignore blank line nlines += 1 cage =  # print "nlines, line", nlines, line if nlines==1: title = line elif nlines == 2: size = string.atoi(line) else: # new cage result = string.atoi(words) operator = words row = string.atoi(words) col = string.atoi(words) cells = [[row,col]] if len(words) > 4: # if have more than one cell moves = words for m in moves: if m == 'r': col += 1 elif m == 'l': col -= 1 elif m == 'd': row += 1 elif m == 'u': row -= 1 if [row,col] not in cells: # if new cell cells = cells + [[row,col]] cages.append([result, operator, cells]) return [title, size, cages] def subtract(size, cage): result, operator, cells = cage r =  if result > size: pass # no, just look at multiples that match ... else: for i in range(size): v = i + 1 if (v + result) <= size: r.append([v,v + result]) r.append([v+result,v]) return r def solve(puzzle,choices): title, size,cages = puzzle ncages = len(cages) c = choices trials = 1 trialset =  for trial in range(len(c)): trialset.append(len(c[trial])) trials *= len(c[trial]) print "trials is", trials, " trial set", trialset # trials may be long so ... trial = 0 while 1: # for trial in xrange(trials): if trial >= trials: break trial += 1 t = trial if t % 10000 == 0: print t if t // 100000000: print "too many tries", t, break; solution =  guess =  nfound = 0 for i in range(ncages): (t,g) = divmod(t, len(c[i])) guess.append(g) # now fill out solution for this guess solution =  # This is exhaustive search, # it would be better to check for duplicates on the fly for i in range(ncages): gi = guess[i] choicelist = c[i] choice = choicelist[gi] cage = cages[i] cells = cage for ci in range(len(cells)): row,col = cells[ci] if ci<0 or ci >= len(choice): print "choice index error", ci, trial try: solution.append([row,col, choice[ci]]) nfound += 1 except IndexError: print "error ", row, col, ci, choice raise ValueError if nfound != (size * size): print "sizezzzz", nfound, size if verify(puzzle, solution): print "success:", guess print "took ", trial, " trials" printsolution(puzzle, solution) return guess print "no solution" def trim3(cage, possibles): result, operator, cells = cage pivot = classify(cells) pi = 0 for pin in possibles: p = copy.copy(pin) pvalue = p[pivot] del p[pivot] other1,other2 = p if pivot == other1 or pivot == other2: # if cannot be solution del possibles[pi] pi += 1 def verify(puzzle, solution): #choices, guess): # solution is list of form [row,col, value] title,size, cages = puzzle if len(solution) != (size * size): print "solution,len error", len(solution), size cells =  * (size * size) rows = [] * size cols = [] * size for s in range(len(solution)): row, col, v = solution[s] if row in rows[v-1]: return 0; # value already used, so cannot verify if col in cols[v-1]: return 0; # value already used, so cannot verify rows[v-1] = rows[v-1] + [row] cols[v-1] = cols[v-1] + [col] return 1 # found match! # set up possible assignments puzzle = readpuzzle() pprint.pprint(puzzle) c = choices(puzzle) print "choices" pprint.pprint(c) solve(puzzle, c)
Happy hacking 🙂