import math
import random
# x表示我们随机产生的那个数的平方和n的靠近程度
def func(x, n):
    return abs(x * x - n)
# 模拟退火
def SA(T, dT, eps, n):
    # 根号10大约为3.1622 这里人为限制范围 也可以直接随机 反正后面要受温度影响来回跳动且是随机的
    x = random.uniform(1.6, 5.4)
    # 算出x平方和n的差距f(x0)
    f = func(x, n)
    while T > eps:
        # 根号下的数一定是非负的 所以可以直接随机非负数
        new_x = random.randint(-13, 20) * T # 温度影响来回跳动且是随机无规则的 这里随意限制了下范围
        new_f = func(new_x, n)
        if new_f < f:
            x = new_x  # 替换 如果多个变量就替换多个
            f = new_f
        elif math.exp((f - new_f) / T) > random.random():  # 概率接受 ex在(0,1)之间 实际上random.random()在[0,1)
            x = new_x
            f = new_f
        # 降温
        T *= dT
    # 输出结果 近似值 如我本次是 3.1201885471764994
    print(x)
if __name__ == '__main__':
    n = 10  # n代表我们最后函数要逼近的值
    T = 20000  # 初始温度，初始温度主要是看题目开始需要跳转的幅度。
    dT = 0.993  # 变化率，这里需要速度稍微慢一点，写0.995 或者 0.997都可以，但是越靠近1速度就越慢
    eps = 1e-14  # 10的-14次方已经非常小了，写这个大概率没问题
    SA(T, dT, eps, n)

import copy
import random
import time
import math
import numpy as np
def init():
    cache = {}
    m = np.zeros((8, 8), dtype=int)
    for i in range(0, 8):
        temp = random.randrange(0, 8)
        m[temp, i] = 1
        cache["queen" + str(i)] = [temp, i]
    return m, cache
# 计算当前状态无碰撞数量
def compute_weight(coord_cache):
    weight = 0
    for i in range(0, 8):
        x, y = coord_cache["queen" + str(i)]
        for j in range(i + 1, 8):
            x2, y2 = coord_cache["queen" + str(j)]
            if x2 - x == j - i or x2 - x == i - j:
                weight += 1
            if x2 == x:
                weight += 1
    return 28 - weight
# 随机生成一个新的解
def random_adjust(coord_cache):
    temp = copy.deepcopy(coord_cache)
    row = random.randrange(0, 8)
    column = random.randrange(0, 8)
    temp["queen" + str(column)] = [row, column]  # 调整皇后的位置
    return temp
def draw(coord_cache):
    m = np.zeros((8, 8), dtype=int)
    for i in range(8):
        row, column = coord_cache["queen" + str(i)]
        row, column = int(row), int(column)
        m[row][column] = 1
    return m
def cool(T, eps, dt, L):
    m, coord_cache = init()
    print("初始化八皇后状态为：\n", m)
    while T > eps:  # 温度循环
        for i in range(L):  # 每个温度循环L次
            weight = compute_weight(coord_cache)
            print("当前状态的无碰撞度为：", weight)
            if weight == 28:  # 非碰撞度为28，表明找到了最优解
                return True
            new_coord_cache = random_adjust(coord_cache)  # 随机调整得到一个新的解
            new_weight = compute_weight(new_coord_cache)  # 计算新解的碰撞度
            print("随机调整产生的新解为：\n", draw(new_coord_cache))
            print("随机调整产生的新解的无碰撞度为：", new_weight)
            if new_weight >= weight:  # 新的解碰撞度更小就就收这个解
                coord_cache = new_coord_cache
                print("这是一个更好的解，直接接收：\n", draw(coord_cache))
            else:
                if random.random() < math.exp((new_weight - weight) / T):  # 否则就已模拟退火的概率接受作为新的解
                    coord_cache = new_coord_cache
                    print("当前的接收概率为：", math.exp((new_weight - weight) / T))
                    print("这是一个更差的解，但被接收了：\n", draw(coord_cache))
        T = T * dt
def Cool(T, eps, dt, L, num):
    t1 = time.time()
    success = 0
    fail = 0
    for i in range(num):
        if cool(T, eps, dt, L):
            success += 1
            print("第{0}个例子找到最优解".format(i))
        else:
            fail += 1
            print("第{0}个例子失败".format(i))
    t2 = time.time()
    print("{}个例子中成功解决的例子为：{}".format(num, success))
    print("{}个例子成功解决的百分比为：{}".format(num, success / num))
    print("{}个例子中失败的例子为：{}".format(num, fail))
    print("{}个例子失败的百分比为：{}".format(num, fail / num))
    print("{}个例子运行算法所需的时间为：{}秒".format(num, t2 - t1))
Cool(5, 0.001, 0.98, 150, 1000)

def draw(n, ini):
    for i in ini:
        print('+---' * n + '+', end='')
        print('')
        print('| ' + ' | '.join(['#' if j == '0' else 'Q' for j in list(i[2:].rjust(n, '0'))]) + ' | ')
    print('+---' * n + '+', end='')
def DFS(row, colomn, left, right):
    global ini
    global result
    global flage
    bits = ((1 << n) - 1) & ~(colomn | left | right)  # 当前行可用列
    if bits == 0 and len(ini) != 0:
        ini.pop()
    while bits:
        pos = bits & -bits  # 获取该行列的位置
        bits = bits & (bits - 1)  # bits ^= pos
        if row == n - 1:
            result += 1
            if flage:
                ini.append(bin(pos))
                draw(n,ini)
                flage-=1
        else:
            if flage:
                ini.append(bin(pos))
            DFS(row + 1, colomn | pos, (left | pos) >> 1, (right | pos) << 1)
            if bits == 0 and len(ini) != 0:
                ini.pop()
n = 6
result = 0
flage = 1  # 用来保留单一解
ini = []
DFS(0, 0, 0, 0)
print('\n','{}种情况'.format(result))