Ποιος είναι ο ελάχιστος αριθμός ενδείξεων που μπορεί να έχει ένα Sudoku;
Τελευταία ενημέρωση
Ένα έγκυρο Sudoku - Αυτό με ακριβώς μία λύση - Απαιτεί τουλάχιστον 17 δοσμένα ψηφία. Αυτό είναι ένα αποδεδειγμένο μαθηματικό αποτέλεσμα. Οποιοδήποτε παζλ με 16 ή λιγότερες ενδείξεις είτε έχει πολλαπλές λύσεις είτε καμία απολύτως.
Η Απόδειξη του 2012
Το 2012, οι Gary McGuire, Bastian Tugemann και Gilles Civario στο University College Dublin δημοσίευσαν μια απόδειξη ότι δεν υπάρχει έγκυρο Sudoku με 16 clues. Η εργασία τους ήταν κυρίως υπολογιστική: εξερεύνησαν τον πλήρη χώρο των πιθανών grids με 16 clues και επαλήθευσαν ότι κανένα δεν παρήγαγε μοναδική λύση. Η αναζήτηση απαίτησε περίπου 7 εκατομμύρια ώρες πυρήνα υπολογισμού.
Πριν από αυτό, πιστευόταν ευρέως ότι το 17 ήταν το ελάχιστο και χιλιάδες puzzles με 17 clues είχαν βρεθεί πειραματικά. Η ομάδα του McGuire παρείχε την πρώτη αυστηρή απόδειξη ότι το 16 είναι αδύνατο.
Πώς μοιάζουν τα παζλ με 17 ενδείξεις
Τα παζλ με 17 ενδείξεις είναι εξαιρετικά αραιά - 17 δοθέντα ψηφία σε 81 κελιά, αφήνοντας 64 κενά. Είναι από τα πιο δύσκολα παζλ για επίλυση και συνήθως απαιτούν προχωρημένες τεχνικές. Η εύρεση έγκυρων παζλ με 17 ενδείξεις απαίτησε δεκαετίες υπολογιστικής προσπάθειας. Κατά τη στιγμή της γραφής, είναι γνωστά πάνω από 49.000 ουσιαστικά διαφορετικά παζλ Sudoku με 17 ενδείξεις.
Τι σημαίνει αυτό για τον σχεδιασμό παζλ
Τα published puzzles που απευθύνονται σε human solvers σπάνια πέφτουν κάτω από 22 clues. Τα Expert και Master difficulty puzzles συνήθως χρησιμοποιούν 22-27 given digits, ενώ τα Easy puzzles χρησιμοποιούν 36-45. Το 17-clue minimum είναι ένα theoretical bound - Στην πράξη, η solvability με καλή technique και ένα enjoyable solving path έχουν πολύ μεγαλύτερη σημασία από το clue count μόνο.