Αλγόριθμος κατασκευής 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;
}

}