public
Last active

Solving the N-Queen problem

  • Download Gist
queen_problem.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
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()

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.