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)

Beginner question: which line prints out state after each time a matchstick was moved?

@yemutex line 83. the path to the final success state (which is an exception (sounds weird, yes)) is stored as a tuple array.

@metaphox Oh I see -- he collects the entire path before printing it. Somehow I thought the printing was done in each step along the way and I was looking for that.

@metaphox The exception trick was used to break out of recursion. Any other suggestions to do so? I haven't thought of an alternative yet :|

@yemutex You won't want to do that because until the path reaches a correct final state, it might be a dead end.