Unruly rejtvény automatizált megoldása

Dátum
Folyóirat címe
Folyóirat ISSN
Kötet címe (évfolyam száma)
Kiadó
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.

Leírás
Kulcsszavak
Unruly rejtvény
Forrás