Parkietaże

W autorskim tygodniku internetowym Trapez Jarosław Wróblewski proponuje serię zadań (nr 75-126) o parkietowaniu prostokątów. Na przykład: czy planszę $15 × 15$ da się szczelnie pokryć klockami o wymiarach $|8× 1;1 × 8;11 × 1$ oraz $1 × 11$ (oczywiście klocki nie mogą na siebie zachodzić).

W tego typu zadaniach odpowiedź zazwyczaj brzmi "nie", a typowa strategia polega na zgadnięciu numeracji lub kolorowania pól planszy i użyciu argumentu w stylu "każdy klocek pokrywa trzy pola zielone, ale liczba pól zielonych na całej planszy jest niepodzielna przez $3$ ". Spróbujmy jednak ogólniej zastanowić się, jak systematycznie, od podstaw, można zaatakować problem: czy planszę o wymiarach $n × m$ da się wyparkietować klockami ustalonych typów $a1× b1,...,aℓ× bℓ.$

Niech $|(i, j)$ oznacza pole w $|i$ -tym wierszu i $j$ -tej kolumnie. Każde pokrycie planszy możemy zakodować za pomocą zmiennych

⎧⎪⎪1 jeśli pewien klocek typu a ×b ma lewy gó rny róg na polu (i, j), xai,× jb= ⎨ ⎪⎪⎩0 wpp.

Na przykład pokrycie planszy $4 ×2$ z rysunku obok opisujemy następująco:

x1× 2 = x3×1 = x3×1= 1, 1,1 2,1 2,2

a wszystkie inne zmienne $xa ×b i, j$ są równe zero.

Zapytajmy teraz, kiedy zestaw zmiennych $xai×, jb$ opisuje poprawny parkietaż. Przede wszystkim musimy usunąć wszystkie zmienne

xa×bdla i > n +1 −a lub j > m i, j

ponieważ klocek o wymiarach $a × b$ z lewym górnym rogiem na polu $|(i, j)$ wystawałby poza planszę. Po drugie, wszystkie zmienne muszą przyjmować wartości 0 lub $|1.$ W końcu, musimy zagwarantować, że każde pole planszy jest pokryte przez dokładnie jeden klocek. Ten warunek można zapisać następująco:

ℓ min i,n−ak+1 min j,m Q Q Q xaik ,× j bk= 1 k 1i max 1,i−ak+1 j max 1, j−bk+1

(1)

dla każdego $i = 1,...,n, j = 1,...,m.$ Ten nieprzyjemny wzór oznacza po prostu, że spośród wszystkich legalnych położeń dostępnych klocków, które potencjalnie mogą zahaczać o pole $(i, | j),$ dokładnie jedno jest faktycznie w użyciu. A zatem zerojedynkowe rozwiązania układu $|nm$ równań liniowych (1) odpowiadają jednoznacznie parkietażom.

Dla zupełnej jasności rozważmy przykład. Zapiszmy w tym języku problem parkietowania planszy $3 | × 4$ klockami typu $1× 3$ i $2 × 1.$ Mamy $|12$ równań, z których każde wymienia legalne sposoby pokrycia jednego z pól:

1× 3 2× 1 (1,1) x1,1 +x 1,1 = 1 (1,2) x1×1, 31 +x1×1,23+ x21×,21= 1 (1,3) x1× 3 +x1×3+ x2×1= 1 1,1×1 3 1,22× 1 1,3 (1,4) x1,1×2 3 +x 1,42× 1= 12×1 (2,1) x2,1 +x 1,1 + x2,1 = 1 (2,2) x1×2, 31 +x1×2,32 + x21×,21+ x22×,21= 1 (2,3) x1× 3 +x1×3+ x2×1+ x2×1= 1 2,1×1 3 2,2×2 1 12,3×1 2,3 (2,4) x2,1×2 3 +x 1,42× 1+ x2,4 = 1 (3,1) x3,1 +x 2,1 = 1 (3,2) x1×3, 31 +x1×3,32 + x22×,21= 1 (3,3) x1× 3 +x1×3+ x2×1= 1 3,1×1 3 3,2×2 1 2,3 (3,4) x3,2 +x 2,4 = 1

(2)

Na przykład równanie dla pola $(2,4)$ czytamy następująco: pole to można przykryć klockiem $1 ×3$ z pola $(2,2)$ lub klockiem $2 ×1$ z jednego z pól $|(1,4)$ lub $(2,4).$

Jak łatwo sprawdzić, prostokąta $3× 4$ klockami $|1× 3$ i $2× 1$ pokryć się nie da. Możemy tego faktu dowieść algebraicznie, mianowicie mnożąc równania (2) kolejno przez następujące współczynniki:

− 1,1,0,− 1,1,−1,0,1,−1,1,0,−1

(3)

i dodając wszystko stronami. Wtedy otrzymamy

0 =− 1,

co dowodzi, że układ (2) nie ma rozwiązań rzeczywistych (a więc tym bardziej zerojedynkowych!).

Uogólnijmy ostatnie rozumowanie. Układ równań liniowych nie ma rozwiązań w liczbach rzeczywistych jedynie wówczas, gdy pewna kombinacja liniowa danych równań daje "oczywistą sprzeczność" postaci "zero z lewej, coś niezerowego z prawej strony". Nie udowodnimy tego faktu, a jedynie odwołamy się do intuicji i życiowego doświadczenia Czytelników w tym zakresie.

Co to znaczy w szczególnym przypadku układu (1)? Oznaczmy przez $|yi j$ współczynnik, przez jaki w naszym dowodzie nierozwiązywalności przemnożymy równanie dla pola $(i, j).$ Możemy nawet myśleć o tych współczynnikach jako wpisanych w pola planszy: $yi j$ umieszczamy na polu $|(i, j).$ Na przykład współczynniki (3) dla przykładu (2) pojawią się na planszy $|3× 4$ w następującej kolejności:

|--|---|---|--| − 1| 1 |0 |−1| |--|---|---|--| |-1|−1-|0--|-1| −-1--1--0---−1-

Wtedy (proszę sprawdzić) "oczywista sprzeczność" dla układu (1) polega na tym, że:

każde dopuszczalne położenie klocka na planszy pokrywa pola o sumie $|y i j$ równej zeru,
suma wszystkich $yi j$ jest niezerowa.

Jest zupełnie Jasne (przez duże J, i to bez lektury całego naszego wywodu), że powyższe warunki dowodzą nieistnienia parkietażu! A zatem odkryliśmy od podstaw jeden z wariantów magicznej metody rozwiązywania tego typu zadań, wspomnianej na początku.

Spójrzmy na to, co tutaj się stało, z jeszcze szerszej perspektywy. Układ równań taki jak (1) jest bardzo szczególnym przypadkiem problemu z zakresu programowania całkowitoliczbowego (ang. mixed-integer programming). Wiele trudnych problemów kombinatorycznych można zakodować w tej postaci, wprowadzając zmienne zerojedynkowe opisujące pewne zdarzenia (np. klocek leży na polu) i wyrażając wzajemne ograniczenia (np. klocki nie zachodzą na siebie) w postaci równań i nierówności liniowych, tak jak w (1). Jest to standardowa technika dla wielu tego typu problemów. Rozwiązywanie problemów całkowitoliczbowych, choć możliwe, jest bardzo czasochłonne (w istocie NP-trudne), dlatego możemy na początek zapytać, czy badany problem ma w ogóle rozwiązanie w liczbach rzeczywistych. Ten proces nazywa się relaksacją. Powstały problem liniowy można rozwiązać efektywnie, a jeżeli okaże się, że rozwiązania nie ma, to zawsze można podać certyfikat niespełnialności (ang. infeasibility certificate), analogiczny do naszej tabeli współczynników $|yi j.$ Czytelnikom zainteresowanym tym Olbrzymim (przez duże O) działem optymalizacji proponuję wpisanie wymienionych tu haseł w wyszukiwarce. Reasumując:

dowód nieistnienia parkietażu przez kolorowanie/numerowanie i inne sprytne niezmienniki

to nic innego, jak

certyfikat niespełnialności dla liniowej relaksacji całkowitoliczbowego modelu parkietowania.

Pod tym adresem można znaleźć kod źródłowy wraz z komentarzami, pozwalający własnoręcznie eksperymentować z parkietażami przy użyciu ogólnodostępnych pakietów do modelowania i programowania liniowego/całkowitoliczbowego. Można tam znaleźć rozwiązanie zadania o planszy $15× 15$ ze wstępu.