Bitstring DP for the checkerboard problem http://www.reddit.com/r/math/comments/1bksoo/what_is_your_favorite_logic_or_math_puzzle/c97ots6

dp.py

def gi(n,i):
    return n&(1<<i)

def b(n):
    l = []
    for k in filter(lambda n: n%5 < 4, range(19)):
        if gi(n,k) and not gi(n,k+1) and not gi(n,k+5):
            l.append(k)
    return l

def transition(n, k):
    return n - (1<<k) + (1<<(k+1)) + (1<<(k+5))

def valid(n):
    return not (n&1127)

def ln(n):
    x = 0
    for k in range(25):
      if n&(1<<k):
        x += 1
    return x
    

O = {}
# n, n -> ()
def DP(n, left):
    if n in O:
        return
    
    if not left:
        return
    
    if valid(n):
        print n
        return
    
    O[n] = b(n)
    for k in O[n]:
        m = transition(n,k)
        DP(m, left-1)
    return

def p(n):
    s = (("%s "*5) + "\n")*5
    x = []
    for k in range(25):
        x.append('x' if n&(1<<k) else ' ')
    print s%tuple(x)

DP(1,30)
l = sorted([(n, ln(n)) for n in O], key=lambda p: p[1])

def hm(k):
    return filter(lambda p: p[1] == k, l)