## On Programming. A Program Written Because of a Tweet: Calcu-Doku.py

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

# 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:]]
t = [n]
for o in others:
r.append([n] + o)
if length == 3: # remove obvious incorrect possibilities
trim3(cage, r)
return r

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 == '+':
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
return []

def divide(size, cage):
result = cage
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(&#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, 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: break # if too big
(quot,rem) = divmod(result, n)
if rem: continue # not a divisor
# have possible choice for first
now = &#91;quot, size, cage&#91;1:&#93;&#93;
others = multiply(size, now)
for o in others:
t = &#91;n&#93;
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 &#91;row,col, value&#93;
title, size, operator, cages = puzzle
cells = &#91;0&#93; * (size * size)

for s in range(len(solution)):
row, col, value  = solution&#91;s&#93;
cells&#91;col*size + row&#93; = value
for row in range(size):
for col in range(size):
print " ", cells&#91;col*size + row&#93;, " ",
print ""

# read puzzle from standard input
text  = ""
cages = &#91;&#93;
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 =  &#91;&#93;
#        print "nlines, line", nlines, line
if nlines==1:
title =  line
elif nlines == 2:
size = string.atoi(line)
elif nlines == 3:
operator = line&#91;0&#93;
else:
# new cage
result = string.atoi(words&#91;0&#93;)
row = string.atoi(words&#91;1&#93;)
col =  string.atoi(words&#91;2&#93;)
cells = &#91;&#91;row,col&#93;&#93;
if len(words) > 3: # if have more than one cell
moves = words
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
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 =  * (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

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

### One Comment

1. Finn Wilcox

Well I wrote my KenKen solver in response to your tweet, but I was just copying your idea 🙂

1. […] The Wayward Word Press WordPress gave me a blog to see how I was going to handle it « On Programming. A Program Written Because of a Tweet: Calcu-Doku.py […]

• ### Pages

 Sahana’s Respo… on A brief history of Sahana by S… Sahana’s Respo… on A brief history of Sahana by S… James Murray on On being the maintainer, sole… James Murray on On being the maintainer, sole… mrrdev on On being the maintainer, sole…