Femtonspel

Femtonspel, femtonpussel, en typ av pussel som består av femton kvadratiska brickor i en ram. Brickorna kan vara numrerade från ett till femton, eller utgöra en bild. Ramen rymmer 4*4=16 brickor, så det finns ett hål. Med hjälp av detta hål kan spelaren byta plats på brickorna tills de hamnar på rätt ställen.

Om man plockar isär ett femtonspel och byter ordning på två på varandra följande brickor när man sätter ihop det igen blir spelet olösbart.

Länge innehöll Mac OS Classic ett femtonspel som lät uttråkade användare pussla ihop Apples logotyp.

Ordet femtonspel används även i överförd bemärkelse: Ett antal åtgärder, själva kanske onödiga, måste utföras, kanske i en viss ordning, för att en nödvändig åtgärd skall kunna utföras. De onödiga åtgärderna måste därefter, kanske i omvänd ordning, återställas. Exempel: ommöblering i ett trångt utrymme.

Pusslet finns också i andra storlekar, speciellt det mindre åttaspelet, som är 3×3 rutor stort.

n-spelet är ett klassiskt problem för byggande av algoritmer som innehåller heuristik. Ofta använda heuristiker för detta problem innefattar att räkna antalet felplacerade brickor och hitta Manhattanavståndet mellan varje brickas position och dess mål. Observera att ingen av dessa metoder överskattar antalet drag som är kvar, vilket ger opitmalitet för vissa sökalgoritmer som A*.

I engelsk-talande länder kallas Femtonspelet för "Slide Puzzle".

Lösning

Man löser först antingen de två översta raderna var för sig, eller de två första kolumnerna var för sig. Här beskrivs hur man gör det radvis. De två första brickorna, 1 och 2, är enkla och sedan gäller det att få brickorna 3 och 4 intill varandra och i rätt ordning någonstans och sedan rotera upp dem på sina platser. Med 5-6-7-8 gör man precis likadant och de två översta raderna är klara. Därefter skall man få 9 och 13 intill varandra i rätt ordning och rotera in dem på plats, varefter man gör detsamma med 10 och 14. Brickorna 11, 12 och 15 kan nu roteras tills man är klar. Brickorna 11, 12 och 15 utgör en cyklisk permutation och genom att byta plats på två av dem får man den motsatta ordningen (d.v.s. med motsatt paritet), varför spelet ej är lösbart. Härav följer också att vilka två brickor man än byter plats på, så gör detta spelet olösligt, eftersom pariteten ändras.