Instantly share code, notes, and snippets.

# adewes/eight_queens.py

Last active Aug 29, 2015
Acht Königinnen
 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*i+queen < board_size and 0 <= signs*i+queen < board_size: free_states[queen+signs*i][queen+signs*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
Owner Author

### adewes commented Feb 22, 2014

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