# Example of recursion for puzzle solving: find a chess board with as
# many queens as rows/columns where none threatens another.

size = 8

# Display a chessboard to the terminal window. Just print out whatever is in each position on the board.
def displayBoard(board):
    for i in range(size):
        for j in range(size):
            print board[i][j],
        print
    print

# Check to see if a potential location (row, col) on the board is "safe",
# which means that it cannot be taken by a queen already on the board.
def safe(board, row, col):

    # Check column
    for i in range(size):
        if board[i][col] == 'Q':
            return False

    # Check row
    for j in range(size):
        if board[row][j] == 'Q':
            return False

    # Check diagonal down and right
    for (i,j) in zip(range(row,size),range(col,size)):
        if board[i][j] == 'Q':
            return False

    # Check diagonal up and left
    for (i,j) in zip(range(row,-1,-1),range(col,-1,-1)):
        if board[i][j] == 'Q':
            return False

    # Check diagonal up and right
    for (i,j) in zip(range(row,-1,-1),range(col,size)):
        if board[i][j] == 'Q':
            return False

    # Check diagonal down and left
    for (i,j) in zip(range(row,size),range(col,-1,-1)):
        if board[i][j] == 'Q':
            return False

    # Must be safe
    return True






# completeBoard fills in the board with a successful set of
# queens and returns True if it can be done; otherwise, it leaves
# the board unchanged and returns False
def completeBoard(board):

    # Count queens, return if complete
    numQueens = 0
    for i in range(size):
        for j in range(size):
            if board[i][j] == 'Q':
                numQueens += 1

    if numQueens == size:
        return True

    # If not eight queens, must be fewer: try to add another
    for i in range(size):
        for j in range(size):
            if safe(board,i,j):
                board[i][j] = 'Q'
                if completeBoard(board):
                    return True
                else:
                    board[i][j] = '-'
    
    # Failed to find solution
    return False

if __name__=='__main__':

    board = [['-']*size for i in range(size)]
    success = completeBoard(board)
    if success:
        print 'Did it!'
        displayBoard(board)
    else:
        print 'Failed.'