Solving KenKen with Genetic Algorithms

(2012)

Since being introduced to KenKen a few months ago, I've been slightly addicted, so I thought it'd be interesting to try solving the puzzles in an different sort of way.

Following is a genetic algorithm solution using pyevolve.

The first thing is to define a data format to encode a puzzle. There are several ways to do it, but I went with this:

1 1 1 2
3 4 4 2
3 3 5 5
6 7 7 5
8 *
1 -
6 +
1 -
4 *
3 +
2 /

The first four rows describe what some folks are calling "cages". Any number of following rows describe the rule corresponding to each cage. For example, in this puzzle, Cage #1 consists of cells (1,2,3) and has the rule (8,*), meaning that whatever numbers go in those cells, when multiplied, their product must be 8. Cage #2 consists of cells (4,8) and has the rule (1,-), meaning that the difference of those two numbers must be 1.

You don't really need the initial 4-row cage definitions, you could also list the corresponding cells following each rule, but I find the grid easier to look at.

So to find a solution, all we need to do is generate the correct list of 16 digits (1-4) where none of the horizontal, vertical or mathematical constraints are violated. Picking solutions randomly, with no regard to the constraints, there are about 4 billion possible solutions (almost all of which are illegal). That number drops dramatically if you only generate solutions that follow the horizontal and vertical constraints, but we're gonna do it genetically, so who cares?

So here's code for a pyevolve-based solution. In my tests, it does a pretty good job finding the right answer, but every once in awhile it seems to get stuck and finishes without a solution. C'est la vie with random algorithms, but some more tuning might fix it.

import operator

from pyevolve import G1DList
from pyevolve import GSimpleGA
from pyevolve import Selectors
from pyevolve import Statistics
from pyevolve import DBAdapters

# ensure exactly 4x1s, 4x2s, 4x3s, 4x4s
def error_c(soln):
e1 = len([x for x in soln if x == 1])
e2 = len([x for x in soln if x == 2])
e3 = len([x for x in soln if x == 3])
e4 = len([x for x in soln if x == 4])
e_total = abs(4-e1) + abs(4-e2) + abs(4-e3) + abs(4-e4)
return 1 * e_total

# ensure no duplicates in a horizontal row
def error_h(soln):
score = 0
for i in [0,4,8,12]:
 if soln[i+0] == soln[i+1]: score = score + 1
 if soln[i+0] == soln[i+2]: score = score + 1
 if soln[i+0] == soln[i+3]: score = score + 1
 if soln[i+1] == soln[i+2]: score = score + 1
 if soln[i+1] == soln[i+3]: score = score + 1
 if soln[i+2] == soln[i+3]: score = score + 1
return score

# ensure no duplicates in a vertical row
def error_v(soln):
score = 0
for i in [0,1,2,3]:
 if soln[i+0] == soln[i+4]: score = score + 1
 if soln[i+0] == soln[i+8]: score = score + 1
 if soln[i+0] == soln[i+12]: score = score + 1
 if soln[i+4] == soln[i+8]: score = score + 1
 if soln[i+4] == soln[i+12]: score = score + 1
 if soln[i+8] == soln[i+12]: score = score + 1
return score

# ensure that each cell adds up correctly
def error_r(soln, rules):
score = 0
for rule in rules:
 op, n, cells = rule
 if op == '-':
   if soln[cells[0]] - soln[cells[1]] == n:
     continue
   if soln[cells[1]] - soln[cells[0]] == n:
     continue
   score = score + 1
 if op == '/':
   if soln[cells[0]] / soln[cells[1]] == n:
     continue
   if soln[cells[1]] / soln[cells[0]] == n:
     continue
   score = score + 1
 if op == '+':
   if reduce(operator.add, [soln[cell] for cell in cells]) == n:
     continue
   score = score + 1
 if op == '*':
   if reduce(operator.mul, [soln[cell] for cell in cells]) == n:
     continue
   score = score + 1
return 10*score

# fitness function gives higher scores for fewer rule violations
def eval_func(genome):
    soln = [i for i in genome]
    score = error_c(soln) + error_h(soln) + error_v(soln) + error_r(soln, rules)
    return 1000 - score

# global rules list
rules = []

def solve(infile):
    # read cell definitions from file
    cells = []
    f = open(infile,'r')
    lines = f.readlines()
    for line in lines[:4]:
        parts = line.strip().split()
    for part in parts:
        cells.append(int(part))

# generate global rules list
# rules = list[ operator, number, cells ]
# for example [*, 24, [1,2,3]]
for i, line in enumerate(lines[4:],1):
    parts = line.strip().split()
    n, op = int(parts[0]), parts[1]
    c = [j for j, cell in enumerate(cells) if cell == i]
    rules.append([op,n,c])

# solution is 16-element list
genome = G1DList.G1DList(16)
genome.setParams(rangemin=1, rangemax=4)
genome.setParams(bestrawscore=1000)
genome.evaluator.set(eval_func)

# terminate after 5000 generations or perfect match (score = 1000)
ga = GSimpleGA.GSimpleGA(genome)
ga.selector.set(Selectors.GRouletteWheel)
ga.terminationCriteria.set(GSimpleGA.RawScoreCriteria)
ga.setGenerations(5000)

# run evolution
ga.evolve(freq_stats=100)
print ga.bestIndividual()

if __name__ == "__main__":
solve('75.txt')

It reads the specified puzzle and tries to solve it within 5000 generations. The fitness function works by giving a maximum score of 1000 points for a perfect solution. Each constraint violation lowers the score. Over time, the best solutions propagate and usually a perfect solution is found.

I spent a fair amount of time playing with the settings to try out different population sizes and mutation rates, but ultimately, the defaults did a pretty good job. While the vertical, horizontal and mathematical criteria fully specify the rules, I also added an extra set of criteria to further penalize solutions without 4 of each number. Probably gratuitous, but it seemed to make things converge a bit faster.

Like always, use at your own risk. I think this code is correct, but it was also thrown together in a couple of hours for my own amusement and I only verified the solutions to a couple of puzzles.

This is what it looks like on a typical run:

Gen. 0 (0.00%): Max/Min/Avg Fitness(Raw) [1113.31(961.00)/756.03(897.00)/927.76(927.76)]
Gen. 100 (2.00%): Max/Min/Avg Fitness(Raw) [1137.93(997.00)/853.79(924.00)/948.28(948.27)]
Gen. 200 (4.00%): Max/Min/Avg Fitness(Raw) [1143.24(998.00)/853.01(929.00)/952.70(952.70)]

Evolution stopped by Termination Criteria function !

Gen. 271 (5.42%): Max/Min/Avg Fitness(Raw) [1138.08(1000.00)/825.62(915.00)/948.40(948.40)]
Total time elapsed: 1.869 seconds.
- GenomeBase
    Score:           1000.000000
    Fitness:         1138.080000

    Params:      {'bestrawscore': 1000, 'rangemax': 4, 'rangemin': 1}

    Slot [Evaluator] (Count: 1)
        Name: eval_func - Weight: 0.50
    Slot [Initializator] (Count: 1)
        Name: G1DListInitializatorInteger - Weight: 0.50
        Doc:  Integer initialization function of G1DList

    Slot [Mutator] (Count: 1)
        Name: G1DListMutatorSwap - Weight: 0.50
        Doc:  The mutator of G1DList, Swap Mutator

    Slot [Crossover] (Count: 1)
        Name: G1DListCrossoverSinglePoint - Weight: 0.50
        Doc:  The crossover of G1DList, Single Point

- G1DList
    List size:   16
    List:        [4, 1, 2, 3, 1, 4, 3, 2, 2, 3, 1, 4, 3, 2, 4, 1]

The final "List" at the end is the solution.

Anyway, I like KenKen and thought this was kinda cool. A direct, recursive solution should be reasonably easy to program as well. Just as some folks have done with Sudoku, it should also be possible to do this using a SAT solver. Still working on that one..

UPDATE - Now I'm completely bored with KenKen and haven't played at all since writing this program. That's not super-surprising, since the same thing happened with my online Literati solver (Yahoo's version of Scrabble) in 2003 and my online Word Racer solver (Yahoo's version of Boggle) in 2002. Oh well..