15 (загатка)

15, позната и како петнаесетка или мистично поле — лизгачка загатка којашто се состои од рамка со плочки означени со броеви, поставени во случаен редослед со едно празно поле. Целта на загатката е, со лизгање на плочките означени со броеви низ празното поле, да се подредат редоследно од онаа со најмал до онаа со најголем број.

Загатката е решена кога броевите ќе бидат подредени редоследно од најмал до најголем

Загатката се јавува и во други големини, од кои особено е позната онаа под називот „8“. Така на пример, ако рамката е со димензии 3×3, тогаш таа се нарекува „8“; ако е со димензии 4×4, тогаш се нарекува „15“; а ако е со димензии 5×6, тогаш се нарекува „29“.

Примена

Загатката служи како класичен проблем за моделирање на евристички алгоритми. Често применувани евристички методи за овој проблем се пребројување на бројот на погрешно поставени плочки и пресметување на збирот на растојанието меѓу погрешната и целната поставеност. Притоа, обата методи се изводливи, т.е. тие никогаш не го преценуваат бројот на преостанати потези, што овозможува оптималност за некои пребарувачки алгоритми како што е на пример алгоритмот А*.

Поврзано

• Минусна коцка
• Рубикова коцка

Надворешни врски

• The history of the 15 puzzle
• Fifteen Puzzle Solution
• Maximal number of moves required for the m X n generalization of the 15 puzzle
• 15-Puzzle Optimal Solver