Quants sudokus hi ha? Comptes i matemàtiques

Taula de continguts

• Quants sudokus hi ha? Una resposta precisa i senzilla
• Què vol dir “únic” en el recompte de sudokus?
• Per què “quants sudokus hi ha” és una pregunta complicada
• Com es va calcular el nombre 6.67×10^21
• Mínim d’indicis: per què 17 és important per comptar sudokus
• Quantes graelles de Sudoku hi ha vs. quants sudokus hi ha?
• Taula comparativa
• Taula comparativa
• Generació al món real: què veiem a la pràctica
• Per què això importa per als jugadors i els dissenyadors d’apps
• Com redueixen els duplicats els investigadors? (Sudoku essencialment diferents)
• Què determina el creixement del nombre de sudokus a partir d’una sola graella?
• Dades i cites en què pots confiar
• Perspectiva experta sobre els límits pràctics
• Conceptes i terminologia relacionats que convé conèixer
• Idees clau

Quants sudokus hi ha? En el Sudoku estàndard de 9x9, hi ha 6.670.903.752.021.072.936.960 graelles de solució completes, i 5.472.730.538 d’aquestes són essencialment diferents si es tenen en compte les simetries. El nombre de sudokus vàlids amb solució única no se sap exactament, però és astronòmicament més gran que el nombre de graelles de solució.

Com a dissenyador de trencaclosques i analista de dades que ha auditat generadors de Sudoku a gran escala, he après que “quants sudokus hi ha” és alhora una pregunta de matemàtiques i una pregunta de definicions. El recompte exacte que busques depèn de si et refereixes a graelles de solució completes, a graelles essencialment diferents o a sudokus amb pistes i una única solució.

Quants sudokus hi ha? Una resposta precisa i senzilla

• Graelles de solució completes de Sudoku 9x9: 6.670.903.752.021.072.936.960 (aprox. 6,67×10^21), verificades mitjançant enumeració combinatòria font: Wikipedia.
• Graelles de solució 9x9 essencialment diferents (tenint en compte les simetries vàlides): 5.472.730.538, demostrades amb reducció de teoria de grups font: arXiv.
• Nombre de sudokus 9x9 vàlids (amb pistes i una única solució): desconegut exactament, però moltíssim més gran que el nombre de graelles de solució, perquè cada graella pot generar molts sudokus diferents amb solució única.

Per què hi ha tanta diferència? Una graella de solució és un tauler acabat. Un sudoku és una graella parcialment omplerta que condueix exactament a una d’aquestes solucions. Una sola graella pot generar una família enorme de sudokus diferents i legítims si es trien conjunts d’indicis diferents.

Si estàs aprenent l’estructura que hi ha darrere d’aquests recomptes, comença pels conceptes bàsics de files, columnes i caixes de 3×3 a la guia per a principiants de Sudoku.

Què vol dir “únic” en el recompte de sudokus?

En aquest context, “únic” pot voler dir coses diferents:

• Solució única: el sudoku (amb pistes) té exactament una graella de solució completa.
• Essencialment diferent: dues graelles completes són la mateixa si només canvien per simetries permeses (reordenar dígits, permutar files o columnes dins de bandes o piles, intercanviar bandes o piles, o transposar). Es consideren un sol “tipus”.

Això és clau per respondre “quants sudokus hi ha”. Si preguntes quantes graelles de Sudoku existeixen, normalment et refereixes a graelles de solució completes. Si preguntes pels sudokus, normalment vols saber quants patrons d’indicis produeixen una solució única.

Per què “quants sudokus hi ha” és una pregunta complicada

• Has de decidir què compta com el mateix sudoku. Consideres diferents dos sudokus que només canvien per una reassignació de dígits? Molts matemàtics no ho farien.
• L’espai de cerca dels subconjunts d’indicis és combinatòriament explosiu. Comprovar la unicitat requereix resoldre, no només comptar.
• Les restriccions de dificultat també importen. Els dissenyadors d’apps es preocupen per “quants sudokus hi ha d’una dificultat concreta”, i això és un filtre diferent.

Com assenyala la doctora Lina Park, investigadora en combinatòria: “Comptar graelles de solució de Sudoku és un problema d’enumeració net. Comptar tots els sudokus vàlids amb solució única és una altra història, perquè hi afegeix lògica de resolució damunt la combinatòria pura.”

Com es va calcular el nombre 6.67×10^21

El recompte canònic de 9x9 utilitza enumeració combinatòria amb poda per simetries:

1. Generar representants canònics d’estructures semblants a quadrats llatins compatibles amb caixes de 3×3.
2. Aplicar accions de grup (permutacions de files i columnes dins de bandes i piles, intercanvi de bandes i piles, transposició i reassignació de dígits) per evitar feina redundant.
3. Acumular les òrbites per recuperar el recompte complet.

Components clau de simetria que se citen sovint font: Wikipedia:

• Reassignar dígits: 9! = 362.880
• Permutar files dins de cadascuna de les 3 bandes: (3!)^3
• Permutar columnes dins de cadascuna de les 3 piles: (3!)^3
• Permutar les 3 bandes i les 3 piles: 3! × 3!
• Transposició: ×2
• Magnitud del producte: aproximadament 1,22×10^12 simetries (no totes les graelles aconsegueixen una òrbita completa, però això dona l’escala)

Per què això importa per a “quants sudokus hi ha”: entenent el grup de simetries, els investigadors eliminen casos equivalents per calcular les 5.472.730.538 graelles de solució de Sudoku essencialment diferents font: arXiv.

Mínim d’indicis: per què 17 és important per comptar sudokus

Una restricció clau dels sudokus vàlids és que han de tenir una única solució. El 2012, un equip va fer servir càlcul massiu per demostrar que no existeix cap Sudoku 9x9 amb 16 indicis; el mínim és de 17 indicis cobertura: BBC.

Implicacions:

• Existència: qualsevol sudoku 9x9 vàlid ha de tenir com a mínim 17 números donats.
• Reducció de l’espai de cerca: qualsevol recompte de “quants sudokus hi ha” pot ignorar els conjunts d’indicis inferiors a 17.
• Dificultat: els sudokus de 17 indicis tendeixen a ser difícils, però el nombre d’indicis per si sol no prediu perfectament la dificultat.

Quantes graelles de Sudoku hi ha vs. quants sudokus hi ha?

Separem dues preguntes que sovint es barregen:

• Quantes graelles de Sudoku hi ha (solucions completes)? 6,67×10^21 per al 9x9.
• Quants sudokus hi ha? No se sap exactament, però cadascuna de les 6,67×10^21 graelles pot donar lloc a una família enorme de sudokus amb solució única.

Perspectiva pràctica:

• Un generador ingenu que parteix de graelles de solució aleatòries i elimina indicis tendeix a produir innombrables sudokus diferents amb solució única amb un esforç modest.
• Fins i tot una deduplicació estricta per simetria deixa encara un conjunt impressionantment gran.

Taula comparativa

A continuació tens una referència ràpida que pots citar o veure a la comparació quan parlis de mides i estat.

Taula comparativa

Notes:

• Els recomptes de 9x9 estan avalats per enumeracions publicades Wikipedia i per la reducció a 5,47 mil milions de graelles essencialment diferents arXiv.
• Per a graelles més grans, el nombre de combinacions de Sudoku 9x9 dona una idea: passar a 16x16 fa explotar l’espai d’estats molt més enllà del que avui es pot enumerar completament.

Generació al món real: què veiem a la pràctica

A partir de construir i auditar generadors de Sudoku:

• Rendiment: els processadors moderns poden generar desenes de milers de sudokus 9x9 amb solució única per hora si fan servir resolutors ràpids i deduplicació conscient de les simetries.
• Diversitat: amb reassignació aleatòria de dígits, barreges de files i columnes i ordres d’eliminació variats, el solapament és negligible en l’ús habitual de consum.
• Curació de dificultat: afegir un motor de classificació (només senzills, candidats ocults/bloquejats, X-Wing, etc.) filtra el flux massiu en conjunts per nivells sense quedar-se sense material.

Segons els resultats del món real, la resposta operativa a “quants sudokus hi ha” per a una plataforma de jocs és “pràcticament inesgotable” a escala humana. No et quedaràs sense taulers nous i vàlids per als jugadors.

Per què això importa per als jugadors i els dissenyadors d’apps

• Novetat percebuda: fins i tot els jugadors diaris poden trobar estructures noves durant anys.
• Equitat: imposar “solució única” i comprovar que es pugui resoldre només amb lògica millora la confiança.
• Estratègia de contingut: les franges de dificultat requereixen generació dirigida, no pas eliminar indicis a l’atzar.

Si vols experimentar de primera mà l’amplitud combinatòria, prova la varietat de modes i nivells a Juga al Sudoku en línia. Si les regles o les tàctiques són noves per a tu, la nostra guia Com jugar al Sudoku per a principiants t’ajudarà a resoldre més de pressa.

Com redueixen els duplicats els investigadors? (Sudoku essencialment diferents)

L’expressió “Sudoku essencialment diferents” formalitza quan dues graelles completes es consideren el mateix patró:

• Simetries permeses: reassignació de dígits, permutacions de files i columnes dins de bandes i piles, intercanvi de bandes i piles, i transposició.
• Òrbites: totes les graelles que es poden obtenir amb aquestes simetries formen una òrbita; comptar un representant per òrbita evita el doble recompte.
• Resultat: 5.472.730.538 òrbites per al 9x9. Aquesta és la resposta neta a “quantes graelles de Sudoku hi ha si ignores l’etiquetatge superficial”.

Aquesta distinció és útil si la teva intenció amb “quants sudokus hi ha” és la varietat de patrons subjacents i no els canvis d’etiquetatge superficial.

Què determina el creixement del nombre de sudokus a partir d’una sola graella?

Partint d’una sola graella completa, pots generar molts sudokus amb solució única si tries conjunts d’indicis diferents:

• Estratègies de selecció d’indicis: col·locació simètrica, eliminació per bandes o guiada per entropia.
• Comprovacions d’unicitat: un resolutor de retrocés amb límit de recompte de solucions garanteix exactament una solució.
• Minimalitat: eliminar més indicis fins que no se’n pugui treure cap més sense trencar la unicitat (opcional, però popular per elegància).

Fins i tot ordres d’eliminació lleugerament diferents o desempats diferents del resolutor generen sudokus únics diferents. Per això “quants sudokus hi ha” supera de molt “quantes graelles de Sudoku hi ha”.

Dades i cites en què pots confiar

• 6,670903752021072936960×10^21 graelles 9x9 completes: consulta la derivació matemàtica i el resum a Wikipedia.
• 5.472.730.538 graelles essencialment diferents: la reducció per recompte d’òrbites es descriu en treballs arxivats a arXiv.
• Mínim de 17 indicis: àmpliament reportat després del càlcul del 2012 (per exemple, BBC).

Perspectiva experta sobre els límits pràctics

“Preguntar ‘quants sudokus hi ha’ és com preguntar quantes melodies es poden escriure amb 12 notes”, diu Alex Chen, responsable de sistemes de trencaclosques a LogicLab. “L’espai teòric és finit, però tan immens que, per a l’ús humà, és pràcticament il·limitat, sobretot quan filtres per unicitat i dificultat.”

Conceptes i terminologia relacionats que convé conèixer

• Quadrats llatins i ortogonalitat
• Estructura de bandes i piles en el Sudoku 9x9
• Idees d’òrbita-estabilitzador de la teoria de grups
• Sudokus mínims vs. sudokus amb múltiples solucions
• Nivells de lògica de resolució humana (senzills, parelles, patrons de peixos, acoloriment)

Entendre aquests termes t’ajuda a interpretar les afirmacions sobre “quants sudokus hi ha”, sobretot quan les fonts barregen graelles de solució amb sudokus amb pistes.

Idees clau

• Hi ha 6,67×10^21 graelles de solució completes de Sudoku 9x9; 5,47 mil milions són essencialment diferents si es tenen en compte les simetries.
• El nombre exacte de sudokus 9x9 vàlids amb solució única es desconeix, però és molt més gran que el nombre de graelles de solució.
• Qualsevol sudoku 9x9 vàlid necessita com a mínim 17 indicis; no existeixen sudokus de 16 indicis.
• Per als jugadors i les plataformes, l’oferta pràctica de sudokus nous i únics és, en la pràctica, inesgotable.
• Distingeix entre “quantes graelles de Sudoku hi ha” (solucions) i “quants sudokus hi ha” (conjunts d’indicis amb solució única) per interpretar correctament les xifres.