Sudoku-enciklopédia · Matematika és számítástechnika

A Sudoku matematikája

Frissítve: 2026-10-05

Latin négyzet, 3×3-as négyzetekkel

Egy latin négyzetben minden jel minden sorban és minden oszlopban egyszer szerepel. Egy kitöltött Sudoku egy 9-es méretű latin négyzet egy további feltétellel: a kilenc 3×3-as négyzet mindegyikében is minden számjegy egyszer szerepel.

Források: Wikipedia: Latin square

Hány rács létezik

Bertram Felgenhauer és Frazer Jarvis 2005-ben számolta meg a kitöltött 9×9-es rácsokat: számuk 6 670 903 752 021 072 936 960, körülbelül 6,67 × 10²¹. Közülük sok valójában ugyanaz a rács, csak álcázva. Ha két rácsot egynek számítunk, amikor az egyik átalakítható a másikba a számjegyek átcímkézésével, forgatással vagy tükrözéssel, illetve a sorok és oszlopok olyan átrendezésével, amely a rácsot érvényesen hagyja, 5 472 730 538 lényegében különböző rács marad; ezt a számot Ed Russell és Frazer Jarvis számította ki.

Források: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

A 17-es minimum

Egyetlen olyan szabványos 9×9-es Sudoku sincs, amelynek 16 vagy kevesebb megadott szám mellett pontosan egy megoldása van. Gary McGuire, Bastian Tugemann és Gilles Civario ezt kimerítő számítógépes kereséssel mutatta ki, és 2012 januárjában jelentette be az eredményt. A tizenhét a minimum, nem garancia: sok olyan rácsnak, amelyben 17 megadott szám van, mégis több megoldása van.

Források: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

A Sudoku mint gráfszínezés

Rajzoljunk egy-egy pontot a 81 cella mindegyikéhez, és kössünk össze két pontot, ha a celláik közös sorban, oszlopban vagy négyzetben vannak. Ennek a Sudoku-gráfnak 810 összeköttetése van, és minden pontnak pontosan 20 szomszédja van. A rejtvény megoldása azt jelenti, hogy a megadott számok által rögzített színeket úgy egészítjük ki, hogy összekötött pontok soha ne legyenek azonos színűek. Legalább kilenc színre van szükség, mert minden sor, oszlop és négyzet kilenc olyan pontból álló csoport, amelyek mind össze vannak kötve egymással, és bármely kitöltött rács megmutatja, hogy kilenc elég.

Források: Wikipedia: Sudoku graph

Általában nehéz, 9×9-ben gyors

A korlátlanul növelhető Sudoku-rácsokra (n²×n²-es rácsok n×n-es négyzetekkel) annak eldöntése, hogy egy részben kitöltött rács kiegészíthető-e, NP-teljes probléma; ezt az eredményt Jato Takajuki és Szeta Takahiro publikálta 2003-ban. A hatékony számítógépes programok a szokásos 9×9-es rejtvényeket jellemzően a másodperc töredéke alatt megoldják, bár az idő a programtól, a számítógéptől és a rejtvénytől függ.

Források: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

Lásd még

Források

Összes szócikk →