Quadrato Magico

[axpgn]

Costruire un quadrato magico composto da interi positivi di dimensioni $3 xx 3$, la cui costante magica sia $99$ e che contenga il numero $12$.

Cordialmente, Alex

[ghira1]

Con 12 al centro non è possibile. Con 12 nell'angolo possiamo fare:

$((12,62,25),(46,33,20),(41,4,54))$
o più generalmente
$((12,a,87-a),(108-a,33,a-42),(a-21,66-a,54))$
con 12 sul bordo:
$((32,12,55),(56,33,10),(11,54,34))$
o più generalmente:
$((a,12,87-a),(120-2a,33,2a-54),(a-21,54,66-a))$

(Tutto fatto con le equazioni simultanee, lo confesso.)

Vogliamo evitare i duplicati (e 0 i numeri negativi) ma a parte questo non so se ci sono soluzioni chiaramente "migliori". Minimizziamo la differenza fra il numero massimo e il numero minimo?

[axpgn]

Va bene tutto, basta rispettare le condizioni
D'altra parte, il quadrato magico è veramente un "passatempo"

Cosa intendi con "minimo" e "massimo"?

Cose così?

$((12,43,44),(65,33,1),(22,23,54))$

$((28,12,59),(64,33,2),(7,54,38))$

Cordialmente, Alex

[ghira1]

"axpgn":

Cosa intendi con "minimo" e "massimo"?

Magari se c'è una soluzione dove il numero minimo nel quadrato è 1 e il massimo è 80, e un'altra dove tutti i numeri sono fra 10 e 60, preferiamo la seconda perché c'è meno variazione. Ma forse no. Chiaramente un 12 ci deve essere.

[Umby2]

Visto che ci sono diverse soluzioni,
non sarebbe il caso di scrivere 4 righe di codice, per conoscere QUANTE ne sono ?

[axpgn]

Mica sono un programmatore
Dammi un attimo ...

Me ne risultano $200$ ... ma proprio tutte ...

La minima differenza mi viene $42$ tra l'altro son tutti con minimo $12$ (e massimo $54$ ovviamente)

S.E.&O.

Cordialmente, Alex

[axpgn]

Effettivamente diverse dovrebbero essere solo $25$, di cui $11$ con il $12$ in un angolo e $14$ con il $12$ al centro del bordo.

Cordialmente, Alex

[Super Squirrel]

Non avendo alcuna esperienza con i quadrati magici, ho provato ad implementare la prima idea che mi è venuta in mente:

#include <iostream>

using namespace std;

void stampa_quadrato_magico(int *v, const unsigned int m)
{
    for(unsigned int i = 0; i < 9; ++i)
    {
        if(!(i % 3))
        {
            cout << endl;
        }
        cout << "  " << v[i];
    }
    cout << endl << endl;
}

int main()
{
    const int m = 99;
    const int n = 12;
    unsigned int cont = 0;
    unsigned int u[m - 2] = {0};
    unsigned int w[3][23] = {{4, 0, 8, 2, 6, 1, 3, 5, 7, 0, 2, 0, 6, 2, 8, 6, 8, 3, 4, 5, 1, 4, 7},
                             {0, 1, 2, 3, 6, 4, 5, 7, 8, 2, 6, 3, 4, 1, 4, 2, 5, 0, 4, 8, 6, 7, 8},
                             {1, 0, 2, 4, 7, 6, 8, 3, 5, 2, 4, 0, 4, 0, 6, 2, 8, 3, 4, 5, 6, 7, 8}};
    int v[9];
    ++u[n];
    for(unsigned int k = 0; k < 3; ++k)
    {
        v[w[k][0]] = n;
        for(int i_1 = m - n - 1, j_1 = 1; i_1 > j_1 * (k != 1); --u[i_1--], --u[j_1++])
        {
            if(!(u[v[w[k][1]] = i_1]++ + u[v[w[k][2]] = j_1]++))
            {
                for(int i_2 = k ? 1 : j_1 + 1, j_2 = k ? m - n - 1 : i_1 - 1; j_2 > i_2 * !k + j_1 * (k == 1); --u[i_2++], --u[j_2--])
                {
                    if(!(u[v[w[k][3]] = i_2]++ + u[v[w[k][4]] = j_2]++))
                    {
                        v[w[k][5]] = v[w[k][6]] = v[w[k][7]] = 0;
                        if((m - v[w[k][9]]  - v[w[k][10]]) > 0 && !u[v[w[k][5]] = m - v[w[k][9]]  - v[w[k][10]]]++ &&
                           (m - v[w[k][11]] - v[w[k][12]]) > 0 && !u[v[w[k][6]] = m - v[w[k][11]] - v[w[k][12]]]++ &&
                           (m - v[w[k][13]] - v[w[k][14]]) > 0 && !u[v[w[k][7]] = m - v[w[k][13]] - v[w[k][14]]]++ &&
                           (m - v[w[k][15]] - v[w[k][16]]) > 0 && !u[v[w[k][8]] = m - v[w[k][15]] - v[w[k][16]]]   &&
                            v[w[k][17]] + v[w[k][18]] + v[w[k][19]] == m &&
                            v[w[k][20]] + v[w[k][21]] + v[w[k][22]] == m)
                        {
                            cout << ++cont << ":";
                            stampa_quadrato_magico(v, m);
                        }
                        --u[v[w[k][5]]];
                        --u[v[w[k][6]]];
                        --u[v[w[k][7]]];
                    }
                }
            }
        }
    }
}

Il programma calcola i quadrati magici di costante magica $m$ e contenente il numero $n$ (supposti entrambi positivi).
Questo l'output per il caso in esame:

1:
  12  65  22
  43  33  23
  44   1  54

2:
  12  64  23
  44  33  22
  43   2  54

3:
  12  63  24
  45  33  21
  42   3  54

4:
  12  62  25
  46  33  20
  41   4  54

5:
  12  61  26
  47  33  19
  40   5  54

6:
  12  60  27
  48  33  18
  39   6  54

7:
  12  59  28
  49  33  17
  38   7  54

8:
  12  58  29
  50  33  16
  37   8  54

9:
  12  57  30
  51  33  15
  36   9  54

10:
  12  56  31
  52  33  14
  35  10  54

11:
  12  55  32
  53  33  13
  34  11  54

12:
  59  12  28
   2  33  64
  38  54   7

13:
  58  12  29
   4  33  62
  37  54   8

14:
  57  12  30
   6  33  60
  36  54   9

15:
  56  12  31
   8  33  58
  35  54  10

16:
  55  12  32
  10  33  56
  34  54  11

17:
  53  12  34
  14  33  52
  32  54  13

18:
  52  12  35
  16  33  50
  31  54  14

19:
  51  12  36
  18  33  48
  30  54  15

20:
  50  12  37
  20  33  46
  29  54  16

21:
  49  12  38
  22  33  44
  28  54  17

22:
  48  12  39
  24  33  42
  27  54  18

23:
  46  12  41
  28  33  38
  25  54  20

24:
  45  12  42
  30  33  36
  24  54  21

25:
  44  12  43
  32  33  34
  23  54  22


Process returned 0 (0x0)   execution time : 0.131 s
Press any key to continue.

[axpgn]

@Super Squirrel

Il programma non so leggerlo ( ) però volevo chiederti cosa rappresenta quell'array di numeri 3x23 mentre presumo che per evitare rotazioni e riflessioni hai limitato la posizione del 12 all'angolo e al centro bordo.
E comunque un gran lavoro

Cordialmente, Alex

[Super Squirrel]

In pratica, una volta fissato il valore iniziale $n$ in una determinata casella, scelgo due sequenze (nel senso di riga, colonna o diagonale) passanti per essa e vado a generare tutte le possibili somme (facendo riferimento al codice sarà $n+i_1+j_1=n+i_2+j_2=m$). A questo punto saranno rimaste quattro caselle vuote che possono essere univocamente calcolate in base ai numeri già presenti nel quadrato. Infine non resta che verificare che la somma delle due sequenze rimaste inutilizzate sia anch'essa pari a $m$. Il tutto ovviamente analizzando passo passo la fattibilità e l'assenza di "doppioni".

"axpgn":volevo chiederti cosa rappresenta quell'array di numeri 3x23

Le tre righe si riferiscono rispettivamente ai casi "centro", "angolo in alto a sinistra" e "bordo superiore". Ogni riga contiene invece le informazioni relative a quali caselle del quadrato (rappresentato dall'array $v$ come

v[0] v[1] v[2]
v[3] v[4] v[5]
v[6] v[7] v[8]

) considerare per le varie operazioni e controlli. Per esempio w[k][0] contiene l'indice dell'elemento di $v$ contenente $n$, w[k][1] e w[k][2] contengono gli indici dei due elementi di $v$ (a cui saranno assegnati rispettivamente i valori $i_1$ e $j_1$) appartenenti alla prima delle due sequenze passanti per $n$, ecc...

"axpgn":mentre presumo che per evitare rotazioni e riflessioni hai limitato la posizione del 12 all'angolo e al centro bordo.

Esatto, fissare $n$ nell'angolo in alto a sinistra e nel bordo superiore serve per evitare rotazioni e alcune simmetrie, rimangono però i problemi dovuti rispettivamente alla simmetria rispetto alla diagonale principale e rispetto all'asse verticale. A tal proposito, come peraltro per il caso di $n$ centrale, per evitare di considerare più volte la stessa soluzione ho dovuto imporre delle condizioni sulle variabili $i_1$,$j_1$ e $i_2$,$j_2$.

In ogni caso credo che studiando meglio il problema si possa fare sicuramente di meglio!

[axpgn]

Più o meno ho capito

[Umby2]

"Super Squirrel":

Non avendo alcuna esperienza con i quadrati magici, ho provato ad implementare la prima idea che mi è venuta in mente:

Il codice non è molto leggibile, ma vedendo solo l'output ti chiedo:

Perchè hai fissato il "12" solo sulla prima riga ?

[Umby2]

Le regole del quadrato:

- le 9 caselle vanno compilate con numeri da 1 a 99 (anzi 96 [1-2-96]), lo ZERO è escluso, giusto ?
- la somma delle 3 righe, delle 3 colonne, delle 2 diagonali, deve essere 99. Giusto ?
- i 9 numeri non si possono ripetere. Giusto ?

Dimentico qualcosa ?
(a parte il "12" che nel ns. gioco deve essere presente ...)

[Super Squirrel]

"Umby":Il codice non è molto leggibile, ma vedendo solo l'output ti chiedo:

Perchè hai fissato il "12" solo sulla prima riga ?

In effetti mi rendo conto che concentrandomi sulla brevità, la leggibilità ne ha risentito parecchio!
In ogni caso ho fissato la posizione di $n$ (pari a $12$ nel caso specifico) per evitare di considerare più volte la stessa soluzione, ossia quelle 7 soluzioni ricavabili da quella "originale" attraverso rotazioni o simmetrie.
In fin dei conti in un quadrato 3x3 la posizione di $n$ si limita a 3 casi: angolo, bordo e centro. E nei casi "angolo" e "bordo" fissare la posizione significa già escludere rotazioni e alcune simmetrie.
In particolare:
- fissare $n$ nell'angolo in alto a sinistra significa escludere tutte le rotazioni e le simmetrie eccetto quella rispetto alla diagonale principale;
- fissare $n$ nel bordo in alto significa escludere tutte le rotazioni e le simmetrie eccetto quella rispetto all'asse verticale.
Per escludere anche queste, oltre alle rotazioni e simmetrie nel caso di $n$ centrale, ho poi imposto delle condizioni sulle variabili $i_1$, $j_1$ e $i_2$, $j_2$.

"Umby":Le regole del quadrato:

- le 9 caselle vanno compilate con numeri da 1 a 99 (anzi 96 [1-2-96]), lo ZERO è escluso, giusto ?
- la somma delle 3 righe, delle 3 colonne, delle 2 diagonali, deve essere 99. Giusto ?
- i 9 numeri non si possono ripetere. Giusto ?

Dimentico qualcosa ?
(a parte il "12" che nel ns. gioco deve essere presente ...)

Tutto giusto, ovviamente!
Ipotizzo che con questo post tu mi stia chiedendo in che modo l'algoritmo che ho implementato sfrutti queste regole base dei quadrati magici, giusto?

[Umby2]

"Super Squirrel":
Tutto giusto, ovviamente!
Ipotizzo che con questo post tu mi stia chiedendo in che modo l'algoritmo che ho implementato sfrutti queste regole base dei quadrati magici, giusto?

No,
chiedevo perchè avevo intenzione di scrivere qualche riga di codice,
e confrontarmi con la tua soluzione, e volevo essere sicuro delle "regole del gioco".

In effetti, per ogni variante della tua soluzione, hai più "quadrati magici",
ma non hai detto quanti (in totale)

Ho fatto una prima elaborazione, ed il mio risultato è diverso dal tuo
(ma intendo controllare l'output, visto che l'ho scritto su due piedi).

[axpgn]

I quadrati magici esistono da millenni e ci sono alcune regole base ma esistono miriadi di varianti, quindi dipende da quale scegli

Battute a parte, in questo caso è come hai detto: i numeri devono essere interi positivi; ogni riga, ogni colonna e le due diagonali principali devono sommare $99$; in più uno dei nove numeri deve essere il $12$.

Come ho già detto, ci "sarebbero" duecento quadrati magici diversi che rispettano queste condizioni; per "diversi" si intende che se li sovrapponi esattamente, non ce ne saranno due uguali.
Però, è consuetudine considerare "diversi" solo quelli che NON si ottengono dagli altri per rotazioni o riflessioni.
E questi dovrebbero essere solo $25$


Cordialmente, Alex

[Umby2]

Concordo con le 200 soluzioni possibili,

il "12" sarà presente in questo modo:

[Umby2]

"Super Squirrel":

Questo l'output per il caso in esame:

Ci sarà qualche errorino nel tuo codice,

ad esempio:
la soluzione: [44-43-12-01-33-65-54-23-22],

non mi sembra di vederla (la num. 25 è simile, ma non uguale...)

[Super Squirrel]

"Umby":In effetti, per ogni variante della tua soluzione, hai più "quadrati magici",
ma non hai detto quanti (in totale)

Non sono sicuro di aver capito cosa intendi, in ogni caso nel precedente post ho scritto:

"Super Squirrel":ho fissato la posizione di n (pari a 12 nel caso specifico) per evitare di considerare più volte la stessa soluzione, ossia quelle 7 soluzioni ricavabili da quella "originale" attraverso rotazioni o simmetrie.

In pratica da ogni soluzione se ne possono ricavare altre 7, di cui 3 attraverso rotazioni di 90°, 180°, 270° e 4 attraverso riflessioni rispetto ad asse orizzontale, asse verticale, diagonale principale, diagonale secondaria.

"Umby":Ci sarà qualche errorino nel tuo codice,

ad esempio:
la soluzione: [44-43-12-01-33-65-54-23-22],

non mi sembra di vederla (la num. 25 è simile, ma non uguale...)

La numero 1, rotazione antioraria di 90°.

[axpgn]

@Umby
Scusami ma non mi sembra che hai letto tutti i post, perché le risposte alle tue domande le avresti già trovate ... IMHO

Cordialmente, Alex

[Umby2]

"Super Squirrel":
La numero 1, rotazione antioraria di 90°.

p.s. per soluzioni totali, intendevo il 200.