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