[Rozumowanie łańcuchowe ①] Podstawy: Silne i słabe łącza
Rozumowanie łańcuchowe to podstawowa rama teoretyczna dla zaawansowanych technik Sudoku. Prawie wszystkie zaawansowane techniki eliminacji — od prostego X-Wing po złożone AIC — można zrozumieć i opisać poprzez rozumowanie łańcuchowe. Ten artykuł zgłębia dwa najbardziej fundamentalne pojęcia rozumowania łańcuchowego: Silne łącza i Słabe łącza.
Czym jest łańcuch?
W Sudoku łańcuch to sekwencja połączeń utworzonych między kandydatami poprzez określone relacje logiczne. Wyobraź sobie: jeśli możemy ustalić relacje rozumowania takie jak „jeśli A jest prawdziwe, to B jest prawdziwe/fałszywe" między kandydatami i połączyć te relacje razem, tworzymy łańcuch.
Istotą łańcucha jest propagacja logiczna: zaczynając od jednego punktu, poprzez serię dedukcji logicznych, dochodzimy do wniosku. Ten wniosek jest zwykle używany do:
- Ustalenia, że kandydat musi być prawdziwy (potwierdzenie umieszczenia)
- Ustalenia, że kandydat musi być fałszywy (eliminacja kandydata)
Aby zrozumieć łańcuchy, musimy najpierw zrozumieć podstawowe jednostki tworzące łańcuchy: Łącza. Łącza opisują logiczną relację między dwoma kandydatami, dzieląc się na silne i słabe w zależności od siły relacji.
Silne łącze
Silne łącze istnieje między dwoma kandydatami A i B wtedy i tylko wtedy, gdy: dokładnie jeden z A i B jest prawdziwy, a drugi jest fałszywy.
Innymi słowy, jeśli A jest fałszywe, to B musi być prawdziwe, a jeśli A jest prawdziwe, to B musi być fałszywe (wzajemnie wykluczające się i kompletne).
Notacja: A = B lub A ═══ B (podwójna linia)
Źródła silnych łączy
Silne łącza mogą pochodzić z następujących sytuacji:
1. Silne łącze w komórce dwuwartościowej
Gdy komórka ma tylko dwóch kandydatów, silne łącze istnieje między tymi dwoma kandydatami.
Logika: Jeśli 4 jest fałszywe, komórka musi być 7; jeśli 7 jest fałszywe, komórka musi być 4.
Komórki dwuwartościowe są najczęstszym źródłem silnych łączy, ponieważ są intuicyjne: komórka jest albo tą liczbą, albo tamtą.
2. Silne łącze z pary sprzężonej
Gdy cyfra pojawia się tylko w dwóch pozycjach w jednostce (wierszu, kolumnie lub kwadracie), silne łącze istnieje między tym kandydatem w tych dwóch pozycjach. Ta relacja nazywa się Parą sprzężoną.
Logika: Wiersz 5 musi mieć 3. Jeśli R5C2 nie jest 3, R5C8 musi być 3; i odwrotnie.
Dwa końce silnego łącza pary sprzężonej to ta sama cyfra w różnych pozycjach, a nie różne cyfry w tej samej pozycji. To fundamentalnie różni się od silnych łączy w komórkach dwuwartościowych.
3. Grupowe silne łącze
Szerzej mówiąc, gdy grupa kandydatów i inna grupa kandydatów spełniają relację „dokładnie jedna grupa jest prawdziwa", istnieje silne łącze. To będzie omówione w zaawansowanych technikach i szczegółowo przedyskutowane w trzecim artykule tej serii.
Podstawowe właściwości silnych łączy
- Dokładnie jedno prawdziwe: Dokładnie jeden koniec silnego łącza jest prawdziwy, drugi jest fałszywy
- Fałsz propaguje prawdę: Jeśli jeden koniec jest fałszywy, drugi musi być prawdziwy
- Prawda propaguje fałsz: Jeśli jeden koniec jest prawdziwy, drugi musi być fałszywy
Słabe łącze
Słabe łącze istnieje między dwoma kandydatami A i B wtedy i tylko wtedy, gdy: jeśli A jest prawdziwe, to B musi być fałszywe.
Innymi słowy, co najwyżej jeden z A i B jest prawdziwy (oba mogą być fałszywe, ale oba nie mogą być prawdziwe).
Notacja: A - B lub A ─── B (pojedyncza linia)
Źródła słabych łączy
Słabe łącza również mają wiele źródeł:
1. Słabe łącze między różnymi kandydatami w tej samej komórce
W tej samej komórce słabe łącze istnieje między dowolnymi dwoma różnymi kandydatami.
Logika: Komórka może pomieścić tylko jedną liczbę. Jeśli umieścimy 1, nie może być 5.
2. Słabe łącze między tymi samymi kandydatami w tej samej jednostce
W tej samej jednostce (wierszu, kolumnie lub kwadracie) słabe łącza istnieją parami między wszystkimi pozycjami tego samego kandydata.
Logika: Cyfra może pojawić się tylko raz w kwadracie. Jeśli R1C7 jest 6, to R2C8 i R3C9 nie mogą być 6.
W porównaniu do silnych łączy, słabe łącza są bardziej wszechobecne. W rzeczywistości podstawowe zasady Sudoku (brak powtarzających się cyfr w wierszu, kolumnie lub kwadracie; jedna cyfra na komórkę) zasadniczo definiują dużą liczbę relacji słabych łączy.
Podstawowe właściwości słabych łączy
- Co najwyżej jedno prawdziwe: Co najwyżej jeden koniec słabego łącza jest prawdziwy
- Prawda propaguje fałsz: Jeśli jeden koniec jest prawdziwy, drugi musi być fałszywy
- Oba mogą być fałszywe: Oba końce mogą być jednocześnie fałszywe (inaczej niż silne łącza!)
Porównanie silnych i słabych łączy
Zrozumienie różnicy między silnymi i słabymi łączami jest kluczem do opanowania rozumowania łańcuchowego. Podsumujmy to w tabeli porównawczej:
| Właściwość | Silne łącze | Słabe łącze |
|---|---|---|
| Podstawowa właściwość | Dokładnie jedno prawdziwe, jedno fałszywe | Co najwyżej jedno prawdziwe |
| Propagacja logiczna | Fałsz → Prawda, Prawda → Fałsz | Prawda → Fałsz |
| Czy oba mogą być prawdziwe | ✗ Nie | ✗ Nie |
| Czy oba mogą być fałszywe | ✗ Nie | ✓ Tak |
| Notacja | ═══ (podwójna linia) lub = | ─── (pojedyncza linia) lub - |
| Typowe źródła | Komórki dwuwartościowe, Pary sprzężone | Różne cyfry w tej samej komórce, Ta sama cyfra w tej samej jednostce |
Przypadek specjalny: Silne łącza są również słabymi łączami
Oto ważna koncepcja do zrozumienia: Silne łącza są często również słabymi łączami.
Perspektywa silnego łącza: Jeśli 4 jest fałszywe, 7 musi być prawdziwe → Silne łącze istnieje
Perspektywa słabego łącza: Jeśli 4 jest prawdziwe, 7 musi być fałszywe → Słabe łącze również istnieje
Wniosek: Ci dwaj kandydaci mają zarówno silne, jak i słabe łącze!
Perspektywa silnego łącza: Jeśli 3 w R5C2 jest fałszywe, 3 w R5C8 musi być prawdziwe → Silne łącze istnieje
Perspektywa słabego łącza: Jeśli 3 w R5C2 jest prawdziwe, 3 w R5C8 musi być fałszywe (ten sam wiersz nie może mieć dwóch 3) → Słabe łącze również istnieje
Wniosek: Pary sprzężone również spełniają warunki zarówno silnego, jak i słabego łącza!
Gdy dwaj kandydaci spełniają relację „dokładnie jeden prawdziwy, jeden fałszywy" (ani oba nie mogą być prawdziwe, ani oba nie mogą być fałszywe), mają zarówno silne, jak i słabe łącze. To jest „najsilniejsza" relacja łącza i jest bardzo przydatna w konstrukcji łańcuchów.
Wskazówka do zapamiętania: Komórki dwuwartościowe i pary sprzężone zawsze mają zarówno silne, jak i słabe łącza.
Koncepcja „widzenia"
W rozumowaniu łańcuchowym koncepcja „widzenia" (see) jest często używana. Zrozumienie „widzenia" jest kluczowe dla identyfikacji relacji łączy.
Kandydat A „widzi" kandydata B oznacza, że istnieje słabe łącze między A i B.
Jeśli A jest prawdziwe, to B musi być fałszywe — A może „wyeliminować" B.
Relacje „widzenia" istnieją między:
- Różnymi kandydatami w tej samej komórce
- Tym samym kandydatem w tym samym wierszu
- Tym samym kandydatem w tej samej kolumnie
- Tym samym kandydatem w tym samym kwadracie
Ta koncepcja będzie często używana podczas omawiania zastosowań łańcuchów, takich jak „kandydaci, których widzą oba końce, mogą być wyeliminowani".
Dlaczego rozróżnianie silnych i słabych łączy jest tak ważne?
Rozróżnienie między silnymi i słabymi łączami jest kamieniem węgielnym rozumowania łańcuchowego. Ich różnice determinują:
Silne łącza pozwalają wywnioskować „prawdę" z „fałszu"; słabe łącza pozwalają wywnioskować „fałsz" z „prawdy". Rozumowanie łańcuchowe wykorzystuje te dwa różne kierunki propagacji do konstruowania złożonych dedukcji logicznych.
Podczas budowania łańcuchów musisz poprawnie zidentyfikować, czy każdy krok jest silnym czy słabym łączem, aby zapewnić prawidłowe rozumowanie. Błędne traktowanie słabego łącza jako silnego doprowadzi do błędnych wniosków.
Wiele pozornie różnych technik (jak X-Wing, Skyscraper, XY-Wing itp.) to w istocie łańcuchy o określonych wzorcach. Zrozumienie silnych i słabych łączy pozwala pojąć te techniki w ujednoliconych ramach.
Następne kroki
Ten artykuł wprowadził dwa najbardziej fundamentalne pojęcia rozumowania łańcuchowego: silne i słabe łącza. Po zrozumieniu tych pojęć możemy zacząć uczyć się, jak je łączyć, aby budować kompletne łańcuchy.
W następnym artykule omówimy:
- Jak naprzemiennie stosować silne i słabe łącza do budowania łańcuchów
- Zasady propagacji stanów prawda/fałsz w łańcuchach
- Podejście „kolorowania" w rozumowaniu łańcuchowym
- Metody wyciągania wniosków z końców łańcucha
- Słownik Sudoku - Szybkie odniesienie do terminów użytych w tym artykule
- Technika XY-Wing - Praktyczne zastosowanie rozumowania łańcuchowego
- Technika XY-Chain - Rozszerzone zastosowanie łańcuchów komórek dwuwartościowych