Räkna Sudoku

En Sudoku-graf är en oriktad graf vars hörn representerar cellerna i ett (tomt) Sudoku-pussel, och vars kanter representerar par av celler som tillhör samma rad, kolumn eller pusselblock. Sudoku-pusselproblemet kan representeras som en förlängning av förfärgningen på denna graf. Grafen är en heltalsgraf av Cayley .

Grundläggande egenskaper och exempel

På ett Sudoku-fält av storlek har Sudoku-grafen hörn, var och en med exakt sina grannar. Därför är det en vanlig graf . Till exempel har grafen som visas i figuren med spelplanen 16 hörn och är 7-regelbunden. För de flesta typer av Sudoku på spelplanen är Sudoku-grafen en 20-regelbunden graf med 81 hörn [1] [2] . $n^{2}\times n^{2}$ ${\displaystyle n^{4))$ $3n^{2}-2n-1$ $4\times 4$ $9\times 9$

Lösa pusslet och färglägga grafen

Varje rad, kolumn eller block i ett Sudoku-pussel bildar en klick i Sudoku-grafen, vars storlek är lika med antalet symboler som används i pusslet. Att färglägga en Sudoku-graf med en uppsättning med detta antal färger (minsta möjliga antal färger för denna graf) kan tolkas som en lösning på pusslet. Den vanliga formen av ett Sudoku-pussel, där vissa celler är fyllda med symboler och resten måste fyllas i av spelaren, motsvarar problemet med förfärgningsförlängningen för denna graf [1] [2] .

Algebraiska egenskaper

För alla , är fältets Sudoku-graf en heltalsgraf , vilket betyder att spektrumet för dess närliggande matris endast består av heltal. Mer exakt består dess spektrum av egenvärden [3] $n$ $n^{2}\times n^{2}$

$3n^{2}-2n-1$ , med mångfald , $ett$
$2n^{2}-2n-1$ , med mångfald , $2(n-1)$
$n^{2}-n-1$ , med mångfald , $2n(n-1)$
$n^{2}-2n-1$ , med mångfald , $(n-1)^{2}$
$-ett$ , med mångfald , ${\displaystyle n^{2}(n-1)^{2))$
$-n-1$ , med mångfald . ${\displaystyle 2n(n-1)^{2))$

Det kan representeras som Cayley-grafen för en abelsk grupp [4] . ${\displaystyle Z_{n}^{4))$

Relaterade grafer

Sudoku-grafen innehåller som en undergraf torngrafen , som definieras på samma sätt, men bara på raderna och kolumnerna (men inte på blocken) på Sudoku-spelfältet.

Den 20-regelbundna 81-vertex Sudoku-grafen bör särskiljas från en annan 20-reguljär 81-vertex-graf, Brouwer-Hemers-grafen , som har mindre klickar (storlek 3) och kräver färre färger (7 istället för 9) [5] .

Anteckningar

↑ 1 2 Jesús Gago-Vargas, Maria Isabel Hartillo-Hermoso, Jorge Martín-Morales, Jose Maria Ucha-Enríquez. Sudokus och Gröbner-baser: Not only a divertimento // Computer Algebra in Scientific Computing, 9th International Workshop, CASC 2006, Chisinau, Moldavien, 11–15 september 2006, Proceedings / Victor G. Ganzha, Ernst W. Mayr, Evgenii V. Vorozhtsov. - Springer, 2006. - T. 4194. - S. 155-165. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/11870814_13 .
↑ 1 2 Agnes M. Herzberg, M. Ram Murty. Sudoku-rutor och kromatiska polynom // Notices of the American Mathematical Society . - 2007. - T. 54 , nr. 6 . — S. 708–717 .
↑ Torsten Sander. Sudoku-grafer är integrerade // Electronic Journal of Combinatorics. - 2009. - T. 16 , nr. 1 . — C. Not 25, 7s .
↑ Walter Klotz, Torsten Sander. Integral Cayley-grafer över abelska grupper // Electronic Journal of Combinatorics. - 2010. - T. 17 , nr. 1 . — C. Forskningsuppsats 81, 13pp .
↑ Weisstein, Eric W. Brouwer–Haemers Graph på Wolfram MathWorld -webbplatsen .