15-spillet

15-spillet er et velkendt logisk spil, som spilles med 15 brikker placeret på et bræt med 4 * 4 = 16 felter; dvs. at et af felterne er tomt. Brikkerne er som regel nummereret fra 1 til 15; men andre symboler kan ligeledes bruges. Disse kan være bogstaverne i alfabetet, et billede, som er delt op i stykker eller andre fænomener.

Spillet går ud på at få brikkerne stillet op i den rigtige rækkefølge ud fra en tilfældig startkonfiguration. Et (tilladt) træk består i, at en brik kan skubbes hen på nabofeltet, såfremt dette er tomt. Hvis det er cifrene fra 1 til 15 der er brugt som symboler, vil den endelige løsning se således ud:

Man kan ikke være sikker på, at der altid findes en løsning, da den afhænger af hvordan brikkerne er permuteret (ombyttet). Hvis man ud fra den færdige opsætning flytter rundt på brikkerne ved lovlige træk, så er det oplagt at der altid findes en løsning; nemlig den hvor man foretager de inverse flytninger og ender tilbage hvor man startede. Andre måder hvorpå spillet kan løses, er ved brute force-metoden, hvor man prøver sig frem, til man finder løsningen.

Som nævnt er der ikke altid en løsning, og følgende figur viser et eksempel på en sådan opsætning, hvor der blot er byttet om på tallene 14 og 15:

Det er faktisk således at hvis det er en lige permutation så findes en løsning – medens ulige permutationer ingen løsning har.