Těžké kombinace v killer sudoku

Těžké kombinace v killer sudoku je to, k čemu sáhneš, když má součet klece příliš mnoho možností na vyhledání v tabulce. Místo přečtení odpovědi vygeneruješ všechny sady číslic, které součet dovoluje, každou otestuješ na políčkách a ponecháš jen přeživší.

Co je to za vzorec

Krajní součty jsou snadné. Tříbuňková klec se součtem 6 může být jen {1, 2, 3} a dvoupolíčková klec se součtem 17 jen {8, 9}. Problémem jsou součty uprostřed rozsahu: tři políčka se součtem 17 mají sedm možností a čtyři políčka se součtem 22 jich mají jedenáct.

Technika tu mezeru zaplňuje. Kombinace je skutečná, jen když lze každou její číslici opravdu umístit do jiného políčka klece vzhledem k aktuálním kandidátům. Otestuj umístění, zahoď kombinace, které se nevejdou, a pak po políčkách sesbírej číslice, které přežily. Cokoli zbude navíc, je vyloučení.

Kdy ji hledat

• Středně velká klec o 3 až 5 políčkách, jejíž součet leží uprostřed rozsahu.
• Klec, která přišla o kandidáty kvůli jiným technikám, takže surový seznam kombinací je teď příliš shovívavý.
• Klec sdílející řádek, sloupec nebo čtverec s jinou klecí, jejíž číslice jsou už pevně určené.
• Klec s jednou už umístěnou číslicí, což obvykle seznam zpolovičí.

Jak ji použít krok za krokem

1. Vypiš všechny sady různých číslic, které dají součet ve správném počtu políček.
2. Škrtni každou sadu obsahující číslici, kterou nemůže nést žádné políčko klece.
3. Pro každou zbylou sadu zkus přiřadit její číslice políčkům. Pokud žádné přiřazení nevyhovuje kandidátům, je sada mrtvá.
4. Pro každé políčko shrň číslice, které převzalo alespoň v jednom přeživším přiřazení. Každý jiný kandidát odchází.
5. Proveď průnik se sousedy. Pokud je jiná klec ve stejné oblasti uzamčena na pevný pár nebo trojici, jsou ty číslice pro políčka tvé klece v té oblasti nedostupné a další kombinace odpadají.

Vyřešený příklad

Klec 22 pokrývá E1, E2, E3 a F1, všechna ve čtverci 4. Čtyři políčka se součtem 22 mají jedenáct možných sad, ale E2 je už 1, takže E1, E3 a F1 musí dát dohromady 21. Sleduj, jak se každá sada testuje.

Tři číslice dají 21 třemi způsoby: 4+8+9, 5+7+9 a 6+7+8. Řádek E už má 7 (E6) a 6 (E8), takže E1 a E3 nemohou nést ani jednu. F1 by tedy musel nést 6 i 7 v sadě 6+7+8, což je nemožné, takže ta sada umírá. V sadě 5+7+9 může být E3 jen 9 a E1 jen 5, takže F1 je 7. V sadě 4+8+9 je F1 rovno 4, 8 nebo 9.

Žádná přeživší sada neobsahuje 3, takže 3 odchází z E1, E3 i F1. F1 může být stále 4, 7, 8 nebo 9, takže odchází i 5 a 6. Umístěná 1 zmenšila jedenáct sad na tři a řádek E dokončil práci.

Sousední klec může seznam ještě zkrátit. Klec uzamčená na pár nebo trojici ve stejné oblasti odstraní ty číslice z políček tvé klece v té oblasti, jako samostatný tah po tomto.

Snadné versus těžké kombinace

Časté chyby

• Povolení opakování. Číslice uvnitř klece jsou vždy různé, takže {5, 5, 7} nikdy není kombinací pro 17.
• Kontrola sady číslic, ale ne umístění. Sada může obsahovat jen platné číslice a přesto selhat, protože dvě z nich potřebují totéž políčko.
• Jednorázové provedení. Každé umístění v kleci nebo poblíž seznam zkracuje. Spusť to znovu, kdykoli se mřížka pohne.
• Příliš velký začátek. Klece o 6 nebo více políčkách mají obrovské seznamy a snahu skoro nikdy nesplatí. Pracuj raději s jejich doplňkem.

Kde se s nimi setkáš

Je to práce pokročilých strategií. Lehká a střední killer sudoku jsou postavená na klecích, které stačí vyhledat, ale od těžkého killer sudoku výše volí autoři součty uprostřed rozsahu právě proto, aby na ně tabulka neodpověděla. Zrychlení v ořezávání kombinací je největší zisk rychlosti, jaký v killer sudoku existuje.