#!/bin/env python
""" General solution to the 8 queens puzzle.
"""

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 list of queens?
        """
        for queen in queens:
            if self.attacked_by(queen):
                return False
        return True
    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

try:
    while True:
        board_size = int(raw_input("board size? "))
        for queens in queens_puzzle(board_size):
            print ", ".join(["%s" % qq for qq in queens])
except ValueError, v:
    print "Bye for now!"