Solver of puzzle game Cross Match Sticks https://itunes.apple.com/ca/app/cross-match-sticks/id586669268?mt=8

cross-match-sticks.py

def test(state):
    ' test if the state is final '
    return all(d == 0 or d == 2 for d in state)


def next(state, cross=2):
    ' generate all possible moves from the current state '
    for i, d in enumerate(state):
        if d == 1:
            l = left(state, i, cross)
            if l is not None:
                yield l

            r = right(state, i, cross)
            if r is not None:
                yield r


def left(state, i, cross=2):
    ' move stick at state[i] to the left '
    assert state[i] == 1
    jump = 0
    j = i-1
    while jump < cross and j > 0:
        jump += state[j]
        j -= 1

    if jump == cross:
        while 0 < j:
            if state[j] == 1:
                new = list(state)
                new[j] = 2
                new[i] = 0
                return tuple(new)
            elif state[j] == 0:
                j -= 1
            else:
                return


def right(state, i, cross=2):
    ' move stick at state[i] to the right '
    assert state[i] == 1
    jump = 0
    j = i+1
    l = len(state)
    while jump < cross and j < l-1:
        jump += state[j]
        j += 1

    if jump == cross:
        while j < l:
            if state[j] == 1:
                new = list(state)
                new[j] = 2
                new[i] = 0
                return tuple(new)
            elif state[j] == 0:
                j += 1
            else:
                return


def solve(state, cross=2, path=[]):
    ' recursively generate and test moves '
    path = path[:] + [state]

    if test(state):
        raise Exception(path)       # terminate recursion

    for each in next(state, cross):
        solve(each, cross, path)


def run(stick=8, cross=2):
    try:
        print '_' * 40
        print '%d stick %d cross' % (stick, cross)
        solve((1,) * stick, cross)
        print 'no solution found'
    except Exception as e:
        for each in e.args[0]:
            print each


run(8, 2)
run(10, 2)
run(12, 2)
run(14, 2)
run(12, 4)
run(14, 4)