Pulmapelien matemaattinen mallintaminen ja ratkaiseminen

Abstract

Tässä tutkielmassa tarkastellaan erilaisia pulmapelejä sekä niiden matemaattista mallintamista ja ratkaisemista. Lähemmin käsitellään tiilitys- ja reunasovitusongelmia, erilaisia sudokuja sekä summafunktioon perustuvia pulmapelejä. Tiilitysongelmissa annetut epäsymmetriset palat tulee sijoittaa pelilaudalle siten, että koko alue tulee peitetyksi. Puolestaan reunasovitusongelmissa annetut symmetriset palat tulee sijoittaa pelilaudalle siten, että vierekkäisten palojen reunojen kuviot sopivat yhteen. Sudoku on tunnettu pulmapeli, jossa luvut 1–9 tulee sijoittaa ruudukkoon annettujen sääntöjen mukaisesti. Summafunktioon perustuvien pulmapelien keskeinen idea on se, että tietyssä rivissä tai sarakkeessa esiintyvät luvut tai symbolien lukumäärät summautuvat annettuun vihjenumeroon.

Tutkielma alkaa katsauksella pulmapelien historiaan, jonka jälkeen tutustutaan keskeisimpiin käsitteisiin ja mallinnustapoihin. Tämän jälkeen siirrytään tarkastelemaan lähemmin neljää edellä mainittua pulmapelikategoriaa. Jokaisesta pulmapelistä muodostetaan optimointitehtävä, jonka mallinnus käydään yksityiskohtaisesti läpi. Joillekin pulmapeleille muodostetaan muutama vaihtoehtoinen malli. Lopuksi pulmapeliongelmia ratkaistaan numeerisesti GAMS-ohjelmistolla, ja saatuja tuloksia vertaillaan keskenään. Yhtäläisyyksiä ja eroja etsitään sekä kaikkien tarkasteltujen pulmapelien väliltä, että myös yhden pulmapelityypin modifikaatioiden väliltä.