Pietnastka

[Gołąbpocztowy]

Witam
Ostatnio natknąłem się na pewien artykuł na Wikipedii odnośnie gry logicznej "Piętnastka". Wg. wielu nie da się jej rozwiązać. Czy nie możemy spróbować napisać prosty program który będzie leciał bruteforcem wszystkie możliwe kombinacje i może się uda :>? BOINC nadaje się do tego świetnie :) W ogóle pomyślałem, że można założyć projekt w ramach B@P który będzie zajmował się właśnie próbowaniem złamania pewnych kombinacji metodą wielokrotnych prób. Nie potrzeba nam do tego, ani zaplecza naukowego, ani danych do badań. Takie dla relaksu, a nóż widelec się uda  :boing:

[Troll81]

a nie bedzie to wyciąganie armaty na słonia?

[migawron]

15@HOME!!!

pisz kolego, koduj, ja się na 100% przyłączę

[Gołąbpocztowy]

Może to być odskocznia od tych górnolotnych projektów, które mają za zadanie zbawić świat. Taka zabawka dla rozrywki ;p Według wielu Seti jest bez sensu bo i tak wg. nich nie ma życia poza naszą planetą (tak wiem, szukanie gwiazd czy tam planetoid działa). Niektóre osoby mogą być zmęczone już ciągłym wynajdywaniem leku na raka czy przewidywaniem klimatu. Krótkie jednostki mogą pomóc w używaniu komputerów używanych rzadko lub nieregularnie.

[Agbar]

Bardzo dobry pomysł, niestety istnieje dowód matematyczny na to, że nie da się rozwiązać niektrórych układów.

[phobos]

Istnieją matematyczne dowody na to, iż problem jest nierozwiązywalny

Jak jest dowód, to znaczy że się nie da.

[Gołąbpocztowy]

Niby się nie da, ale czy nie macie choć odrobiny ochoty na spróbowanie? W końcu o wielu rzeczach mówiono, że się nie da...

[Troll81]

no jeśli ktoś przeprowadził dowód to znaczy tyle że o ile nie zmienisz zasad matematyki i logiki to pewne układy pozostaną bez rozwiązania.....

[Mchl]

no jeśli ktoś przeprowadził dowód to znaczy tyle że o ile nie zmienisz zasad matematyki i logiki to pewne układy pozostaną bez rozwiązania.....

Względnie zasad gry przez wyciągnięcie klocków ;P

[Agbar]

Ciekawe, że próbując napisać program, który sprawdzałby możliwe rozwiązania, musiałbyś znaleźć dowód nierozwiązywalności. (Albo okazać się półgłówkiem.  %) )

[Gołąbpocztowy]

Oczywiście zakładamy, że rozwiązanie jest i odrzucamy herezje typu: "to jest be, to nie będzie działać". Oczywiście przy 15tce jeżeli ten dowód matematyczny naprawdę istnieje i jest prawdziwy (nie zagłębiałem się) takie coś nie ma sensu, ale jest tyle innych tez do obalenia lub chociaż spróbowania.

[Karlik]

W zasadzie gdyby udało się empirycznie obalić dowód matematyczny w tego rodzaju problemie miałoby to bardzo ciekawe następstwa. Już pomijając fakt, że pewnie osoba znajdująca kontrprzykład do dowodu formalnego by dostała pewnie jakąś nagrodę ;D

[Agbar]

OK. Przynajmniej zarys dowodu wam podam:
Po pierwsze jest nam potrzebne pojęcie premutacji.
W tej układance są dozwolone tylko pewne szczególne permutacje (można przesuwać jedną płytkę na raz, tylko na puste miejsce).
Można pokazać, że ten ograniczony zbiór permutacji nie daje wszystkich permutacji i, co ważne, zamiana 14 z 15 jest niemożliwa (bo tak brzmiała chyba oryginalna treść: wszystkie są ułożone dobrze, poza 14 i 15, ktróre są zamienione).
I tyle.
Ten dział matematyki jest na tyle stary, że nic nowego nie wymyślicie. A przynajmniej nie w tak prostym problemie.

O ile pamiętam dowód był kiedyś na angielskiej Wikipedii, ale nie chce mi się go teraz szukać, bo szkoda czasu.

[Mchl]

Zgadza się. Pisał o tym Szczepan Jeleński w Lilavati, a to przecież rok 1926.