Matematiikkaa sudokun takana
Lindroos, Julia (2023)
2023
Tekniikan ja luonnontieteiden kandidaattiohjelma - Bachelor's Programme in Engineering and Natural Sciences
Tekniikan ja luonnontieteiden tiedekunta - Faculty of Engineering and Natural Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2023-06-19
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202306166809
https://urn.fi/URN:NBN:fi:tuni-202306166809
Tiivistelmä
Tässä kandidaatintutkielmassa perehdytään sudokun rakenteeseen ja ratkaisuun graafiteorian näkökulmasta. Työ alkaa graafiteorian keskeisimpien määritelmien ja esimerkkien esittelyllä. Esimerkeissä käsitellään graafeja, jotka ovat yhtenäisiä, yksinkertaisia ja painottomia, koska sellaisten graafien tunteminen riittää sudokugraafin ymmärtämiseen. Tutkielmassa määritetään, mitä graafien värittämisellä tarkoitetaan ja kuinka sitä voidaan soveltaa.
Koska latinalainen neliö on tunnetusti sudokun esi-isä, on siihen syytä tutustua. Latinalaisiin neliöihin perehdytään yleisten määritelmien, lauseiden ja niiden todistusten myötä. Graafiteorian perusteiden avulla latinalaisen neliön pohjalta muodostetaan graafi ja toteutetaan sen solmu- ja särmäväritys.
Latinalaisen neliön käsittelyn jälkeen siirrytään tarkastelemaan sudokua ja sen terminologiaa tarkemmin. Terminologiaan liittyy vahvasti sudokun ratkaiseminen, joten työssä esitellään yleinen ratkaisumenetelmä ja logiikka sudokun täydentämisen takana. Sudokun pohjalta saadaan muotoiltua graafi, jota kutsutaan sudokugraafiksi. Sudokugraafin väritysongelma on laajempi, kuin latinalaisen neliön, koska sudokun värittämiseen liittyy enemmän ehtoja. Työn tuloksena saatiin selvitettyä, kuinka monta eri väriä sudokugraafin kunnolliseen väritykseen tarvitaan. Tutkielmassa on myös esimerkki solmuväritetystä sudokugraafista.
Työssä esitellään kaksi erityistapausta, joissa osittain väritetyt sudokugraafit voidaan värittää loppuun kahdella eri tavalla. Esimerkkien sudokugraafit poikkeavat toisistaan, sillä värittämättömien solmujen lukumäärä ei ole yhtä suuri. Tutkielmassa kerrotaan, miksi vaihtoehtoja on kaksi, ja miksi sudokugraafin värittäminen näissä tapauksissa ei ole yksikäsitteistä.
Tutkielman lopussa perustellaan, miksi sudoku sisältyy graafiteorian täydellisiin NP-ongelmiin. Luokitus NP-ongelmaksi kertoo siitä, ettei kaikenkokoisia sudokuja ratkovaa tehokasta ohjelmaa voida luoda realistisessa ajassa. Graafiteorian ja sudokun yhteyttä voidaan kuitenkin hyödyntää tällaisen ohjelman luomisessa, kun kyseessä on esimerkiksi normaali 9x9-kokoinen sudoku.
Koska latinalainen neliö on tunnetusti sudokun esi-isä, on siihen syytä tutustua. Latinalaisiin neliöihin perehdytään yleisten määritelmien, lauseiden ja niiden todistusten myötä. Graafiteorian perusteiden avulla latinalaisen neliön pohjalta muodostetaan graafi ja toteutetaan sen solmu- ja särmäväritys.
Latinalaisen neliön käsittelyn jälkeen siirrytään tarkastelemaan sudokua ja sen terminologiaa tarkemmin. Terminologiaan liittyy vahvasti sudokun ratkaiseminen, joten työssä esitellään yleinen ratkaisumenetelmä ja logiikka sudokun täydentämisen takana. Sudokun pohjalta saadaan muotoiltua graafi, jota kutsutaan sudokugraafiksi. Sudokugraafin väritysongelma on laajempi, kuin latinalaisen neliön, koska sudokun värittämiseen liittyy enemmän ehtoja. Työn tuloksena saatiin selvitettyä, kuinka monta eri väriä sudokugraafin kunnolliseen väritykseen tarvitaan. Tutkielmassa on myös esimerkki solmuväritetystä sudokugraafista.
Työssä esitellään kaksi erityistapausta, joissa osittain väritetyt sudokugraafit voidaan värittää loppuun kahdella eri tavalla. Esimerkkien sudokugraafit poikkeavat toisistaan, sillä värittämättömien solmujen lukumäärä ei ole yhtä suuri. Tutkielmassa kerrotaan, miksi vaihtoehtoja on kaksi, ja miksi sudokugraafin värittäminen näissä tapauksissa ei ole yksikäsitteistä.
Tutkielman lopussa perustellaan, miksi sudoku sisältyy graafiteorian täydellisiin NP-ongelmiin. Luokitus NP-ongelmaksi kertoo siitä, ettei kaikenkokoisia sudokuja ratkovaa tehokasta ohjelmaa voida luoda realistisessa ajassa. Graafiteorian ja sudokun yhteyttä voidaan kuitenkin hyödyntää tällaisen ohjelman luomisessa, kun kyseessä on esimerkiksi normaali 9x9-kokoinen sudoku.
Kokoelmat
- Kandidaatintutkielmat [8683]