Пъзел 15

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

Пъзел 15 е популярната логическа пермутационна игра за подреждане на петнадесет цифри.

История[редактиране | edit source]

Пъзелът е изобретен през 1874 от Noyes Palmer Chapman. Интересното при този пъзел е, че първоначалното предизвикателство е било той да бъде подреден, като в изходно състояние се разменят последните две плочки (номера 14 и 15). Години по-късно аналитично е доказано, че пъзелът не може да бъде подреден, тъй като състоянието на подреденост е недостижимо, ако плочките са така разменени.

Начин на игра[редактиране | edit source]

Играта се състои от рамка в която са поставени плочки във формация 4х4. От всичките възможни позици, една плочка е извадена, така че се получават 15 номерирани плочки. Шестнадесетото празно място се използва като буфер за преместването на плочките в негово съседство. Тъй като играта е от тип пъзел, изходното състояние е всички номерирани плочки да са по реда на своята номерация. На първия ред стоят плочките с номера от 1 до 4, на втория от 5 до 8, на третия от 9 до 12 и на последния ред само три плочки с номера от 13 до 15.

Изкуствен интелект[редактиране | edit source]

При логическите игри, които попадат в класа на пермутационните игри, всяка възможна подредба на игралното пространство се описва с конкретна пермутация. При този вид игри броя пермутации винаги е краен и в повечето случаи добре известен. Тъй като по своя характер Пъзел 15 е пермутационна игра, то решение на пъзела може да се търси с помоща на [генетични алгоритми].неясно? ] Ако си представим, че във формалната граматика на играта има само четири фрази (нагоре, надясно, надолу и наляво), то можем да означим тези фрази (или команди) с четирите латински букви U, R, D и L. С помощта на тези четири команди можем да изграждаме изречения от вида - URDLURDL, които да бъдат с произволна дължина. За да бъде подреден пъзелът, от разбъркано състояние, е достатъчно да намерим подходящо изречение в граматиката на играта. Важно е да кажем, че играта е винаги наредима (стига да не са размествани плочки неправомерно), тоест гарантирано същестува решение. Важен е въпросът дали това решение е единствено, като в случая това решение не е единствено, тъй като с различни изречениа от граматиката на играта може да се достигне от разредено състояние до подредено състояние. В термините на генетичните алгоритми всяка хромозома може да олицетворява едно изречение и на базата на рекомбинация, мутация и селекция да се търси тази комбинация от команди, която води до подредба на пъзела. Този подход за решаване на пъзела е описан в проекта Genetic Algorithms solving Puzzle 15.