Femtonspelet
Femtonspelet är en ram med femton numrerade brickor och en tom ruta. Skjut tillbaka brickorna i ordning, så är det löst. Det ser enkelt ut, men det orsakade en vurm 1880, och bakom det finns ett av de snyggaste bevisen i rekreationsmatematiken: hälften av alla ställningar går aldrig att lösa.
Vurmen 1880
Pusslet kommer från delstaten New York på 1870-talet; Noyes Chapman, postmästare i Canastota, brukar anges som uppfinnaren. I början av 1880 blev det en vurm, först i hela USA och sedan i Europa.
Sam Loyds 14-15
Den amerikanske pusselmakaren Sam Loyd påstod senare att han hade uppfunnit pusslet, och berättade om ett pris på 1 000 dollar till den som kunde lösa det med bara 14 och 15 omkastade. Ingen vann priset, och ingen kunde: den ställningen går inte att lösa. Hans anspråk på uppfinningen var inte heller sant.
Varför hälften av ställningarna är omöjliga
Se den tomma rutan som en sextonde bricka. Varje drag byter plats på den tomma rutan och en bricka. För att komma tillbaka till sitt hörn måste den tomma rutan flytta lika många gånger åt vänster som åt höger och lika många gånger uppåt som nedåt, så en ställning med den tomma rutan i hörnet ligger alltid ett jämnt antal byten från den lösta ordningen. Att byta 14 och 15 är ett byte, och det är udda, så inga drag kan nå den ställningen. År 1879 bevisade William Johnson och William Story att exakt hälften av alla uppställningar kan nås.
Ett test för varje ställning
Räkna paren av brickor som står i fel ordning när du läser ramen rad för rad. På ett 3×3- eller 5×5-bräde går en ställning att lösa när det antalet är jämnt. På ett 4×4-bräde lägger du till den tomma rutans rad räknad nedifrån: ställningen går att lösa när summan är udda.
Lösning med dator
En dator kan söka en väg tillbaka med A*, som alltid tittar på den mest lovande ställningen först. Den uppskattar hur många drag som återstår utifrån hur långt varje bricka är från sin hemruta, plus två drag för varje par brickor som blockerar varandra på sin egen rad eller i sin egen kolumn. Att hitta den kortaste lösningen blir mycket svårt på stora bräden. De svåraste ställningarna i femtonspelet kräver 80 drag, och 8-spelet kräver aldrig mer än 31.
Prova i PictorX
Öppna Femtonspelet och klicka på en bricka för att skjuta den. Blanda kastar om brickorna till en ny ställning som går att lösa, Lös spelar upp en lösning drag för drag, och Visa brickor på plats färgar siffrorna på de brickor som redan står rätt. Välj ”Loyds 14-15” för att se den omöjliga ställningen, och med storlek växlar du mellan 3×3, 4×4 och 5×5.
Ofta ställda frågor
Vem uppfann femtonspelet?
Noyes Chapman, postmästare i Canastota, New York, brukar anges som uppfinnaren, på 1870-talet. Sam Loyds senare anspråk på det var falskt.
Går 14-15-pusslet att lösa?
Nej. Det ligger ett byte från den lösta ordningen, och varje ställning som dragen kan nå ligger ett jämnt antal byten bort.
Hur många ställningar har femtonspelet?
De 16 rutorna kan fyllas på 20 922 789 888 000 sätt. Exakt hälften av dem, 10 461 394 944 000, kan nås genom att skjuta brickorna.
Laddar PictorX upp något?
Nej. Pusslet ritas på en canvas i webbläsaren. Spara laddar ner en PNG, och Redigera öppnar bilden i PictorX-redigeraren.
Relaterade verktyg
Femtonspelet
Spela det klassiska femtonspelet i webbläsaren med träbrickor på 3×3, 4×4 eller 5×5. Blanda, skjut hela rader på en gång, prova Sam Loyds omöjliga 14-15 eller se Lös göra det färdigt.
Tornen i Hanoi
Flytta ett torn av skivor mellan tre pinnar i webbläsaren. En skiva i taget, aldrig en större på en mindre. Den kortaste lösningen är 2ⁿ − 1 drag.
Tornen i Hanoi
Tornen i Hanoi: tre pinnar, en skiva i taget och aldrig en större på en mindre. Den kortaste lösningen är 2ⁿ−1 drag. Édouard Lucas presenterade pusslet 1883.
Springartur
Låt en springare hoppa till varje ruta på brädet exakt en gång. Spela själv med Warnsdorff-tips, eller se Lös slutföra en öppen eller sluten tur. Spara vägen som PNG.
Åtta damer
Placera åtta damer på ett schackbräde så att ingen angriper en annan. Prova själv, se sökningen med backtracking hitta en lösning steg för steg och gå igenom alla 92 lösningar.
Langtons Myra
Kör Langtons myra i webbläsaren. Se symmetri, kaos och motorvägen på 104 steg, och prova sedan flerfärgade regler, flera myror, ett sexkantigt rutnät och turmiter.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Spela Femtonspelet