Kreivi Sudoku

Sudoku-graafi on suuntaamaton graafi , jonka kärjet edustavat (tyhjän) Sudoku-palapelin soluja ja jonka reunat edustavat solupareja, jotka kuuluvat samaan riviin, sarakkeeseen tai pulmalohkoon. Sudoku-tehtävä voidaan esittää esivärjäyksen jatkeena tässä kaaviossa. Kaavio on Cayleyn kokonaislukukaavio .

Perusominaisuudet ja esimerkit

Sudoku-kentässä, jonka koko on , Sudoku-graafilla on pisteitä, joista jokaisella on täsmälleen naapurinsa. Siksi se on säännöllinen kaavio . Esimerkiksi kuvassa esitetyssä graafisessa pelikentässä on 16 kärkeä ja se on 7-säännöllinen. Useimmille Sudoku-tyypeille pelikentällä Sudoku-graafi on 20-säännöllinen graafi, jossa on 81 kärkeä [1] [2] . $n^{2}\times n^{2}$ ${\näyttötyyli n^{4))$ $3n^{2}-2n-1$ ${\näyttötyyli 4\kertaa 4}$ ${\näyttötyyli 9\kertaa 9}$

Palapelin ratkaiseminen ja kaavion värittäminen

Jokainen Sudoku-pulman rivi, sarake tai lohko muodostaa Sudoku-kaaviossa klikkin , jonka koko on yhtä suuri kuin pulmapelissä käytettyjen symbolien lukumäärä. Sudoku -kaavion värjääminen joukolla, jossa on tämä määrä värejä (vähintään mahdollinen värien määrä tälle kaaviolle), voidaan tulkita pulman ratkaisuksi. Sudoku-palapelin tavallinen muoto, jossa osa soluista on täytetty symboleilla ja loput on pelaajan täytettävä, vastaa tämän kaavion esivärjäyslaajennus -tehtävää [1] [2] .

Algebralliset ominaisuudet

Minkä tahansa kentän Sudoku-graafi on kokonaislukukuvaaja , mikä tarkoittaa, että sen viereisyysmatriisin spektri koostuu vain kokonaisluvuista. Tarkemmin sanottuna sen spektri koostuu ominaisarvoista [3] $n$ $n^{2}\times n^{2}$

$3n^{2}-2n-1$ , moninkertaisesti , $yksi$
$2n^{2}-2n-1$ , moninkertaisesti , ${\näyttötyyli 2(n-1)}$
$n^{2}-n-1$ , moninkertaisesti , $2n(n-1)$
$n^{2}-2n-1$ , moninkertaisesti , ${\näyttötyyli (n-1)^{2))$
$-yksi$ , moninkertaisesti , ${\displaystyle n^{2}(n-1)^{2))$
$-n-1$ , moninkertaisuudella . ${\displaystyle 2n(n-1)^{2))$

Se voidaan esittää Abelin ryhmän Cayley-graafina [4] . ${\displaystyle Z_{n}^{4))$

Aiheeseen liittyvät kaaviot

Sudoku-graafi sisältää aligraafina tornin graafin , joka määritellään samalla tavalla, mutta vain Sudoku-pelikentän riveille ja sarakkeille (mutta ei lohkoille).

20-säännöllinen 81-pisteinen Sudoku-graafi on erotettava toisesta 20-säännöllisestä 81-pisteen graafista, Brouwer-Hemers-graafista , jossa on pienempiä klikkejä (koko 3) ja joka vaatii vähemmän värejä (7 9 sijasta) [5] .

Muistiinpanot

↑ 1 2 Jesús Gago-Vargas, Maria Isabel Hartillo-Hermoso, Jorge Martín-Morales, Jose Maria Ucha-Enríquez. Sudokus ja Gröbner Bases: Not only a divertimento // Computer Algebra in Scientific Computing, 9th International Workshop, CASC 2006, Chisinau, Moldova, 11.–15.9.2006, Proceedings / Victor G. Ganzha, Ernst W. Mayr, Evgenii V. Vorozhtsov. - Springer, 2006. - T. 4194. - S. 155-165. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/11870814_13 .
↑ 1 2 Agnes M. Herzberg, M. Ram Murty. Sudoku-neliöt ja kromaattiset polynomit // Notices of the American Mathematical Society . - 2007. - T. 54 , no. 6 . — S. 708–717 .
↑ Torsten Sander. Sudoku-kaaviot ovat olennaisia // Electronic Journal of Combinatorics. - 2009. - T. 16 , no. 1 . — C. Huomautus 25, 7 s .
↑ Walter Klotz, Torsten Sander. Integral Cayley kuvaajat Abelin ryhmien yli // Electronic Journal of Combinatorics. - 2010. - T. 17 , no. 1 . — C. Tutkimuspaperi 81, 13 s .
↑ Weisstein, Eric W. Brouwer–Haemers Graph Wolfram MathWorld -verkkosivustolla .