BOINC@Poland

Inne => Archiwum => Wątek zaczęty przez: Gołąbpocztowy w 15 Listopad 2011, 14:22

Tytuł: Pietnastka
Wiadomość wysłana przez: Gołąbpocztowy w 15 Listopad 2011, 14:22
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:
Tytuł: Pietnastka
Wiadomość wysłana przez: Troll81 w 15 Listopad 2011, 14:40
a nie bedzie to wyciąganie armaty na słonia?
Tytuł: Pietnastka
Wiadomość wysłana przez: migawron w 15 Listopad 2011, 14:44
15@HOME!!!

pisz kolego, koduj, ja się na 100% przyłączę
Tytuł: Pietnastka
Wiadomość wysłana przez: Gołąbpocztowy w 15 Listopad 2011, 14:47
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.
Tytuł: Pietnastka
Wiadomość wysłana przez: Agbar w 15 Listopad 2011, 14:57
Bardzo dobry pomysł, niestety istnieje dowód matematyczny na to, że nie da się rozwiązać niektrórych układów.
Tytuł: Pietnastka
Wiadomość wysłana przez: phobos w 15 Listopad 2011, 14:58
CytatIstnieją matematyczne dowody na to, iż problem jest nierozwiązywalny

Jak jest dowód, to znaczy że się nie da.
Tytuł: Pietnastka
Wiadomość wysłana przez: Gołąbpocztowy w 15 Listopad 2011, 15:33
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...
Tytuł: Pietnastka
Wiadomość wysłana przez: Troll81 w 15 Listopad 2011, 19:46
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.....
Tytuł: Pietnastka
Wiadomość wysłana przez: Mchl w 15 Listopad 2011, 19:55
Cytat: Troll81 w 15 Listopad 2011, 19:46
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
Tytuł: Pietnastka
Wiadomość wysłana przez: Agbar w 16 Listopad 2011, 01:00
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.  %) )
Tytuł: Pietnastka
Wiadomość wysłana przez: Gołąbpocztowy w 16 Listopad 2011, 02:10
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.
Tytuł: Pietnastka
Wiadomość wysłana przez: Karlik w 16 Listopad 2011, 10:15
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
Tytuł: Pietnastka
Wiadomość wysłana przez: Agbar w 17 Listopad 2011, 14:15
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.
Tytuł: Pietnastka
Wiadomość wysłana przez: Mchl w 17 Listopad 2011, 16:53
Zgadza się. Pisał o tym Szczepan Jeleński w Lilavati, a to przecież rok 1926.