Piętnaście puzzle odznacza się tym, że tylko połowa możliwych stanów układu są rozwiązywalne. Jeśli przerzucisz płytki 14 i 15, nie ma możliwości przesunięcia bloków, aby zostały one odwrócone.

Twoim zadaniem jest zbudowanie programu, który akceptuje listę liczb całkowitych w wybranym przez Ciebie formacie (zawierającym dokładnie jedno wystąpienie każdej liczby od 0 do 15, gdzie 0 to puste miejsce) reprezentujące stan ułożenia płytek w siatka 4x4 i generuje pojedynczą wartość logiczną określającą, czy siatka jest rozwiązalna, czy nie.

Wygrywa najkrótszy kod do wykonania tego w dowolnym języku.

Galaretka , 9 bajtów

Œc>/€;TSḂ

Monadyczny link akceptujący listę liczb całkowitych czytających w rzędzie głównym na przemian między lewą prawą a prawą lewą, która daje 0rozwiązywalność, a 1jeśli nie (w celu odwrócenia tego dodania ¬po prawej stronie kodu).

Wypróbuj online! (ten przykład to tablica, na której 12 musi tylko wsunąć się na miejsce)

W jaki sposób?

Podobnie do odpowiedzi Johna Dvoraka obliczamy parzystości i wykorzystujemy wężowy porządek wejściowy, aby uprościć parzystość szachownicy, chociaż zamiast sprawdzania równości parzystości sumujemy liczbę poza kolejnością z niezerowymi indeksami i sprawdzamy, czy to jest dziwny:

Œc>/€;TSḂ - Link: list of integers
Œc        - unordered pairs
    €     - for each:
   /      -   reduce with:
  >       -     greater than?
      T   - truthy indices (i.e. [1..16] without 1-indexed index of 0)
     ;    - concatenate
       S  - sum
        Ḃ - is odd?

J, 28 znaków

((C.!.2=_1^i.&0)&.".&.stdin''

Kolejność wprowadzania jest większa od rzędu, a wiersze odczytywane są naprzemiennie od lewej do prawej i od prawej do lewej w jednej ścieżce w poprzek tabeli. Zakłada, że ​​zero należy do lewego górnego rogu.

Użycie w systemie Windows:

<nul set /p="0 1 2 3 7 6 5 4 8 9 10 11 15 14 13 12" | jconsole c:\...\15.jhs

Wyjaśnienie:

• <nul set /p= służy do zapobiegania nowej linii na wejściu, że echo powoduje, że ".się nie podoba. Oczywiście Unix obsługuje echo /n.
• v&.".&.stdin''odczytuje „v pod analizą pod stdin”, co oznacza „wejście”, następnie parsuje dane wejściowe, następnie wykonuje v, następnie anuluje parsowanie (= format), a następnie cofa dane wejściowe (= wyjście) ”. 1!:1]3jest o jeden znak krótszy, ale nie ma zdefiniowanej odwrotności.
• C.!.2oznacza „parzystość permutacji”. Zwraca albo1 (parzystość) albo _1(nieparzystość). To jest,_1^inversions
• _1^i.&0 oznacza „-1 do potęgi indeksu 0”.
• a zatem, C.!.2=_1^i.&0oznacza „czy parzystość permutacji jest równa parzystości pozycji otworu?”

Działa to na płycie 4x4, ale jeśli pożądana pozycja końcowa jest większa od rzędu od lewej do prawej, to permutacja dla rozwiązanej pozycji ma nieparzystą liczbę inwersji, a zatem nieparzystą parzystość. Również parzystość jest odwracana (dla dowolnej kolejności wprowadzania), gdy żądana pozycja otworu przesuwa się z lewego górnego na prawy dolny. W obu przypadkach poprawka dotyczy jednego znaku: dodaj -po= aby odwrócić oczekiwaną parzystość.

Dowód poprawności:

Po każdym ruchu zero zmienia pozycję z pewną liczbą, odwracając parzystość permutacji. Zero zmienia się również między białymi i czarnymi pozycjami szachownicy, oznaczonymi nieparzystymi i parzystymi pozycjami w kolejności wprowadzania. Zatem warunek ten jest konieczny. Wystarczający jest również argument liczenia: powszechnie wiadomo, że dokładnie połowę pozycji można rozwiązać. Ten warunek odfiltrowuje dokładnie połowę możliwych pozycji.