Autor Wątek: Przesuwane puzzle  (Przeczytany 3295 razy)

Offline dynax

  • Użytkownik

# Grudzień 27, 2013, 17:27:07
Czy jest taka możliwość, że typowe przesuwane puzzle (slide puzzle), wygenerowane kompletnie losowo nie będą możliwe do rozwiązania? Jeśli tak to czy jest jakiś algorytm który dość sprawnie oceniałby czy dany zestaw jest rozwiązywalny?

Jestem dość zielony w tym temacie. Proszę o podpowiedzi.

EDIT: Chodzi o typowe liczbowe puzzle z jedną dziurą, typu 3x3, 4x4...

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline dynax

  • Użytkownik

# Grudzień 27, 2013, 17:42:47

Offline ShadowDancer

  • Redaktor

# Grudzień 27, 2013, 19:23:16
Takie puzzle są rozwiązywalne, jeśli znak permutacji jest jest taki sam (liczba zamienionych elementów jest parzysta/nieparzysta w porównaniu do ustawienia docelowego).