|
1
|
|
|
from copy import deepcopy |
|
2
|
|
|
from itertools import combinations |
|
3
|
|
|
|
|
4
|
|
|
|
|
5
|
|
|
COLS = "abcdefgh" |
|
6
|
|
|
ROWS = "12345678" |
|
7
|
|
|
THREATS = { |
|
8
|
|
|
c |
|
9
|
|
|
+ r: set( |
|
10
|
|
|
[c + ROWS[k] for k in range(8)] |
|
11
|
|
|
+ [COLS[k] + r for k in range(8)] |
|
12
|
|
|
+ [COLS[k] + ROWS[i - j + k] for k in range(8) if 0 <= i - j + k < 8] |
|
13
|
|
|
+ [COLS[k] + ROWS[-k + i + j] for k in range(8) if 0 <= -k + i + j < 8] |
|
14
|
|
|
) |
|
15
|
|
|
for i, r in enumerate(ROWS) |
|
16
|
|
|
for j, c in enumerate(COLS) |
|
17
|
|
|
} |
|
18
|
|
|
|
|
19
|
|
|
|
|
20
|
|
|
def checkAvailablePosition(board, placed): |
|
21
|
|
|
tempBoard = deepcopy(board) |
|
22
|
|
|
for i in placed: |
|
23
|
|
|
if i not in tempBoard: |
|
24
|
|
|
tempBoard = [] |
|
25
|
|
|
break |
|
26
|
|
|
threats = sorted(THREATS[i]) |
|
27
|
|
|
tempBoard = [j for j in tempBoard if j not in threats] |
|
28
|
|
|
return tempBoard |
|
29
|
|
|
|
|
30
|
|
|
|
|
31
|
|
|
def place_queens(placed): |
|
32
|
|
|
board = [c + r for c in COLS for r in ROWS] |
|
33
|
|
|
availablePositions = checkAvailablePosition(board, placed) |
|
34
|
|
|
# print availablePositions |
|
35
|
|
|
remainedQueens = 8 - len(placed) |
|
36
|
|
|
queenPositionCombinations = [ |
|
37
|
|
|
i for i in combinations(availablePositions, remainedQueens) |
|
38
|
|
|
] |
|
39
|
|
|
# print len(queenPositionCombinations) |
|
40
|
|
|
for position in queenPositionCombinations: |
|
41
|
|
|
colIndicators = set([i[0] for i in position] + [i[0] for i in placed]) |
|
42
|
|
|
if len(colIndicators) < 8: |
|
43
|
|
|
continue |
|
44
|
|
|
rowIndicators = set([i[1] for i in position] + [i[1] for i in placed]) |
|
45
|
|
|
if len(rowIndicators) < 8: |
|
46
|
|
|
continue |
|
47
|
|
|
i = list(position) |
|
48
|
|
|
tempPositions = deepcopy(availablePositions) |
|
49
|
|
|
while True: |
|
50
|
|
|
if len(i) == 1 and i[0] not in tempPositions: |
|
51
|
|
|
break |
|
52
|
|
|
queen = i.pop() |
|
53
|
|
|
tempPositions = checkAvailablePosition(tempPositions, [queen]) |
|
54
|
|
|
if not tempPositions: |
|
55
|
|
|
break |
|
56
|
|
|
# i is empty means all queen can be positioned |
|
57
|
|
|
if not i: |
|
58
|
|
|
return set(list(placed) + list(position)) |
|
59
|
|
|
return set({}) |
|
60
|
|
|
|
|
61
|
|
|
|
|
62
|
|
|
if __name__ == '__main__': |
|
63
|
|
|
# These "asserts" using only for self-checking and not necessary for |
|
64
|
|
|
# auto-testing |
|
65
|
|
|
def check_coordinate(coor): |
|
66
|
|
|
c, r = coor |
|
67
|
|
|
return c in COLS and r in ROWS |
|
68
|
|
|
|
|
69
|
|
View Code Duplication |
def checker(func, placed, is_possible): |
|
|
|
|
|
|
70
|
|
|
user_set = func(placed.copy()) |
|
71
|
|
|
if not all( |
|
72
|
|
|
isinstance(c, str) and len(c) == 2 and check_coordinate(c) for c in user_set |
|
73
|
|
|
): |
|
74
|
|
|
print("Wrong Coordinates") |
|
75
|
|
|
return False |
|
76
|
|
|
threats = [] |
|
77
|
|
|
for f, s in combinations(user_set.union(placed), 2): |
|
78
|
|
|
if s in THREATS[f]: |
|
79
|
|
|
threats.append([f, s]) |
|
80
|
|
|
if not is_possible: |
|
81
|
|
|
if user_set: |
|
82
|
|
|
print("Hm, how did you place them?") |
|
83
|
|
|
return False |
|
84
|
|
|
else: |
|
85
|
|
|
return True |
|
86
|
|
|
if not all(p in user_set for p in placed): |
|
87
|
|
|
print("You forgot about placed queens.") |
|
88
|
|
|
return False |
|
89
|
|
|
if is_possible and threats: |
|
90
|
|
|
print("I see some problems in this placement.") |
|
91
|
|
|
return False |
|
92
|
|
|
return True |
|
93
|
|
|
|
|
94
|
|
|
assert checker(place_queens, {"b2", "c4", "d6", "e8"}, True), "1st Example" |
|
95
|
|
|
assert checker( |
|
96
|
|
|
place_queens, {"b2", "c4", "d6", "e8", "a7", "g5"}, False |
|
97
|
|
|
), "2nd Example" |
|
98
|
|
|
|
KenMercusLai /
checkio
Loading history...