Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
KenKen
#!/usr/bin/env python
# References
# http://en.wikipedia.org/wiki/KenKen
# https://docs.python.org/2/library/itertools.html
import argparse
import itertools
def check_board(board, cardinality):
rows = [set() for i in xrange(cardinality)]
cols = [set() for i in xrange(cardinality)]
for position, item in enumerate(board):
row = position / cardinality
col = position % cardinality
rows[row].add(item)
cols[col].add(item)
for row in rows:
if len(row) != cardinality:
return False
for col in cols:
if len(col) != cardinality:
return False
return True
def get_boards(cardinality):
items = []
for item in xrange(1, cardinality+1):
for i in xrange(cardinality):
items.append(item)
items = ''.join(map(str, items))
return itertools.permutations(items, len(items))
def get_num_combinations(cardinality, verbose=False):
results = {
True: 0,
False: 0,
}
seen = set()
for i, board in enumerate(get_boards(cardinality), 1):
if i % 1000000 == 0:
print "checking board %s ..." % i
if board in seen:
continue
result = check_board(board, cardinality)
results[result] += 1
if verbose:
print board, result
seen.add(board)
return results[True], results[False]
def main():
parser = argparse.ArgumentParser()
parser.add_argument('cardinality',
type=int,
help="Number of rows/columns (ie 6)")
parser.add_argument('-v', '--verbose', action='store_true')
args = parser.parse_args()
good, bad = get_num_combinations(args.cardinality, args.verbose)
print "Number of unique combinations for cardinality %s: %s" % (args.cardinality,
good + bad)
print "Good: %s" % good
print "Bad: %s" % bad
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment