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

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

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

---

Dimitris-Ilias Gkanatsios
Developer Evangelist, Microsoft Hellas

My Blog
StudentGuru
Twitter
Facebook

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

---

Palladinos Nick
Software Engineer
-----------------------
The limits of my language mean the limits of my world. (Ludwig Wittgenstein)

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

---

Palladinos Nick
Software Engineer
-----------------------
The limits of my language mean the limits of my world. (Ludwig Wittgenstein)

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

---

Vir prudens non contra ventum mingit

PALLADIN:

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

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

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

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

---

Dimitris-Ilias Gkanatsios
Developer Evangelist, Microsoft Hellas

My Blog
StudentGuru
Twitter
Facebook

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

---

Powered by openSuSE 11 64-bit Edition

KelMan:

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

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

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

---

Palladinos Nick
Software Engineer
-----------------------
The limits of my language mean the limits of my world. (Ludwig Wittgenstein)

thrylos:

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

 

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

---

Palladinos Nick
Software Engineer
-----------------------
The limits of my language mean the limits of my world. (Ludwig Wittgenstein)

PALLADIN:

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

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

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

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

---

Dimitris-Ilias Gkanatsios
Developer Evangelist, Microsoft Hellas

My Blog
StudentGuru
Twitter
Facebook

dt008:

PALLADIN:

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

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

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

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

---

Palladinos Nick
Software Engineer
-----------------------
The limits of my language mean the limits of my world. (Ludwig Wittgenstein)

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

---

Powered by openSuSE 11 64-bit Edition

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

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

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

---

Palladinos Nick
Software Engineer
-----------------------
The limits of my language mean the limits of my world. (Ludwig Wittgenstein)

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.

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

---

Dimitris-Ilias Gkanatsios
Developer Evangelist, Microsoft Hellas

My Blog
StudentGuru
Twitter
Facebook

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

(4! * 4 ^ 4) * (56! * 4 ^ 56) * (196! * 4 ^ 196) = 11622830686486453039512310108490989229462506114950234274249959181005316101163214849\
 
>    00689207768820009878036046555407771377549933800805576419888675785121334150563767837500\
 
>    86598773899535939112241177721260570750782470562695622565187249500013642608113237866998\
 
>    09753099834131401191757240779237171506903791465921395978643369965039878857408050207469\
 
>    29274514718805330649731748360959347620512463487350032430122200028775232214955296447627\
 
>    74268057998914464978218440617074264624790841374983861268950712499058953932087167135518\
 
>    057791089715679282069504000000000000000000000000000000000000000000000000000000000000

---

Palladinos Nick
Software Engineer
-----------------------
The limits of my language mean the limits of my world. (Ludwig Wittgenstein)