Le otto regine

Ultimamente i miei post sui miei vari blog si sono un po’ rarefatti. Troppe cose da fare a casa e al lavoro, e spesso arrivo alla sera che sono distrutto. Però ci tengo a scrivere post per Ok, panico, davvero. Sono contento di come è venuto su questo blog, grazie anche ai colleghi e in particolare all’infaticabile Juhan!

Uno dei miei impegni pressanti è come al solito il mio lavoro, e in particolare l’insegnamento. Questo post mi serve innanzitutto per segnalarvi che io metto a disposizione le slide dei miei corsi sul mio sito web istituzionale, e magari potrebbero esservi utili, anche solo per ripassare! Eccoli:

• Fondamenti di programmazione con il linguaggio C. Questo è un corso di informatica di base. Comprende un’introduzione al linguaggio C, con un po’ di esempi, e poi un po’ di strutture dati. E’ di sole 30 ore. Lo faccio per gli studenti di ingegneria della Scuola Sant’Anna non informatici (meccanici, aeronautici, ecc.)

• Programmazione con il C++. Questo invece è un corso avanzato di C++. Presuppone la conoscenza di base del C, e arriva fino ai template, al template metaprogramming, ai design pattern, alla programmazione concorrente, al nuovo standard c++11.

Non ho ancora pubblicato tutte le slide, perché le scrivo/aggiusto man mano che ci sono le lezioni. Quindi, se non trovate quello che vi serve, magari potete tornarci nei prossimi giorni. E se trovate qualche errore o qualche corbelleria, vi prego di segnalarmela!

Durante il mio corso di C, l’altro ieri abbiamo risolto insieme ai miei studenti il problema delle 8 regine.

Si tratta di un problema abbastanza semplice da spiegare: data una normale scacchiera, piazzare 8 regine in maniera che nessuna sia in grado di “mangiare” le altre. Il problema ha 92 soluzioni. Se eliminiamo quelle equivalenti per simmetria (riflessione e  rotazione) si riducono solo a 12.

Ecco un programma in C che calcola tutte le soluzioni nel caso generico NxN:

/**
   Lists all possible solutions of the n-queens problems. The program 
   can work on boards of all dimensions, but keep it limited! 
 */
#include <stdio.h>

// number of rows (and columns) on the board (default is 4)
#define N  8

// number of solutions
int count = 0;

/* initialize the board */
void init_board(char board[N][N])
{
    int i, k;
    
    for (i=0; i<N; i++)
        for (k=0; k<N; k++) 
            board[i][k] = '.'; 
}

/* print the board on the screen */
void print_board(char board[N][N])
{
    int i, j;

    for(i=0; i<N; i++) putchar('-');

    printf("\n");

    for(i=0; i<N; i++) {
        for (j=0; j<N; j++)
            putchar(board[i][j]);
        printf("\n");
    }

    for(i=0; i<N; i++) putchar('-');
    printf("\n\n");
}

/* copy the board into myboard */
void copy_board(char myboard[N][N], char board[N][N])
{
    int i, k;

    for (i=0; i<N; i++) 
        for (k=0; k<N; k++) myboard[i][k] = board[i][k];
}

/* main algorithm */
void queens(char board[N][N], int row)
{
    char myboard[N][N];
    int i, j;

    if (row == N) {
        print_board(board);
        count++;
        return;
    }

    copy_board(myboard, board);
  
    for (j=0; j<N; j++) {
        if (myboard[row][j] != 'x') {
            for (i=0; i<N; i++) {
                if (i == row) continue;
                myboard[i][j] = 'x';   // same column
                
                if ((j-row+i >= 0) && (j-row+i < N)) 
                    myboard[i][j-row+i] = 'x';
                
                if ((j+row-i >= 0) && (j+row-i < N)) 
                    myboard[i][j+row-i] = 'x';
            }
            myboard[row][j] = 'R';
            queens(myboard, row+1);
            copy_board(myboard, board);
        }
    }
}

int main()
{
    char board[N][N];
    init_board(board);
    queens(board, 0);
    printf("The total number of solutions is %d\n", count);
    return 0;
}

La costante N rappresenta la dimenzione della scacchiera. Potete provare con un qualunque numero, ma vi avverto che se mettete un valore superiore a 14 il pogramma ci mette un po’ troppo. Infatti, fa una ricerca esaustiva di tutte le possibili posizioni, che sono “un bel po’” (quante?).

La funzione principale è queens. Questa funzione è ricorsiva, naturalmente: essa ha il compito di piazzare una regina alla riga row e poi di chiamare se stessa con row+1. Inoltre fa una copia della scacchiera prima di cominciare a piazzare la regina e a marcare le caselle “vietate”. Per provare, salvate il file (per esempio in queens.c), e compilate con il comando gcc queens.c -o queens. Quindi eseguite con ./queens.

Naturalmente non è il programma più ottimizzato possibile, sia dal punto di vista della velocità o della memoria, se avete consigli per migliorare, sono benvenuti!

E poi, due semplici esercizi:

1) sapete modificare il programma per evitare le soluzioni equivalenti per riflessione? e per evitare le soluzioni equivalenti per rotazione?

2) sapete scrivere un programma analogo in un altro linguaggio? (qualunque linguaggio va bene, objective-c, newLISP, python, fortran, gambas, go, java, delphi…)

Se volete, potete scrivere le vostre soluzioni nei commenti. E se non avrete tempo di farlo… vi capisco benissimo!

Alla prossima!

About these ads