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 🙂
7 Comments
iKendu is a new Sudoku like logic puzzle game now available for the iPhone and iPod touch.
Click here to check out iKendu
If you like Sudoku, you’ll love iKendu!
Can this solve for puzzles with multiple solutions?
thanks
It stops at first solution found.
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
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.
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.
http://www.mlsite.net/kenken/
I remember this python solver provides all the solutions.
3 Trackbacks
[…] leave a comment » Yes, there is. It can be found in my recent post, Kenken Solver in Python. […]
[…] Shields has also posted a Python solver for these puzzles. It takes a somewhat different approach, and (I think) relies more heavily on […]
[…] 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 […]