Sudoku puzzles και συνδυαστικά προβλήματα

• Κύριος συγγραφέας: Ζώττου, Δήμητρα Νεφέλη
• Άλλοι συγγραφείς: Αλεβίζος, Παναγιώτης
• Μορφή: Thesis
• Γλώσσα: Greek
• Έκδοση: 2013
• Θέματα: Πολυπλοκότητα; Χρωματικότητα; Complexity; Colorability; Sudoku; 793.74

Στην παρούσα εργασία προσεγγίζονται τα Sudoku puzzles χρησιμοποιώντας μαθηματικές έννοιες κυρίως από την θεωρία γραφημάτων, την άλγεβρα, τη θεωρία πινάκων αλλά και την κρυπτογραφία και τη θεωρία ανάπτυξης αλγορίθμων, oυσιαστικά χρησιμοποιούνται διάφορες οπτικές γωνίες προκειμένου να απεικονιστεί η μελέτη αυτών των puzzles μέσω των μαθηματικών. Η εργασία χωρίζεται σε έξι βασικά κεφάλαια: Το πρώτο κεφάλαιο περιέχει βασικές έννοιες της άλγεβρας και της θεωρίας γραφημάτων, όπως ο ορισμός της ομάδας, του συνεκτικού γραφήματος, ο βαθμός κορυφής και άλλα, οι οποίες χρησιμοποιούνται επανειλημμένα στην εργασία, έτσι ώστε να μπορεί να γίνει κατανοητή χωρίς να απαιτείται η χρήση άλλων επιστημονικών πηγών. Χωρίζεται σε τέσσερεις βασικές ενότητες οι οποίες παρουσιάζονται με την ακόλουθη σειρά. Η πρώτη ενότητα είναι οι Βασικές Έννοιες Γραφημάτων, η οποία ουσιαστικά αναφέρεται στην βασική ορολογία των γραφημάτων. Η δεύτερη ενότητα είναι τα Βασικά Είδη Γραφημάτων και περιέχει γραφήματα με συγκεκριμένα χαρακτηριστικά και ιδιότητες, οι οποίες είναι απαραίτητες για την ανάλυση της παρούσας εργασίας. Στη συνέχεια η τρίτη ενότητα είναι οι Βασικές Έννοιες Γραμμικής Άλγεβρας, η οποία περιέχει συγκεκριμένους ορισμούς κυρίως των ομάδων και των συμμετριών που χρησιμοποιούνται για την απαρίθμηση των Sudoku. Τέλος η τελευταία ενότητα είναι οι Αλγεβρικές Ιδιότητες Γραφημάτων, η οποία περιέχει ορισμούς και αλγεβρικές αλληλεπιδράσεις πάνω στα γραφήματα. Για περισσότερες λεπτομέρειες σχετικά με την άλγεβρα και τη θεωρία γραφημάτων, παραπέμπουμε στα [6], [7] και [29]. Το δεύτερο κεφάλαιο περιέχει τους ορισμούς του Sudoku puzzle και των λατινικών τετραγώνων, τα οποία είναι μια γενίκευση των Sudoku puzzles, όπως θα αναφερθεί παρακάτω. Για εκτενέστερη έρευνα πάνω στα λατινικά τετράγωνα παραπέμπουμε στα [3], [10], [11], [12],[13], [15], [16], [17], [18] και [29]. Στο τρίτο κεφάλαιο απαριθμούνται οι κλάσεις ισοδυναμίας των λατινικών τετραγώνων αρχικά και στη συνέχεια γίνεται απαρίθμηση τριών ειδών Sudoku puzzles, τα οποία είναι τα junior Sudoku puzzles τάξης 44, τα Sudoku puzzles τάξης 9x9 και τα 2-Quasi-μαγικά Sudoku, τα οποία έχουν έναν παραπάνω περιορισμό σε σχέση με τα συνήθη Sudoku. Τέλος, απαριθμούνται οι συμμετρίες των Sudoku puzzles τάξης 9x9 και γίνεται μια σύντομη ανάλυση των μητρώων μετάθεσής τους. Περαιτέρω πληροφορίες βρίσκονται στα [1], [2], [4], [5], [9], [14], [19], [20], [21], [22], και [26]. Στο τέταρτο κεφάλαιο αλλάζει η αυστηρά αλγεβρική προσέγγιση που υπάρχει στις παραπάνω ενότητες. Εδώ παρουσιάζεται το Sudoku puzzle με μια ισοδύναμη μορφή γραφήματος και γίνεται μια σύντομη παρουσίαση βασικών εννοιών της κρυπτογραφίας, καθώς και μια θεωρητική προσέγγιση της κρυπτογράφησης του Sudoku puzzle, με τη βοήθεια του πρωτοκόλλου της μηδενικής γνώσης. Περαιτέρω πληροφορίες βρίσκονται στα [8], [23] και [24]. Στο πέμπτο κεφάλαιο αλλάζει πάλι ο επιστημονικός κλάδος, μέσω του οποίου εξετάζουμε τα Sudoku puzzles και επικεντρώνεται στην απεικόνιση ενός στιγμιοτύπου του puzzle Sudoku σε ένα στιγμιότυπο του προβλήματος SAT. Όλοι οι περιορισμοί του Sudoku θα μπορέσουν να διατηρηθούν μέσω των κανονικών συζευκτικών προτάσεων του προβλήματος SAT, οι οποίες έχουν χωριστεί σε πέντε ενότητες. Η καταμέτρηση των κανονικών συζευκτικών προτάσεων του προβλήματος SAT μέσω αναδρομικών τύπων, αποτελεί το πρωτότυπο τμήμα της διπλωματικής καθώς και η ανάλυση των τύπων αυτών, την οποία περιέχει το επισυναπτόμενο CD. Για πιο θεωρητική προσέγγιση προτείνονται τα [25], [26], [27], [30]. Το έκτο κεφάλαιο της εργασίας περιέχει μια διασκεδαστική εφαρμογή κρυπτογράφησης οποιουδήποτε Sudoku puzzle τάξης 99 . Η εφαρμογή υλοποιείται με τραπουλόχαρτα, έτσι ώστε ο αναγνώστης να είναι σε θέση να κρυπτογραφήσει οποιοδήποτε λύση puzzle Sudoku, χωρίς να είναι υποχρεωμένος να παρουσιάσει τη λύση του στον αντίπαλο, χρησιμοποιώντας μόνο τρείς τράπουλες. Ο στόχος του τελευταίου κεφαλαίου είναι να κάνει τον επίλογο της εργασίας πιο ευχάριστο και πιο ανάλαφρο ακόμα και για νέους επιστήμονες στο χώρο της κρυπτογραφίας, της θεωρίας γραφημάτων και της άλγεβρας.