Kenken Solver in Python

On February 13, 2009, the New York Times began publishing two kenken puzzles every weekday. See KENKEN® Puzzles , and A New Puzzle Challenges Math Skills.

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
#

# 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

# 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(&#91;n, result - n&#93;)
#                if result -n != n: # append complentary choice if it is different
#                    r.append(&#91;result - n, n&#93;)
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 = &#91;result - n, '+', cells&#91;1:&#93;&#93;
others = add(size, tail)
t = &#91;n&#93;
for o in others:
r.append(&#91;n&#93; + o)
if length == 3: # remove obvious incorrect possibilities
trim3(cage, r)
return r

r0, c0 = cell0
r1, c1 = cell1
if r0 == r1 or c0 == c1: return True
return False

def choices(puzzle):
title,size,cages = puzzle
res = &#91;&#93;
for cage in cages:
result, operator, cells = cage
length = len(cells)
if operator == '=':
possible = &#91;&#91;result&#93;&#93;
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 &#91;&#93;

def divide(size, cage):
result = cage&#91;0&#93;
r = &#91;&#93;
if result > size:
print "error, impossible division", result,size
else:

for i in range(size):
n = i + 1
if n * result <= size:
r.append(&#91;n, n*result&#93;)
r.append(&#91;n*result, n&#93;)
return r

def multiply(size, cage):
#   ways to get -result- by multiplying -length- numbers for puzzle of given -size-
r = &#91;&#93;
result, operator, cells = cage
length = len(cells)
if result == 1:
# here if want result of 1, so add appropriate number of 1's
t = &#91;&#93;
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(&#91;quot, result // quot&#93;)
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 = [0] * (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 ""

# read puzzle from standard input
text  = ""
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[0])
operator = words[1]
row = string.atoi(words[2])
col =  string.atoi(words[3])
cells = [[row,col]]
if len(words) > 4: # if have more than one cell
moves = words[4]
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(&#91;v,v + result&#93;)
r.append(&#91;v+result,v&#93;)
return r

def solve(puzzle,choices):
title, size,cages = puzzle
ncages = len(cages)
c = choices
trials = 1
trialset = &#91;&#93;
for trial in range(len(c)):
trialset.append(len(c&#91;trial&#93;))
trials *= len(c&#91;trial&#93;)
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[2]
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 = [0] * (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

pprint.pprint(puzzle)
c =  choices(puzzle)
print "choices"
pprint.pprint(c)
solve(puzzle, c)

Happy hacking 🙂

1. Posted April 12, 2009 at 01:39 | Permalink | Reply

iKendu is a new Sudoku like logic puzzle game now available for the iPhone and iPod touch.

If you like Sudoku, you’ll love iKendu!

2. galeo rhinus
Posted May 23, 2009 at 18:49 | Permalink | Reply

Can this solve for puzzles with multiple solutions?

thanks

• Posted June 19, 2012 at 13:42 | Permalink | Reply

It stops at first solution found.

3. Posted May 26, 2009 at 20:23 | Permalink | Reply

David,
This Kenken fails. I think there is a problem either with my input or your program. Could you take a look at it?
Thanks for a great program!
George

6×6 from Kenken website on Carole’s Macintosh
6
32 * 0 0 dr
4 – 0 1 r
3 / 0 3 r
10 + 0 5 dl
150 * 1 2 rdl
2 / 2 0 r
5 + 2 4 r
2 – 3 0 d
2 / 3 1 r
7 + 3 4 ld
1 – 3 5 d
4 = 4 2
10 + 4 4 dr
8 + 5 0 ru
10 + 5 2 r

4. Peter Heichelheim
Posted August 7, 2009 at 16:32 | Permalink | Reply

Is there a program when giving a particular Kenken that does not just solve it but goes step by step explaining how to solve it. I have a difficult 8×8 puzzle that I so far have not figured out to solve.

• Posted August 30, 2009 at 11:24 | Permalink | Reply

Dave replies:

My program does a “brute force” search, trying all possibilities, though it does have some code to limit guesses to boxes with more than two squares. It would be an interesting exercise to try to “explain” the logic as it goes along, though I don’t think it would provide much insight.

• Galeo Rhinus
Posted June 19, 2012 at 14:00 | Permalink | Reply

http://www.mlsite.net/kenken/

I remember this python solver provides all the solutions.

1. […] leave a comment » Yes, there is. It can be found in my recent post, Kenken Solver in Python. […]

2. […] Shields has also posted a Python solver for these puzzles. It takes a somewhat different approach, and (I think) relies more heavily on […]

3. […] inspired me to write the following variant of my KenKen Solver in Python. I expect this is one of the first, if not the first, program to be written because of a […]