Il problema delle otto regine è un noto rompicapo che consiste nel trovare il modo di posizionare correttamente otto regine su una scacchiera 8×8 tali che nessuna di esse possa catturarne un’altra, usando le regole standard di movimento del gioco degli scacchi.

Il codice Python seguente risolve il problema delle 8 regine in modo itertivo, stampando tutte le 92 soluzioni calcolate. L’ algoritmo e basato sulla tecnica del backtracking riassumibile nella seguente macchina a stati finiti:

Programma Python: stampa tutte le 92 soluzioni del problema

############################################################
import os

# Costanti globali
L = 8  # Numero di regine
X = [0] * (L+1)  # Vettore di stato (0-indexed, quindi da 0 a 8)
j = 0  # Contatore delle soluzioni


def q_place(k):
    # Verifica se la regina in posizione k sta al sicuro.
    b = True
    if k == 0:
        b = false
        return b
    else:
        for i in range(1, k):
            u = abs(i - k)
            v = abs(X[i] - X[k])
            if v == 0:  # Stessa colonna
                b = False
            if u == v:  # Stessa diagonale
                b = False
        return b


def write_x(fntxt=None):
    # Stampa la soluzione a video e, opzionalmente, la appende a un file.
    # Crea la stringa unendo i valori del vettore (convertiti in stringa)
    # Python usa la list comprehension per farlo in modo pulito
    rout = "".join(str(val + 1) for val in X)  # +1 per mostrare output 1-8 

    print(f"Soluzione {j + 1}: {rout}")

    # Se vuoi scrivere su file basta passare il percorso
    if fntxt:
        with open(fntxt, "a") as f:
            f.write(rout + "\n")
    return 0


def n_queens():
    global j, X
    # Inizializzazione del vettore di stato
    X = [0] * (L+1)
    k = 1  
    X[1] = 0
    j = 0

    while k > 0:
        X[k] = X[k] + 1

        # Ciclo di verifica per la posizione della regina
        while (X[k] <= L) and (not q_place(k)):
               X[k] = X[k] + 1

        
        # Verifica se siamo rimasti all'interno della scacchiera (<= L)
        #  X[k] in Python parte da 1 a L dentro la logica di controllo:
        if X[k] <= L:
            if k == L:  # Trovata una soluzione (ultimo indice)
                fs = "X.txt" # decommenta se vuoi salvare su un file specifico
                write_x(fs)
                j = j + 1
            else:
                k = k + 1
                X[k] = 0
                
        else:
            k = k - 1  # Backtrack

        # Limite di sicurezza a 100 soluzioni 
        if j == 100:
            break
       
    return j

r = n_queens()
#####################################################################