Lights Out -pelin ratkaiseminen pseudoinverssin avulla

Abstract

Tässä kandidaatintyössä esitetään 25 ruudun Lights Out -peli lineaarisena systeeminä, joka koostuu vieruspistematriisista A, tilannevektorista p ja strategiavektorista x. Työssä tarkastellaan pelin ratkeavuutta lineaarialgebran keinoin ja esitetään yleinen ratkaisutapa ratkeaviin alkutilanteisiin. Yleinen ratkaisutapa perustuu vieruspistematriisin A pseudoinverssin A+ muodostamiseen. Tämän lisäksi esitellään ratkeavuustesti, jonka avulla voidaan selvittää minkä tahansa alkutilanteen ratkeavuus. Näihin tavoitteisiin päästään selvittämällä vieruspistematriisin A aste ja lineaarisensysteeminratkaisujenlukumäärä.Työn lukijalta oletetaan lineaarialgebran, matriisilaskennan, algebran ja graafiteorian perusteiden tuntemus. Edellä esiteltyjä tuloksia sovelletaan vaikeimman tapauksen minimisiirtojen selvittämiseen.