| الوصف: |
Tiivistelmä. Sudoku on 2000-luvulla suosioon noussut päättelypeli, joka on neliön muotoinen yhdeksään laatikkoon jaettu ruudukko. Jokainen laatikko koostuu yhdeksästä ruudusta ja jokaiseen sudoku-ruudukon laatikkoon, riviin ja sarakkeeseen tulee saada luvut 1, 2,…,9. Sudokun juuret ylettyvät aina 1700-luvulle matemaatikon Leonhard Eulerin kehittämiin latinalaisiin neliöihin. Latinalaisen neliön jokaiselle riville ja sarakkeelle tulee saada luvut 1, 2,…,9. Täten sudokut ovat latinalaisten neliöiden erikoistapauksia. Sudokun kaltaisia ongelmia julkaistiin ensimmäisenä ranskalaisessa sanomalehdessä jo 1900-luvulla. Ensimmäiset sudokut kuitenkin julkaistiin vasta 1970-luvulla nimellä Number Place, Dell Magazines lehdessä Yhdysvalloissa, kun Howard Garnes lisäsi latinalaiseen neliöön laatikkovaatimuksen. Japanissa vuonna 1984 Nikoli-yhtiö julkaisi päättelypelin nimellä Sudoku, joka sai nimensä japaninkielisestä sanonnasta ”Suuji wa dokushin ni kagiru”, joka tarkoittaa, että numeroiden tulee olla yksittäisiä. Sudokujen suosio räjähti japanissa, sillä japaninkieliset aakkoset eivät sovellu sanaristikoihin. Sudokut nousivat suosiossa muuallakin maailmassa 2000-luvulla, kun uusiseelantilainen Wayne Gould kehitti ensimmäisenä tietokoneohjelman, jonka avulla pystyttiin luomaan sudokuja nopeasti. Tässä työssä tutustutaan sudokun lisäksi rodokuun ja shidokuun, jotka omaavat sudokun säännöt, mutta ovat kooltaan pienempiä. Rodoku on neliön muotoinen kuuteen laatikkoon jaettu ruudukko, jossa jokainen laatikko koostuu kuudesta ruudusta ja joihin tulee saada numerot 1, 2,…,6. Shidoku on puolestaan jaettu neljään eri laatikkoon, joihin jokaiseen tulee saada numerot 1, 2,…,4. Tässä työssä lasketaan kuinka monta sudokua, rodokua ja shidokua on olemassa ja kuinka monta ekvivalentisti eroavaa sudokua, shidokua ja rodokua on olemassa. Ekvivalentisti eroavilla sudokuilla tarkoitetaan sudokuja, joita ei voi muuttaa toisikseen niin sanottujen sudokun symmetrioiden avulla. Uudelleen numerointi on yksi sudokun symmetrioista ja sen avulla voidaan vaihtaa esimerkiksi kaikkien numeroiden 1 ja 2 paikkoja. Tällöin saadaan aikaiseksi uusi sudoku, joka ei kuitenkaan ole ekvivalentisti eroava alkuperäisestä, sillä se on saatu aikaiseksi yhdellä sudokun symmetrioista. Ekvivalentisti eroavien sudokujen, rodokujen ja shidokujen lukumäärän laskemiseen tarvitsemme Burnsiden Lemmaa. Burnsiden Lemma on ryhmäteoriaan perustuva tulos, jota voidaan käyttää, kun lasketaan esimerkiksi väritykseltään eroavien symmetristen kappaleiden lukumääriä. Sudokun tapauksessa numerot voidaan ajatella väreiksi, jolloin voidaan soveltaa Burnsiden Lemmaa. Sudokujen lukumääräksi saatiin 6670903752021072936960 ≈ 6,671 ×10^21 kappaletta ja ekvivalentisti eroavia sudokuja saatiin 5472730538 kappaletta. Shidokujen lukumääräksi saatiin 288 kappaletta ja ekvivalentisti eroavia shidokuja saatiin 2 kappaletta. Rodokujen lukumääräksi saatiin 28200960 kappaletta ja ekvivalentisti eroavia rodokuja saatiin 49 kappaletta. Työssä tutustutaan myös algoritmeihin, joilla sudokuja voidaan ratkaista. James Crook:in kehittelemän algoritmin avulla haastavia sudokuja voidaan ratkaista vain kynän ja paperin avulla. Brute force -algoritmi tunnetaan kaikkein alkukantaisimpana algoritmina. Nimensä mukaisesti se kokeilee kaikkia mahdollisia ratkaisuvaihtoehtoja, kunnes se löytää ratkaisun. Geeniperimä-algoritmi yhdistää mahdollisia ratkaisuja usean sukupolven ajan ja pyrkii löytämään ratkaisun matkimalla luonnonvalintaa, eli evoluutioprosessia. |