Generating solutions to the 8 Queens Puzzle

2006-07-21, Comments

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
    print
    
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!"