Personal Web Page

Sunday, January 4, 2009


Domino counting problem

My brother is writing a combinatorics paper about playing with dominoes. Pure mathematics is a lot of fun that way, but with more Hamiltonian paths of graphs embedded on a torus. Here is a Python script I wrote for him last night to solve a counting problem.

#!/usr/bin/env python
# Author: Jared Brothers
# Find the orderings of a set of dominoes such that
# adjacent dominoes share a number and the other two
# numbers differ by one.

def search(start):
""" Depth first search, generating all solutions. """
fringe = [start]
while fringe:
s = fringe.pop()
if s.check():
yield s

class state():
""" A state in the search space. """
def __init__(self, d, r):
""" The ordered dominoes are in done (list),
and the unordered dominoes are in rest (set). """
self.done = d = r

def __str__(self):
return str(self.done)

def check(self):
""" Is this a solution? """
return not

def successors(self):
""" The states you can get to by moving a domino from rest to done. """
if self.done:
# Try only dominoes adjacent to the previous one,
a,b = self.done[-1]
a1 = (a + 1) % n
a2 = (a - 1) % n
b1 = (b + 1) % n
b2 = (b - 1) % n
adjs = set([(a,b1), (b1,a), (a,b2), (b2,a), (b,a1), (a1,b), (b,a2), (a2,b)])
for x in
d = self.done[:]
r =
yield state(d, r)
# or all the rest if nothing has been done yet.
for x in sorted(
d = [x]
r =
yield state(d, r)

if __name__ == '__main__':
n = 7 # The number of numbers. The number of dominoes is sum(range(n + 1)).
start = state([], set((a, b) for a in range(n) for b in range(a + 1)))
for s in search(start):

Labels: ,


Post a Comment

<< Home
My Photo
Name: Jared Brothers
Location: New York, NY, United States


November 2008   December 2008   January 2009   May 2009   June 2009   July 2009  

This page is powered by Blogger. Isn't yours?

Subscribe to Posts [Atom]