# Per aumentare il limite di ricorsione per problemi più grandi #import sys #sys.setrecursionlimit(10000) class Column: """ Rappresenta sia un header di colonna che un nodo generico nella matrice sparsa. Ogni nodo è collegato in 4 direzioni (up, down, left, right), creando liste doppiamente concatenate circolari sia per le righe che per le colonne. """ def __init__(self, name=""): self.name = name self.left = self.right = self.up = self.down = self self.column_header = self self.size = 0 # Usato solo dagli header di colonna def __str__(self): return f"Node({self.name})" class ExactCoverSolver: """ Risolve il problema della copertura esatta usando l'Algorithm X di Knuth con l'implementazione Dancing Links (DLX). """ def __init__(self, universe, subsets): self.subsets = subsets self.solutions = [] self._build_matrix(universe, subsets) def _build_matrix(self, universe, subsets): """ Costruisce la struttura dati toroidale con liste doppiamente concatenate. """ self.root = Column("root") # Crea gli header delle colonne columns = [] for element in universe: col_header = Column(name=str(element)) columns.append(col_header) # Collega l'header alla lista circolare degli header col_header.right = self.root col_header.left = self.root.left self.root.left.right = col_header self.root.left = col_header # Itera sui sottoinsiemi (righe) per aggiungere i nodi for subset_name, subset_elements in subsets.items(): first_node_in_row = None for element in subset_elements: col_header = columns[element] col_header.size += 1 new_node = Column(name=f"{subset_name}:{element}") new_node.column_header = col_header # Inserisci il nuovo nodo nella lista verticale della colonna new_node.down = col_header new_node.up = col_header.up col_header.up.down = new_node col_header.up = new_node # Inserisci il nuovo nodo nella lista orizzontale della riga if first_node_in_row is None: first_node_in_row = new_node else: new_node.right = first_node_in_row new_node.left = first_node_in_row.left first_node_in_row.left.right = new_node first_node_in_row.left = new_node def solve(self): """Avvia la ricerca delle soluzioni.""" self.solutions = [] self._search([]) return self.solutions def _select_column(self): """Sceglie la colonna con il minor numero di '1' (euristica S).""" min_size = float('inf') best_col = None current = self.root.right while current != self.root: if current.size < min_size: min_size = current.size best_col = current current = current.right return best_col def _cover(self, column): """ "Copre" una colonna: la rimuove dalla lista degli header e rimuove tutte le righe che si trovano in essa dalle altre colonne. """ # Rimuove la colonna dalla lista degli header column.right.left = column.left column.left.right = column.right # Itera su tutte le righe della colonna row_node = column.down while row_node != column: # Itera su tutti i nodi della riga node_in_row = row_node.right while node_in_row != row_node: # Rimuovi il nodo dalla sua colonna node_in_row.down.up = node_in_row.up node_in_row.up.down = node_in_row.down node_in_row.column_header.size -= 1 node_in_row = node_in_row.right row_node = row_node.down def _uncover(self, column): """ "Scopre" una colonna: annulla le operazioni di _cover in ordine inverso. """ # Itera su tutte le righe della colonna (in ordine inverso) row_node = column.up while row_node != column: # Itera su tutti i nodi della riga (in ordine inverso) node_in_row = row_node.left while node_in_row != row_node: # Reinserisci il nodo nella sua colonna node_in_row.column_header.size += 1 node_in_row.down.up = node_in_row node_in_row.up.down = node_in_row node_in_row = node_in_row.left row_node = row_node.up # Reinserisce la colonna nella lista degli header column.right.left = column column.left.right = column def _search(self, partial_solution): """La funzione ricorsiva di backtracking che implementa l'Algorithm X.""" # Se la matrice è vuota, abbiamo trovato una soluzione if self.root.right == self.root: self.solutions.append(list(partial_solution)) return # 1. Scegli una colonna c column_to_cover = self._select_column() # Se una colonna ha dimensione 0, non può essere coperta. Backtrack. if column_to_cover.size == 0: return self._cover(column_to_cover) # 2. Per ogni riga r in c... row_node = column_to_cover.down while row_node != column_to_cover: # Aggiungi il nome del sottoinsieme alla soluzione parziale subset_name = row_node.name.split(':')[0] partial_solution.append(subset_name) # Copri tutte le altre colonne toccate da questa riga node_in_row = row_node.right while node_in_row != row_node: self._cover(node_in_row.column_header) node_in_row = node_in_row.right # 3. Ricorsione self._search(partial_solution) # --- BACKTRACK --- # Rimuovi la riga dalla soluzione parziale partial_solution.pop() # Scopri le colonne in ordine inverso node_in_row = row_node.left while node_in_row != row_node: self._uncover(node_in_row.column_header) node_in_row = node_in_row.left row_node = row_node.down self._uncover(column_to_cover) U = list(range(7)) S = { 'A': [0, 3, 6], 'B': [0, 3], 'C': [3, 4, 6], 'D': [2, 4, 5], 'E': [1, 2, 5, 6], 'F': [1, 6], } print("Risoluzione del problema di Copertura Esatta:") print("Universo:", U) print("Sottoinsiemi:", S) print("-" * 30) solver = ExactCoverSolver(U, S) solutions = solver.solve() if solutions: print(f"Trovate {len(solutions)} soluzioni:") for i, sol in enumerate(solutions): print(f"Soluzione {i+1}: {sorted(sol)}") else: print("Nessuna soluzione trovata.")

Risoluzione del problema di Copertura Esatta: Universo: [0, 1, 2, 3, 4, 5, 6] Sottoinsiemi: {'A': [0, 3, 6], 'B': [0, 3], 'C': [3, 4, 6], 'D': [2, 4, 5], 'E': [1, 2, 5, 6], 'F': [1, 6]} ------------------------------ Trovate 1 soluzioni: Soluzione 1: ['B', 'D', 'F']