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)

Advertisements

## One Comment

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

## One Trackback

[…] 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 […]