ΕΛΛΗΝΙΚΗ ΔΗΜΟΚΡΑΤΙΑΣκοπός
Ο στόχος της άσκησης αυτής είναι να βοηθήσει στην εκμάθηση/κατανόηση (1) της αναδρομικής κλήσης και διαχείριση της στοίβας, (2) του περάσματος παραμέτρων by value και by reference, και (3) της χρήσης αναδρομής για ψάξιμο ενός συνόλου επιλογών.
Η άσκηση
Δίνεται το interface sudoku.h (στο directory ~hy255/as4_sudoku/include). Το interface χρησιμοποιεί έναν ADT grid.h. Η άσκηση σας ζητάει να:
- Ορίσετε το grid.h. Μπορείτε είτε να ορίσετε το δικό σας grid.h είτε να χρησιμοποιήσετε το grid.h που σας δίνει η άσκηση (στο directory ~hy255/as4_sudoku/include).
- Υλοποιήσετε το grid.h σε ένα αρχείο grid.c.
- Υλοποιήσετε το sudoku.h σε ένα αρχείο sudoku.c.
- Υλοποιήσετε το εκτελέσιμο sudoku που εκτελείται με τις εξής
παραμέτρους:
- sudoku: διαβάζει από το stdin ένα puzzle και
- τυπώνει το input puzzle στο stderr,
- λύνει το puzzle,
- τυπώνει στο stderr ένα μήνυμα που λέει αν το puzzle έχει λύση μοναδικής, περισσότερων επιλογών, ή καμία λύση, και
- τυπώνει στο stdout μια λύση αν υπάρχει ή κάποιο από τα puzzles που εξέτασε ως πιθανή λύση με τα λάθη που αυτό παρουσιάζει.
- sudoku –c: διαβάζει από το stdin ένα puzzle και
- τυπώνει το input puzzle στο stderr,
- ελέγχει αν το puzzle είναι σωστό, και
- τυπώνει στο stderr ένα μήνυμα που λέει αν το puzzle είναι σωστό ή όχι και αν όχι ποια είναι τα λάθη του.
- sudoku –g nelts: παράγει ένα νέο puzzle που έχει «περίπου» nelts μη κενά (μηδενικά) στοιχεία και τυπώνει το puzzle στο stdout
- Ένα ενδεικτικό εκτελέσιμο
sudoku βρίσκεται στο directory ~hy255/as4_sudoku/run. Π.χ.
$ sudoku -g 50 | sudoku | sudoku -c New puzzle: 1 2 0 4 0 0 8 0 0 0 7 0 2 8 0 1 3 0 3 4 8 1 7 9 5 0 6 0 5 1 9 0 0 0 0 2 6 3 2 0 1 5 4 9 8 9 0 4 6 3 2 0 5 0 0 6 0 3 2 0 0 8 0 2 1 3 0 0 0 6 4 5 0 9 7 5 0 4 2 0 0 Puzzle has a (unique choice) solution: 1 2 6 4 5 3 8 7 9 5 7 9 2 8 6 1 3 4 3 4 8 1 7 9 5 2 6 7 5 1 9 4 8 3 6 2 6 3 2 7 1 5 4 9 8 9 8 4 6 3 2 7 5 1 4 6 5 3 2 1 9 8 7 2 1 3 8 9 7 6 4 5 8 9 7 5 6 4 2 1 3 Puzzle solution is correct.
Το directory ~hy255/as4_sudoku/run έχει κατάλληλα permissions ώστε να μπορείτε να τοποθετήσετε σε αυτό τα δικά σας εκτελέσιμα (προσοχή όχι sources) sudoku ώστε να μπορείτε να χρησιμοποιήσετε διαφορετικούς generators/solvers/checkers για να δοκιμάσετε τον κώδικά σας. Χρησιμοποιήστε τη σύμβαση login_sudoku ώστε να μην υπάρχουν conflicts και αποφύγετε να βάζετε πολλά versions για λόγους χώρου.
Sudoku
Το sudoku είναι ένα παιχνίδι με puzzles αριθμών. Σε κάθε puzzle δίνεται ένα grid 9x9 που αποτελείται από 3x3 υπο-grids το κάθε ένα με μέγεθος 3x3. Αρχικά το puzzle έχει ορισμένες από τις θέσεις του grid συμπληρωμένες με αριθμούς. O στόχος είναι να συμπληρώσει κανείς το υπόλοιπο puzzle με αριθμούς έτσι ώστε κάθε γραμμή, κάθε στήλη, και κάθε 3x3 grid να περιέχει όλα τα ψηφία από 1 ως 9. Περισσότερες πληροφορίες για το sudoku μπορείτε να βρείτε σε διάφορα sites του internet.
Υλοποίηση grid.h
Το grid.h περιλαμβάνει τη δομή που χρησιμοποιείται για την αποθήκευση του grid και των επιπλέον δεδομένων που χρησιμοποιούνται κατά την επίλυση του grid. Το grid.h που δίνεται ορίζει ένα συγκεκριμένο τύπο για το Grid_T και ένα σύνολο από εξαιρετικά απλές συναρτήσεις που χρησιμοποιούνται για να προσπελαύνουν (διαβάζουν ή γράφουν) τα στοιχεία ενός αντικειμένου Grid_T.
Παρατηρήστε ότι συναρτήσεις που μόνο διαβάζουν δεδομένα από ένα αντικείμενο Grid_T παίρνουν ως παράμετρο ένα αντίγραφο του αντικειμένου, ενώ συναρτήσεις που μεταβάλουν ένα αντικείμενο Grid_T παίρνουν ως παράμετρο έναν pointer στο αντικείμενο.
Υλοποίηση sudoku.h
Υλοποιήστε πρώτα τις συναρτήσεις:
- Grid_T sudoku_read(void);
- void sudoku_print(FILE *s, Grid_T g);
- void sudoku_print_errors(Grid_T g);
- int sudoku_is_correct(Grid_T g);
Στη συνέχεια υλοποιήστε τις συναρτήσεις:
- Grid_T sudoku_solve(Grid_T g);
- int sudoku_solution_is_unique(Grid_T g);
Η συνάρτηση sudoku_solve παίρνει ως παράμετρο ένα puzzle (grid) το οποίο και δεν αλλάζει καθόλου και επιστρέφει τη λύση του puzzle. Αν το puzzle δεν έχει μοναδική λύση, τότε επιστρέφει μια από τις δυνατές λύσεις, ενώ αν δεν υπάρχει καμία λύση, επιστρέφει ένα συμπληρωμένο puzzle που εξέτασε ως πιθανή λύση. Η συνάρτηση sudoku_solve πρέπει να καλύπτει 2 περιπτώσεις, αν το puzzle έχει μοναδική λύση ή όχι.
Για να λύσουμε ένα puzzle μπορούμε να χρησιμοποιήσουμε τον εξής αλγόριθμο:
- Για κάθε κενή θέση του grid σχηματίζουμε τις δυνατές επιλογές, που περιλαμβάνουν όλους τους αριθμούς οι οποίοι δεν επαναλαμβάνονται στην ίδια γραμμή, στήλη, ή υπο-grid.
- Διαλέγουμε μια κενή θέση του grid και μια από τις δυνατές επιλογές για να τη συμπληρώσουμε. Αν το puzzle έχει μοναδική λύση, τότε θα πρέπει να υπάρχει κάθε φορά τουλάχιστον μια θέση του puzzle που θα έχει ακριβώς μια πιθανή λύση/επιλογή. Αν το puzzle έχει περισσότερες από μια λύσεις, τότε ίσως δεν υπάρχει θέση με μοναδική επιλογή.
- Αφαιρούμε την επιλογή μας από το στοιχείο που διαλέξαμε.
- Υπάρχουν δύο περιπτώσεις:
- Αν το puzzle έχει σε κάθε βήμα ένα τουλάχιστον στοιχείο με μοναδική επιλογή, τότε η επιλογή μας είναι «σίγουρη» και δε θα χρειαστεί να «δοκιμάσουμε» άλλες επιλογές, και επομένως αφαιρούμε την επιλογή μας από τις πιθανές επιλογές όλων των άλλων θέσεων του puzzle.
- Αν όχι, η προηγούμενη επιλογή δεν είναι μοναδική και επομένως μπορεί να μην οδηγεί σε λύση. Οπότε, πρέπει να την εφαρμόσουμε προσωρινά μόνο, ώστε αν τυχόν δεν οδηγεί σε λύση να δοκιμάσουμε την επόμενη δυνατή επιλογή. Αυτή η τεχνική ονομάζεται backtracking και μας εγγυάται ότι θα βρούμε τη λύση, αν υπάρχει. Για να υλοποιήσουμε το backtracking χρησιμοποιούμε ένα αντίγραφο (βοηθητικό) grid, το οποίο αρχικοποιούμε με βάση το g και το οποίο “λύνουμε” αναδρομικά χρησιμοποιώντας την sudoku_solve(). Αν το βοηθητικό αυτό grid έχει λύση τότε το επιστρέφουμε ως αποτέλεσμα της τρέχουσας κλήσης της solve_grid() διαφορετικά το «πετάμε» και επιστρέφουμε το αρχικό g (έχοντας ήδη αφαιρέσει την επιλογή που δοκιμάσαμε ώστε να μην έχουμε άπειρη αναδρομή).
- Επαναλαμβάνουμε έως ότου το puzzle συμπληρωθεί σωστά.
Για το βήμα (1) μπορείτε να υλοποιήσετε μια συνάρτηση:
- static void sudoku_init_choices(Grid_T *g);
η οποία παίρνει σαν input ένα puzzle και το αλλάζει ώστε να συμπληρώσει στo input αντικείμενο τις δυνατές επιλογές που υπάρχουν για κάθε θέση του puzzle, ανάλογα με τις τιμές που ήδη περιέχει το puzzle.
Για το βήμα (2) μπορείτε να υλοποιήσετε μια συνάρτηση:
- static int sudoku_try_next(Grid_T g, int *row, int *col);
η οποία παίρνει ως input ένα puzzle, εξετάζει τις διάφορες επιλογές που υπάρχουν και αν υπάρχει μια ή περισσότερες μοναδικές επιλογές, επιστρέφει κάποια από αυτές (θα δείτε ότι ίσως σας βολεύει να μη διαλέγετε κάθε φορά την ίδια μοναδική επιλογή αλλά να χρησιμοποιήσετε τη συνάρτηση rand() για να εισάγετε κάποιο βαθμό τυχαιότητας) διαφορετικά επιστρέφει κάποια άλλη επιλογή (ποια είναι μια καλή επιλογή να επιστρέψει σε αυτή την περίπτωση;).
Για το βήμα (3) μπορείτε να υλοποιήσετε τη συνάρτηση:
- static int sudoku_update_choice(Grid_T *g, int i, int j, int n);
η οποία παίρνει ως input ένα Grid_T αντικείμενο και το αλλάζει ώστε να αφαιρεί από το στοιχείο i,j την επιλογή n και επιστρέφει τον αριθμό των επιλογών που υπήρχαν για το στοιχείο i,j.
Για το βήμα (4a) μπορείτε να υλοποιήσετε τη συνάρτηση
- static void sudoku_eliminate_choice(Grid_T *g, int r, int c, int n);
η οποία αφαιρεί από τη γραμμή r, τη στήλη c, και το σχετικό υπο-grid, την επιλογή n.
Για το βήμα (4b) το backtracking υλοποιείται «αυτόματα» με αναδρομική κλήση της sudoku_solve() με κατάλληλες παραμέτρους και να ελέγξουμε το αποτέλεσμα που επιστρέφει ώστε να αποφασίσουμε αν η αναδρομή θα τελειώσει ή αν θα συνεχίσει να δοκιμάζει επιλογές.
Για την υλοποίηση της sudoku_generate(), μια προσέγγιση είναι να παράγετε αρχικά ένα σωστά συμπληρωμένο puzzle. Αυτό μπορείτε να το κάνετε με μια συνάρτηση:
- static Grid_T sudoku_generate_complete(void);
που ξεκινάει από ένα άδειο puzzle, παράγει όλες τις δυνατές επιλογές για κάθε θέση (sudoku_init_choices()) και χρησιμοποιεί την sudoku_try_next() για να αντικαταστήσει ένα-ένα τα μηδενικά του αρχικού puzzle με σωστές τιμές (σε αυτό το σημείο αν η sudoku_try_next() επιστρέφει τυχαίες θέσεις/επιλογές σε κάθε εκτέλεση θα έχετε ένα διαφορετικό puzzle). Επειδή ωστόσο δεν υπάρχει κάποια εγγύηση ότι το puzzle που θα παραχθεί θα είναι σωστό, η sudoku_generate_complete() μπορεί μετά από μερικές προσπάθειες (π.χ. 10 προσπάθειες) να επιστρέφει κάποιο προ-συμπληρωμένο puzzle.
Στη συνέχεια, η sudoku_generate() προσπαθεί να αφαιρέσει από το συμπληρωμένο puzzle όλα εκτός από nelts στοιχεία. Κάθε φορά διαλέγει τυχαία μια θέση του puzzle και θέτει το στοιχείο στην τιμή 0.
Σημείωση: Παρ’ότι εμείς χρησιμοποιούμαι ως ένδειξη δυσκολίας τον αριθμό των συμπληρωμένων αρχικών στοιχείων και την ύπαρξη μοναδικής επιλογής σε κάθε βήμα, αυτό δεν ισχύει απαραίτητα στην πράξη, μια και η δυσκολία έχει σχέση με το πως σκέφτεται ο κάθε παίκτης. Από την άλλη, η ύπαρξη backtracking είναι κάτι που φαίνεται να δυσκολεύει πάντα ανθρώπινους (σε αντίθεση με μηχανικούς) παίκτες.
Τυχαιότητα
Για να εισάγετε τυχαιότητα σε σημεία που πιθανόν χρειάζεται η υλοποίηση σας μπορείτε να χρησιμοποιήσετε τις συναρτήσεις rand() και srand() της stdlib (man rand, man srand). Για να αρχικοποιήσετε τις συναρτήσεις αυτές θα πρέπει να καλέσετε την srand με κάποια παράμετρο που αλλάζει σε κάθε κλήση του προγράμματος σας. Αυτό μπορεί να γίνει με την κλήση:
- srand(getpid());
H getpid() είναι μια συνάρτηση που επιστρέφει το process id του προγράμματος (και το οποίο είναι γενικά διαφορετικό από εκτέλεση σε εκτέλεση). Επειδή η getpid() ορίζεται στο <unistd.h> θα χρειστεί να χρησιμοποιήσετε το συγκεκριμένο interface.
Τέλος, για να αναθέσετε σε μια μεταβλητή r τυχαία τις τιμές π.χ. 0 έως Ν μπορείτε να χρησιμοποιήσετε:
- r = rand()%Ν;
Test puzzles
Δίνονται διάφορα puzzles “s.*” στο directory ~hy255/as4_sudoku/puzzles.
Makefile
Δημιουργήστε ένα Makefile το οποίο θα περιέχει τουλάχιστον τους εξής targets:
- make clean: πρέπει να σβήνει όλα τα αρχεία που παράγονται κατά την μετάφραση του προγράμματος και να αφήνει μόνο τα header και source αρχεία του προγράμματος σας.
- make: πρέπει να παράγει το εκτελέσιμο sudoku.
Logistics
- Γράψτε το πρόγραμμα σας στα συστήματα sparc του CSD χρησιμοποιώντας τα εργαλεία gcc, emacs/vim/nano, gdb.
- Χρησιμοποιήστε τον gcc με τις command line παραμέτρους “-Wall, -ansi, -pedantic” για να κάνετε preprocess, compile, assemble, και link το πρόγραμμά σας.
- Δημιουργήστε ένα “readme” text file που περιέχει:
- Το όνομά σας
- Πράγματα που χειρίζεστε με διαφορετικό τρόπο από ότι ορίζει η άσκηση.
- Μια περιγραφή της βοήθειας που είχατε από άλλους στη δημιουργία του προγράμματος σας, και σε συμφωνία με το “Policies” section του web page του μαθήματος.
- (Προαιρετικά) Μία ένδειξη του πόσο χρόνο αφιερώσατε για την άσκηση.
- (Προαιρετικά) Οτιδήποτε άλλο θέλετε να αναφέρετε.
- Σχόλια που περιγράφουν τον κώδικά σας δεν πρέπει να υπάρχουν στο readme file. Πρέπει να τα ενσωματώσετε στο κατάλληλο σημείο του προγράμματος σας.
Turnin
Υποβάλετε την άσκηση σας όπως αναφέρεται στο section Policies του web page του μαθήματος. Υποβάλετε όλα τα source αρχεία της άσκησης σας: sudoku.h, grid.h, sudoku.c, grid.c, Makefile, test puzzles.
Βαθμολογία
Η βαθμολογία θα βασιστεί και στην ορθότητα αλλά και στο σχεδιασμό, όπως αναφέρεται στη σελίδα Policies του μαθήματος. Για να ενθαρρύνεται η χρήση σωστών πρακτικών προγραμματισμού, προσπαθείτε να τηρείτε όσο το δυνατόν πιο κοντά τις οδηγίες της σχετικής σελίδας και επίσης τις αρχές που εξηγούνται στο μάθημα. Όπως πάντα, η κατανόηση της άσκησης αλλά και η αναγνωσιμότητα ενός προγράμματος είναι σημαντικό μέρος του σχεδιασμού.
