Acht Königinnen

eight_queens.py

board_size = 8

def get_free_states(queens):
    """
    Get free board states for a set of queens
    """
    free_states = [[True]*board_size for i in range(0,board_size)]
    for queen in queens:
        for i in range(0,board_size):
            for signs in [(1,1),(-1,-1),(1,-1),(-1,1),(1,0),(-1,0),(0,1),(0,-1)]:
                if 0 <= signs[0]*i+queen[0] < board_size and 0 <= signs[1]*i+queen[1] < board_size:
                    free_states[queen[0]+signs[0]*i][queen[1]+signs[1]*i] = False
    return free_states

all_states = []
for i in range(0,board_size**2):
    x,y = i / board_size,i % board_size
    all_states.append("".join(["Q" if j==i else "O" if x == True else "X" for (j,x) in enumerate(reduce(lambda x,y:x+y,get_free_states(set([(x,y)]))))]))

def get_compatible_states(state,possible_states):
    """
    Which other states can we possibly add to a given state.
    """
    compatible_states = []
    for possible_state in possible_states:
        compatible = True
        for i in range(0,board_size**2):
            if state.index("Q") >= possible_state.index("Q") or (state[i] == "Q" and possible_state[i] == "Q") or (state[i] == "Q" and possible_state[i] == "X") or (possible_state[i] == "Q" and state[i] == "X"):
                compatible = False
                break
        if compatible:
            compatible_states.append(possible_state)
    return compatible_states

#Generate a "state compatibility" table, for faster lookup
compatibilities = [[all_states.index(state) for state in get_compatible_states(first_state,all_states)] for first_state in all_states]
state_indexes = dict([(state,i) for i,state in enumerate(all_states)])

def narrow_down(current_solutions,level = board_size-1):
    """
    Narrows down a list of possible solutions, recursively adding new states to the list.
    """
    for solution in current_solutions:
        compatible_states = [state for state in all_states if not state in solution]
        for state in solution:
            compatible_states = [s for s in compatible_states if state_indexes[s] in compatibilities[state_indexes[state]]]
        new_solutions = [solution + [compatible_state] for compatible_state in compatible_states]
        if level > 1:
            for higher_solution in narrow_down(new_solutions,level-1):
                yield higher_solution 
        else:
            for solution in new_solutions:
                yield solution

#Generate and print the solution
cnt = 0
for solution in narrow_down([[state] for state in all_states],board_size-1):
    cnt+=1
    print ",".join(["%.2d" % i for i in sorted([all_states.index(state) for state in solution]) ]),"\n\n"
    print "\n".join(solution),"\n"
print cnt

Solves the famous "eight queens" problem, using generators.