-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathdfs_back.py
93 lines (75 loc) · 3.32 KB
/
dfs_back.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
from state import map_state
import state as maf
import numpy as np
import queue as queue
def dfs(state, visited=None, max_depth=100, path=None):
if visited is None:
visited = set()
if path is None:
path = np.array([])
path = np.array([state.parent])
for item_state in visited:
if maf.my_equals.equals(item_state, state):
# if (item_state.parent != state.parent):
return False, path[:path.size-1], []
visited.add(state)
if state.you_win():
len_visited = len(visited)
return True, path, len_visited
if max_depth <= 0:
return False, None
for next_state in state.all_next_state_move():
if next_state not in visited:
len_visited = len(visited)
path = np.append(path, next_state.parent)
if (next_state.you_win() == True):
print("%"*20)
len_visited = len(visited)
return True, path, len_visited
if maf.my_equals.equals(next_state, state) == False:
found, path, len_visited = dfs(next_state, visited,
(max_depth - 1), path)
if found:
return found, path, len_visited
return False, path, []
initial_state = maf. map_state(11)
initial_state.parent = "root"
initial_state.printer(1, 1, "black", "⬛️", False, False)
initial_state.printer(1, 6, "black", "⬛️", False, False)
initial_state.printer(1, 5, "black", "⬛️", False, False)
initial_state.printer(1, 7, "black", "⬛️", False, False)
initial_state.printer(2, 5, "black", "⬛️", False, False)
initial_state.printer(1, 8, "black", "⬛️", False, False)
initial_state.printer(1, 9, "black", "⬛️", False, False)
initial_state.printer(2, 6, "black", "⬛️", False, False)
initial_state.printer(2, 9, "black", "⬛️", False, False)
initial_state.printer(3, 9, "black", "⬛️", False, False)
initial_state.printer(5, 9, "black", "⬛️", False, False)
initial_state.printer(6, 1, "black", "⬛️", False, False)
initial_state.printer(6, 4, "black", "⬛️", False, False)
initial_state.printer(6, 5, "black", "⬛️", False, False)
initial_state.printer(6, 6, "black", "⬛️", False, False)
initial_state.printer(6, 7, "black", "⬛️", False, False)
initial_state.printer(6, 8, "black", "⬛️", False, False)
initial_state.printer(6, 9, "black", "⬛️", False, False)
initial_state.printer(7, 1, "black", "⬛️", False, False)
initial_state.printer(7, 2, "black", "⬛️", False, False)
initial_state.printer(7, 3, "black", "⬛️", False, False)
initial_state.printer(7, 4, "black", "⬛️", False, False)
initial_state.printer(4, 4, "black", "⬛️", False, False)
initial_state.printer(4, 6, "black", "⬛️", False, False)
initial_state.printer(4, 5, "black", "⬛️", False, False)
initial_state.printer(4, 9, "red", "🔴", True, False)
initial_state.printer(1, 2, "red", "🟥", False, False)
initial_state.printer(2, 7, "blue", "🔵", True, False)
initial_state.printer(6, 2, "blue", "🟦", False, False)
initial_state.print_map()
found, path, len_visited = dfs(initial_state)
if found:
print("تم العثور على حل!")
print("خطوات الحل:")
print(path)
print(len(path))
print(len_visited)
else:
print("لم يتم العثور على حل.")