Αλγόριθμος κατασκευής SudoKu


Ο λόγος για το πολύ διάσημο παιχνιδάκι λογικής…

Αν προσωπικά μ’ αρέσουν τα SudoKu? Από λίγο έως καθόλου.

Καθότι όμως η λογική κατασκευής τους είναι ένα… προγραμματιστικό challenge (btw, εντάσσεται στα NP-Complete problems) κι απ’ όσο διαπίστωσα ψάχνοντας στο internet δεν υπάρχει μεγάλη διαθεσιμότητα πληροφορίας όσον αφορά την κατασκευή τους κατά τρόπο αυτοματοποιημένο, αποφάσισα να ασχοληθώ και να εξηγήσω έναν πρόχειρο-αλλά-αποτελεσματικό αλγόριθμο (βασισμένο σε bruteforce και randomization) στον οποίον κατέληξα, ο οποίος και θα είναι η βάση για τα SudoKu που θα δημοσιευθούν στη Φωλιά.

Τι είναι το Sudoku ?

(Στην διαδεμόνη του μορφή) είναι ένα τετράγωνο 9×9, δηλαδή με συνολικά 81 κουτάκια (που σχηματίζουν παράλληλα 9 μεγάλα τετράγωνα) καθένα εκ των οποίων περιέχει έναν αριθμό από το 1 μέχρι το 9

Οι 3 “νόμοι” του Sudoku

  • Κάθε γραμμή του τετραγώνου πρέπει να περιέχει κάθε ψηφίο ΜΟΝΟ μία φορά.
  • Κάθε στήλη του τετραγώνου πρέπει να περιέχει κάθε ψηφίο ΜΟΝΟ μία φορά.
  • Καθένα από τα 9 μεγάλα τετράγωνα πρέπει να περιέχει κάθε ψηφίο ΜΟΝΟ μία φορά.

Πώς παίζεται ?

Στην τελική του μορφή, τα περισσότερα ψηφία είναι “κρυμμένα”. Επομένως, για να “λυθεί” το SudoKu, ο παίκτης – με λογικούς συνειρμούς και όχι με “μαντεψιές”, χρησιμοποιώντας τους 3 παραπάνω κανόνες – πρέπει να συμπληρώσει τα κενά.

Η λογική κατασκευής

Για να κατασκευάσουμε “αυτόματα” ένα Sudoku, σε αδρές γραμμές, πρέπει :

  1. Να δημιουργήσουμε έναν τετράγωνο 9×9
  2. Να συμπληρώσουμε όλα τα κουτάκια του με ψηφία – καθένα εκ των οποίων πληρεί τους παραπάνω τρείς κανόνες.
  3. Να “κρύψουμε” κάποια από τα ψηφία, έτσι ώστε ο παίκτης να μπορεί να “λύσει” το Sudoku – δηλαδή να συμπληρώσει αυτά που λείπουν

Αναλύοντας τα βήματα

[Προειδοποιώ ότι ο αλγόριθμος αυτός δεν είναι ό,τι-πιο-έξυπνο-μπορεί-να-κυκλοφορήσει – αλλά επειδή η προγραμματιστική μου τακτική ήταν πάντα “πρώτα βλέπουμε αποτέλεσμα και μετά καλλωπίζουμε”, here it is!]

  • Δημιουργούμε ένα πίνακα table 9×9 – και κάνουμε initialization με την τιμή 0 (όπου 0 σημαίνει ότι το κουτάκι δεν έχει συμπληρωθεί)
  • Δημιουργούμε ένα πίνακα move 81 στοιχείων (στην php, ελλείψει structs, δημιούργησα 3 ξεχωριστούς πίνακες), όπου θα αποθηκευτούν οι “κινήσεις” μας, για κάθε τοποθέτηση ψηφίου στο table
  • Όσο υπάρχουν κενα κουτάκια :

    • Εντοπίζουμε τυχαία ένα κενό κουτάκι, με συντεταγμένες (xrand, yrand).
    • “Δοκιμάζουμε” στο (xrand, yrand) τυχαία κάποιο από τα 9 ψηφία, έστω num (μέχρι Ή κάποιο να “ταιριάζει” στη συγκεκριμμένη θέση ΕΙΤΕ να έχουμε δοκιμάσει και τα 9 ψηφία)
    • Αν ο num πληρεί για τη θέση table[xrand][yrand] τους 3 κανόνες (τους οποίους ελέγχουμε με την συνάρτηση OK), τότε είσαγουμε τον num στο table[xrand][yrand] και αποθηκεύουμε την “κίνηση” στον ψευδό-πίνακα move
    • Αν έχουμε δοκιμάσει όλα τα ψηφία χωρίς αποτέλεσμα, για τη θέση table[xrand][yrand] , τότε επιλέγουμε τυχαία μια προηγηθείσα “κίνηση” από τον πίνακα move και την “αναιρούμε” όριζοντας την θέση του πίνακα στο μηδέν, με table[move_x[rundo]][move_y[rundo]] = 0
  • Κρύβουμε (κατά τυχαίο τρόπο ή βάσει κάποιου pattern) ορισμένα από τα ψηφία.
  • Τυπώνουμε τον πίνακα table

Πολύ μιλάς… Give me the code now!

[Το παρακάτω είναι η βασική ρουτίνα σε PHP – κάποιες συναρτήσεις που καλούνται από τη βασική, μπορούν εύκολα να προστεθούν. Για πλήρες reference, μπορείτε να ρίξετε μια ματιά στον ανοικτό κώδικα του XSudoku που είχα γράψει παλιότερα σε Pascal/Delphi]


function createSudoku() {

global $move_x; global $move_y; global $move_no; global $table; global $checked;

srand(time()); initTable(); $moves_made=0; $max_moves_made=0;

while (!finished()) { $xrand=(rand()%9)+1; $yrand=(rand()%9)+1;

while ($table[$xrand][$yrand]!=0)
{
    $xrand=(rand()%9)+1;
    $yrand=(rand()%9)+1;
}

uncheck();
$Done=false;

while ((!$Done)&&(!allChecked()))
{
    $num=(rand()%9)+1;
    $checked[$num]=true;
    if (OK($xrand,$yrand,$num))
    {
        $Done=true;
        $table[$xrand][$yrand]=$num;
        $moves_made++;

        $move_x[$moves_made]=$xrand;
        $move_y[$moves_made]=$yrand;
        $move_no[$moves_made]=$num;
    }
}

if ((allChecked())&&(!$Done))
{
    $rundo=(rand()%(moves_made+1))+1;
    $table[$move_x[$rundo]][$move_y[$rundo]]=0;

    for ($zz=$rundo;$zz<=$moves_made-1;$zz++)
    {
        $move_x[$zz]=$move_x[$zz+1];
        $move_y[$zz]=$move_y[$zz+1];
        $move_no[$zz]=$move_no[$zz+1];
    }
    $moves_made--;
}

if ($moves_made>$max_moves_made)
    $max_moves_made=$moves_made;

}

}


Ετικέττες

-

Σού άρεσε? Πρότεινέ το σ' έναν φίλο!

Συναφή Άρθρα

Κάνε ένα σχόλιο τώρα (όσο προλαβαίνεις...)