Symmetric Sudoku-Type Games from Perfect Codes

Technische Samenvatting: Symmetrische Sudoku-achtige Spellen uit Perfecte Codes

Probleemstelling
Hoewel de standaard $9 \times 9$ Sudoku een goed bestudeerd combinatorisch object met rijke symmetrie is, veranderen veel varianten (zoals Jigsaw Sudoku) de roosterverdelingen op een manier die rotatie- en reflectiesymmetrieën vernietigt. Dit verlies aan symmetrie maakt veel standaard oplossingsstrategieën en theoretische hulpmiddelen onbruikbaar. Het artikel adresseert de behoefte aan een gegeneraliseerd kader voor het construeren van Sudoku-achtige spellen die hoge niveaus van symmetrie behouden die analoog zijn aan het klassieke spel, terwijl ze nieuwe structurele variaties bieden.

Methodologie
De auteurs stellen een constructiemethode voor gebaseerd op Lee-afstand perfecte codes en diameter-perfecte codes over ringen van gehele getallen modulo $n$ ($\mathbb{Z}_n$).

1. Theoretische Grondslag: De methode maakt gebruik van het "tegelpatroon" (tiling property) van deze codes. Een perfecte code $C$ verdeelt de ruimte $\mathbb{Z}_n^2$ in disjuncte ballen met straal $t$. Een "diameter-perfecte code" bereikt gelijkheid in de Code-Anticode-grens, waarbij de ruimte wordt verdeeld met behulp van anticodes met een specifieke diameter.
2. Roosterconstructie:
   • Er wordt een paletrooster $I$ geconstrueerd waarbij elke cel $(x, y)$ een symbool krijgt toegewezen op basis van de bal (of anticode-translatie) van welk codewoord die coördinaat bevat.
   • Een Sudokurooster $S$ wordt gedefinieerd als een Latijns vierkant van orde $n$ dat orthogonaal is ten opzichte van het paletrooster $I$. Deze orthogonaliteit garandeert dat elk symbool precies één keer voorkomt binnen de regio's die worden gedefinieerd door het tegelpatroon van de code.
3. Equivalentierelaties: De auteurs definiëren equivalentieklassen voor de resulterende roosters onder:
   • Hervermelding: Permutatie van symbolen.
   • Rijge Bewegingen: Een specifieke groep $G_S$ gegenereerd door rotaties, reflecties en translaties die de onderliggende codestructuur behouden.
4. Casestudies: Het kader wordt toegepast op twee minimale gevallen:
   • $5 \times 5$ Sudoku: Geconstrueerd uit een 1-foutcorrigerende perfecte code in $\mathbb{Z}_5^2$ (waarbij $n=5$).
   • $8 \times 8$ Sudoku: Geconstrueerd uit 3-diameter perfecte codes in $\mathbb{Z}_8^2$ (waarbij $n=8$).
5. Moeilijkheidsbeoordeling: Een "mensachtige solver" wordt geïmplementeerd om speelbaarheid te evalueren. Deze solver gebruikt uitsluitend elementaire logische deducties (Naked Single en Hidden Single) gecombineerd met een fase van trial-and-error. De moeilijkheid wordt gekwantificeerd door het aantal trial-and-error-inserties dat nodig is bovenop de initiële aanwijzingen.

Belangrijkste Bijdragen en Resultaten

• Enumeratie van Oplossingen:
  • Voor het $5 \times 5$ geval identificeerden de auteurs 2.040 geldige roosters. Tot op hervermelding en de actie van de groep van rigide bewegingen reduceren deze tot 17 niet-equivalente oplossingen.
  • Voor het $8 \times 8$ geval werden twee onderscheiden typen diameter-perfecte codes geanalyseerd. Het eerste type leverde ongeveer $2,80 \times 10^{11}$ geldige roosters op, gereduceerd tot 232.735 niet-equivalente oplossingen. Het tweede type leverde ongeveer $1,95 \times 10^{11}$ geldige roosters op, gereduceerd tot 304.014 niet-equivalente oplossingen.
• Analyse van Minimale Sudoku's:
  • Voor het $5 \times 5$ geval enumerateerden de auteurs minimale Sudoku-puzzels (die met het minimum aantal aanwijzingen vereist voor een unieke oplossing). Ze vonden in totaal 15.898.200 minimale puzzels (35.759 tot op equivalentie) met aantallen aanwijzingen variërend van 4 tot 7.
  • Voor het $8 \times 8$ geval werd een volledige enumeratie van minimale puzzels computationeel onuitvoerbaar geacht. In plaats daarvan identificeerden de auteurs minimale puzzels met aantallen aanwijzingen variërend van 10 tot 18.
• Speciale Roosters: De studie identificeerde "speciale Sudokuroosters" die voldoen aan de Sudoku-beperkingen voor elke perfecte code van de gegeven parameters, niet alleen voor de specifieke code die voor de constructie werd gebruikt. Er zijn 240 dergelijke roosters voor $5 \times 5$ en $4 \times 8!$ voor $8 \times 8$.
• Verdeling van Moeilijkheid: De analyse van de $5 \times 5$ spellen met de mensachtige solver onthulde een gebalanceerde verdeling van moeilijkheidsniveaus. Puzzels werden geclassificeerd als Gemakkelijk (score 0), Middel (score 1–10) en Moeilijk (score >10). De resultaten toonden een levensvatbare mix van moeilijkheden, waarbij veel puzzels oplosbaar zijn met basislogica en anderen aanzienlijke trial-and-error vereisen.

Betekenis en Claims
Het artikel claimt dat perfecte codes een systematisch en wiskundig rigoureus kader bieden voor het genereren van symmetrische Sudoku-achtige spellen. De primaire betekenis ligt in het aantonen dat:

1. Behoud van Symmetrie: In tegenstelling tot irreguliere varianten behouden deze op codes gebaseerde constructies inherent de rotatie- en reflectiesymmetrieën die in klassieke Sudoku worden aangetroffen, waardoor de toepassing van standaard groepstheoretische analyse mogelijk wordt.
2. Structurele Diversiteit: Het kader genereert structureel diverse geldige roosters, waardoor het landschap van Sudoku wordt uitgebreid voorbij het standaard $9 \times 9$ formaat.
3. Praktische Speelbaarheid: De moeilijkheidsanalyse bevestigt dat deze spellen niet louter theoretische constructies zijn, maar een "gebalanceerde verdeling van moeilijkheidsniveaus bieden, variërend van Gemakkelijk tot Moeilijk", waardoor ze levensvatbare alternatieven zijn voor traditionele Sudoku voor recreatief spel.

De auteurs concluderen dat deze benadering coderingstheorie en recreatieve wiskunde overbrugt, en een nieuwe weg biedt voor het genereren van logische puzzels met rijke algebraïsche structuren. Toekomstig werk wordt gesuggereerd om deze constructies uit te breiden naar andere ringen en afstandsmetrieken (bijvoorbeeld Mannheim- of rangmetrieken).