Café

Απ: Ένα παζλ.... διαφορετικό από τα άλλα!

PALLADIN — Fri, 12 Oct 2007 04:29:40 GMT

Το mathematica έδωσε την απάντηση

(4! * 4 ^ 4) * (56! * 4 ^ 56) * (196! * 4 ^ 196) = 11622830686486453039512310108490989229462506114950234274249959181005316101163214849\

>    00689207768820009878036046555407771377549933800805576419888675785121334150563767837500\

>    86598773899535939112241177721260570750782470562695622565187249500013642608113237866998\

>    09753099834131401191757240779237171506903791465921395978643369965039878857408050207469\

>    29274514718805330649731748360959347620512463487350032430122200028775232214955296447627\

>    74268057998914464978218440617074264624790841374983861268950712499058953932087167135518\

>    057791089715679282069504000000000000000000000000000000000000000000000000000000000000

Απ: Ένα παζλ.... διαφορετικό από τα άλλα!

Δημήτρης Γκανάτσιος — Thu, 11 Oct 2007 06:54:00 GMT

PALLADIN:

Εάν λάβουμε υπόψιν τον διαχωρισμό τότε είναι (60! * 4 ^ 60) * (196! * 4 ^ 196)

(αν και όντως δεν έχει πολύ σημασία, απλά food for thought... )

δίκιο έχεις, είχα κάνει λάθος πριν. Σκέφτομαι, όμως, τώρα ότι έχουμε 4 γωνιακά κομμάτια (πάνω αριστερά, πάνω δεξιά, κάτω αριστερά, κάτω δεξιά). Οι διατάξεις για αυτά είναι 4! * 4 ^ 4. Τα υπόλοιπα περιμετρικά είναι 56. Άρα για αυτά είναι 56! * 4 ^ 56. Και για τα υπόλοιπα 196, όπως είπες, είναι 196! * 4 ^ 196.
Σύνολο δηλαδή, (4! * 4 ^ 4) * (56! * 4 ^ 56) * (196! * 4 ^ 196)

Αποτέλεσμα;;;(αν έχω σκεφτεί σωστά) Ιδού:

1,1622830686486453039512310108489e+596

thrylos:
Γεννικά εαν κάνετε κάποιες αναζητήσεις θα βρείτε ότι υπάρχουν αρκετοί αλγόριθμοι SAT-solvers και τεχνικές που χρησιμοποιούνται στο σχεδιασμό hardware.

Βρήκα αυτό. Πρέπει να παραδεχτώ πως έχει εντυπωσιακά πραγματάκια μέσα!!

Απ: Ένα παζλ.... διαφορετικό από τα άλλα!

PALLADIN — Thu, 11 Oct 2007 05:46:12 GMT

Μετά από μια πιο προσεκτική μελέτη... ένας γενικός τύπος (χωρίς να λάβουμε υπόψιν τον διαχωρισμό μεταξύ εξωτερικων/εσωτερικων) είναι 256!*4^256

Εάν λάβουμε υπόψιν τον διαχωρισμό τότε είναι (60! * 4 ^ 60) * (196! * 4 ^ 196)

Δεν έχει και πολύ σημασία ο ακριβής αριθμός... καθώς τα μεγέθη είναι ασύλληπτα...

Απ: Ένα παζλ.... διαφορετικό από τα άλλα!

thrylos — Wed, 10 Oct 2007 18:51:23 GMT

Όντως ακόμα δεν υπάρχει κάποιος γεννικός τρόπως επίλυσης NP-Complete προβλημάτων.
ΑΛΛΑ στην Αγγλία μου είχαν πει για έναν τυπά ονόματι Stälmark που το 1995 έβγαλε μια πατέντα που μπορεί να επιλύει κάποια 3-SAT προβλήματα, εξαιρετικά γρήγορα.
Η πατέντα έχει χρησιμοποιηθεί με επιτυχία στο SAT-Solving για Hardware design. Ο ίδιος εξάλλου ήταν ηλεκτρονικός μηχανικός.
Γεννικά εαν κάνετε κάποιες αναζητήσεις θα βρείτε ότι υπάρχουν αρκετοί αλγόριθμοι SAT-solvers και τεχνικές που χρησιμοποιούνται στο σχεδιασμό hardware.

Απ: Ένα παζλ.... διαφορετικό από τα άλλα!

PALLADIN — Wed, 10 Oct 2007 18:30:40 GMT

dt008:
PALLADIN:

Το πρόβλημα είναι NP-Complete και είναι "αρκετά" δύσκολο....

Σωστός!!!!! Έκανα μία απόπειρα χθες να υπολογίσω πόσες βγαίνουνε οι διατάξεις. Τα κομμάτια είναι 256. 4 δυνατές περιστροφές για κάθε κομμάτι.
62 εξωτερικά κομμάτια, άρα 194 "μέσα". Χωρίς τις περιστροφές λοιπόν, οι δυνατές διατάξεις είναι 62! + 194! . Επειδή όμως κάθε κομμάτι δύναται να περιτραφεί σε 4 σημεία, το πλήθος των δυνατών διατάξεων θα βγαίνει (62! + 194!) * 4 ^ 256 .... τρομακτικό νούμερο (αν δεν έχω κάνει κάνα λάθος στον υπολογισμό...)

Φίλε Νίκο, καλά κουράγια, ελπίζω να καταφέρεις να βρεις τον (ή τους...) ευριστισκούς αλγόριθμους που απαιτούνται για να το λύσεις

Σε ευχαριστώ φιλε Δημήτρη... Οι υπολογισμοί σου είναι σωστοί, το νούμερο είναι σοκαριστικό...

Απ: Ένα παζλ.... διαφορετικό από τα άλλα!

Δημήτρης Γκανάτσιος — Wed, 10 Oct 2007 18:26:02 GMT

PALLADIN:

Οι ιδέες είναι πολύ πιο δυνατές από οποιοδήποτε πρόγραμμα υπολογιστή (ειδικά όταν το πρόβλημα είναι NP-Complete)

Σίγουρα... Οι ιδέες είναι και η βάση των αλγορίθμων, άλλωστε No ideas => no algorithm

thrylos, το έχω δει, ένα παζλ είναι κατά τα άλλα, οπότε δεν νομίζω να είναι απίστευτα ακριβό.

edit: τώρα είδα το post του Νίκου, κάπου εκεί λογικά.

Απ: Ένα παζλ.... διαφορετικό από τα άλλα!

PALLADIN — Wed, 10 Oct 2007 18:21:31 GMT

thrylos:
Πόσο κάνει;
Σκεύτομαι να το κάνω δωράκι σε έναν ξάδελφό μου.

Είναι ακριβούτσικο... εάν θυμάμαι καλά κοντά στα 40 euros

Απ: Ένα παζλ.... διαφορετικό από τα άλλα!

PALLADIN — Wed, 10 Oct 2007 18:19:02 GMT

KelMan:

"Ιδέες" όπως λέμε, "φτιάχνω ένα προγραμματάκι για να το λύσω" ??

Οι ιδέες είναι πολύ πιο δυνατές από οποιοδήποτε πρόγραμμα υπολογιστή (ειδικά όταν το πρόβλημα είναι NP-Complete)

Πάντως με τον ξαδελφο μου (πολύ ικανός μαθηματικός) που το δουλεύουμε έχουμε αναπτύξει κάποιες πολύ ενδιαφέρουσες ιδέες...

Απ: Ένα παζλ.... διαφορετικό από τα άλλα!

thrylos — Wed, 10 Oct 2007 18:17:04 GMT

Πόσο κάνει;
Σκεύτομαι να το κάνω δωράκι σε έναν ξάδελφό μου.

Απ: Ένα παζλ.... διαφορετικό από τα άλλα!

Δημήτρης Γκανάτσιος — Wed, 10 Oct 2007 18:03:20 GMT

PALLADIN:

Το πρόβλημα είναι NP-Complete και είναι "αρκετά" δύσκολο....

Σωστός!!!!! Έκανα μία απόπειρα χθες να υπολογίσω πόσες βγαίνουνε οι διατάξεις. Τα κομμάτια είναι 256. 4 δυνατές περιστροφές για κάθε κομμάτι.
62 εξωτερικά κομμάτια, άρα 194 "μέσα". Χωρίς τις περιστροφές λοιπόν, οι δυνατές διατάξεις είναι 62! + 194! . Επειδή όμως κάθε κομμάτι δύναται να περιτραφεί σε 4 σημεία, το πλήθος των δυνατών διατάξεων θα βγαίνει (62! + 194!) * 4 ^ 256 .... τρομακτικό νούμερο (αν δεν έχω κάνει κάνα λάθος στον υπολογισμό...)

Φίλε Νίκο, καλά κουράγια, ελπίζω να καταφέρεις να βρεις τον (ή τους...) ευριστισκούς αλγόριθμους που απαιτούνται για να το λύσεις

ΥΓ. Δείτε και μια light version (4x4) του παιχνιδιού εδώ

Απ: Ένα παζλ.... διαφορετικό από τα άλλα!

KelMan — Wed, 10 Oct 2007 18:02:14 GMT

"Ιδέες" όπως λέμε, "φτιάχνω ένα προγραμματάκι για να το λύσω" ??

Απ: Ένα παζλ.... διαφορετικό από τα άλλα!

PALLADIN — Wed, 10 Oct 2007 17:38:50 GMT

Μεταξύ μας ...το έχω αγοράσει από το Καλοκαίρι και δοκιμάζω κάποιες ιδέες... είδομεν

Απ: Ένα παζλ.... διαφορετικό από τα άλλα!

PALLADIN — Wed, 10 Oct 2007 17:27:03 GMT

Το πρόβλημα είναι NP-Complete και είναι "αρκετά" δύσκολο....

Ένα παζλ.... διαφορετικό από τα άλλα!

Δημήτρης Γκανάτσιος — Wed, 10 Oct 2007 05:53:18 GMT

Πρόκειται για ένα παζλ game διαφορετικό από τα άλλα, μιας και δίνει έπαθλο 2.000.000$ σε όποιον το λύσει!

Με 256 τετράγωνα κομμάτια, έχει πάρα πολλούς συνδυασμούς αλλά και αρκετές λύσεις! Δεν μου φαίνεται εύκολο πάντως

Για περισσότερα, δείτε εδώ