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
Post a comment or leave a trackback: Trackback URL.

Commenti

  • Massimiliano  On 9 marzo 2012 at 03:35

    Ciao. Grazie per i link alle slide dei tuoi corsi. Ti segnalo un microscopico errore su http://retis.sssup.it/~lipari/courses/infbase2012/: il link a http://retis.sssup.it/~lipari/courses/infbase2012/04.functions-handout.pdf dovrebbe essere http://retis.sssup.it/~lipari/courses/infbase2012/04.c_functions-handout.pdf
    Aspetto con ansia il resto :-)

    • glipari  On 9 marzo 2012 at 12:55

      grazie! lo correggo subito (stasera carico altri due file: template e exception per c++, e memoria dinamica per il C)

  • juhan  On 9 marzo 2012 at 10:14

    È uma grossa tentazione l’esercizio #2. Avendo tempo ci sarei per diverse proposte, anche non di quelle elencate. Purtroppo sono indaffarato tutto il giorno con codice vecchio (era vecchio già nell’altro millennio) e quando smetto vedo labels che mi ballano davanti agli occhi. Sì quel linguaggio, principalmente.

    • glipari  On 9 marzo 2012 at 12:56

      ieri sera mi sono scervellato 5 minuti per farlo in haskell, ma la soluzione non mi è ancora saltata davanti agli occhi, ci riprovo stasera se la mente è più lucida! in booca al lupo con quel linguaggio lì.

  • dikiyvolk  On 9 marzo 2012 at 13:03

    Ciao,

    Grazie per i link sono andato subito a vederli e il testo di Bruce Eckel è li nella mia libreria (comprato oramai 10/15 anni fa), non c’è il link attivo sulla pagina. Appena comincio la pausa pranzo mi leggo tutto il post

  • HopfMap  On 9 marzo 2012 at 16:43

    In Mathematica (sperando che il codice appaia leggibile):

    dim = 8;
    scacchiera = Table[{i, j}, {i, dim}, {j, dim}];

    regina[pos_List] :=
    Join[Table[{pos[[1]], j}, {j, Delete[Range[8], pos[[2]]]}],
    Table[{i, pos[[2]]}, {i, Delete[Range[8], pos[[1]]]}],
    Select[Table[{i, (pos[[2]] – pos[[1]]) + i}, {i,
    Delete[Range[8], pos[[1]]]}], 0 < #[[2]] <= dim &],
    Select[Table[{i, (pos[[2]] + pos[[1]]) – i}, {i,
    Delete[Range[8], pos[[1]]]}], 0 < #[[2]] <= dim &]]

    allperm = Permutations[Range[dim]];

    conf = {};
    Do[
    pattern =
    Join[regina[{1, allperm[[n, 1]]}], regina[{2, allperm[[n, 2]]}],
    regina[{3, allperm[[n, 3]]}], regina[{4, allperm[[n, 4]]}],
    regina[{5, allperm[[n, 5]]}], regina[{6, allperm[[n, 6]]}],
    regina[{7, allperm[[n, 7]]}], regina[{8, allperm[[n, 8]]}]];
    If[Length[Complement[Flatten[scacchiera, 1], pattern]] == 8,
    AppendTo[conf, Complement[Flatten[scacchiera, 1], pattern]]],
    {n, Length[allperm]}]

    conf // Length

    Le configurazioni totali che si ottengono sono 92, che andrebbero "moddate" da tutte le configurazioni equivalenti per simmetria.

    • glipari  On 9 marzo 2012 at 22:21

      Bellissimo, grazie! Lo provo appena posso. Hai fatto una prova di velocità?

      • HopfMap  On 10 marzo 2012 at 10:15

        Ciao, dunque il codice su un I3 (2.27 GHz) con Ubuntu 11.04 gira in circa 30 secondi (misurati con la funzione AbsoluteTiming). Immagino che si possa ottimizzare già semplicemente utilizzando il Compile.
        Nel frattempo ho esteso il codice che adesso funziona per ogni dimensione della scacchiera (e disegna anche le configurazioni) e se vuoi lo posso postare. Rimane solamente da eliminare le configurazioni equivalenti per simmetria.

    • juhan  On 10 marzo 2012 at 11:22

      Dr prof propongo di chiedere a HopfMap di raccontarci tutto in un post tutto suo. Con l’occasione ci svelerebbe da dove viene il suo nick ;-)
      Dovresti chiederglielo tu, sai la carica…
      OK! basta trollare, mi metto a lavorare.
      Però sarebbe bello, davvero :-D

      • glipari  On 10 marzo 2012 at 14:30

        Certo. Ehi, HopftMap, ti andrebbe di collaborare con un bel post sul tuo programmino? in tal caso mi serve la tua e-mail, puoi contattarmi a uno dei miei vari indirizzi e-mail che si trovano in giro sulla rete, oppure vai sulla pagina “Chi siamo” di questo blog! Se invece preferisci di no, va beh, mandaci il programmino che lo pubblichiamo noi.
        (certo 30 secondi sono tanti, e con il compile?)

  • Dikiyvolk  On 11 marzo 2012 at 08:44

    Questo è il codice pascal. Impiega 1.766 s in una macchina windows virtuale, ho aggiunto solo il pezzo che calcola il tempo :)
    Era un bel po’ che non usavo write e writeln…

    Ciao e buona domenica a tutti.

    program QueensDos;

    {$APPTYPE CONSOLE}

    {$R *.res}

    uses
    System.SysUtils;

    const
    N = 8;

    type
    MyBoard = array[0..N - 1, 0..N - 1] of char;

    var
    board: MyBoard;
    count: integer;
    dStart, dEnd: TDateTime;

    procedure init_board(var board: MyBoard);
    var
    i, k: integer;

    begin
    for i := 0 to N – 1 do
    for k := 0 to N – 1 do
    board[i, k] := ‘.';
    end;

    procedure print_board(var board: MyBoard);
    var
    i, j: integer;

    begin
    for i := 0 to N – 1 do
    write(‘-‘);
    writeln(”);

    for i := 0 to N – 1 do
    begin
    for j := 0 to N – 1 do
    write(board[i, j]);

    writeln(”);
    end;

    for i := 0 to N – 1 do
    write(‘-‘);
    writeln(”);
    writeln(”);
    end;

    procedure copy_board(var my_board: MyBoard; var board: MyBoard);
    var
    i, k: integer;

    begin
    for i :=0 to N – 1 do
    for k := 0 to N – 1 do
    my_board[i, k] := board[i, k];
    end;

    procedure queens(var board: MyBoard; row: integer);
    var
    my_board: MyBoard;
    i, j: integer;

    begin
    if row = N then
    begin
    print_board(board);
    inc(count);
    end
    else
    begin
    copy_board(my_board, board);

    for j := 0 to N – 1 do
    begin
    if my_board[row, j] ‘x’ then
    begin
    for i := 0 to N – 1 do
    begin
    if i row then
    begin
    my_board[i, j] := ‘x';

    if ((j – row + i >= 0) and (j – row + i = 0) and (j + row – i < N)) then
    my_board[i, j + row - i] := 'x';
    end;
    end;
    my_board[row, j] := 'R';
    queens(my_board, row + 1);
    copy_board(my_board, board);
    end;
    end;
    end;
    end;

    begin
    try
    dStart := now;
    init_board(board);
    queens(board, 0);
    dEnd := now;
    writeln('The total number of solutions is ' + IntToStr(count));
    writeln('Elasped time: ' + FormatDateTime('hh:nn:ss.zzz', dEnd – dStart));

    except
    on E: Exception do
    Writeln(E.ClassName, ': ', E.Message);
    end;
    end.

    • juhan  On 11 marzo 2012 at 10:48

      Fa un certo effetto vedere tutto appiattito sulla sinistra e la fila di quattro end; uno di seguito all’altro.
      Mi sa che alla fine ci dovrà essere un post riassuntivo, scritto come si deve ;-)
      Ah! lo sapete che nessuno ha pensato di farlo in newLISP? Ma c’è in altri Lisp, chissà…

      • Dikiyvolk  On 11 marzo 2012 at 14:17

        Ciao Juhan,

        Si è veramente brutto l’allineamento tutto a sinistra :( per di più mi ha cancellato il simbolo di diverso in un if… uffi & uffi.

        Questo invece è il codice in ruby che mi sto studiando nel tempo libero.

        
        N = 8
        
        $count = 0
        
        def init_board(board)
          for i in 0..N - 1
            for k in 0..N - 1
              board[i][k] = '.'
            end
          end
        end
        
        def print_board(board)
          for i in 0..N - 1
            print "-"
          end
        
          puts ""
        
          for i in 0..N - 1
            for j in 0..N - 1
              print board[i][j]
            end
            puts ""
          end
        
          for i in 0..N - 1
            print "-"
          end
        
          puts ""
          puts ""
        end
        
        # copy the board into myboard
        def copy_board(myboard, board)
          for i in 0..N - 1
            for k in 0..N - 1
              myboard[i][k] = board[i][k]
            end
          end
        end
        
        # main algorithm
        def queens(board, row)
          myboard = Array.new(N) {Array.new(N)}
        
          if (row == N)
            print_board(board)
            $count += 1
          else
            copy_board(myboard, board);
        
            for j in 0..N - 1
              if myboard[row][j] != "x"
                for i in 0..N - 1
                  if i != row
                    myboard[i][j] = 'x';   # same column
        
                    if ((j - row + i >= 0) && (j - row + i < N))
                      myboard[i][j - row + i] = "x";
                    end
        
                    if ((j + row - i >= 0) && (j + row - i < N))
                      myboard[i][j + row - i] = "x";
                    end
                  end
                end
                myboard[row][j] = "R";
                queens(myboard, row+1);
                copy_board(myboard, board);
              end
            end
          end
        end
        
        
        board = Array.new(N) {Array.new(N)}
        
        init_board(board)
        queens(board, 0)
        puts "The total number of solutions is " + $count.to_s
        
        
      • Dikiyvolk  On 11 marzo 2012 at 14:22

        Visto che ho scoperto che anche i commenti accettano il tag sourcecode :) rimando quello di delphi in formato leggibile :)

        program QueensDos;
        
        {$APPTYPE CONSOLE}
        
        {$R *.res}
        
        uses
          System.SysUtils;
        
        const
          N = 8;
        
        type
          MyBoard = array[0..N - 1, 0..N - 1] of char;
        
        var
          board: MyBoard;
          count: integer;
          dStart, dEnd: TDateTime;
        
          procedure init_board(var board: MyBoard);
          var
            i, k: integer;
        
          begin
            for i := 0 to N - 1 do
              for k := 0 to N - 1 do
                board[i, k] := '.';
          end;
        
          procedure print_board(var board: MyBoard);
          var
            i, j: integer;
        
          begin
            for i := 0 to N - 1 do
              write('-');
            writeln('');
        
            for i := 0 to N - 1 do
            begin
              for j := 0 to N - 1 do
                write(board[i, j]);
        
              writeln('');
            end;
        
            for i := 0 to N - 1 do
              write('-');
            writeln('');
            writeln('');
          end;
        
          procedure copy_board(var my_board: MyBoard; var board: MyBoard);
          var
            i, k: integer;
        
          begin
            for i :=0 to N - 1 do
              for k := 0 to N - 1 do
                my_board[i, k] := board[i, k];
          end;
        
          procedure queens(var board: MyBoard; row: integer);
          var
            my_board: MyBoard;
            i, j: integer;
        
          begin
            if row = N then
            begin
              print_board(board);
              inc(count);
            end
            else
            begin
              copy_board(my_board, board);
        
              for j := 0 to N - 1 do
              begin
                if my_board[row, j] <> 'x' then
                begin
                  for i := 0 to N - 1 do
                  begin
                    if i <> row then
                    begin
                      my_board[i, j] := 'x';
        
                      if ((j - row + i >= 0) and (j - row + i < N)) then
                        my_board[i, j - row + i] := 'x';
        
                      if ((j + row - i >= 0) and (j + row - i < N)) then
                        my_board[i, j + row - i] := 'x';
                    end;
                  end;
                  my_board[row, j] := 'R';
                  queens(my_board, row + 1);
                  copy_board(my_board, board);
                end;
              end;
            end;
          end;
        
        begin
          try
            dStart := now;
            init_board(board);
            queens(board, 0);
            dEnd := now;
            writeln('The total number of solutions is ' + IntToStr(count));
            writeln('Elasped time: ' + FormatDateTime('hh:nn:ss.zzz', dEnd - dStart));
        
          except
            on E: Exception do
              Writeln(E.ClassName, ': ', E.Message);
          end;
        end.
        
  • Francesco  On 4 settembre 2014 at 10:59

    Se volete giocarci… http://www.sblendorio.eu/Misc/DosGames

Trackbacks

  • By Ancora regine « Ok, panico on 13 aprile 2012 at 00:04

    [...] mi sforzerò più di tanto perché vi propongo la soluzione in Haskell del problema delle regine, di cui avevo già parlato qualche eone fa, ricordate? No, allora ripeto velocemente. Lo so, non c'entra niente con il post, ma Elisabetta I [...]

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

Iscriviti

Ricevi al tuo indirizzo email tutti i nuovi post del sito.

Unisciti agli altri 77 follower

%d blogger cliccano Mi Piace per questo: