Om 15-spillet | Historie, paritet og Sam Loyds 14-15

Dillen i 1880

Spillet stammer fra staten New York i 1870'erne; Noyes Chapman, postmester i Canastota, nævnes normalt som opfinderen. I begyndelsen af 1880 blev det en dille, først i hele USA og siden i Europa.

Sam Loyds 14-15

Den amerikanske gådemager Sam Loyd hævdede senere, at han havde opfundet spillet, og fortalte om en præmie på 1.000 dollars til den, der kunne løse det med kun 14 og 15 byttet om. Ingen vandt præmien, og ingen kunne: Den stilling kan ikke løses. Hans påstand om at have opfundet det var heller ikke sand.

Hvorfor halvdelen af stillingerne er umulige

Betragt det tomme felt som en sekstende brik. Hvert skub bytter det tomme felt med én brik. For at komme tilbage til sit hjørne skal det tomme felt flytte lige så mange gange til venstre som til højre og lige så mange gange op som ned, så en stilling med det tomme felt i hjørnet ligger altid et lige antal ombytninger fra den løste rækkefølge. At bytte om på 14 og 15 er én ombytning, som er ulige, så ingen skub kan nå den. I 1879 beviste William Johnson og William Story, at præcis halvdelen af alle opstillinger kan nås.

En test for enhver stilling

Tæl de par af brikker, der står i forkert rækkefølge, når du læser rammen række for række. På et 3×3- eller 5×5-bræt kan en stilling løses, når det antal er lige. På et 4×4-bræt lægger du det tomme felts række talt nedefra til: Stillingen kan løses, når summen er ulige.

Løsning med computer

En computer kan søge efter en vej tilbage med A*, som altid ser på den mest lovende stilling først. Den anslår, hvor mange træk der stadig mangler, ud fra hvor langt hver brik er fra sit hjemfelt, plus to træk for hvert par brikker, der blokerer hinanden i deres egen række eller kolonne. At finde den korteste løsning bliver meget svært på store brætter. De sværeste stillinger i 15-spillet kræver 80 træk, og 8-spillet kræver aldrig mere end 31.

Prøv det i PictorX

Åbn 15-spillet, og klik på en brik for at skubbe den. Bland sætter brikkerne i en ny stilling, der kan løses, Løs spiller en løsning træk for træk, og Vis brikker på plads farver tallene på de brikker, der allerede står rigtigt. Vælg »Loyds 14-15« for at se den umulige stilling, og brug Størrelse til at skifte mellem 3×3, 4×4 og 5×5.

Ofte stillede spørgsmål

Hvem opfandt 15-spillet?

Noyes Chapman, postmester i Canastota, New York, nævnes normalt som opfinderen, i 1870'erne. Sam Loyds senere påstand om at have opfundet det var falsk.

Kan 14-15-puslespillet løses?

Nej. Det ligger én ombytning fra den løste rækkefølge, og alle stillinger, som skub kan nå, ligger et lige antal ombytninger væk.

Hvor mange stillinger har 15-spillet?

De 16 felter kan fyldes på 20.922.789.888.000 måder. Præcis halvdelen af dem, 10.461.394.944.000, kan nås ved at skubbe.

Uploader PictorX noget?

Nej. Spillet tegnes på et lærred i din browser. Gem henter et PNG, og Rediger åbner billedet i PictorX-editoren.