import random
import math

class Board():

    def __init__(self, numRowsCols):
        self.cells = [[0] * numRowsCols for i in range(numRowsCols)]
        self.numRows = numRowsCols
        self.numCols = numRowsCols

        # negative value for initial h...easy to check if it's been set or not
        self.h = -1

    # Print board
    def printBoard(self):
        for row in self.cells:
            print(row)

    # Randomize the board
    def rand(self):
        for row in self.cells:
            i = random.randint(0, self.numCols - 1)
            row[i] = 1

    # Swap two locations on the board
    def swapLocs(self, a, b):
        temp = self.cells[a[0]][a[1]]
        self.cells[a[0]][a[1]] = self.cells[b[0]][b[1]]
        self.cells[b[0]][b[1]] = temp


# Cost function for a board
def numAttackingQueens(board):
    # Collect locations of all queens
    locs = []
    for r in range(len(board.cells)):
        for c in range(len(board.cells[r])):
            if board.cells[r][c] == 1:
                locs.append([r, c])
    # print 'Queen locations: %s' % locs

    result = 0

    # For each queen (use the location for ease)
    for q in locs:

        # Get the list of the other queen locations
        others = [x for x in locs if x != q]
        # print 'q: %s others: %s' % (q, others)

        count = 0
        # For each other queen
        for o in others:
            # print 'o: %s' % o
            diff = [o[0] - q[0], o[1] - q[1]]

            # Check if queens are attacking
            if o[0] == q[0] or o[1] == q[1] or abs(diff[0]) == abs(diff[1]):
                count = count + 1

        # Add the amount for this queen
        result = result + count

    return result


# Move any queen to another square in the same column
# successors all the same
def getSuccessorStates(board):
    result = []

    for i_row, row in enumerate(board.cells):
        # Get the column the queen is on in this row
        i_queen = [i for i, x in enumerate(row) if x == 1][0]

        # For each column in the row
        for i_col in range(board.numCols):

            # If the queen is not there
            if row[i_col] != 1:
                # Make a copy of the board
                bTemp = Board(board.numRows)
                bTemp.cells[:] = [r[:] for r in board.cells]

                # Now swap queen to i_col from i_queen
                bTemp.swapLocs([i_row, i_col], [i_row, i_queen])
                # bTemp.printBoard()
                result.append(bTemp)

    return result


def schedule(t_value, decay_rate):
    return t_value * decay_rate


def simulated_annealing (problem, schedule):
    # current_node = problem

# def localSearch(board, decay_rate, threashold):
#     Tempurature = 100

#     board.rand()
#     current = board
#     h = numAttackingQueens(current)

#     print('Initial state: ')
#     current.printBoard()
#     print('h-value: ' + str(h) + '\n')

#     while Tempurature > threashold :
#         if h == 0 :
#             break
#         successor_list = getSuccessorStates(board)
#         successor_state = successor_list[random.randint(0, len(successor_list) - 1)]

#         if numAttackingQueens(current) > numAttackingQueens(successor_state) :
#             current = successor_state
#         else :
#             if (probability(current, successor_state, Tempurature) > random.random()):
#                 current = successor_state

#         h = numAttackingQueens(current)
#         Tempurature = schedule(Tempurature, decay_rate)

#     print('Final state: ')
#     current.printBoard()
#     print('h-value = ' + str(h))

#     return current

def simulated_annealing_2 (board, t_start_val, threshhold, decay_rate):
  best_board = board
  best_val = numAttackingQueens(board)
  tval = t_start_val


  while (tval > threshold):
    nextStates = getSuccessorStates()
    next_possible = random.choice(nextStates)
    next_possible_val = numAttackingQueens(next_possible)

    if  next_possible_val > best_val:
      best_board = next_possible
      best_val = numAttackingQueens(next_possible)
    elif next_possible_val < bestVal:
      probability = math.e**((best_val - next_possible_val) / tval)

      # continue from here, do something with the probability var

    tval = tval * decay_rate



def main():
    print('Starting main function for Simulated Annealing program')

    board_size = 4
    T = 100
    decay_rates = [0.9, 0.75, 0.5]
    thresholds = [0.000001, 0.0000001, 0.00000001]
    pair_1 = schedule(thresholds[0], decay_rates[0])
    pair_2 = schedule(thresholds[1], decay_rates[1])
    pair_3 = schedule(thresholds[2], decay_rates[2])

    for i in range(3):
        board = Board(board_size)
        board_size *= 2
        for j in range(10):
            board.rand()
            board.printBoard()
            print(" ")
            simulated_annealing(board, pair_1)
            simulated_annealing(board, pair_2)
            simulated_annealing(board, pair_3)

    print('Printing Board:')

if __name__ == '__main__':
    main()
    print('\nExiting normally')