-
Notifications
You must be signed in to change notification settings - Fork 39
/
solution_38.py
31 lines (25 loc) · 1.43 KB
/
solution_38.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
def coding_problem_38(n):
"""
You have an N by N board. Write a function that, given N, returns the number of possible arrangements of the board
where N queens can be placed on the board without threatening each other, i.e. no two queens share the same row,
column, or diagonal. The following are the first 7 terms of the sequence (from [Wikipedia's
https://en.wikipedia.org/wiki/Eight_queens_puzzle page):
>>> [coding_problem_38(n + 1) for n in range(7)]
[1, 0, 0, 2, 10, 4, 40]
Note: could be made faster by passing only valid coordinates instead of all of them each time.
"""
def is_threat(new_queen, board_arrangement):
for already_placed in board_arrangement:
if new_queen[0] == already_placed[0] or new_queen[1] == already_placed[1] or \
abs(new_queen[0] - already_placed[0]) == abs(new_queen[1] - already_placed[1]):
return True
return False # otherwise
all_coordinates = [(i, j) for i in range(n) for j in range(n)]
valid_arrangements = {frozenset()} # set for duplicate removal, empty initial arrangement
for _ in range(n):
valid_arrangements = set(arrangement.union([coord]) for arrangement in valid_arrangements
for coord in all_coordinates if not is_threat(coord, arrangement))
return len(valid_arrangements)
if __name__ == '__main__':
import doctest
doctest.testmod(verbose=True)