Sudokun tietosanakirja · Matematiikka ja tietotekniikka

Sudokun matematiikka

Päivitetty 2026-10-05

Latinalainen neliö, jossa on lohkot

Latinalaisessa neliössä jokainen symboli esiintyy kerran kullakin rivillä ja kussakin sarakkeessa. Täytetty sudoku on kertalukua 9 oleva latinalainen neliö, jossa on yksi lisäehto: myös jokaisessa yhdeksästä 3×3-lohkosta kukin numero esiintyy kerran.

Lähteet: Wikipedia: Latin square

Kuinka monta ruudukkoa on olemassa

Bertram Felgenhauer ja Frazer Jarvis laskivat täytettyjen 9×9-ruudukoiden määrän vuonna 2005: niitä on 6 670 903 752 021 072 936 960 eli noin 6,67 × 10²¹. Monet niistä ovat sama ruudukko eri asussa. Kun kaksi ruudukkoa lasketaan samaksi, jos toisen voi muuttaa toiseksi nimeämällä numerot uudelleen, kiertämällä, peilaamalla tai järjestämällä rivejä ja sarakkeita uudelleen sääntöjenmukaisuuden säilyttävillä tavoilla, jäljelle jää 5 472 730 538 olennaisesti erilaista ruudukkoa. Tämän luvun laskivat Ed Russell ja Frazer Jarvis.

Lähteet: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

Vähintään 17 vihjettä

Yhdelläkään tavallisella 9×9-sudokulla, jossa on enintään 16 lähtölukua, ei ole täsmälleen yhtä ratkaisua. Gary McGuire, Bastian Tugemann ja Gilles Civario osoittivat tämän kattavalla tietokonehaulla ja julkistivat tuloksen tammikuussa 2012. Seitsemäntoista on vähimmäismäärä, mutta se ei takaa yhtä ainoaa ratkaisua: monilla 17 lähtöluvun ruudukoilla on edelleen useampi kuin yksi ratkaisu.

Lähteet: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

Sudoku graafin värityksenä

Piirrä yksi piste jokaista 81:tä solua kohti ja yhdistä kaksi pistettä aina, kun niiden solut kuuluvat samaan riviin, sarakkeeseen tai lohkoon. Tässä sudokugraafissa on 810 yhteyttä, ja jokaisella pisteellä on täsmälleen 20 naapuria. Pulman ratkaiseminen tarkoittaa lähtölukujen määräämän värityksen laajentamista niin, ettei yhdistetyillä pisteillä ole koskaan samaa väriä. Vähintään yhdeksän väriä tarvitaan, koska jokainen rivi, sarake ja lohko on yhdeksän pisteen ryhmä, jonka kaikki pisteet on yhdistetty toisiinsa. Mikä tahansa täytetty ruudukko osoittaa, että yhdeksän väriä riittää.

Lähteet: Wikipedia: Sudoku graph

Yleisesti vaikea, 9×9-koossa nopea

Kun sudokuruudukoiden koko voi kasvaa rajatta (n²×n²-ruudukot, joissa on n×n-lohkot), sen ratkaiseminen, voiko osittain täytetyn ruudukon täyttää loppuun, on NP-täydellinen ongelma. Takayuki Yato ja Takahiro Seta julkaisivat tämän tuloksen vuonna 2003. Tehokkaat tietokoneohjelmat ratkaisevat tavalliset 9×9-pulmat tyypillisesti sekunnin murto-osassa, mutta aika riippuu ohjelmasta, tietokoneesta ja pulmasta.

Lähteet: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

Katso myös

Lähteet

Kaikki artikkelit →