Sudoku 17 vihjeitä Asiantuntija
Uusin pistetilasto #8wmme:lle
Uusin pistetilasto Sudoku 17 vihjeitä:lle
Kuinka pelata Sudoku 17 vihjeitä
On todistettu, että tavallisessa Sudoku-pulmassa on oltava vähintään 17 vihjettä ainutlaatuisen ratkaisun saamiseksi.
Sudokusäännöt:
-
Täytä numerot 1–9 jokaiselle riville, sarakkeelle ja 3 x 3 -aliruudukko 9 x 9 -ruudukkoon.
-
Jokainen numero voi esiintyä vain kerran kullakin rivillä, sarakkeessa ja 3x3-aliruudukossa.
-
Täytä tyhjät kohdat numeroilla 1–9, jotta jokaisella rivillä, sarakkeella ja 3x3-aliruudukolla on kaikki numerot 1–9.
Sudoku on logiikkaan perustuva numerosijoittelupulma. Tavoitteena on täyttää 9x9-ruudukko numeroilla 1-9 siten, että jokainen rivi, sarake ja 3x3-aliruudukko sisältää kaikki yhdeksän numeroa täsmälleen kerran.
Vuonna 2009 Gary McGuire ja hänen tiiminsä osoittivat, että jokaisessa 16 vihjeen sisältävässä Sudoku-pulmassa on oltava vähintään kaksi ratkaisua. He tekivät tämän käyttämällä tekniikkaa nimeltä "kuollut kuviot".
Kuollut kuvio on Sudoku-kokoonpano, jossa on kaksi tai useampia mahdollisia ratkaisuja. McGuire ja hänen tiiminsä havaitsivat, että minkä tahansa 16 vihjeen sisältävän Sudoku-pulman täytyy sisältää vähintään yksi kuollut kuvio. Siksi näissä pulmissa on oltava vähintään kaksi ratkaisua.
Tällä tuloksella on useita seurauksia. Ensinnäkin se tarkoittaa, ettei ole olemassa sellaista asiaa kuin 16 vihjeen Sudoku-pulma, jossa on ainutlaatuinen ratkaisu. Toiseksi se tarkoittaa, että mikä tahansa 16 vihjeen Sudoku-pulma voidaan ratkaista useilla tavoilla. Kolmanneksi se tarkoittaa, että 16 vihjeen Sudoku-pulmia on ääretön määrä.
Tässä on teknisempi selitys todistukselle siitä, että Sudoku-pulmissa on oltava vähintään 17 vihjettä ainutlaatuisen ratkaisun saamiseksi:
Todistus alkaa pohtimalla Sudoku-pulmaa, jossa on 16 vihjettä. Voimme ajatella tätä palapeliä joukkona rajoituksia numeroille, jotka voidaan sijoittaa tyhjiin neliöihin.
Voimme sitten käyttää "backtracking"-nimistä tekniikkaa yrittääksemme löytää ratkaisun pulmaan. Backtracking on rekursiivinen algoritmi, joka yrittää kaikkia mahdollisia numeroyhdistelmiä tyhjissä neliöissä, kunnes löytää ratkaisun.
Jos pulmalle on ainutlaatuinen ratkaisu, perääntyminen löytää sen lopulta. Jos ratkaisuja on kuitenkin useita, paluumatkalla ei ehkä koskaan löydy ratkaisua.
McGuire ja hänen tiiminsä käyttivät backtrackingia osoittaakseen, että jos on olemassa 16 vihjeen Sudoku-pulma, jossa on ainutlaatuinen ratkaisu, on oltava tapa käynnistää paluualgoritmi siten, että se löytää aina ratkaisun.
Sitten he osoittivat, että tämä ei ole mahdollista. He tekivät tämän rakentamalla 16 vihjeen sarjan, joka johtaa kuolleeseen kuvioon. Tämä kuollut kuvio tarkoittaa, että pulmalle on kaksi mahdollista ratkaisua, eikä paluualgoritmia voi käynnistää siten, että se löytää aina saman ratkaisun.
Tämä tulos osoittaa, että jokaisessa 16 vihjeen Sudoku-pulmassa on oltava vähintään kaksi ratkaisua.
