-
Notifications
You must be signed in to change notification settings - Fork 0
/
warnsdorff.py
132 lines (101 loc) · 3.69 KB
/
warnsdorff.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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
import numpy as np
class Warnsdorf():
'''
Клас для розв'язання задачі
"Хід конем" за Правилом Вансдорфа
'''
EMPTY = 0
VISITED = 1
KNIGHT = 7
MOVES = (
(2, 1), (-2, -1), (-2, 1), (2, -1),
(1, 2), (-1, -2), (-1, 2), (1, -2)
)
def __init__(self, board_size, knight_pos):
self.chessboard = np.zeros(board_size)
self.knight_pos = knight_pos
self.chessboard[knight_pos] = self.KNIGHT
self.chessboard_path = np.zeros(board_size)
self.move_number = 0
self.has_next_move = True
def solve(self):
'''
Знаходить розв'язок
Повертає кортеж з трьох елементів:
- результуюча шахівниця
- шлях
- True, якщо вся шахівниця відвідана, інакше False
'''
while self.__has_next():
_ = self.__next()
return (
self.chessboard,
self.chessboard_path,
self.__is_all_visited()
)
def __is_all_visited(self):
'''
Перевіряє, чи всі клітинки відвідані
'''
return not self.EMPTY in self.chessboard
def __has_next(self):
'''
Перевіряє, чи є наступний хід
'''
return self.has_next_move
def __next(self):
'''
Повертає наступний хід
'''
moves = self.__find_moves(self.knight_pos)
self.chessboard[self.knight_pos] = self.VISITED
next_cell = self.__find_next_cell(moves)
self.chessboard_path[(self.knight_pos)] = self.move_number
self.move_number += 1
if next_cell is None:
self.chessboard[self.knight_pos] = self.KNIGHT
self.has_next_move = False
else:
self.knight_pos = next_cell
self.chessboard[next_cell] = self.KNIGHT
return next_cell
def __find_moves(self, start_pos):
'''
Повертає координати можливих ходів
'''
legal_moves = []
for move in self.MOVES:
new_cell = (
start_pos[0] + move[0],
start_pos[1] + move[1],
)
if self.__is_cell_legal(new_cell):
legal_moves.append(new_cell)
return legal_moves
def __find_next_cell(self, cells):
'''
Серед ходів знаходить той,
що має найменше можливих майбутніх ходів
'''
weight = float('inf')
index = None
for i, cell in enumerate(cells):
new_weight = len(self.__find_moves(cell))
if new_weight < weight:
weight = new_weight
index = i
if index == None:
return None
return cells[index]
def __is_cell_legal(self, cell):
'''
Перевіряє, чи клітинка відвідана та
чи не виходить за межі шахівниці
'''
if cell[0] < 0 or cell[1] < 0:
return False
if cell[0] > len(self.chessboard[0]) - 1 or cell[1] > len(self.chessboard) - 1:
return False
if self.chessboard[cell] == self.VISITED:
return False
return True