-
Notifications
You must be signed in to change notification settings - Fork 1
/
main.py
110 lines (87 loc) · 2.65 KB
/
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
import random
from math import exp
import time
from copy import deepcopy
N_QUEENS = 500
TEMPERATURE = 4000
def threat_calculate(n):
'''Combination formular. It is choosing two queens in n queens'''
if n < 2:
return 0
if n == 2:
return 1
return (n - 1) * n / 2
def create_board(n):
'''Create a chess boad with a queen on a row'''
chess_board = {}
temp = list(range(n))
random.shuffle(temp) # shuffle to make sure it is random
column = 0
while len(temp) > 0:
row = random.choice(temp)
chess_board[column] = row
temp.remove(row)
column += 1
del temp
return chess_board
def cost(chess_board):
'''Calculate how many pairs of threaten queen'''
threat = 0
m_chessboard = {}
a_chessboard = {}
for column in chess_board:
temp_m = column - chess_board[column]
temp_a = column + chess_board[column]
if temp_m not in m_chessboard:
m_chessboard[temp_m] = 1
else:
m_chessboard[temp_m] += 1
if temp_a not in a_chessboard:
a_chessboard[temp_a] = 1
else:
a_chessboard[temp_a] += 1
for i in m_chessboard:
threat += threat_calculate(m_chessboard[i])
del m_chessboard
for i in a_chessboard:
threat += threat_calculate(a_chessboard[i])
del a_chessboard
return threat
def simulated_annealing():
'''Simulated Annealing'''
solution_found = False
answer = create_board(N_QUEENS)
# To avoid recounting when can not find a better state
cost_answer = cost(answer)
t = TEMPERATURE
sch = 0.99
while t > 0:
t *= sch
successor = deepcopy(answer)
while True:
index_1 = random.randrange(0, N_QUEENS - 1)
index_2 = random.randrange(0, N_QUEENS - 1)
if index_1 != index_2:
break
successor[index_1], successor[index_2] = successor[index_2], \
successor[index_1] # swap two chosen queens
delta = cost(successor) - cost_answer
if delta < 0 or random.uniform(0, 1) < exp(-delta / t):
answer = deepcopy(successor)
cost_answer = cost(answer)
if cost_answer == 0:
solution_found = True
print_chess_board(answer)
break
if solution_found is False:
print("Failed")
def print_chess_board(board):
'''Print the chess board'''
for column, row in board.items():
print("{} => {}".format(column, row))
def main():
start = time.time()
simulated_annealing()
print("Runtime in second:", time.time() - start)
if __name__ == "__main__":
main()