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
# 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(&#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

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 = &#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 ""
        
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(&#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


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

Happy hacking 🙂

Advertisements

7 Comments

  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.

    Click here to check out iKendu

    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

  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.

3 Trackbacks

  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 […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

  • Pages

  • February 2009
    M T W T F S S
    « Feb   Mar »
     1
    2345678
    9101112131415
    16171819202122
    232425262728  
  • RSS The Wayward Word Press

  • Recent Comments

    dave porter on On being the maintainer, sole…
    daveshields on On being the maintainer, sole…
    Paul Tallett on On being the maintainer, sole…
    mrrdev on On being the maintainer, sole…
    KT on On being the maintainer, sole…
  • Archives

  • Blog Stats

  • Top Posts

  • Top Rated

  • Recent Posts

  • Archives

  • Top Rated

  • %d bloggers like this: