Source code for hal.maths.problems
# -*- coding: utf-8 -*-
"""Useful problems """
[docs]class EightQueen:
"""8 queen problem solver"""
def __init__(self, board_size):
self.board_size = board_size
[docs] @staticmethod
def under_attack(col, queens):
"""Checks if queen is under attack
:param col: Column number
:param queens: list of queens
:return: True iff queen is under attack
"""
left = right = col
for _, column in reversed(queens):
left, right = left - 1, right + 1
if column in (left, col, right):
return True
return False
[docs] def solve(self, table_size):
"""Solves problem
:param table_size: Size of table
:return: List of possible solutions
"""
if table_size == 0:
return [[]]
smaller_solutions = self.solve(table_size - 1)
solutions = []
for solution in smaller_solutions:
for column in range(1, self.board_size + 1):
# try adding a new queen to row = n, column = column
if not self.under_attack(column, solution):
solutions.append(solution + [(table_size, column)])
return solutions