Generating solutions to the 8 Queens Puzzle
Here’s a Python solution to the 8 Queens puzzle. I think that generator functions are perfectly suited to this kind of thing: they are easy to code and easy to use, they yield results as soon as they can, and clients have full control over when to stop them yielding results.
n-queens.py
class Queen:
"""A queen on a chess board.
"""
def __init__(self, row, col):
self.row, self.col = row, col
def __str__(self):
return "(%d, %d)" % (self.row, self.col)
def safe_from(self, queens):
"""Is this queen safe from the input list of queens?
"""
return not any(self.attacked_by(queen) for queen in queens)
def attacked_by(self, queen):
"""Is this queen attacked by the input queen?
"""
r, c = self.row, self.col
qr, qc = queen.row, queen.col
def same_row():
return r == qr
def same_column():
return c == qc
def same_diagonal():
return r + c == qr + qc or r - c == qr - qc
return same_row() or same_column() or same_diagonal()
def queens_puzzle(board_size):
"""Generate solutions to the Queens puzzle for the input board size.
"""
def queen_columns(cols):
if cols == 0:
yield list()
else:
cols -= 1
for queens in queen_columns(cols):
for row in range(board_size):
new_queen = Queen(row, cols)
if new_queen.safe_from(queens):
yield queens + [new_queen]
for queens in queen_columns(board_size):
yield queens
def outer_join(s, seq):
return "%s%s%s" % (s, s.join(seq), s)
def print_solution(board_size, queens):
line = outer_join("+", "-" * board_size)
for row in range(board_size):
print line
print outer_join("|",
[" Q"[q.row == row] for q in queens])
print line
try:
print """\
Queens puzzle solver.
Puts N chess queens on an N by N chessboard such that none of
them is able to capture any other.
At the prompt, enter the board size or Q to quit.
"""
while True:
board_size = int(raw_input("board size (Q to quit)? "))
if board_size <= 0:
print "Please enter a positive board-size."
else:
if board_size > 16:
print ("That's a tough one but I'll try my best. "
"Press CTRL-C to interrupt.")
try:
solutions = -1
for solutions, queens in enumerate(queens_puzzle(board_size)):
print_solution(board_size, queens)
solutions += 1 # Users count from 1, not 0
print "There %s %d solution%s to the %d Queen%s puzzle.\n" % (
"is" if solutions == 1 else "are",
solutions, "s"[solutions==1:],
board_size,"s"[board_size==1:])
except KeyboardInterrupt:
print "Execution interrupted."
except ValueError, v:
print "Bye for now!"