-
Notifications
You must be signed in to change notification settings - Fork 0
/
Game.py
101 lines (76 loc) · 2.58 KB
/
Game.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
# File: Game.py
# Authors: Alejandro Cirugeda & Juancarlos Quintana
# Description:
#
#
from queue import PriorityQueue
from Node import Node
class Game:
def __init__(self):
self.initial_state = None
self.list_games = []
self.list_solutions = []
# we should save different games with different number of rows and different number of blank spaces
return
def add_game(self, initial_game_state):
self.list_games.append(initial_game_state)
def add_solution(self, solution):
self.list_solutions.append(solution)
def print_game(self, index):
print("Initial state:")
print (self.list_games[index])
print("Solution")
print (self.list_solutions[index])
def breadth_first_search(root, solution):
nodes_visited = 0
queue = [] # we will store all the nodes that we didnt visit yet
queue.append(root)
while queue:
node = queue.pop(0)
nodes_visited += 1
if node.state == solution:
return nodes_visited
else :
queue.append(node.left_child)
queue.append(node.right_child)
print("Queue empty, solution not found")
return -1
def A_search(root, solution):
nodes_visited = 0
priority = []
priority.append((1, root))
while len(priority):
min_value = priority[0][0]
min_index = 0
for i in range(0, len(priority)):
if priority[i][0] < min_value:
min_value = priority[i][0]
min_index = i
tupla = priority.pop(min_index)
node = tupla[1]
nodes_visited += 1
if(node.state == solution):
return nodes_visited
right_child = node.right_child
left_child = node.left_child
if not (left_child == None):
value = g_fution(left_child) + heuristic(left_child, solution)
#print("Value = " + str(value))
priority.append((value, left_child))
value = g_fution(right_child) + heuristic(right_child, solution)
priority.append((value, right_child))
print("Queue empty, solution not found")
return -1
# Heuristic function
# Heursitic function will compare the actual state with the solution and count
# the numer of errors
def heuristic(node, solution):
err_counter = 0
lenght = len(node.state)
for i in range(0, lenght):
for j in range(0, lenght):
if(node.state[i][j] != solution[i][j]):
err_counter += 1
return err_counter
def g_fution(node):
return node.depth