Olisi tällainen peli:
http://pommisuoja.omablogi.fi/files/2015/11/color_rotate_puzzle_demo.gif
Tuosta demonstraatiosta jo varmaan käykin ilmi mikä pelin idea on. Siinä täytyy siis noita neljää ympyrää pyörittelemällä saada kuulat alkuperäiseen asentoon, joka on: kultaiset kultaisella ympyrällä, musta keskellä ja loput värit omilla ympyröillään (paikoissa, jotka ovat vielä määräämättä, eli tuolla reunoilla.)
Minkälaisella algoritmilla tämä ratkeaisi?
Tätähän voisi mallintaa permutaatioryhmän S_16 (kuusitoista eri kuulaa) aliryhmänä, jonka nuo neljä eri ympyrän pyöräytystä virittää. (Onko tämä muuten koko ryhmä eli saadaanko kuulat mihin tahansa järjestyksee noin pyörittelemällä?) Tässähän on tietysti monta samanväristä, joten periaatteessa se ei ole S_16, koska eri järjestykset on monet samanlaisia, kun saman väriset kuulat ajatellaan identtisiksi, mutta voidaan vaikka ajatella, että jokainen kuula on erilainen. Tämähän ei ratkaisuun vaikuta: riittää, että saadaan kuulat jossain järjestyksessä oikeille väripaikoilleen.
http://pommisuoja.omablogi.fi/files/2015/11/color_rotate_puzzle_demo.gif
Tuosta demonstraatiosta jo varmaan käykin ilmi mikä pelin idea on. Siinä täytyy siis noita neljää ympyrää pyörittelemällä saada kuulat alkuperäiseen asentoon, joka on: kultaiset kultaisella ympyrällä, musta keskellä ja loput värit omilla ympyröillään (paikoissa, jotka ovat vielä määräämättä, eli tuolla reunoilla.)
Minkälaisella algoritmilla tämä ratkeaisi?
Tätähän voisi mallintaa permutaatioryhmän S_16 (kuusitoista eri kuulaa) aliryhmänä, jonka nuo neljä eri ympyrän pyöräytystä virittää. (Onko tämä muuten koko ryhmä eli saadaanko kuulat mihin tahansa järjestyksee noin pyörittelemällä?) Tässähän on tietysti monta samanväristä, joten periaatteessa se ei ole S_16, koska eri järjestykset on monet samanlaisia, kun saman väriset kuulat ajatellaan identtisiksi, mutta voidaan vaikka ajatella, että jokainen kuula on erilainen. Tämähän ei ratkaisuun vaikuta: riittää, että saadaan kuulat jossain järjestyksessä oikeille väripaikoilleen.
Vastaukset 3
Vanhimmat
Luulisin, että iteratiivisesti syvenevä A* voisi toimia tässä, https://en.wikipedia.org/wiki/Iterative_deepening_A* .
S24:ssä on kai bugi, mutta tuo asteriski kuuluu vielä URLiin.
Minä yrittäisin niin että laittaisin ensin kahden ympyrän ulkokehällä olevat kolme väriä paikalleen ja sitten yrittäisin keskiympyrällä ja yhdellä ulkoympyrällä. Jos ei onnistuisi vaihtaisin kaksi palloa keskenään "jäädytetyllä" ympyrällä ja yrittäisin uudelleen.