from random import *

class NQueens:
    """
    This class can be used to represent instances of the N-Queens
    problem.  In this problem N Queens must be placed on an NxN board
    in such a way that no Queen can attack another.  Queens can move
    horizontally, vertically, or diagonally.

    The board is represented as an NxN array of booleans, where True
    indicates the location of a Queen.  The Queens are initially
    placed in unique rows.  
    """
    def __init__(self, colPosition=None, n=8):
        """
        Use the given column positions for each row to generate a board.
        Or generate a randomly configured board with one queen in each row.
        """
        if colPosition != None:
            self.n = len(colPosition)
            self.board = [[False for c in range(self.n)] for r in range(self.n)]
            for r in range(self.n):
                self.board[r][colPosition[r]] = True
        else:
            self.n = n
            self.board = [[False for c in range(n)] for r in range(n)]
            for i in range(n):
                self.board[i][randint(0,n-1)] = True
    def __str__(self):
        result = ""
        result += ("-" * ((self.n*2)+1)) + "\n"
        for i in range(self.n):
            result += "|"
            for j in range(self.n):
                if self.board[i][j] == True:
                    result += 'Q|'
                else:
                    result += ' |'
            result += "\n" 
        result += ("-" * ((self.n*2)+1)) + "\n"
        return result
    def safeDirection(self, r, c, deltaR, deltaC):
        """
        Starting from the current row r and the current column c, look
        in one direction defined by deltaR and deltaC.  If another queen
        is encountered return False, otherwise return True.
        """
        r += deltaR
        c += deltaC
        while r>=0 and r<self.n and c>=0 and c<self.n:
            if self.board[r][c]:
                return False
            r += deltaR
            c += deltaC
        return True
    def eval(self):
        """
        Returns the number of safe queens on the board.
        """
        count = 0
        for r in range(self.n):
            c = self.board[r].index(True)
            if (self.safeDirection(r, c, 1, 0) and
                self.safeDirection(r, c, -1, 0) and
                self.safeDirection(r, c, 1, 1) and
                self.safeDirection(r, c, 1, -1) and
                self.safeDirection(r, c, -1, -1) and
                self.safeDirection(r, c, -1, 1)):
                count += 1
        return count
    def successors(self):
        """
        Successors are created by producing every possible new column
        placement.
        """
        position = []
        for r in range(self.n):
            position.append(self.board[r].index(True))
        result = []
        for r in range(self.n):
            for c in range(1,self.n):
                position[r] = (position[r]+1) % self.n
                result.append(NQueens(colPosition = position ))
            position[r] = (position[r]+1) % self.n
        return result
    def goalFound(self):
        return self.eval() == self.n
                
if __name__ == '__main__':
    # generate a random 6x6 board
    b1 = NQueens(n=6)
    print b1
    print "Safe queens:", b1.eval()
    # generate a particular 4x4 board where the queen in row r
    # is placed at column r
    b2 = NQueens([0,1,2,3,4])
    print b2
    print "Safe queens:", b2.eval()