Instantly share code, notes, and snippets.

# nolenroyalty/queen_problem.py Created Jul 17, 2012

What would you like to do?
Solving the N-Queen problem
 def get_candidate_boards(board): boards = [] queen_locations = [(x, y) for x in range(len(board)) for y in range(len(board)) if board[x][y] == "Q"] left_diagonals = [(x-y, 0) for (x, y) in queen_locations] right_diagonals = [(x+y, 0) for (x, y) in queen_locations] for x, y in ((x, y) for x in range(len(board)) for y in range(len(board)) if board[x][y] != "Q"): temp_board = board[:x] + [board[x][:y] + ["Q"] + board[x][y+1:]] + board[x+1:] valid_cols = all(col.count("Q") < 2 for col in temp_board) valid_rows = all(row.count("Q") < 2 for row in zip(*temp_board)) valid_left = (x-y, 0) not in left_diagonals valid_right = (x+y, 0) not in right_diagonals if valid_cols and valid_rows and valid_left and valid_right: boards.append(temp_board) return boards def solve_board(board, queens_remaining): if queens_remaining == 0: return board for candidate_board in get_candidate_boards(board): solution = solve_board(candidate_board, queens_remaining-1) if solution: return solution def main(): size = input("Size of board: ") board = [["-" for _ in range(size)] for __ in range(size)] solution = solve_board(board, size) try: print "\n".join([" ".join(row) for row in solution]) except TypeError: print "Error: unable to find solution for board" if __name__ == "__main__": main()