n_queens.py

# Implement the N-Queens Algorithm

# The N-Queens problem asks you to place N queens on an N×N chessboard so that no two queens attack each other (no two share a row, column, or diagonal).

# For example, if there is a 4x4 board, one valid arrangement is:

# [1, 3, 0, 2]

# That means that in row 0, the queen is placed in column 1; in row 1, the queen is placed in column 3; in row 2, the queen is placed in column 0; and in row 3, the queen is placed in column 2.

# Visually, this arrangement looks like:

# . Q . .
# . . . Q
# Q . . .
# . . Q .

# Where Q represents a queen and . represents an empty square.

# In this lab, you will implement the N-Queens problem solver using the depth-first search approach.

# Objective: Fulfill the user stories below and get all the tests to pass to complete the lab.

# User Stories:

#     You should have a function named dfs_n_queens.
#     The function should accept exactly one argument: an integer n.
#     If n is less than 1, the function should return an empty list ([]).
#     The function should return a list of solutions; each solution is itself a list of length n, where the element at index i is the column index (0-based) of the queen in row i.


def dfs_n_queens(n: int) -> list[list[int]]:
    """
    Resolution du problème des n reines pour une
    grille de taille n x n, en utilisant dfs
    :param n: la taille de la grille
    """
    # Validation
    if n < 1:
        return []
    if n == 1:
        return [[0]]

    # Liste des solutions trouvées
    soluce: list[list[int]] = []

    # Utilistaire pour obtenir les diagonales
    DIAGONALES = [-1,1]
    get_dangerous_pos = lambda cur, col: {
        y + (col - x) * signe
        for x, y in enumerate(cur)
        for signe in DIAGONALES
        if 0 <= y + (col - x) * signe < n
    }|set(cur)
    # Point de départ par défaut
    start = 0

    # On boucle sur toute les cases de la première colonne
    # Pour chaque case de départ, on établis une liste de solutions
    # Pour chaque case valide de la solution actuelle on on établis une liste des coups possibles
    # Backtracking se fera grâce à un dictionnaire des coups autorisés qui sera
    # mis à jour après chaque colonne

    while start < n:
        print(" Nouvelle Itération. Start: ", start)
        # Configuration actuelle de l'échiquier
        current: list[int] = []
        print("Current: ", current)
        # Colonne actuelle sur l'échiquier
        column = 0

        # Ensemble des positions verticale non autorisées dans la colonne col
        not_allowed: set[int] = get_dangerous_pos(current, column)
        print("Position non valides: ", not_allowed)
        # Liste des Cases valides à visiter par colones
        to_visit: list[list[int]] = [[] for _ in range(n)]
        to_visit[0] = [start]
        print("A visiter: ", to_visit)
        # On teste si la case est valide
        # Pour qu'il n'y ait pas de problème à l'horizontale
        # il faut que chaque reine soit sur une ligne unique
        # i.e la liste not_allowed marque l'index horizontale de chaque
        # reine. Pour les diagonales gauche et droite, on decrement et increment
        # respectivement l'index de la case

        # On continue d'itérer sur les colones jusqu'à obtenir une solution
        while len(current) != n:
            print("C'est repartie !!")
            # Condition d'arrêt: plus aucune case à visiter
            if not any(len(l) > 0 for l in to_visit):
                # Deadend. On change de point de départ
                print("Impasse atteinte: ", to_visit)
                break

            # Mecanisme de backtracking
            if not to_visit[column]:
                if column == 0:
                    break
                print(f"Backtracking from column {column} to {column - 1}")
                current.pop()
                to_visit[column] = []
                column -= 1
                continue

            #  Pose un piece sur l'une des cases dispo
            current.append(to_visit[column].pop())
            print("Nouvelle piece posée: ", current)

            if len(current) == n:
                print("Success !")
                soluce.append(list(current))
                current.pop()
                continue

            next_column: int = column + 1
            not_allowed = get_dangerous_pos(current, next_column)
            print("MAJ des positions non valides: ", not_allowed)

            # On recense les cases valides de la prochaine colonne
            to_visit[next_column] = [row for row in range(n) if row not in not_allowed]
            print("Reste à visiter ensuite: ", to_visit)

            # Si aucune case n'est valide, on backtrack
            if not to_visit[next_column]:
                # On retire la dernière pièce ajoutée à l'échiquier
                current.pop()
                print("Aucune case valide dans ", next_column, "...Bactracking")
                continue

            column += 1
            print("On passe à la column: ", column, "Current = ", current)
        print("Nouvelle solution: ", current)
        start += 1
        print("Fin du tour sur ", start, "\nSoluce: ", soluce)
    return soluce

if __name__ == "__main__":
    print(dfs_n_queens(5))