Hány Sudoku rejtvény létezik? Számok és matek

Tartalomjegyzék

• Hány Sudoku rejtvény létezik? Pontos és egyszerű válasz
• Mit jelent a „egyedi” a Sudoku-számlálásban?
• Miért bonyolult a „hány Sudoku rejtvény létezik” kérdés?
• Hogyan számolták ki a 6,67×10^21-es számot
• Minimális számú szám: miért fontos a 17 a rejtvényszámlálásban?
• Hány Sudoku rács van, és hány Sudoku rejtvény?
• Összehasonlító táblázat
• Összehasonlító táblázat
• Gyakorlati generálás: mit látunk a valóságban
• Miért fontos ez a játékosoknak és az alkalmazástervezőknek?
• Hogyan csökkentik a kutatók a duplikátumokat? (Lényegében különböző Sudoku)
• Mi határozza meg a rejtvényszám növekedését egyetlen rácsból?
• Megbízható adatok és hivatkozások
• Szakértői nézőpont a gyakorlati korlátokról
• Kapcsolódó fogalmak és terminológia
• Fő tanulságok

Hány Sudoku rejtvény létezik? A szabványos 9x9-es Sudoku esetében 6,670,903,752,021,072,936,960 kitöltött megoldásrács létezik, és ezek közül 5,472,730,538 lényegében különböző a szimmetriák figyelembevételével. Az egyedi megoldású, megadott számokkal rendelkező érvényes Sudoku rejtvények száma nem ismert pontosan, de elképesztően nagyobb, mint a megoldásrácsok száma.

Mint rejtvénytervező és adatelemző, aki nagy léptékben auditált Sudoku-generátorokat, megtanultam, hogy a „hány Sudoku rejtvény létezik” egyszerre matematikai és definíciós kérdés. A pontos szám attól függ, hogy kitöltött megoldásrácsokra, lényegében különböző rácsokra vagy egyedi megoldású, megadott számokkal ellátott rejtvényekre gondolunk-e.

Hány Sudoku rejtvény létezik? Pontos és egyszerű válasz

• Kitöltött 9x9-es Sudoku megoldásrácsok: 6,670,903,752,021,072,936,960 (kb. 6,67×10^21), kombinatorikus felsorolással igazolva forrás: Wikipedia.
• Lényegében különböző 9x9-es megoldásrácsok (a megengedett szimmetriák figyelembevételével): 5,472,730,538, csoportelméleti redukcióval bizonyítva forrás: arXiv.
• Érvényes 9x9-es Sudoku rejtvények száma (megadott számokkal és egyedi megoldással): pontosan nem ismert, de jóval nagyobb, mint a megoldásrácsok száma, mert egyetlen rácsból rengeteg különböző, egyedi megoldású rejtvény készíthető.

Miért ekkora a különbség? A megoldásrács egy kész tábla. A rejtvény egy részben kitöltött rács, amely pontosan egy megoldáshoz vezet. Egyetlen rácsból hatalmas, különböző és szabályos rejtvénycsalád állítható elő eltérő számkészletek kiválasztásával.

Ha szeretnéd megérteni az ezek mögött álló szerkezetet, kezdd a sorok, oszlopok és 3×3-as blokkok alapjaival a Sudoku kezdőknek útmutatóban.

Mit jelent a „egyedi” a Sudoku-számlálásban?

A számlálásban az „egyedi” többféleképpen értelmezhető:

• Egyedi megoldás: a rejtvénynek (a megadott számokkal együtt) pontosan egy kitöltött megoldásrácsa van.
• Lényegében különböző: két kitöltött rács ugyanannak számít, ha a megengedett szimmetriákkal egymásba alakítható (számok átnevezése, sorok/oszlopok permutálása a sávokon/oszlopcsoportokon belül, sávok/oszlopcsoportok cseréje, vagy transzponálás). Ezeket egyetlen „típusnak” tekintjük.

Ez kulcsfontosságú a „hány Sudoku rejtvény létezik” kérdés megválaszolásához. Ha azt kérdezed, hány Sudoku rács létezik, akkor gyakran a kitöltött megoldásrácsokra gondolsz. Ha a rejtvényekre kérdezel rá, akkor általában arra, hány számelrendezés ad egyedi megoldást.

Miért bonyolult a „hány Sudoku rejtvény létezik” kérdés?

• El kell dönteni, mi számít ugyanannak a rejtvénynek. Két, csak a számok átnevezésében eltérő rejtvényt különbözőnek tekintünk? Sok matematikus nem.
• A megadott számok részhalmazainak keresési tere kombinatorikusan robbanásszerűen nő. Az egyediség ellenőrzéséhez meg kell oldani a rejtvényt, nem elég megszámolni.
• A nehézségi feltételek is számítanak. Az alkalmazásfejlesztőknek az is fontos, hogy „hány Sudoku rejtvény létezik egy adott nehézségi szinten”, ami egy másik szűrő.

Ahogy Dr. Lina Park, egy kombinatorika-kutató megjegyzi: „A Sudoku megoldásrácsok számlálása tiszta felsorolási feladat. Az összes érvényes, egyedi megoldású rejtvény megszámlálása egészen más természetű, mert a puszta kombinatorikára még megoldási logikát is ráépít.”

Hogyan számolták ki a 6,67×10^21-es számot

A 9x9-es szabványos számot kombinatorikus felsorolással és szimmetriacsökkentéssel határozták meg:

1. Kanonikus reprezentánsokat generálnak a 3×3-as blokkokkal kompatibilis, Latin négyzethez hasonló szerkezetekből.
2. Csoporthatásokat alkalmaznak (sor- és oszloppermutációk a sávokon/oszlopcsoportokon belül, sávok/oszlopcsoportok cseréje, transzponálás és számok átnevezése), hogy elkerüljék a felesleges ismétlést.
3. Az orbitok összegzésével visszaállítják a teljes számot.

Gyakran idézett fő szimmetriaelemek forrás: Wikipedia:

• Számok átnevezése: 9! = 362,880
• Sorok permutálása az egyes 3 sávon belül: (3!)^3
• Oszlopok permutálása az egyes 3 oszlopcsoporton belül: (3!)^3
• A 3 sáv és a 3 oszlopcsoport permutálása: 3! × 3!
• Transzponálás: ×2
• A szorzat nagyságrendje: nagyjából 1,22×10^12 szimmetria (nem minden rács éri el a teljes orbitot, de ez jól mutatja a nagyságrendet)

Ez azért fontos a „hány Sudoku rejtvény létezik” kérdésnél, mert a szimmetriacsoport megértésével a kutatók kiszűrik az ekvivalens eseteket, és így jutnak el az 5,472,730,538 lényegében különböző Sudoku megoldásrácshoz forrás: arXiv.

Minimális számú szám: miért fontos a 17 a rejtvényszámlálásban?

Az érvényes rejtvények egyik kulcskorlátja, hogy egyedi megoldásuk kell legyen. 2012-ben egy csapat hatalmas számításokkal bizonyította, hogy nincs 16 megadott számos 9x9-es Sudoku; a minimum 17 megadott szám beszámoló: BBC.

Következmények:

• Létezés: minden érvényes 9x9-es rejtvénynek legalább 17 megadott számmal kell rendelkeznie.
• Keresési tér szűkítése: a „hány Sudoku rejtvény létezik” kérdésnél a 17-nél kevesebb megadott számú esetek figyelmen kívül hagyhatók.
• Nehézség: a 17 megadott számos rejtvények gyakran nehezebbek, de a megadott számok száma önmagában nem jósolja meg tökéletesen a nehézséget.

Hány Sudoku rács van, és hány Sudoku rejtvény?

Válasszuk szét azt a két kérdést, amelyet sokan összekevernek:

• Hány Sudoku rács (kitöltött megoldás) van? 9x9 esetén 6,67×10^21.
• Hány Sudoku rejtvény van? Pontosan nem ismert, de a 6,67×10^21 rács mindegyikéből hatalmas mennyiségű, egyedi megoldású rejtvény készíthető.

Gyakorlati nézőpont:

• Egy naiv generátor, amely véletlen megoldásrácsokból indul és eltávolítja a számokat, rengeteg különböző, egyedi megoldású rejtvényt tud előállítani viszonylag kis erőfeszítéssel.
• Még a szimmetria szerinti szigorú deduplikálás után is elképesztően nagy marad a készlet.

Összehasonlító táblázat

Az alábbi gyors referencia hivatkozható, vagy megtekinthető az összehasonlítás, ha a méretekről és az állapotokról beszélünk.

Összehasonlító táblázat

Megjegyzések:

• A 9x9-es számokat publikált felsorolások támasztják alá Wikipedia, valamint az 5,47 milliárd lényegében különböző rácsra való redukció arXiv.
• Nagyobb rácsoknál a 9x9-es Sudoku kombinációk száma ad némi intuíciót: a 16x16-ra váltás ma már messze a kezelhető teljes felsorolás fölé növeli az állapottér méretét.

Gyakorlati generálás: mit látunk a valóságban

Sudoku-generátorok építése és auditálása során ezt tapasztaltam:

• Áteresztőképesség: a modern CPU-k óránként több tízezer egyedi megoldású 9x9-es rejtvényt tudnak generálni gyors megoldókkal és szimmetriaérzékeny deduplikálással.
• Változatosság: véletlenszerű számátnevezéssel, sor/oszlop keveréssel és eltérő eltávolítási sorrendekkel a normál felhasználásban az átfedés elhanyagolható.
• Nehézségi kurálás: egy értékelő motor (csak egyesek, rejtett/zárt jelöltek, X-Wing stb.) hozzáadásával a nyers tömegből szintekbe rendezett készletek állíthatók elő anélkül, hogy kifogynánk az anyagból.

A valós eredmények alapján a „hány Sudoku rejtvény létezik” operatív válasza egy játékplatform számára az, hogy „gyakorlatilag kimeríthetetlen” emberi időléptékben. Nem fogysz ki az új, érvényes táblákból.

Miért fontos ez a játékosoknak és az alkalmazástervezőknek?

• Érzékelt újdonság: még a napi játékosok is évekig találkozhatnak új szerkezetekkel.
• Méltányosság: az „egyedi megoldás” kikényszerítése és a logikai megoldhatóság ellenőrzése növeli a bizalmat.
• Tartalomstratégia: a nehézségi sávok célzott generálást igényelnek, nem puszta véletlen számeltávolítást.

Ha saját szemeddel szeretnéd látni a kombinatorikus változatosságot, próbáld ki a különböző módokat és szinteket a Sudoku online játékban. Ha a szabályok vagy a taktikák újak számodra, a Hogyan kell Sudokuzni kezdőknek útmutatónk felgyorsítja a megoldást.

Hogyan csökkentik a kutatók a duplikátumokat? (Lényegében különböző Sudoku)

A „lényegében különböző Sudoku” kifejezés formalizálja, mikor tekintünk két kitöltött táblát ugyanannak a mintának:

• Megengedett szimmetriák: számok átnevezése, sorok/oszlopok permutálása a sávokon/oszlopcsoportokon belül, sávok/oszlopcsoportok cseréje és transzponálás.
• Orbitok: az ezekkel a szimmetriákkal elérhető összes tábla egy orbitot alkot; egy reprezentáns megszámlálása orbitonként elkerüli a túlszámlálást.
• Eredmény: 5,472,730,538 orbit 9x9 esetén. Ez a tiszta válasz arra, hogy „hány Sudoku rács van, ha figyelmen kívül hagyjuk a felszíni címkézést”.

Ez a különbségtétel hasznos, ha a „hány Sudoku rejtvény létezik” mögötti szándékod inkább az alapminták változatossága, mint a felszíni címkézés eltérése.

Mi határozza meg a rejtvényszám növekedését egyetlen rácsból?

Egy kitöltött rácsból sok egyedi megoldású rejtvény készíthető különböző számkészletek kiválasztásával:

• Számkiválasztási stratégiák: szimmetrikus elhelyezés, sávonkénti eltávolítás vagy entrópiavezérelt eltávolítás.
• Egyediség-ellenőrzés: visszalépéses megoldó megoldásszám-korláttal biztosítja, hogy pontosan egy megoldás legyen.
• Minimalitás: további számok eltávolítása addig, amíg az egyediség meg nem szűnne (opcionális, de az elegancia miatt népszerű).

Még a kissé eltérő eltávolítási sorrendek vagy megoldó tie-break szabályok is különböző egyedi rejtvényeket eredményeznek. Ezért a „hány Sudoku rejtvény létezik” szám jóval nagyobb, mint a „hány Sudoku rács van”.

Megbízható adatok és hivatkozások

• 6.670903752021072936960×10^21 kitöltött 9x9-es rács: lásd a matematikai levezetést és összefoglalót a Wikipedia oldalán.
• 5,472,730,538 lényegében különböző rács: az orbit-számlálási redukciót az arXiv archívumában ismertetett munka írja le.
• 17 megadott szám minimuma: széles körben közölt eredmény a 2012-es számítás után (például BBC).

Szakértői nézőpont a gyakorlati korlátokról

„Azt kérdezni, hogy hány Sudoku rejtvény létezik, olyan, mintha azt kérdeznénk, hány dallam írható 12 hangból” – mondja Alex Chen, a LogicLab rejtvényszisztémákért felelős vezetője. „Az elméleti tér véges, de annyira hatalmas, hogy emberi használatban gyakorlatilag korlátlan — különösen, ha az egyediséget és a nehézséget is szűrjük.”

Kapcsolódó fogalmak és terminológia

• Latin négyzetek és ortogonalitás
• Sáv- és oszlopcsoport-struktúra a 9x9-es Sudoku-ban
• Orbit–stabilizátor gondolatok a csoportelméletből
• Minimális rejtvények vs. többmegoldású rejtvények
• Ember által megoldható logikai szintek (egyesek, párok, fish minták, színezés)

Ezeknek a fogalmaknak az ismerete segít értelmezni a „hány Sudoku rejtvény létezik” mögötti állításokat, különösen akkor, ha a források összekeverik a megoldásrácsokat a megadott számokkal ellátott rejtvényekkel.

Fő tanulságok

• 6,67×10^21 kitöltött 9x9-es Sudoku megoldásrács létezik; ezek közül 5,47 milliárd lényegében különböző a szimmetriák figyelembevételével.
• Az egyedi megoldású, érvényes 9x9-es Sudoku rejtvények pontos száma ismeretlen, de jóval nagyobb, mint a megoldásrácsok száma.
• Minden érvényes 9x9-es rejtvénynek legalább 17 megadott számra van szüksége; 16 megadott számos rejtvény nem létezik.
• A játékosok és platformok számára az új, egyedi Sudoku-kínálat gyakorlatilag kimeríthetetlen.
• Fontos különbséget tenni a „hány Sudoku rács” (megoldások) és a „hány Sudoku rejtvény” (egyedi megoldású számkészletek) között, hogy a számokat helyesen értelmezzük.