Ťažké kombinácie v killer sudoku

Ťažké kombinácie v killer sudoku sú to, k čomu sa vrátiš, keď má súčet klietky príliš veľa možností na vyhľadanie v tabuľke. Namiesto vyčítania odpovede vygeneruješ každú množinu číslic, ktorú súčet dovoľuje, otestuješ každú na políčkach a ponecháš len tie, ktoré prežili.

Čo je to za vzor

Extrémne súčty sú jednoduché. Trojpolíčková klietka so súčtom 6 môže byť len {1, 2, 3} a dvojpolíčková klietka so súčtom 17 len {8, 9}. Problémom sú súčty v strede rozsahu: tri políčka so súčtom 17 majú sedem možností a štyri políčka so súčtom 22 jedenásť.

Technika túto medzeru zatvára. Kombinácia je skutočná, len ak sa každá jej číslica dá naozaj umiestniť do rôzneho políčka klietky pri súčasných kandidátoch. Otestuj umiestnenia, vyhoď kombinácie, ktoré sa nezmestia, a potom zozbieraj číslice, ktoré prežili, po políčkach. Všetko, čo zostane navyše, je eliminácia.

Kedy ho hľadať

• Stredne veľká klietka s tromi až piatimi políčkami, ktorej súčet leží v strede rozsahu.
• Klietka, ktorá prišla o kandidátov kvôli iným technikám, takže surový zoznam kombinácií je teraz oveľa príliš veľkorysý.
• Klietka zdieľajúca riadok, stĺpec alebo blok s inou klietkou, ktorej číslice sú už pevne dané.
• Klietka s jednou už umiestnenou číslicou, čo zvyčajne zoznam zníži na polovicu.

Ako ho použiť krok za krokom

1. Vypíš každú množinu rôznych číslic, ktorá dáva súčet v správnom počte políčok.
2. Prečiarkni každú množinu obsahujúcu číslicu, ktorú nemôže prijať žiadne políčko klietky.
3. Pre každú zostávajúcu množinu skús priradiť jej číslice políčkam. Ak žiadne priradenie nesedí s kandidátmi, množina je mŕtva.
4. Pre každé políčko zozbieraj číslice, ktoré dostalo aspoň v jednom prežívajúcom priradení. Každý ďalší kandidát odchádza.
5. Prienik so susedmi. Ak je iná klietka v tej istej jednotke uzamknutá na pevný pár alebo trojicu, tieto číslice sú pre políčka tvojej klietky v tej jednotke nedostupné a padajú ďalšie kombinácie.

Vyriešený príklad

Klietka 22 pokrýva E1, E2, E3 a F1, všetky v bloku 4. Štyri políčka so súčtom 22 majú jedenásť možných množín, ale E2 je už 1, takže E1, E3 a F1 musia dať dokopy 21. Sleduj, ako sa testuje každá množina.

Tri číslice dávajú 21 tromi spôsobmi: 4+8+9, 5+7+9 a 6+7+8. Riadok E už má 7 (E6) a 6 (E8), takže E1 a E3 nemôžu prijať ani jednu. F1 by teda muselo niesť 6 aj 7 v 6+7+8, čo je nemožné, a táto množina umiera. V 5+7+9 môže byť E3 len 9 a E1 len 5, takže F1 je 7. V 4+8+9 je F1 4, 8 alebo 9.

Ani jedna z prežívajúcich množín neobsahuje 3, takže 3 odchádza z E1, E3 a F1. F1 môže byť ešte 4, 7, 8 alebo 9, takže odchádzajú z neho aj 5 a 6. Umiestnená 1 zmenšila jedenásť množín na tri a riadok E dokončil prácu.

Susedná klietka môže zoznam ešte skrátiť. Klietka uzamknutá na pár alebo trojicu v tej istej jednotke odstráni tieto číslice z políčok tvojej klietky v tej jednotke, ako samostatný ťah po tomto.

Ľahké a ťažké kombinácie

Časté chyby

• Povolenie opakovaní. Číslice v klietke sú vždy rôzne, takže {5, 5, 7} nie je nikdy kombinácia pre 17.
• Kontrola množiny číslic, ale nie umiestnenia. Množina môže obsahovať len povolené číslice a aj tak zlyhať, lebo dve z nich potrebujú to isté políčko.
• Jednorazové použitie. Každé umiestnenie v klietke alebo pri nej skracuje zoznam. Spusti to znova vždy, keď sa mriežka pohne.
• Príliš veľký začiatok. Klietky so šiestimi alebo viac políčkami majú obrovské zoznamy a námaha sa takmer nikdy nevyplatí. Pracuj radšej s ich doplnkom.

Kde sa s ním stretneš

Toto je práca pokročilej úrovne. Ľahké a stredné killer hlavolamy sú postavené na klietkach len s vyhľadávaním, ale od ťažkého killer sudoku zadávatelia vyberajú súčty v strede rozsahu práve preto, aby na ne tabuľka nestačila. Zrýchlenie v orezávaní kombinácií je najväčší jednotlivý prírastok rýchlosti, aký v killer sudoku existuje.