Skip to content

Instantly share code, notes, and snippets.

Last active Aug 29, 2015
What would you like to do?
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[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
if compatible:
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
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):
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
Copy link

adewes commented Feb 22, 2014

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment