La 15-enigmo (aŭ la 15-ludo) estas meĥanika enigmo konsistanta el 16-fenda tabulo, ene de kiu 15 tabuloj portas la numerojn 1-15 kaj unu loko restas malplena. Por solvi la enigmon, vi devas eliri el stato kie la kaheloj estas miksitaj sur la tabulo, aranĝi ilin en ordo, kiam la ununura ago permesita estas movi kahelon najbaran al la malplena loko en ĝin (kaj tiel krei novan malplenan lokon).

La enigmo akiris multe da diskonigo je la fino de la 19-a jarcento, post kiam en 1880 oni proponis premion al tiu kiu sukcesus aranĝi la tabulon tiel, ke la kaheloj 14 kaj 15 ŝanĝu siajn lokojn (tasko matematike pruvebla sed neeble farita pere de lude ĝustaj agoj, kiel klarigite en la sekva sekcio). La provo solvi la puzlon provokis paseman frenezon, kiu daŭris plurajn monatojn ĝis ĝi formortis en julio 1880.

Kvizisto Sam Lloyd, kiu enorme popularigis la enigmon ofertante la premion, asertis ke li inventis la enigmon. Ĉi tiu aserto estis akceptita dum pli ol 100 jaroj. En 2006 la libro estis publikigita: The 15 Puzzle book, kiu deklaris ke la enigmo estis inventita fare de Noyce Palmer Chapman, leterportisto de Nov-Jorkio, proksimume dek jarojn antaŭ ĝia publikigo de Lloyd ^[1][2].

.

Kiel menciite, en 1880 Sam Lloyd ofertis grandan kontantpremion al tiu, kiu solvus la enigmon, kiam en la komenca pozicio la 14-a kaj 15-a kaheloj interŝanĝis lokojn. Sam Lloyd povus esti certa, ke la premio ne estus kolektita, ĉar ĉi tiu enigmo ne havas solvon.

Por pruvi tion, vi povas uzi la principon de pareco. Supozu, ke la enigmo povas esti solvita. Oni kolorigus la kahelojn sur la tabulo per nigra kaj blanka, kiel ŝaktabulo, kaj rigardus la movon de la malplena loko. En ĉiu turno kahelo estas movita en la malplenan lokon, tiel ke oni povas vidi la turnon kvazaŭ la malplena loko estas tiu kiu moviĝas en unu el la kvar kaheloj apud ĝi. Kiam ĝi moviĝas, ĝi ankaŭ ŝanĝas sian koloron. Tial se ĝi komencas de nigra kahelo, en la sekva movo ĝi estos sur blanka kahelo, la sekva movo sur nigra kahelo, kaj tiel plu: post nepara nombro da movoj ĝi estos sur blanka kahelo kaj post para nombro da movoj ĝi estos sur nigra kahelo. Ĉar en la fina kaj komenca stato la malplena loko estas en la sama loko, tio signifas sur la sama koloro, tiam la nombro da movoj necesaj por la solvo estas para.

Aliflanke, la ludo povas esti vidita kiel ludo de permutaĵoj . Oni rigardos la malplenan lokon kvazaŭ ĝi ankaŭ havus kahelon, kaj oni akceptos, ke ĉiu stato de la ludo estas efektive ia (re)aranĝo de la nombroj de 1 ĝis 16, kaj tia aranĝo nomiĝas permutaĵo. La celo en la ludo estas ricevi la permutaĵon:

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16

(La malplena loko estas markita ĉi tie kun la numero 16)

Al la permutaĵo:

1,2,3,4,5,6,7,8,9,10,11,12,13,15,14,16

Permutaĵoj ĝenerale estas dividitaj en parajn kaj neparajn permutaĵojn. Paraj permutaĵoj estas permutaĵoj kiuj povas esti atingitaj de la komenca stato per para nombro da interŝanĝoj de du membroj, kaj neparaj permutaĵoj estas tiuj kiuj povas esti atingitaj de la komenca stato per nepara nombro da interŝanĝoj de du membroj. Estas teoremo kiu deklaras ke ĉiu permutaĵo estas aŭ para aŭ nepara - tio estas, se ĝi povas esti atingita per para nombro da interŝanĝoj de du membroj, ĝi ne povas esti atingita per nepara nombro da interŝanĝoj, kaj inverse.

La fina stato estas nepara permutaĵo ĉar ĝi povas esti atingita per unu interŝanĝo (de la numeroj 14 kaj 15), kaj do la solvo, kiu estas serio de interŝanĝoj de du membroj (nur ke en la solvo unu el la du membroj devas esti la malplena loko, la numero 16) ankaŭ devas havi neparan nombron da interŝanĝoj. Ĉi tie ni atingis kontraŭdiron ĉar ni pruvis, ke la solvo enhavas paran nombron da movoj. Tial la solvo ne ekzistas. Tial la mona rekompenco ofertita de Sam Lloyd por solvado de la enigmo neniam estis kolektita.

Por solveblaj statoj - statoj por kiuj la enigmo povas esti solvita, ĝi ne estas precipe malfacila.

• Jerry Slocum, Dic Sonneveld, La 15 Puzlo-libro, Slocum Puzzle Foundation, 2006.

• La historio de la 15 enigmo
• Solvo de Dekkvin Enigmo
• Maksimuma nombro de movoj postulita por la m X n ĝeneralaĵo de la 15 enigmo
• 15-enigmo optimuma solvo kun deŝuto (de Herbert Kociemba)