I noticed a few days back that Twitter @Puzzlewright had started following me on Twitter. I sent a note saying, “Thanks for the vote of confidence. I am returning the favor.”

Soon thereafter I saw a twit from P. Wright about “calcu-doku,” yet another variant of sudoko and kenken. Calcu-doku has several variants, perhaps the simplest being kenken with just one arithmetic operator.

This 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 tweet.

I see by Puzzlewright’s home page that next week is Calcu-Doku week, and so offer this code as a contribution to that effort.

# Copyright (C) 2009, David Shields
# Licensed under "License Dave Shields for Software" available at https://daveshields.wordpress.com/about/#license
#
# 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)
# operator is a string, one of '+', '-', '*', '/' and '='
# cage-list is a list of cages
# A cage is a list (result-value, cell-list)
# where
# result-value is the value of the operator applied to the values in the cells in the cell-list
# 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, 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 0 and (result - n) > 0:
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,operator, cages = puzzle
res = []
for cage in cages:
result, cells = cage
length = len(cells)
if length == 1:
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, 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: 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, operator, 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)
elif nlines == 3:
operator = line[0]
else:
# new cage
result = string.atoi(words[0])
row = string.atoi(words[1])
col = string.atoi(words[2])
cells = [[row,col]]
if len(words) > 3: # if have more than one cell
moves = words[3]
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, cells])
return [title, size, operator, cages]
def subtract(size, cage):
result, 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) = 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[1]
for ci in range(len(cells)):
row,col = cells[ci]
if 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, 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, operator, 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)