Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
fast and clean solution in Speedy category for Magic Domino by bunnychai
import itertools
import random
DOMINO = [(i, j) for i in range(7) for j in range(7) if j >= i]
# all cols that sum up to number
def all_cols(size, number):
ret = []
for d in itertools.combinations(DOMINO, size // 2):
if sum(sum(map(list, d), [])) == number:
ret.append(d)
# shuffle to get shorter expected time to the first solution
random.shuffle(ret)
return ret
# choose m disjoint rows or columns from collection
def choose(collection, m, used=set()):
if m == 0:
yield []
else:
for i, x in enumerate(collection):
u = used | set(x)
dj = [x for x in collection[i + 1:] if all(y not in u for y in x)]
for y in choose(dj, m - 1, u):
yield [x] + y
# all good and disjoint 2-rows
def good_2_rows(board, size, number):
good = []
s = number * 2
for r in itertools.product(*board):
if sum(sum(map(list, r), [])) == s:
good.append(r)
return choose(good, size // 2)
# given a list of domino and a row, return another row
def compliment(dom_lst, row):
return (d[0] if row[i] == d[1] else d[1] for i, d in enumerate(dom_lst))
# all single good rows
def good_rows(board, size, number):
perm = []
for d in board:
row1 = set()
for r in itertools.product(*d):
if sum(r) == number:
row1.add(r)
row1 = list(row1)
row2 = [tuple(compliment(d, r)) for r in row1]
perm.append(zip(row1, row2))
return itertools.product(*perm)
# permute over every rows, then cols
def rotate(board):
for br in itertools.permutations(board):
flat = []
for r in br:
flat.extend(r)
flat = zip(*flat)
for bc in itertools.permutations(flat):
yield bc
# check if diagonal sum is correct
def check(board, number):
size = len(board)
return sum(board[i][i] for i in range(size)) == number and \
sum(board[i][size - 1 - i] for i in range(size)) == number
def magic_domino(size, number):
cols = all_cols(size, number)
# for each board with all good cols
for b_col in choose(cols, size):
# for each board with good 2-row
for b_2_row in good_2_rows(b_col, size, number):
# for each board with all good rows
for b_row in good_rows(b_2_row, size, number):
# for each board over all rows and cols rotations
for b in rotate(b_row):
if check(b, number):
return list(zip(*b))
Aug. 7, 2014
Comments:
