Peli Sudoku koostuu valmiiksi neliön ruudukko on jaettu N alueille N laatikot, osittain täytetty numeroita, siten, että kussakin rivissä, kukin sarake ja kunkin alueen numerot 1 N esiintyä kerran ja vain kerran.
Sudokun matemaattinen analyysi antaa sinun löytää tämän pelin ja sen muunnelmien takana olevat erilaiset ominaisuudet ja ongelmat.
Sudokun matemaattinen analyysi on jaettu kahteen pääosaan: kokonaisten ruudukkojen ominaisuuksien analysointi ja ruudukon resoluution analyysi.
Ruudukkoanalyysissä on keskitytty suuressa määrin mahdollisten ratkaisujen luettelointiin pelin eri muunnelmille.Ratkaisututkimus keskittyy ruudukon alkuarvoihin ja täyteen ruudukkoon johtaviin vaiheisiin. Nämä tekniikat vaativat useita tieteenaloja: kombinatorinen analyysi, algoritminen, ryhmateoria ja ohjelmointi, koska tietokone mahdollistaa verkkojen nopean ratkaisemisen.
Sudoku-muunnelmia on paljon, tyypillisesti ruudukon koko ( N- parametri ) ja alueiden muoto. Klassisten sudokujen N on yhtä suuri kuin 9, ja niiden alueet ovat 3 × 3 solua. Suorakulmaisessa sudokussa on suorakulmaisia alueita, joiden koko on L × C, missä L on rivien lukumäärä ja C sarakkeiden määrä. Tällaisesta sudokusta, jonka koko on L × 1 (tai 1 × C ), tulee latinankielinen neliö, koska alue on yksi rivi tai sarake.
On olemassa monimutkaisempia muunnelmia, kuten epäsäännöllisesti leikatut alueet ( Nanpure ), lisärajoituksilla ( Samunamupure tai Killer Sudoku , ainutlaatuisuuden kunnioittaminen Kokonotsun lävistäjillä , rajoituksilla elementtien järjestyksellä Suurempana -Thanilla ) tai useita ruudukoita ( Samurai , Sudoku 3D-muodossa). Joissakin muunnelmissa numerot korvataan kirjaimilla. Tämä käytettyjen merkkien korvaaminen ei kuitenkaan muuta palapelin luontaisia ominaisuuksia, jos säännöt pysyvät samoina.
Sudokun matemaattinen analyysi on seurannut pelin suosiota. Analyysit pelin algoritmisesta monimutkaisuudesta ja NP-täydellisyydestä dokumentoitiin vuoden 2002 loppupuolella, luettelointitulokset ilmestyivät vuoden 2005 puolivälissä. Lukuisten tutkijoiden ja harrastajat ovat mahdollistaneet pelin ominaisuuksien päivittämisen.Sudoku-muunnosten ulkonäkö laajentaa matemaattisia elementtejä, jotka on otettava huomioon ja tutkittava.
Päinvastoin kuin alussa mainitut kaksi päämatemaattista lähestymistapaa, matemaattiseen logiikkaan perustuvaa lähestymistapaa ja pulmien ratkaisemisongelman ratkaisemista ehdotettiin hiljattain Denis Berthierin kirjassa "Sudokun piilotettu logiikka" piilotettu sudoku). Tämä antoi mahdollisuuden löytää ja virallistaa kaikki pelin yleistetyt symmetriat ja löytää niihin perustuvia uusia ratkaisusääntöjä, kuten piilotetut xy-ketjut.
Numeroiden sijoittaminen n 2 × n 2 -verkkoon, jossa on n × n alueita, on NP-täydellinen .
Ratkaista sudoku voidaan virallistaa ongelma on kaavio värjäys . Pelin klassisessa versiossa tavoitteena on soveltaa 9 väriä tietylle kuvaajalle osavärityksestä (ruudukon alkuperäinen kokoonpano). Tässä kuvaajassa on 81 kärkeä, yksi solua kohden. Jokainen Sudoku-ruutu voidaan merkitä järjestetyllä parilla (x, y) , jossa x ja y ovat kokonaislukuja välillä 1 ja 9. Kaksi erillistä kärkeä, jotka on merkitty (x, y) ja (x ', y'), on kytketty toisiinsa. reunan vain ja vain, jos:
Ruudukko täydennetään määrittämällä kokonaisluku väliltä 1–9 kullekin kärjelle, jotta kaikki reunan linkittämät pisteet eivät jaa samaa kokonaislukua.
Ratkaisuristikko on myös latinankielinen neliö . Kahden teorian suhde on nyt täysin tiedossa, koska D. Berthier osoitti teoksessa ”Sudokun piilotettu logiikka”, että ensimmäisen asteen looginen kaava, jossa ei mainita lohkoja (tai alueita), on sopiva sudokulle, jos ja vain, jos se on voimassa latinalaisille neliöille.
Ratkaisuruudukoita on huomattavasti vähemmän kuin latinankielisiä neliöitä, koska Sudoku asettaa lisärajoituksia (katso alla oleva kohta 4: mahdollisten täydellisten ruudukkojen määrä).
Toisin kuin ratkaisuruudukkojen lukumäärä, tarkkaa minimipulmien määrää ei tiedetä. (Palapeli on vähäinen, jos paljastettua ei voida poistaa ratkaisun ainutlaatuisuutta vaarantamatta.) Tilastollisia tekniikoita yhdistettynä uuden tyyppisen generaattorin määritelmään (ohjattu biasgeneraattori (sisään) ) käytetään kuitenkin osoittamaan, että noin (suhteellisen virheen ollessa 0,065%):
(katso kirja Pattern-Based Constraint Satisfaction and Logic Puzzles tai artikkeli CSP: n puolueettomat tilastot - kontrolloidun ennakkoluulon generaattori ).
Paljastettujen enimmäismäärä ilman yhtä ratkaisua, joka ilmestyy heti, versiosta riippumatta, on ruudukon koko miinus 4: jos kahta ehdokasparia ei ole rekisteröity ja tyhjät solut vievät suorakulmion kulmat, ja että täsmälleen kaksi solua ovat alueella, ehdokkaita voidaan rekisteröidä kahdella tavalla. Tämän ongelman päinvastainen, paljastusten vähimmäismäärä yhden ratkaisun takaamiseksi , on ratkaisematon ongelma, vaikka japanilaiset harrastajat ovat löytäneet 9 × 9 ristikon, jossa ei ole symmetriaa ja joka sisältää vain 17 paljastusta (lue lisää, katso (en) ). Vuonna 2007 julkaistu tulos paljastaa, että jotta sudokulla olisi ainutlaatuinen ratkaisu, kahdeksasta 9: stä numerosta on paljastettava, kun taas 18 on symmetristen 9 × 9-verkkojen paljastettujen vähimmäismäärä.
Palapeli on epätäydellinen ruudukko alkuvaiheen arvoihin. Alueita kutsutaan myös lohkoiksi tai alueiksi. Termiä neliö vältetään sekaannusten poistamiseksi.
Liuska on sarja vierekkäisiä lohkoja vaaka-akselilla. Pino on sarja vierekkäisiä lohkoja pystyakselilla. 9 × 9 neliön muotoisessa sudokussa on siis 3 nauhaa ja 3 pinoa.
Oikein suunnitellulla sudokulla on yksi ja ainoa ratkaisu: lopullinen ruudukko on ainutlaatuinen, mutta osittaisen ruudukon ratkaiseminen voi kuitenkin mennä eri reiteillä.
Mahdollisten täydellisten ruudukkojen määrä on 9! × 72 2 × 2 7 × 27704267771 (eli 6670903752201029936960 ristikot ≈ 6,67 × 10 21 ).
Viimeinen tekijä on alkuluku . Bertram Felgenhauer ja Frazer Jarvis osoittivat tämän tuloksen vuonna 2005 tyhjentävällä tutkimuksella . Frazer Jarvis yksinkertaisti sitten todistusta huomattavasti yksityiskohtaisen analyysin avulla. Ed Russell on itsenäisesti vahvistanut mielenosoituksen.
Useat ruudukot ovat kuitenkin samanarvoisia, jos otetaan huomioon tietty määrä symmetrioita, nimittäin
(Huomaa analogia matriisitoimintojen kanssa lineaarisessa algebrassa ). Kun nämä symmetriat otettiin huomioon, Jarvis ja Russell osoittivat, että oli olemassa 5 472 730 538 ristiriitaa.
Päinvastoin, tänä päivänä super sudokun (16 × 16 ruudukko) kokonaisten pulmien lukumäärästä ei ole tulosta.
Jos nyt olemme kiinnostuneita mahdollisista ongelmista, tämä luku on selvästi tärkeämpi, koska on olemassa useita tapoja paljastaa saman ruudukon luvut.
Esitäytettyjen solujen vähimmäismäärä resoluution tekemiseksi ainutlaatuiseksi on 17; se on todistettu laskemalla vuonnatammikuu 2012irlantilainen joukkue. Japanilainen on koonnut luettelon kaikista yksittäisratkaisuista sudokusta, jossa on 17 täytettyä laatikkoa.
Vastaus kysymykseen "Kuinka monta sudoku-pulmaa on?" »Riippuu ratkaisun määritelmästä ja vastaavuudesta useiden ratkaisujen välillä. Kaikkien mahdollisten ratkaisujen ( eli täydelliset ruudukot) luetteloimiseksi säilytetään seuraava määritelmä:
Ruudukko A on erilainen kuin ruudukko B, jos kohdassa A (i, j) olevan laatikon arvo on erilainen kuin B (i, j), ainakin yhdelle parille i, j (arvot rajoittuvat ritilä).
Jos ruudukko A saadaan ruudukon B symmetrialla, niiden katsotaan olevan erilaisia. Kierrokset lasketaan myös uusiksi ratkaisuiksi.
|
|
|
|||||||||||||||||||||||||||
|
|
|
|||||||||||||||||||||||||||
|
|
|
On :
Ratkaisujen määrä riippuu ruudukon koosta, sovelletuista säännöistä ja erillisen ratkaisun tarkasta määritelmästä. Sudokussa, jossa on 3 × 3 aluetta, ruudukon sisällön näyttökäytännöt ovat seuraavat: nauhat on numeroitu ylhäältä alas, pinot vasemmalta oikealle. Alueet on siksi numeroitu vasemmalta oikealle ja ylhäältä alas. Tätä käytäntöä sovelletaan myös suorakaiteen muotoisiin ristikoihin.
Muut termit ovat hyödyllisiä, jos sudokussa on 3 × 3 aluetta:
Esimerkiksi merkintä H56 vastaa kolmikon alueen 5, rivi 6 Englanti, käytämme merkintätapa r on rivi ja c varten sarake .
Puhumme myös minirivistä tai minisarakkeista rivin tai ruudukon sarakkeen alueella olevan osan osoittamiseksi.
Kahden ruudukon sanotaan olevan symmetrisesti erillisiä, jos toista ei voida johtaa toisesta (yhdellä tai useammalla symmetrian säilyttämistoiminnolla).
Symmetrian säilyminenSeuraavat toiminnot muuttavat kelvollisen ruudukon aina muuksi kelvolliseksi ruudukoksi:
Nämä operaatiot määrittelevät symmetriasuhteen kahden samanarvoisen ruudukon välillä. Poistamalla tarrojen muutos ja ottamalla huomioon ruudukossa olevat 81 arvoa nämä toiminnot muodostavat symmetrisen ryhmän S 81 alaryhmän järjestyksessä 3! 8 × 2 = 3 359 232.
Tunnista ratkaisut Burnside's lemman avullaRatkaisua varten joukko vastaavia ratkaisuja, jotka voidaan saada käyttämällä näitä operaatioita (lukuun ottamatta arvojen uudelleennimeämistä), muodostaa symmetrisen ryhmän kiertoradan. Symmetrisesti erilaisten ratkaisujen lukumäärä on siis kiertoradojen lukumäärä, arvo, joka voidaan laskea Burnside'n lemman avulla . Burnside-menetelmän kiinteät kohdat ovat ratkaisuja, jotka eroavat toisistaan vain uudelleennimeämisessä. Tätä tekniikkaa käyttäen Jarvis Russell laski symmetrisesti erillisten ratkaisujen lukumäärän: 5 472 730 538.
Suurille L- ja C- arvoille käytetään Kevin Kilfoilin menetelmää (myöhemmin yleistetty) arvioimaan tapojen lukumäärä ruudukon täydentämiseksi. Tässä menetelmässä oletetaan, että riveihin ja sarakkeisiin liittyvät rajoitukset ovat ensimmäisessä likiarvossa ehdollisesti riippumattomia satunnaismuuttujia alueen rajoituksen suhteen. Algebralliset laskelmat johtavat Kilfoil-Silver-Pettersen-kaavaan:
jossa b L, C on tapojen määrä suorittaa sudoku L- alueiden (koko L × C ) kanssa vaakasuorassa vierekkäin. Silverin toteuttama Pettersen-algoritmi on tällä hetkellä nopein tunnettu tekniikka arvioida tarkasti b L, C- arvoja .
Kaistaleiden lukumäärä ongelmille, joissa "sudoku-palapelien kokonaismäärä ei ole tiedossa" on annettu alla. Kuten jäljempänä tässä artikkelissa, mitat vastaavat alueiden mittoja.
Mitat | Bändien lukumäärä | Tekijä (t) | Virallinen tarkastus |
---|---|---|---|
2 × C | (2 C )! ( C !) 2 | (ilmeinen) | Joo |
3 × C | Pettersen | Joo | |
4 × C | (Katso matematiikkatulos alla.) | Pettersen | Joo |
4 × 4 | 16! × 4! 12 × 1273 431 960 = c. 9.7304 × 10 38 | Hopea | Joo |
4 × 5 | 20! × 5! 12 × 879 491 145 024 = c. 1,9078 × 10 55 | Russell | Joo |
4 × 6 | 24! × 6! 12 × 677542884561056 = c. 8.1589 × 10 72 | Russell | Joo |
4 × 7 | 28! × 7! 12 × 563 690 747 238 465 024 = c. 4,6169 × 10 91 | Russell | Joo |
( Silver suoritti laskelmat enintään 4 × 100 , mutta niitä ei näytetä tässä.) | |||
5 × 3 | 15! × 3! 20 × 324408987992064 = c. 1,5510 × 10 42 | Hopea | Kyllä # |
5 × 4 | 20! × 4! 20 × 518910437330304134176 = c. 5,0751 × 10 66 | Hopea | Kyllä # |
5 × 5 | 25! × 5! 20 × 1 165 037 550 432 885 119 709 241 344 = noin. 6,9280 × 10 93 | Pettersen / hopea | Ei |
5 × 6 | 30! × 6! 20 × 3 261 734 691 836 217 181 002 772 823 310 336 = c. 1,2127 x 10 123 | Pettersen / hopea | Ei |
5 × 7 | 35! × 7! 20 × 10 664 509 989 209 199 533 282 539 525 535 793 414 144 = c. 1,2325 × 10154 | Pettersen / hopea | Ei |
5 × 8 | 40! × 8! 20 × 391192897379023322766428892551 42802665250700700966 = n. 4,1157 x 10 186 | Pettersen / hopea | Ei |
4 × C-tapauksen lauseke on:
kanssa:
ulkoinen summa koskee kaikkia a , b , c siten, että 0 ⩽ a , b , c ja a + b + c = 2 C sisempi summa koskee kaikkia k 12 , k 13 , k 14 , k 23 , k 24 , k 34 = 0 siten, että k 12 , k 34 = a ja k 13 , k 24 = b ja k 14 , k 23 = c ja k 12 + k 13 + k 14 = a - k 12 + k 23 + k 24 = b - k 13 + c - k 23 + k 34 = c - k 14 + b - k 24 + a - k 34 = CSudokussa, jossa on 3 × 3 aluetta, on monenlaisia rajoituksia. Nimiä ei ole standardoitu, ulkoiset linkit viittaavat määritelmiin:
Tyyppi | Ruudukkojen lukumäärä | Tekijä (t) | Virallinen tarkastus |
---|---|---|---|
3doku | 104 015 259 648 | Stertenbrink | Joo |
Eristetyt ryhmät | 201105135151764480 | Russell | Joo |
Hyperkuutio | 37 739 520 | Stertenbrink | Joo |
Taika Sudoku | 5,971,968 | Stertenbrink | Joo |
Sudoku X | 55 613 393 399 531520 | Russell | Joo |
NRC Sudoku | 6 337174388428800 | Brouwer | Joo |
Kaikki sudokut ovat kelvollisia (numeroiden ainutlaatuisuus riveissä, sarakkeissa ja alueilla) niiden toimintojen jälkeen, jotka säilyttävät sudoku-ryhmän ominaisuudet. Jotkut sudokut ovat erityisiä siinä mielessä, että joillakin toiminnoilla on sama vaikutus kuin numeroiden uudelleennimeämisellä:
Muutos | Ruudukkojen lukumäärä | Tekijä (t) | Virallinen tarkastus |
---|---|---|---|
Saattaminen osaksi kansallista lainsäädäntöä | 10980179804160 | Russell | Välillisesti |
Neljännesvuoro | 4 737 761 280 | Välillisesti | |
Puoli kierrosta | 56425664693760 | Välillisesti | |
Vaihda nauhat | 5 384 326 348 800 | Välillisesti | |
Linjojen permutaatiot kaistoilla | 39007939401120 | Välillisesti |
Oikein tehdyissä ristikoissa on oltava yksi ja ainoa ratkaisu. Ruudukon sanotaan olevan lukukelvoton tai vähäinen, jos se on kelvollinen ja jos ylimääräisen numeron poistaminen johtaa sen pätemättömyyteen ( ts. Se ei enää salli yhtä ratkaisua). On mahdollista luoda minimaalinen ruudukko, jolla on erilainen määrä alkuarvoja. Tässä osassa kuvataan tähän ongelmaan liittyvät ominaisuudet.
Klassista sudokua, jonka ruudukko on 9 × 9, ts. 81 neliötä, rajoittaa tällä hetkellä alkuarvo, joka on 17 alkuarvoa, tai 18, kun alkuperäisten numeroiden sijaintia voidaan kääntää 90 °. On oletus, jonka mukaan tämä 17: n sidonta on paras mahdollinen, mutta muodollista näyttöä ei ole, on vain tyhjentävä haku satunnaisilla ruudukoilla:
Lisärajoitukset (sudokuksilla, joiden alueet ovat 3 × 3) muuttavat yhden ratkaisun keksimiseksi tarvittavien vähimmäisarvojen määrää:
Aluetta voidaan kuvata sen mitoilla: L × C, jossa L on rivien lukumäärä ja C sarakkeiden lukumäärä alueella. Sudokun klassisessa versiossa L = C = 3. Tämä tarkoittaa, että nauhoja kohden on L alueita ja pinoa kohden C alueita. On kätevämpää mainita alueen koko kuin elementtien lukumäärä, koska 2 × 6 -alueella on sama määrä laatikoita kuin 3 × 4-alueella.
Seuraava leikkaus voidaan käyttää luokittelemaan karkeasti:
Lisärajoitukset antavat mahdollisuuden kohdistaa paremmin pelityyppiä.
N × N: n alueiden neliönmuotoisella sudokulla on useita kunnioitettuja ominaisuuksia kaikille sen alielementeille klassisen säännön mukaan, ettei kopioita ole. Jokaisella rivillä ja sarakkeella on todellakin leikkauspiste N alueen kanssa, ja niillä on N ruutua kullekin. Olevien liuskojen lukumäärä ja pinot on myös yhtä suuri kuin N . Suorakulmaisella Sudokulla ei ole näitä ominaisuuksia.
Sudoku, jossa on 3 × 3 aluetta, piilottaa toisen oman ominaisuutensa: N on pelissä huomioon otettujen alayksikköjen määrä, nimittäin kolme: rivi, sarake ja alue.
Du-summa-OH korvata alueilla 3 x 3 (tai yleisemmin L x C) epäsäännöllinen alueilla, joilla on kiinteä koko. Bob Harris osoittanut, että se on aina mahdollista luoda du-summa-TTT kanssa N -1 alkuarvoilla koskevasta N jonka N- verkkoon . Hän antoi useita esimerkkejä.
Vuonna Samunamupure tai Killer Sudoku alueilla on paitsi epäsäännöllisiä muotoja, vaan myös eri kokoisia. Rivien, alueiden ja sarakkeiden numeroiden ainutlaatuisuutta koskevat säännöt ovat edelleen voimassa. Alkuindikaatiot annetaan alueiden arvosummien muodossa (esimerkiksi 4 solun alue, jonka summa on 10, sisältää numerot 1, 2, 3, 4 tietyssä järjestyksessä). Ruudukon käynnistämiseen tarvittavaa vähimmäisarvoa ei tiedetä eikä arveltu.
Miyuki Misawan ehdottama muunnos korvaa summat suhteilla: indikaatiot ovat symboleja = , < , > , jotka osoittavat tiettyjen vierekkäisten alueiden suhteelliset arvot. Annetaan esimerkki, jossa on vain 8 relaatiota, mutta ei tiedetä, onko tämä luku alaraja.
Tässä kuvattu lähestymistapa on historiallisesti ensimmäinen strategia, jota käytetään klassisen sudoku-ruudukon (3 × 3 aluetta 9 × 9-ruudukossa) ratkaisujen luetteloimiseksi. Sen ehdottivat Felgenhauer ja Jarvis.
Analyysi alkaa tutkimalla ensimmäisen validissa ratkaisussa käytetyn kaistan permutaatioita. Kun ekvivalenssiluokka ja tämän kaistan symmetriat osittaisratkaisuille on tunnistettu, olemme kiinnostuneita kahdesta muusta kaistasta, jotka on rakennettu ja laskettu kullekin ekvivalenssiluokalle. Ottamalla kaikkien yhdistelmien summa saadaan ratkaisujen kokonaismäärä eli 6 670 903 752 021 072 936 960 (noin 6,67 × 10 21 ).
Hakutilan pienentämiseksi oletamme, että solujen uudelleennimeäminen (esimerkiksi "1" muuttaminen "2": ksi ja päinvastoin) tuottaa vastaavan ratkaisun. Ruudukko sallii 9! = 362880 tämäntyyppistä nimeä: 9 mahdollisen numeron joukosta valittu numero osoitetaan ensimmäiselle laatikkotyypille, yksi numero jäljellä olevista 8: sta osoitetaan toiselle laatikkotyypille, yksi numero jäljellä olevista 7: stä osoitetaan kolmannen tyyppinen tapaus jne.