https://en.wikipedia.org/wiki/Exact_cover
https://arxiv.org/abs/cs/0011047
Dancing links, Donald E. Knuth.
Problem dokładnego pokrycia zbioru (the exact cover problem) może być określony abstrakcyjnie następująco [Knuth, Dancing links]: Jeżeli dana jest macierz zer i jedynek, to czy posiada ona zbiór wierszy zawierający dokładnie jedną 1 w każdej kolumnie? Przykładowo macierz A poniżej posiada taki zbiór (wiersze 1, 4, 5).
+----------+---------------+ | Kolumna | A B C D E F G | +----------+---------------+ | Wiersz 1 | 0 0 1 0 1 1 0 | * | Wiersz 2 | 1 0 0 1 0 0 1 | | Wiersz 3 | 0 1 1 0 0 1 0 | | Wiersz 4 | 1 0 0 1 0 0 0 | * | Wiersz 5 | 0 1 0 0 0 0 1 | * | Wiersz 6 | 0 0 0 1 1 0 1 | +----------+---------------+
Można też patrzeć na kolumny jak na przestrzeń, a na wiersze jak na podzbiory tej przestrzeni. Wtedy będziemy chcieli pokryć przestrzeń podzbiorami rozłącznymi. W każdym przypadku problem jest trudny, NP-zupełny. Rozwiązuje się go za pomocą algorytmów z powrotami (backtracking).
Problem układania parkietu identycznymi klockami 2 × 1. Rozważamy planszę 2 × 3.
+----------+ Numeracja pól planszy | 11 12 13 | | 21 22 23 | +----------+ +----------+-------------------+ | Kolumna | 11 12 13 21 22 23 | +----------+-------------------+ | Wiersz 1 | 1 1 0 0 0 0 | poziomo | Wiersz 2 | 0 1 1 0 0 0 | poziomo | Wiersz 3 | 0 0 0 1 1 0 | poziomo | Wiersz 4 | 0 0 0 0 1 1 | poziomo | Wiersz 5 | 1 0 0 1 0 0 | pionowo | Wiersz 6 | 0 1 0 0 1 0 | pionowo | Wiersz 7 | 0 0 1 0 0 1 | pionowo +----------+-------------------+ Przygotowany plik z danymi: 11 12 12 13 21 22 22 23 11 21 12 22 13 23 Są 3 rozwiązania tego problemu. +-------+ +-------+ +-------+ | A A C | | A B B | | A B C | | B B C | | A C C | | A B C | +-------+ +-------+ +-------+
Ciekawostka. Układanie parkietu klockami 2 × 1 można zapisać jako problem znajdowania skojarzenia doskonałego w pewnym grafie. Tutaj dostajemy graf dwudzielny postaci 11---12---13 | | | 21---22---23 Istnieją algorytmy działające w czasie wielomianowym, znajdujące skojarzenie doskonałe w grafach ogólnych i dwudzielnych.
Podobnie możemy analizować różne puzzle i układanki, np. pentomino, sudoku.
W artykule Knutha mamy podany algorytm postępowania.
Jeżeli A jest pusta, to zakończ.
Wybierz kolumnę c (deterministycznie).
Ustal wiersze r, dla których A[r,c]=1.
Dla każdego wiersza r:
Dodaj r do częściowego rozwiązania.
Ustal kolumny j takie, że A[r,j]=1.
Dla każdej kolumny j:
Usuń/zaznacz kolumnę j z A.
Ustal wiersze i takie, że A[i,j]=1.
Dla każdego wiersza i:
Usuń wiersz i z A.
Wykonaj algorytm na zredukowanej macierzy A.
Przywróć usunięte wiersze i.
Przywróć/odznacz kolumny j.
Usuń r z częściowego rozwiązania.
Krok pierwszy to reprezentacja macierzy A. Macierz jest zwykle rzadka (niewiele jedynek), co sugeruje zapisywanie tylko niezerowych pozycji. Możemy wykorzystać elastyczność Pythona i korzystać z etykiet tekstowych. Szukając rozwiązania będziemy usuwać wiersze z macierzy A aż do jej całkowitego opróżnienia. Z drugiej strony wybrane wiersze będą wchodziły w skład rozwiązania. Pierwszy pomysł na reprezentację macierzy A to wykorzystanie słownika:
A1 = {(1, "C"): 1, (1, "E"): 1, (1, "F"): 1,
(2, "A"): 1, (2, "D"): 1, (2, "G"): 1,
(3, "B"): 1, (3, "C"): 1, (3, "F"): 1,
(4, "A"): 1, (4, "D"): 1,
(5, "B"): 1, (5, "G"): 1,
(6, "D"): 1, (6, "E"): 1, (6, "G"): 1}
Wszystkie niezerowe wartości w macierzy A to jedynki, co sugeruje, że nie musimy ich zapisywać, tylko pamiętać pozycje (węzły). Stąd drugi pomysł przechowywania macierzy jako listy węzłów (para wiersz i kolumna). Będziemy mogli korzystać z bogatej kolekcji metod dla list.
A2 = [(1, "C"), (1, "E"), (1, "F"), (2, "A"), (2, "D"), (2, "G"), (3, "B"), (3, "C"), (3, "F"), (4, "A"), (4, "D"), (5, "B"), (5, "G"), (6, "D"), (6, "E"), (6, "G")]
W globalnym słowniku covered_cols zapiszemy stan każdej kolumny, czy jest już pokryta (True), czy nie (False).
covered_cols = dict((c, False) for (r, c) in A)
Rozwiązania będziemy szukali za pomocą rekurencyjnej funkcji search(k), która na każdym poziomie ustala jeden wiersz rozwiązania. Wiersz ten (listę węzłów) zapiszemy w globalnym słowniku B pod kluczem k.
B = {}
def print_solution():
for k in B:
print(" ".join(str(node[1]) for node in B[k]))
Na każdym poziomie wywołania funkcji search(k) będziemy wybierać jedną kolumnę jeszcze nie pokrytą, którą chcemy pokryć. Trzeba to robić systematycznie aż do pokrycia wszystkich kolumn. Kod zapiszemy w osobnej funkcji, aby łatwo testować różne sposoby wybierania kolumn.
Definiujemy wyjątek dla sytuacji błędnych danych. Dokładniej: jeżeli są niepokryte kolumny, to funkcja powinna jedną z nich podać, nawet taką, która nie ma pokrywającego ją wiersza. Funkcja generuje wyjątek, jeżeli nie ma niepokrytych kolumn. Sytuację kolumny bez wiersza, który może ją pokryć, obsługujemy w funkcji search() [to jest ślepy zaułek, ale nie generujemy wyjątku, tylko funkcja oddaje sterowanie wyżej].
def choose_col1():
# Wybieramy pierwszą niepokrytą kolumnę.
for c in covered_cols:
if not covered_cols[c]:
return c
raise ValueError("Wszystkie kolumny pokryte")
def choose_col2():
# Wybieramy ostatnią niepokrytą kolumnę.
cols = [c for c in covered_cols if not covered_cols[c]]
if not cols:
raise ValueError("Wszystkie kolumny pokryte")
#return cols[0] # można wybrać pierwszą
return cols[-1] # wybieram ostatnią
def choose_col3():
# Wybieramy kolumnę z najmniejszą liczbą jedynek.
# Najpierw szukamy niepokrytych kolumn.
cols = [c for c in covered_cols if not covered_cols[c]]
if not cols:
raise ValueError("Wszystkie kolumny pokryte")
# Dla kolumn niepokrytych szukam liczby wierszy.
# Mogą się trafić kolumny bez wierszy, więc trzeba inicjalizować zerem.
tmp = dict((c, 0) for c in cols)
for (r, c) in A:
if c in cols:
tmp[c] = tmp[c] + 1
# Szukamy minimalnej liczby wierszy.
min_c = cols[0]
for c in cols:
if tmp[c] < tmp[min_c]:
min_c = c
return min_c
choose_col = choose_col1 # wybrany wariant
Właściwa funkcja szukająca rozwiązania ma postać.
def search(k): # szukaj kolejnego wiersza nr k w tablicy A
if not A: # już nie ma wierszy
for c in covered_cols:
if not covered_cols[c]: # ślepy zaułek
return
print_solution() # wszystkie pokryte
return
c = choose_col()
# Wybieramy wiersze z 1 w kolumnie c.
rows = [node[0] for node in A if node[1]==c]
if not rows:
# Nie ma wiersza z jedynką w kolumnie c.
return
for r in rows:
box = [] # tymczasowo usuniete wiersze
# dodaj wiersz r do częściowego rozwiązania
B[k] = [node for node in A if node[0] == r]
# Usuwam wiersz r z A.
for node in B[k]:
box.append(node)
A.remove(node)
# Wybieram kolumny j takie, że A[r, j] == 1 (tu jest c!)
cols = [node[1] for node in B[k]]
for j in cols:
# Zaznaczam kolumnę j.
covered_cols[j] = True
# Wybieram wiersze i takie, że A[i, j] == 1.
# Tu są też wiersze z rows.
rows2 = [node[0] for node in A if node[1] == j]
# Przenoszę wiersze z A do box.
# Nie wolno iterować po A i zmieniać A jednocześnie!
tmp = [node for node in A if node[0] in rows2]
for node in tmp:
box.append(node)
A.remove(node)
search(k+1)
# Przywracam wiersze do A.
for node in box:
A.append(node)
del box
del B[k]
# Anuluję zaznaczenie kolumn.
for j in cols:
covered_cols[j] = False
return
Do funkcji search(k) można dodać kod zliczający wybrane operacje, aby lepiej zrozumieć działanie algorytmu.
Dla dużych problemów wygodnie jest wczytać macierz A z pliku tekstowego zawierającego wiersze. Dla przykładowej macierzy A plik będzie miał postać
C E F A D G B C F A D B G D E G
Funkcja wczytująca macierz A z pliku może mieć postać:
def read_table(file_name):
afile = open(file_name, "r")
table = []
row = 0
for line in afile:
row += 1
for col in line.split():
table.append((row, col))
afile.close()
return table