KenKen Solver
Inspired by Peter Norvig's Sudoku solver, I thought I'd try my hand at a KenKen solver using constraint propagation. As it turns out, I'm not the first person to have that exact thought. KenKens are smaller, but they're a bit more complex because of their structure.
Open the file containing the kenken. It's printed out in a form which is neither properly human readable or unreadable.
import itertools
from __future__ import print_function
puzzle = open("kenkenhard.txt", "r")
print(puzzle.read())
puzzle.seek(0)
dim = int(puzzle.readline())
puzzle.readline();
I need to define the cages for the Ken-Ken. A dictionary of lists of coordinates for each cage is created
cages = []
i = 0
j = 0
for line in puzzle:
if line == '\n':
break
number = ""
for char in line[:-1]:
if (char != ','):
number += char
else:
value = int(number) - 1
if len(cages) == value:
cages.append([])
cages[value].append([i,j])
number = ""
i += 1
i = 0
j += 1
print(cages)
We also want the operation and result for each cage
calcs = []
for line in puzzle:
calcs.append([line[0:-2], line[-2:-1]])
print(calcs)
Let's create a our initial unconstrained values for the solution grid
cell = []
for i in range(dim):
cell.append(i + 1)
line = []
for i in range(dim):
line.append(cell)
grid = []
for i in range(dim):
grid.append(list(line))
I need to be able to constrain other cell values in the same column and row when a cell value is determined
def constrain_lines(grid, dim, x, y):
#if there are no possible values then we have an error
if len(grid[x][y]) == 0:
return False
#if there's one possible value, constrain the column and line
if len(grid[x][y]) == 1:
val = grid[x][y][0]
for i in range(dim):
if i != x:
if val in grid[i][y]:
temp = list(grid[i][y])
temp.remove(val)
grid[i][y] = temp
for j in range(dim):
if j != y:
if val in grid[x][j]:
temp = list(grid[x][j])
temp.remove(val)
grid[x][j] = temp
#if a value can only go in one cell, it must go in that cell
for i in range(dim):
occurences = list(filter(lambda a : (i+1) in a, grid[:][y]))
if len(occurences) == 0:
return False
if len(occurences) == 1:
for j in grid[:][y]:
if (i+1) in j:
j = i+1
for i in range(dim):
occurences = list(filter(lambda a : (i+1) in a, grid[x][:]))
if len(occurences) == 0:
return False
if len(occurences) == 1:
for j in grid[x][:]:
if (i+1) in j:
j = i+1
return grid
The real magic is to constrain all cell values within a cage. Cages are usually small (5 is pretty large) so an exhaustive search over all possibilities is fine. I'm not passing the cell value because that's not a constraint for a cage. Cages can have multiple values which are the same.
def calc_op(op, values, i, result, size):
if op == ".":
if i == result:
return True
elif op == "+":
for candidate in values:
sum = i
for j in candidate:
sum += j
if sum == result:
return True
#All well formed KenKens have two cells in a subtraction and quotient cage
elif op == '-':
for j in values:
if (j[0] - i == result) or (i - j[0] == result):
return True
elif op == '/':
for j in values:
if (j[0]/i == result and j[0]%i == 0) or (i/j[0] == result and i%j[0] == 0):
return True
elif op == "*":
for candidate in values:
product = i
for j in candidate:
product *= j
if product == result:
return True
return False
def constrain_cage(grid, x, y):
cage = []
index = -1
for cage in cages:
index += 1
if [x,y] in cage:
break
cage = list(cage)
cage.remove([x,y])
cageGrid = []
for cell in cage:
cageGrid.append(grid[cell[0]][cell[1]])
[res, op] = calcs[index]
[res, op] = [int(res), op]
for i in list(grid[x][y]):
if not any([calc_op(op, itertools.product(*cageGrid) if len(cageGrid) > 0 else [], i, res, len(cage))]):
temp = list(grid[x][y])
temp.remove(i)
grid[x][y] = temp
Finally, a method of displaying our Ken Kens
def print_KenKen(grid, dim):
for i in range(dim):
for j in range(dim):
print(str(grid[j][i]) + " ", end=" ")
print("")
Now we can iterate over all cells and constrain them by cage and line.
def converge_grid(grid):
change = True
while (change):
prevLen = 0
for i in range(dim):
for j in range(dim):
prevLen += len(grid[i][j])
for i in range(dim):
for j in range(dim):
constrain_cage(grid, i, j)
for i in range(dim):
for j in range(dim):
constrain_lines(grid, dim, i, j)
currLen = 0
for i in range(dim):
for j in range(dim):
currLen += len(grid[i][j])
change = currLen != prevLen
def solve_check(grid, dim):
if (grid == None or grid == False):
return False
for i in range(dim):
for j in range(dim):
if len(grid[i][j]) != 1:
return False
return True
def possible_check(grid, dim):
if (grid == None or grid == False):
return False
for i in range(dim):
for j in range(dim):
if len(grid[i][j]) == 0:
return False
return True
Of course, without some more advanced heuristics our grid will likely never be solved using such a simple mechanistic approach. Happily, due to constraining the search space and the effect of propagating guesses we can just search to find the answer.
import copy
def guess_cell(grid, dim):
#find the first cell where there are multiple options and try them all
for i in range(dim):
for j in range(dim):
if (len(grid[i][j]) > 1):
for k in grid[i][j]:
#copy the grid and try all possible values for the first multiple valued cell
new_grid = copy.deepcopy(grid)
new_grid[i][j] = [k]
#propagate that change through the new grid
converge_grid(new_grid)
#if the convergence solved it we return it
if (solve_check(new_grid, dim)):
return new_grid
#if the grid doesn't have empty cells and contradictions, then recurse
if(possible_check(new_grid, dim)):
new_grid = guess_cell(new_grid, dim)
#if the new grid is solved we return it
if (solve_check(new_grid, dim)):
return new_grid
#at this point we've tried all the possibilities and none of them have worked.
#With our current assumptions, this grid doesn't have a solution
return False
Now we can put it all together
#constrain by rules first before beginning any search
converge_grid(grid)
#if the puzzle is sufficiently easy it may already be solved. If not, begin guessing
if (not solve_check(grid, dim)):
print("gotta try guessing")
grid = guess_cell(grid, dim)
print_KenKen(grid, dim)
Too lazy to time it, but that was instant.