forked from iiitv/algos
-
Notifications
You must be signed in to change notification settings - Fork 0
/
n_queen_problem.py
76 lines (60 loc) · 2.09 KB
/
n_queen_problem.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
"""
Following code is the implementation of the N-queen problem.
The solution is to place the queens on board such that
no queen is under attack by another queen.
This implementation computes all solutions for a board,
then prints the number of solutions. The number of solutions
follows the OEIS sequence https://oeis.org/A000170.
"""
def is_queen_under_attack(col, queens):
"""
:param col: int
Column of queen to test
:param queens: list of tuple of int
List of coordinates of other queens
:return: boolean
True if and only if queen in given position is under attack
"""
left = right = col
for coords in reversed(queens):
left, right = left - 1, right + 1
if coords[1] in (left, col, right):
return True
return False
def get_solutions(board_size, queens):
"""
:param board_size: int
Size of board to solve
:param queens: int
Number of queens to place in board
:return: list of list of tuple of int
Finds solutions of problem
"""
smaller_solutions = n_queen_problem(board_size, queens - 1)
solutions = []
for solution in smaller_solutions:
for column in range(1, board_size + 1):
if not is_queen_under_attack(column, solution):
solutions.append(solution + [(queens, column)])
return solutions
def n_queen_problem(board_size, queens):
"""
:param board_size: int
Size of board to solve
:param queens: int
Number of queens to place in board
:return: list of list of tuple of int
Each list contains the coordinates of the queens
that solve the problem
"""
if queens < 1: # there are no queens to place
return [[]] # 1 solution only: not place any queen
if queens > board_size: # more queens than the board can contain
return [] # pigeonhole principle -> 0 solutions
return get_solutions(board_size, queens)
def main():
board_size = 10
solutions = n_queen_problem(board_size, board_size)
print(len(solutions))
if __name__ == '__main__':
main()