Unruly rejtvény automatizált megoldása
Dátum
Authors
Folyóirat címe
Folyóirat ISSN
Kötet címe (évfolyam száma)
Kiadó
DOI
Absztrakt
A dolgozat az Unruly rejtvényt mutatja be. Ebben a rejtvényben a négyzetekre osztott játékmező festését kell bejezni, hogy nem szerepelhet egymás mellett három azonos színű mező, és minden sornak, minden oszlopnak azonos számú fekete és fehér mezőt kell tartalmaznia. A dolgozat bemutat két módszert ennek a feladatnak a megoldására. Az egyik a kényszer-kielégítésből ismeretes backtrack, melynek a hatékonyságát a szerző 5 heurisztika beépítésével javította. A kétszínű festés miatt a rejtvény tekinthető egy kielégíthetőségi (SAT) feladatnak is, és emiatt alkalmazható rá bármely SAT-solver. Viszont szükséges a játékszabályok és a konkrét rejtvény átalakítása KNF formára. A dolgozatban megtalálható ennek a módszere is. A dolgozatot a két módszer hatékonyságának statisztikai elemzése zárja.