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
# 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[0]
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 = [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 ""
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[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([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[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
puzzle = readpuzzle()
pprint.pprint(puzzle)
c = choices(puzzle)
print "choices"
pprint.pprint(c)
solve(puzzle, c)
Happy hacking 🙂
Tuxer's
Welcome