# Represents an NxN chess board onto which
# queens can be placed.
# Board locations can be accessed by 0-based
# (row, column) index pairs.
class ChessBoard:
    # Constructs a new board of a given size.
    def __init__(self, size):
        self._size = size
        self._board = [[False] * size for i in range(size)]
    
    # Converts the board into a string to print.
    def __str__(self):
        s = ""
        for r in range(self._size):
            for c in range(self._size):
                if self._board[r][c]:
                    s += "Q "
                else:
                    s += "_ "
            s += "\n"
        return s
    
    # Returns True if the given location already contains a queen.
    # If the location is out of bounds, raises a ValueError.
    def has_queen(self, row, col):
        if not self.in_bounds(row, col):
            raise ValueError("Illegal row/col")
        return self._board[row][col]
    
    # Returns True if the given row/col location is within
    # the bounds of this grid, otherwise False.
    def in_bounds(self, row, col):
        return row >= 0 and row < self._size \
           and col >= 0 and col < self._size
    
    # Places a queen on the given row/col location, if it
    # is safe to do so.
    # If the location is out of bounds or unsafe, raises a ValueError.
    def place(self, row, col):
        if not self.in_bounds(row, col):
            raise ValueError("Illegal row/col")
        self._board[row][col] = True
    
    # Removes any queen from the given row/col location.
    # If the location is out of bounds, raises a ValueError.
    def remove(self, row, col):
        if not self.in_bounds(row, col):
            raise ValueError("Illegal row/col")
        self._board[row][col] = False
    
    # Returns True if it would be safe to place a queen
    # at the given row/col location, otherwise False.
    # If the location is out of bounds, raises a ValueError.
    def safe(self, row, col):
        if not self.in_bounds(row, col):
            raise ValueError("Illegal row/col")
        # check for a queen in each of eight directions
        walks = [(-1, 0), (1, 0), (0, -1), (0, 1), \
                 (-1, -1), (1, 1), (1, -1), (-1, 1)]
        for (dr, dc) in walks:
            if not self._walk(row, col, dr, dc):
                return False
        return True
    
    # Returns the size of the board as was passed to
    # its constructor.
    def size(self):
        return self._size
    
    # Returns True if the board's current state is valid.
    def valid(self):
        for row in range(self._size):
            for col in range(self._size):
                if self._board[row][col]:
                    # check for # of queens in each of eight directions
                    walks = [(-1, 0), (1, 0), (0, -1), (0, 1), \
                             (-1, -1), (1, 1), (1, -1), (-1, 1)]
                    for (dr, dc) in walks:
                        if not self._walk(row, col, dr, dc, 1):
                            return False
        return True

    # Internal helper function for "walking" from a given row/col
    # location as far as possible in a given direction, looking for
    # unsafe conflicts. If more than 'allowed' found, returns False.
    # If the walk finishes safely with no conflicts, returns True.
    def _walk(self, row, col, dr, dc, allowed = 0):
        count = 0
        while self.in_bounds(row, col):
            if self._board[row][col]:
                count += 1
                if count > allowed:
                    return False
            row += dr
            col += dc
        return True