N-Queens

queens.py

from collections import namedtuple
from copy import deepcopy
from typing import List
from functools import partial

Point = namedtuple('Point', ['x', 'y'])


def check(p: Point, p_array: List[Point]):
    return all(map(partial(is_safe, p), p_array))


def is_safe(p1: Point, p2: Point):
    return not any(
        [
            p1.x == p2.x,  # same col
            p1.y == p2.y,  # same row
            (p1.x - p2.x) == (p1.y - p2.y),  # diagonal
            (p1.x - p2.y) == (p2.x - p1.y)  # diagonal
        ])


def all_positions(n):
    """
    [
     [(1,1), (1,2)],
     [(2,1), (2,2)],
    ]
    """
    rows = []
    for x in range(1, n + 1):
        row = []
        for y in range(1, n + 1):
            row.append(Point(x, y))
        rows.append(row)
    return rows


COUNT = 0


class Queens:
    def __init__(self, size):
        self.sols = []
        self.size = size

    def boards(self):
        return all_positions(self.size)

    def solve(self, ps: List[List[Point]], placed: List):
        if not ps:
            if len(placed) == self.size:
                self.sols.append(placed)
        else:
            for p in ps.pop(0):
                pss = deepcopy(ps)
                if placed is [] or check(p, placed):
                    self.solve(pss, placed + [p])

    def run(self):
        self.solve(self.boards(), [])


if __name__ == '__main__':
    q = Queens(size=8)
    q.run()
    print(q.sols)
    print(len(q.sols))