<jupyter_start><jupyter_text>Of primes and queens  Primes Load the relevant modules.<jupyter_code>import itertools
from math import sqrt<jupyter_output><empty_output><jupyter_text>Define a function that checks whether a positive integer is prime.<jupyter_code>def is_prime(n):
    return all(map(lambda divisor: n % divisor != 0, range(2, round(sqrt(n)) + 1))) and n > 1<jupyter_output><empty_output><jupyter_text>Test the function.<jupyter_code>for n in range(50):
    if is_prime(n):
        print(f'{n} is prime')<jupyter_output><empty_output><jupyter_text>Iterator Define an iterator that returns all prime numbers.<jupyter_code>class Primes:
    
    def __init__(self):
        self._n = 1
        
    def __iter__(self):
        return self
    
    def __next__(self):
        self._n += 1
        while not is_prime(self._n):
            self._n += 1
        return self._n
nr_primes = 0
for prime in Primes():
    if nr_primes == 10:
        break
    print(prime)
    nr_primes += 1<jupyter_output><empty_output><jupyter_text>Generator function Define a function using `yield`.  The function will resume after the yielded value has been consumed in the calling context.<jupyter_code>def primes():
    n = 2
    while True:
        if is_prime(n):
            yield n
        n += 1    
nr_primes = 0
for prime in primes():
    if nr_primes == 10:
        break
    print(prime)
    nr_primes += 1<jupyter_output><empty_output><jupyter_text>Note that the state of the function is preserved between calls, hence retaining state.  Generator However, things can be even simpler in Python by simply using a generator expression.<jupyter_code>for i, prime in enumerate(p for p in range(10000000) if is_prime(p)):
    print(prime)
    if i == 9:
        break<jupyter_output><empty_output><jupyter_text>Although this is really short, it is also a bit unelegant since the number to range over has to be guessed.  itertools The `itertools` module provides many (composable) iterators.<jupyter_code>for i, prime in enumerate(p for p in itertools.count(2) if is_prime(p)):
    print(prime)
    if i == 9:
        break<jupyter_output><empty_output><jupyter_text>It is beyond the scope of this presentation to introduce `itertools` in depth, but it is very much worth exploring.  $N$ queens Load the relevant modules.<jupyter_code>import matplotlib.pyplot as plt
%matplotlib inline
import numpy as np
import sys<jupyter_output><empty_output><jupyter_text>Consider an $N \times N$ chess board.  We want to place $N$ queens on that board such that none of them can take any of the other $N - 1$ queens. Note that the usual implementation is uses backtracking explicitly, and requires quite some coding to keep track of the options that have already been explored and those that remain to be checked.  Using `yield` to define a generator allows you to simply program a recursive solution. Define a function that creates an empty $N \times N$ board. A board is represented as a numpy array, a 0 element represents an empty position on the board, while 1 indicates a queen has been placed on the corresponding square.<jupyter_code>def create_board(N):
    return np.zeros((N, N), dtype=np.int)<jupyter_output><empty_output><jupyter_text>Define a function that checks whether a given row and column are a safe position to place a queen.<jupyter_code>def is_safe_position(board, row, col):
    # check column
    if np.any(board[:row, col]):
        return False
    # row is okay by construction
    N = board.shape[0]
    # check principal diagonal
    for i, j in zip(range(max((0, row - col)), min((N + row - col, N))),
                    range(max((0, col - row)), min((N + col - row, N)))):
        if board[i, j]:
            return False
    # check minor diagonal
    for i, j in zip(range(min((row + col, N - 1)), max((-1, col + row - N - 1)), -1),
                    range(max((0, col + row - N + 1)), min((row + col + 1, N)))):
        if board[i, j]:
            return False
    return True<jupyter_output><empty_output><jupyter_text>Note, the function above can be made more efficient since only the upper part of the board should be checked. Define a function that returns all valid placements of $N$ queens.<jupyter_code>def place_queens(board, row=0):
    if row == board.shape[0]:
        yield board
    else:
        for col in range(0, board.shape[1]):
            if is_safe_position(board, row, col):
                board[row, col] = 1
                yield from place_queens(board, row + 1)
                board[row, col] = 0<jupyter_output><empty_output><jupyter_text>Define a function to visualize a board.<jupyter_code>def vis_board(board):
    N = board.shape[0]
    plt.imshow(board, aspect='equal', interpolation='none', extent=(0, N, 0, N))
    plt.xticks(range(N))
    plt.yticks(range(N))
    plt.grid(True, color='r', linestyle='-', linewidth=1);<jupyter_output><empty_output><jupyter_text>For a $3 \times 3$ board, there are no solutions.<jupyter_code>board = create_board(3)
for solution in place_queens(board):
    vis_board(solution)
    plt.show()<jupyter_output><empty_output><jupyter_text>For a $4 \times 4$ board, there are two solutions.<jupyter_code>board = create_board(4)
for solution in place_queens(board):
    vis_board(solution)
    plt.show()<jupyter_output><empty_output><jupyter_text>More solutions can be found for a $5 \times 5$ board.  In fact, this can be seen as finding a solution for five $4 \tmies 4$ boards.<jupyter_code>board = create_board(5)
for solution in place_queens(board):
    vis_board(solution)
    plt.show()<jupyter_output><empty_output><jupyter_text>Compute the number of solutions for successive board sizes.<jupyter_code>for N in range(1, 11):
    nr_solutions = 0
    board = create_board(N)
    for _ in place_queens(board):
        nr_solutions += 1
    print(f'{N} x {N}: {nr_solutions}')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09952526280094948, 'fraction_numerical': 0.01186842997626314, 'mean_word_length': 3.696656050955414, 'pattern_counts': {'":': 0, '<': 65, '<?xml version=': 0, '>': 66, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '16', 'dir': 'jupyter-structured-clean-dedup', 'id': '88423', 'license': 'CC-BY-4.0', 'n_tokens_mistral': 1926, 'n_tokens_neox': 1852, 'n_words': 640, 'path': 'Python/Fundamentals/of_primes_and_queens.ipynb', 'repo_name': 'Abd-Elrazek/training-material', 'size': '5898'}