-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathchess_board_lib.py
190 lines (150 loc) · 6.03 KB
/
chess_board_lib.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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
# -*- coding: cp1252 -*-
"""Try Catch's Chess Challenge - Functions Library
Here are the helper functions used by the main process (chess_board_config.py)
to check if a chess board configuration is one where no piece threats another.
List of functions names:
find_configurations
valid_combination
threats
"""
import itertools
import time
def find_configurations(x_dim, y_dim, kings, queens, bishops, rooks,
knights, verbose):
"""Find and print all configurations for a chess board where no piece
threats another.
Keyword arguments:
x_dim -- Number of squares of the X dimension of the board
y_dim -- Number of squares of the Y dimension of the board
kings -- Number of Kings to be placed on the board
queens -- Number of Queens to be placed on the board
bishops -- Number of Bishops to be placed on the board
rooks -- Number of Rooks to be placed on the board
knights -- Number of Knights to be placed on the board
Returns the number of configurations found.
"""
# Set start time (for total elapsed time)
start_time = time.time()
# Create possible positions for every piece
iterators = []
for _ in range(queens):
iterators.append(itertools.product('Q', range(x_dim), range(y_dim)))
for _ in range(bishops):
iterators.append(itertools.product('B', range(x_dim), range(y_dim)))
for _ in range(rooks):
iterators.append(itertools.product('R', range(x_dim), range(y_dim)))
for _ in range(kings):
iterators.append(itertools.product('K', range(x_dim), range(y_dim)))
for _ in range(knights):
iterators.append(itertools.product('N', range(x_dim), range(y_dim)))
# Get combinations of first piece
piece_iter = iterators.pop(0)
# Loop to check all combinations of all pieces
comb_num = -1
while len(iterators) > 0:
sec_piece = iterators.pop(0)
combs = itertools.product(sec_piece, piece_iter)
valid_combs_list = set()
# Loop for these two pieces
for comb in combs:
is_valid, valid_comb = valid_combination(comb)
# If it's a valid combination
if is_valid:
if len(valid_combs_list) == 0:
valid_combs_list.add(valid_comb)
else:
# Don't include duplicates
if not is_duplicate(valid_comb, valid_combs_list):
valid_combs_list.add(valid_comb)
comb_num = len(valid_combs_list)
piece_iter = itertools.chain(valid_combs_list)
# Gets number of combinations if not set
if comb_num < 0:
comb_num = sum(1 for x in piece_iter)
if verbose:
# Set final combinations to print
final_combinations = piece_iter
print ''
print 'Combinations: '
# Print combinations
for elem in final_combinations:
print elem
# Set end time and print elapsed time
elapsed_time = time.time() - start_time
print ''
print 'Total elapsed time: {0} seconds'.format(elapsed_time)
return comb_num
def valid_combination(combination):
"""Check if a combination is one where no piece is threatened.
Keyword arguments:
combination -- Tuple with positions of pieces
Returns a boolean that tells if the combination is one where no piece is
threatened and the combination itself as a Tuple.
"""
first_piece = combination[0]
# If the rest is just one piece
if not isinstance(combination[1][0], tuple):
pieces = [combination[1]]
else:
pieces = list(combination[1])
return_combination = list(pieces)
return_combination.append(combination[0])
# Loop comparissons
while len(pieces) > 0:
for piece in pieces:
if threats(first_piece, piece):
return False, ()
if threats(piece, first_piece):
return False, ()
first_piece = pieces.pop(0)
# If there's no threat
return True, tuple(return_combination)
def threats(first_piece, second_piece):
"""Check if there's a threat between two pieces.
Keyword arguments:
first_piece -- Tuple with a piece type, x position and y position
second_piece -- Tuple with a piece type, x position and y position
Returns a boolean if one of the pieces threats the other.
"""
# Same position
if (first_piece[1] == second_piece[1] and
first_piece[2] == second_piece[2]):
return True
# Same column or line: Queens and Rooks
if first_piece[0] in ('Q', 'R'):
if (first_piece[1] == second_piece[1] or
first_piece[2] == second_piece[2]):
return True
# Diagonal: Queens and Bishops
if first_piece[0] in ('Q', 'B'):
if (abs(second_piece[1] - first_piece[1]) ==
abs(second_piece[2] - first_piece[2])):
return True
# King
if first_piece[0] == 'K':
if (abs(second_piece[1] - first_piece[1]) in (0, 1) and
abs(second_piece[2] - first_piece[2]) in (0, 1)):
return True
# Knight
if first_piece[0] == 'N':
if ((abs(second_piece[1] - first_piece[1]) == 2 and
abs(second_piece[2] - first_piece[2]) == 1) or
(abs(second_piece[1] - first_piece[1]) == 1 and
abs(second_piece[2] - first_piece[2]) == 2)):
return True
def is_duplicate(combination, list_of_combinations):
"""Check if a combination exists in a list of combinations.
Keyword arguments:
combination -- Tuple with positions of pieces
list_of_combinations -- List of Tuples with positions of pieces
Returns True if the combination is contained in the list, False otherwise.
"""
is_contained = False
# Create permutations of the combination
check_combs = itertools.permutations(combination, len(combination))
# Check if any permutation is contained in the list
for check_comb in check_combs:
if check_comb in list_of_combinations:
is_contained = True
break
return is_contained