N-queens σε C με bitmasks και αναδρομή

Όσο προσπαθώ να βρω μια ικανοποιητική λύση για posting κώδικα στο blogspot, θα ήθελα με αυτό το post να μοιραστώ μια πολύ όμορφη λύση στο πρόβλημα των N-Βασιλισσών σε C, η οποία συνδυάζει μικρό και "συμπαγή" κώδικα με αρκετά καλή αποδοτικότητα σε χώρο/χρόνο, χάρη στο συνδυασμό bitmasks και αναδρομής.

Όπως γνωρίζετε (ή διαβάσατε στο παραπάνω άρθρο), το πρόβλημα των N-Queens θέτει ως πρόκληση το να τοποθετηθούν N Βασίλισσες σε μια σκακιέρα μεγέθους NxN έτσι ώστε καμία να μην μπορεί να "επιτεθεί" στις υπόλοιπες (δηλαδή καμία να μη βρίσκεται στην ίδια γραμμή, στήλη ή διαγώνιο με κάποια άλλη).

Ας υποθέσουμε ότι το πρόγραμμά μας χρειάζεται απλώς να μετρά τις λύσεις του προβλήματος για διάφορες τιμές του N.

Αν υποθέσουμε επίσης ότι ο αλγόριθμός μας κάνει ότι πιθανότατα θα έκανε κι ένας άνθρωπος, δηλαδή τοποθετεί μία βασίλισσα στη σκακιέρα τη φορά, τότε μπορούμε εύκολα να δούμε ότι το "βάθος" του δέντρου αναζήτησης του αλγορίθμου είναι N (όταν έχει τοποθετήσει όλες τις βασίλισσες).

Οι περισσότερες τυπικές λύσεις χρησιμοποιούν ένα 2D πίνακα για να αναπαραστήσουν τη σκακιέρα και ένα σωρό for / while loops για να "σημαδέψουν" τα τετράγωνα που "καθαρίζει" κάθε νέα βασίλισσα που τοποθετούμε καθώς και για να ανακαλύψουν το επόμενο ελεύθερο τετράγωνο κάθε φορά.

Αν παρατηρήσουμε το πρόβλημα πιο προσεκτικά, θα δούμε ότι έτσι κι αλλιώς είναι αδύνατον 2 βασίλισσες να τοποθετηθούν στην ίδια στήλη, οπότε μας αρκεί ένας μονοδιάστατος πίνακας του οποίου τα στοιχεία μας δίνουν τη γραμμή όπου έχει τοποθετηθεί η αντίστοιχη βασίλισσα.

Π.χ.,

board[2] = 6;

Σημαίνει ότι μία βασίλισσα είναι τοποθετημένη στο (2,6) τετράγωνο. Αυτό απλοποιεί λίγο τον κώδικα, αλλά μπορούμε να κάνουμε κάτι ακόμα καλύτερο.

Καταρχήν, επειδή μας ενδιαφέρει απλά να απαριθμήσουμε τις λύσεις, μας αρκεί σε κάθε βήμα του αλγορίθμου (στο οποίο εξετάζουμε μια γραμμή της σκακιέρας) να γνωρίζουμε απλά ποιες είναι οι θέσεις που μπορούμε να τοποθετήσουμε μια βασίλισσα με ασφάλεια σε αυτή τη γραμμή. Επίσης για N > 20 με 22, ο ίδιος ο αριθμός των λύσεων γίνεται τόσο τεράστιος που η επίλυση παύει να είναι πρακτική σε ένα συνηθισμένο μηχάνημα από αυτό το σημείο και πέρα (με οποιοδήποτε πλήρη αλγόριθμο, μόνο προσεγγιστικοί αλγόριθμοι που βρίσκουν κάποιες από τις λύσεις είναι εφαρμόσιμοι). Έτσι, το να περιορίσουμε τη λύση μας για N=32 ή 64 δεν μας περιορίζει στην πράξη.

Και οι 2 παραπάνω παρατηρήσεις, μας οδηγούν να σκεφτούμε αν μπορούμε να χρησιμοποιήσουμε bitmasks για την αναπαράσταση της κατάστασης της αναζήτησης. Η απάντηση είναι φυσικά "ναι" :)

Η ιδέα είναι να έχουμε 3 bitmasks σε κάθε βήμα του αλγορίθμου:

1. cols_b: Για το σύνολο των στηλών που "καλύπτονται" από τις ήδη τοποθετημένες βασίλισσες (κάθετα).
2. rd_b: Για το σύνολο των στηλών που "καλύπτονται" λόγω δεξιάς διαγώνιας επίθεσης από τις υπάρχουσες βασίλισσες. Αυτό το mask μπορούμε να το ανανεώνουμε πολύ αποδοτικά σε κάθε βήμα, με ολίσθηση προς τα δεξιά.
3. ld_b: Για το σύνολο των στηλών που "καλύπτονται" λόγω αριστερής διαγώνιας επίθεσης από τις υπάρχουσες βασίλισσες. Αυτό το mask μπορούμε να το ανανεώνουμε πολύ αποδοτικά σε κάθε βήμα, με ολίσθηση προς τα αριστερά.

Όπως βλέπουμε και στο σχήμα, τα 3 bitmasks αποτελούν ουσιαστικά τις προβολές των κάθετων και διαγώνιων γραμμών που καλύπτονται από τις ήδη τοποθετημένες βασίλισσες, πάνω στην τωρινή γραμμή.

Από τα 3 παραπάνω bitmasks μπορούμε φυσικά πολύ γρήγορα (constant-time ουσιαστικά, αφού για το bitmask χρησιμοποιούμε ένα register στο hardware για N ως το word size σε bits) να σχηματίσουμε ένα mask με όλες τις "απαγορευμένες" θέσεις στην τρέχουσα γραμμή, απλά παίρνοντας την ένωση (bitwise or) των 3 bitmasks:

blocked_squares = ld_b | cols_b | rd_b;

όπου τα ld_b, cols_b, rd_b έχουν 1 στις θέσεις που είναι αποκλεισμένες.

Σε κάθε βήμα θέλουμε να βρούμε "την επόμενη ελεύθερη θέση" στην τωρινή γραμμή, άρα το πρώτο μηδενικό στη μάσκα squares_blocked (ας το ονομάσουμε sq_b από εδώ κι εμπρός για συντομία). Αυτό μπορεί να επιτευχθεί με ένα κλασικό bitmask trick:

next = ~sq_b & (sq_b+1)

Το παραπάνω θα μας δώσει ένα bitmask με 1 στη θέση του πρώτου μηδενικού στο sq_b.

Σε κάθε βήμα λοιπόν του αλγορίθμου εξετάζουμε μία γραμμή παίρνοντας το πρώτο μηδενικό στη μάσκα sq_b. Πρώτα αποκλείουμε αυτή τη θέση από περαιτέρω εξέταση:

sq_b |= next;

και μετά προχωρούμε στην εξέταση της επόμενης θέσης με βάση τα δεδομένα που προκύπτουν από την επιλογή μας για την τωρινή:

search((ld_b | next) << 1, cols_b | next,
       (rd_b | next) >> 1);

βλέπουμε την ιδιαίτερα όμορφη και κομψή συνθήκη ανανέωσης για τα bitmasks.

Ο τελικός κώδικας που προκύπτει έχει ως εξής:

#include <iostream>
#include <cstdlib>
using namespace std;

static const unsigned long all = ~0ul;

static unsigned long search(unsigned long ld_b, unsigned long cols_b,
                     unsigned long rd_b, unsigned long nsolns)
{
    if (all == cols_b) { //if all queens have been placed
        nsolns++;  //we have a solution!!
    }
    else {
        unsigned long sq_b = ld_b | cols_b | rd_b;
        while (all != sq_b) {
            unsigned long next = ~sq_b & (sq_b+1); //next free column
            sq_b |= next;
            nsolns = search((ld_b | next) << 1, cols_b | next,
                            (rd_b | next) >> 1, nsolns);
        }
    }
    return nsolns;
}

int main(int argc, char* argv[])
{
    int arg = argc < 2 ? 22 : atol(argv[1]); //we limit ourselves to
    int N = arg < 22 ? arg : 22;             //at most N=22

    for (int i=1;  i<=N; i++)
        cout << i << ": " << search(0, ~0ul >> i, 0, 0)  << endl;
    return 0;
}

Η τεχνική που είδαμε (bitmasks + αναδρομή) εφαρμόζεται και σε άλλα παρόμοια προβλήματα, οπότε είναι χρήσιμο να υπάρχει στο "οπλοστάσιο" ενός προγραμματιστή.

Παντελής