Symmetric Sudoku-Type Games from Perfect Codes

Sintesi Tecnica: Giochi di Tipo Sudoku Simmetrici da Codici Perfetti

Enunciato del Problema
Mentre il classico Sudoku $9 \times 9$ è un oggetto combinatorio ben studiato con ricca simmetria, molte varianti (come il Jigsaw Sudoku) alterano le partizioni della griglia in modi che distruggono le simmetrie rotazionali e riflessive. Questa perdita di simmetria rende inapplicabili molte strategie di risoluzione standard e strumenti teorici. Il lavoro affronta la necessità di un quadro generalizzato per costruire giochi di tipo Sudoku che preservino alti livelli di simmetria analoghi al gioco classico, offrendo al contempo nuove variazioni strutturali.

Metodologia
Gli autori propongono un metodo di costruzione basato su codici perfetti per la distanza di Lee e codici perfetti per il diametro su anelli di interi modulo $n$ ($\mathbb{Z}_n$).

1. Fondamento Teorico: Il metodo utilizza la "proprietà di tassellazione" di questi codici. Un codice perfetto $C$ partiziona lo spazio $\mathbb{Z}_n^2$ in sfere disgiunte di raggio $t$. Un "codice perfetto per il diametro" raggiunge l'uguaglianza nel Legame Codice-Anticodice, partizionando lo spazio utilizzando anticodici di un diametro specifico.
2. Costruzione della Griglia:
   • Viene costruita una griglia palette $I$ in cui ogni cella $(x, y)$ viene assegnata a un simbolo in base a quale sfera (o traslato di anticodice) del codice contiene quella coordinata.
   • Una griglia Sudoku $S$ è definita come un quadrato latino di ordine $n$ che è ortogonale alla griglia palette $I$. Questa ortogonalità garantisce che ogni simbolo appaia esattamente una volta all'interno delle regioni definite dalla tassellazione del codice.
3. Relazioni di Equivalenza: Gli autori definiscono classi di equivalenza per le griglie risultanti sotto:
   • Rietichettatura: Permutazione dei simboli.
   • Moti Rigidi: Un gruppo specifico $G_S$ generato da rotazioni, riflessioni e traslazioni che preservano la struttura del codice sottostante.
4. Casi di Studio: Il quadro è applicato a due casi minimi:
   • Sudoku $5 \times 5$: Costruito a partire da un codice perfetto a correzione di 1 errore in $\mathbb{Z}_5^2$ (dove $n=5$).
   • Sudoku $8 \times 8$: Costruito a partire da codici perfetti per il diametro 3 in $\mathbb{Z}_8^2$ (dove $n=8$).
5. Valutazione della Difficoltà: Viene implementato un "risolutore umanoide" per valutare la giocabilità. Questo risolutore utilizza solo deduzioni logiche elementari (Naked Single e Hidden Single) combinate con una fase di prova ed errore. La difficoltà è quantificata dal numero di inserimenti di prova ed errore richiesti oltre agli indizi iniziali.

Contributi e Risultati Chiave

• Enumerazione delle Soluzioni:
  • Per il caso $5 \times 5$, gli autori hanno identificato 2.040 griglie valide. Fino alla rietichettatura e all'azione del gruppo dei moti rigidi, queste si riducono a 17 soluzioni non equivalenti.
  • Per il caso $8 \times 8$, sono stati analizzati due tipi distinti di codici perfetti per il diametro. Il primo tipo ha prodotto circa $2,80 \times 10^{11}$ griglie valide, riducendosi a 232.735 soluzioni non equivalenti. Il secondo tipo ha prodotto circa $1,95 \times 10^{11}$ griglie valide, riducendosi a 304.014 soluzioni non equivalenti.
• Analisi del Sudoku Minimo:
  • Per il caso $5 \times 5$, gli autori hanno enumerato i puzzle Sudoku minimi (quelli con il numero minimo di indizi richiesti per una soluzione unica). Hanno trovato un totale di 15.898.200 puzzle minimi (35.759 fino all'equivalenza) con conteggi di indizi che variano da 4 a 7.
  • Per il caso $8 \times 8$, una piena enumerazione dei puzzle minimi è stata giudicata computazionalmente non fattibile. Invece, gli autori hanno identificato puzzle minimi con conteggi di indizi che variano da 10 a 18.
• Griglie Speciali: Lo studio ha identificato "griglie Sudoku speciali" che soddisfano i vincoli Sudoku per qualsiasi codice perfetto dei parametri dati, non solo per quello specifico utilizzato per la costruzione. Esistono 240 tali griglie per $5 \times 5$ e $4 \times 8!$ per $8 \times 8$.
• Distribuzione della Difficoltà: L'analisi dei giochi $5 \times 5$ utilizzando il risolutore umanoide ha rivelato una distribuzione equilibrata dei livelli di difficoltà. I puzzle sono stati classificati come Facili (punteggio 0), Medi (punteggio 1–10) e Difficili (punteggio >10). I risultati hanno mostrato una miscela vitale di difficoltà, con molti puzzle risolvibili tramite logica di base e altri che richiedono un significativo prova ed errore.

Significato e Affermazioni
Il lavoro afferma che i codici perfetti forniscono un quadro sistematico e matematicamente rigoroso per generare giochi di tipo Sudoku simmetrici. Il significato principale risiede nel dimostrare che:

1. Preservazione della Simmetria: A differenza delle varianti irregolari, queste costruzioni basate su codici preservano intrinsecamente le simmetrie rotazionali e riflessive presenti nel Sudoku classico, permettendo l'applicazione di un'analisi teorica dei gruppi standard.
2. Diversità Strutturale: Il quadro genera griglie valide strutturalmente diverse, espandendo il panorama del Sudoku oltre il formato standard $9 \times 9$.
3. Giocabilità Pratica: L'analisi della difficoltà conferma che questi giochi non sono meri costrutti teorici, ma offrono "una distribuzione equilibrata di livelli di difficoltà, che va da Facile a Difficile", rendendoli alternative valide al Sudoku tradizionale per il gioco ricreativo.

Gli autori concludono che questo approccio colma il divario tra la teoria dei codici e la matematica ricreativa, offrendo una nuova via per generare puzzle logici con strutture algebriche ricche. Si suggerisce un lavoro futuro per estendere queste costruzioni ad altri anelli e metriche di distanza (ad esempio, metriche di Mannheim o di rango).