Quadrato magico in C++

Il quadrato magico è una particolare matrice di dimensione N x N, con N dispari, e tutti valori distinti da 1 a N², la cui proprietà consiste nell’avere la somma di ogni singola riga uguale, e in più tale somma è uguale alla somma di ogni singola colonna. Vediamo come realizzarne una con dimensione a scelta.

La spiegazione dei singoli passaggi è all’interno dei commenti del codice completo. In questo genere di esercizi dove l’algoritmo è un po’ criptico, consiglio agli alunni di disegnare su foglio una  matrice di prova con tanto di coordinate e provare a risolvere il problema su carta, prima che sul pc. L’algoritmo in questione può essere formulato i due modi. Intanto si parte piazzando il numero 1 al centro della prima riga. Dopodiché, ci si sposta di una casella in alto a sinistra in diagonale. Se si strasborda, è come se si riniziasse dal lato opposto. Alcuni testi riportano analoga procedura, ma esattamente opposta, in diagonale in basso a destra. Cambia poco nelle considerazioni che possono essere trasposte facilmente. Noi scegliamo di muoverci in alto a sinistra.

L’esercizio prevede una matrice di base molto grande, con dim 100 ma se ne può usare una piccola parte selezionando la dimensione reale di interesse.

#include <iostream>
#include <iomanip>      // std::setw

using namespace std;

#define DIM 100

void stampa(int [DIM][DIM], int);

int main()
{
    int n;
    int numero = 1;
    int quadrato [DIM][DIM];

    int riga, colonna;
    cout << "Inserisci la dimensione del quadrato magico (numero dispari)" << endl;
    cin >> n;



    /* Parto dall'esempio 3x3
        (0,0) (0,1) (0,2)
        (1,0) (1,1) (1,2)
        (2,0) (2,1) (2,2)
    */
    //inserisco il numero iniziale in posizione prima riga, al centro  ovvero (0,1) nella 3x3
    quadrato[0][n/2]= 1;

    //uso due variabili riga e colonna per spostarmi tra le celle, parto da quella iniziale
    riga = 0;
    colonna = n/2;

    //devo piazzare tutti i numeri all'interno della matrice
    for (int i=0; i < (n*n); i++)
    {
        //sulla riga mi sposto a sinistra
        riga = riga - 1;
        //controllo se sto sforando con la riga
        if (riga < 0)
        {
            riga = n - 1;
        }

        //sulla colonna mi sposto in alto
        colonna = colonna - 1;
        //controllo se sto sforando con la colonna
        if (colonna < 0)
        {
            colonna = n - 1;
        }

        //potrebbe creare un loop, quindi mi creo uno spostamento ulteriore
        //se ho già scritto il numero
        if (quadrato[riga][colonna] != 0)
        {
            //mi devo spostare in diagonale alta verso sinistra
            riga = riga + 2;
            colonna = colonna + 1;

            //controlli per saltare da una diagonale all'altra
            if (riga == n+1)
            {
				riga=1;
			}

            //controlli per saltare da una diagonale all'altra
            if (colonna == n)
            {
                colonna = 0;
            }

            numero++;
            quadrato[riga][colonna]= numero;

        }
        else
        {
            //ok, posso scrivere semplicemente il numero
            numero++;
            quadrato[riga][colonna]= numero;
        }

    }

    stampa(quadrato, n);
    return 0;
}

void stampa(int _matrice[DIM][DIM], int n)
{
    for (int i=0; i < n; i++)
    {
        cout << setw(2);
        for (int j=0; j < n; j++)
        {
            cout << setw(2) << _matrice[i][j] << " ";
        }
        cout << endl;
    }
}

Ultima modifica 14 Gennaio 2022