Version avec visu

from collections.abc import Iterable

from gturtle import *

def draw_chess_board(solution: Iterable[int], x: int = 0, y: int = 0, size: int = 50, color="black") -> tuple[int, int]:
    def square(cx, cy) -> None:
        setPos(cx - size / 2, cy - size / 2)
        for _ in range(4):
            fd(size)
            rt(90)

    def queen(cx, cy):
        setPos(cx, cy)
        dot(size * 0.7)

    hideTurtle()
    setPenColor(color)
    setFontSize(size)

    n = len(solution)

    for i in range(n):
        for j in range(n):
            cx = x + i * size - size / 2
            cy = y + j * size - size / 2
            square(cx, cy)
            if solution[i] == j:
                queen(cx, cy)

    setPos(x - size, y - 2 * size)
    setHeading(0)
    label("  ".join(str(q) if q is not None else '?' for q in solution))

    return n, size

def check_constraints(q: Iterable[int | None], last_queen: int) -> bool:
    j = last_queen
    for i in range(j):
        if q[i] == q[j]: return False
        if q[i] - q[j] == i - j: return False
        if q[j] - q[i] == i - j: return False

    return True

def dfs(queens: Iterable[int], index: int = 0, on_solution = None) -> None:
    n = len(queens)
    on_solution = on_solution or (lambda q: print(q))
    if index == n:
        # Si on parvient à une feuille, on tient une solution
        # Attention à faire une copie de la liste `queens`
        on_solution(queens[:])
    else:
        for i in range(n):
            queens[index] = i
            # print("board", queens)

            if check_constraints(queens, index):
                dfs(queens, index=index + 1, on_solution=on_solution)

def nqueens_solver(n: int, ms=150, wait: bool = False, size: int = 50) -> None:
    def next(ms=50, feasible=False):
        nonlocal stop_infeasible

        if feasible or not feasible and stop_infeasible:
            while True:
                key = getKeyWait()
                if key == 'i':
                    stop_infeasible = True
                    break
                elif key == 'f':
                    stop_infeasible = False
                    break
                else:
                    continue
        else:
            delay(ms)

    def on_solution(queens: Iterable[int]) -> None:
        clear()
        draw_chess_board(queens, x=0, y=0, size=size, color="green")
        next(ms=2000, feasible=True)

    def on_conflict(queens: Iterable[int]) -> None:
        clear()
        draw_chess_board(queens, x=0, y=0, size=size, color="red")
        next(ms=ms, feasible=False)

    def dfs(queens: Iterable[int], index: int = 0) -> None:
        n = len(queens)

        if index == n:
            # Si on parvient à une feuille, on tient une solution
            # Attention à faire une copie de la liste `queens`
            on_solution(queens[:])
        else:
            for i in range(n):
                queens[index] = i
                on_conflict(queens[:])
                if check_constraints(queens, index):
                    dfs(queens, index=index + 1)
                queens[index] = None

    stop_infeasible = True

    # Préparation du tableau utilisé pour représenter la solution
    queens = [None] * n

    # Générer tous les placements de dames imaginables
    # => feuilles de l'arbre de recherche

    dfs(queens)

if __name__ == '__main__':
    # solutions = nqueens_solver(n=4)
    solutions = nqueens_solver(n=8, ms=1, wait=True, size=20)

    # Dessiner une solution particulière
    # draw_chess_board([0, 3, 3, None], x=0, y=0, size=20, color="red")

    import doctest
    doctest.testmod()