[alg] magisch vierkant oplossen

[AtlonXP1800]

Ik probeer via java onderstaand magisch vierkant op te lossen:

x	51	x	x	x
x	x	x	x	x
x	x	x	63	x
x	x	x	x	39
15	x	69	x	x

Het oplossen moet gebeuren door getallen in te voeren uit de volgende getallenreeks:
3,6,9,12,18,21,24,27,30,33,36,42,45,48,54,57,60,66,72,74

De bedoeling van het vierkant is dat er op elke manier 195 uit komt, als je het horizontaal, verticaal, diagonaal of gebroken diagonaal optelt.

ik heb getracht dit in java op te lossen:

code:

public class Magic {    
    public static void main(String[] args) {         
    int hor1 = 0;
    int hor2 = 0;
    int hor3 = 0;
    int hor4 = 0;
    int hor5 = 0;
    int ver1 = 0;
    int ver2 = 0;
    int ver3 = 0;
    int ver4 = 0;
    int ver5 = 0;
    int dia1 = 0;
    int dia2 = 0;
        
    int gebdia1 = 0;
    int gebdia2 = 0;
    int gebdia3 = 0;
    int gebdia4 = 0;
        
    int gebdia5 = 0;
    int gebdia6 = 0;
    int gebdia7 = 0;
    int gebdia8 = 0;
    
    
    int x = 0;
    int[][] magic = null;
    
    while((hor1 != 195) || (hor2 !=195) || (hor3 !=195) || (hor4 !=195) || (hor5 !=195)
       || (ver1 != 195) || (ver2 !=195) || (ver3 !=195) || (ver4 !=195) || (ver5 !=195)
       || (dia1 != 195) || (dia2 !=195) 
       || (gebdia1 !=195) || (gebdia2 !=195) || (gebdia3 !=195) || (gebdia4 !=195)
       || (gebdia5 !=195) || (gebdia6 !=195) || (gebdia7 !=195) || (gebdia8 !=195)){
        x++;
        int[] getallen = {3,6,9,12,18,21,24,27,30,33,36,42,45,48,54,57,60,66,72,74};
        magic = new int[5][5];
        
        
        magic[0][1] = 51;
        magic[2][3] = 63;
        magic[3][4] = 39;
        magic[4][0] = 15;
        magic[4][2] = 69;
    
        for (int ver = 0;ver <5;ver++){
            for(int hor = 0;hor<5;hor++){
                if (magic[ver][hor] == 0){
                    int rand = (int)(20 * Math.random());
                    while (getallen[rand] == 0)
                        rand = (int)(20 * Math.random());
                if (getallen[rand] != 0){
                    magic[ver][hor] =  getallen[rand];
                    getallen[rand] = 0;}
        }}}
        if ((x % 100000) == 0)
            System.out.print(".");
        if ((x % 1000000) == 0)
            System.out.print(x/1000000);
    
        hor1 = magic[0][0] + magic[0][1] +magic[0][2] +magic[0][3] +magic[0][4];
        hor2 = magic[1][0] + magic[1][1] +magic[1][2] +magic[1][3] +magic[1][4];
        hor3 = magic[2][0] + magic[2][1] +magic[2][2] +magic[2][3] +magic[2][4];
        hor4 = magic[3][0] + magic[3][1] +magic[3][2] +magic[3][3] +magic[3][4];
        hor5 = magic[4][0] + magic[4][1] +magic[4][2] +magic[4][3] +magic[4][4];
        
        ver1 = magic[0][0] + magic[1][0] +magic[2][0] +magic[3][0] +magic[4][0];
        ver2 = magic[0][1] + magic[1][1] +magic[2][1] +magic[3][1] +magic[4][1];
        ver3 = magic[0][2] + magic[1][2] +magic[2][2] +magic[3][2] +magic[4][2];
        ver4 = magic[0][3] + magic[1][3] +magic[2][3] +magic[3][3] +magic[4][3];
        ver5 = magic[0][4] + magic[1][4] +magic[2][4] +magic[3][4] +magic[4][4];
        
        dia1 = magic[0][0] + magic[1][1] +magic[2][2] +magic[3][3] +magic[4][4];
        dia2 = magic[0][4] + magic[1][3] +magic[2][2] +magic[3][1] +magic[4][0];
        
        gebdia1 = magic[0][1] + magic[1][2] +magic[2][3] +magic[3][4] +magic[0][4];
        gebdia2 = magic[0][2] + magic[1][3] +magic[2][4] +magic[3][0] +magic[4][1];
        gebdia3 = magic[0][3] + magic[1][4] +magic[0][2] +magic[1][3] +magic[1][4];
        gebdia4 = magic[0][4] + magic[1][0] +magic[2][1] +magic[3][2] +magic[4][3];
        
        gebdia5 = magic[0][0] + magic[1][4] +magic[2][3] +magic[3][2] +magic[4][1];
        gebdia6 = magic[0][1] + magic[1][0] +magic[2][4] +magic[3][3] +magic[4][2];
        gebdia7 = magic[0][2] + magic[1][1] +magic[2][0] +magic[3][4] +magic[4][3];
        gebdia8 = magic[0][3] + magic[1][2] +magic[2][1] +magic[3][0] +magic[4][4];
        
                
        }   
                
                
                for (int i = 0; i < 5; i++) { 
                for (int j = 0; j < 5; j++) {
                    if (magic[i][j] < 10)  System.out.print(" ");  // for alignment
                    if (magic[i][j] < 100) System.out.print(" ");  // for alignment
                System.out.print(magic[i][j] + " ");            }
                System.out.println();}
                                
                System.out.println("\nhor1: " + hor1);
                System.out.println("hor2: " + hor2);
                System.out.println("hor3: " + hor3);
                System.out.println("hor4: " + hor4);
                System.out.println("hor5: "+ hor5);
                System.out.println("ver1: " +ver1);
                System.out.println("ver2: "+ ver2 );
                System.out.println("ver3: " +ver3);
                System.out.println("ver4: " + ver4);
                System.out.println("ver5: " + ver5);
                
                }
}

Nu is dit volgens mij een veel te omslachtige manier, en moet het veel beter kunnen.
Ik pak nu random een getal uit de reeks, en stop die ergens in het vierkant. Als het vierkant vol zit check ik of het het gezochte vierkant is, zoniet, dan wordt het nog een keer opnieuw gedaan.

Deze manier kost heel veel tijd, en het is niet zeker of ooit wel het gezochte vierkant er uit komt.
Ook kan het voorkomen dat een vierkant meerdere keren langs komt, wat ook niet echt wensbaar is.

Weet iemand of er een betere manier is om dit te doen? of bestaat er een algoritme voor?

[El_kingo]

Ja er is een beter manier om dat te doen, en ja er zullen vast en zeker algoritmes voor bestaan.
Echter, heb jezelf nagedacht over een betere manier?
Zo ja hoe denk jij dat het sneller kan?

een paar hints:
waarom pak je random een getal uit de reeks? is dat nodig?
Je geeft zelf al aan dat een vierkant meerdere keren kan voorkomen, hoe is dit te voorkomen?
Waarom check je pas als het hele vierkant vol is?

[Janoz]

Om er zeker van te zijn dat je het antwoord vind lijkt het me handiger om alle mogelijkheden bij langs te gaan. Kies eerst de eerste en probeer daarna de tweede enz enz. Dat werkt iig al een stuk beter dan random.

Vervolgens kun je gaan kijken of je misschien al voordat je het hele vlak gevuld hebt kunt zien of het een onjuizte oplossing is. Dan kun je die branch immers al gewoon stoppen.

[sjroorda]

Kijk eens naar het backtracking algoritme, samen met de bovengenoemde oplossingen

[ Voor 33% gewijzigd door sjroorda op 01-08-2005 15:32 . Reden: URL'etje toegevoegd ]

[Verwijderd]

Een mmoi voorbeeld van dit vierkant is gemaakt door de Duitse schilder Durer in een koper gravure genaamd Melancholia.

[AtlonXP1800]

Ik had er ook eerst over zitten denken om alle mogelijkheden af te gaan, maar ik kan er niet helemaal uit komen hoe ik dat zou moeten aanpakken. Er zijn erg veel oplossingen (25^25), hoe kan je die systematisch langsgaan?

Ik heb voor random gekozen omdat dat een makkelijkere oplossing was om te maken (maar geen goede dus)

[sjroorda]

AtlonXP1800 schreef op maandag 01 augustus 2005 @ 16:45:Er zijn erg veel oplossingen (25^25)

Nee hoor, er zijn er slechts 25! (faculteit dus)

[AtlonXP1800]

sjroorda schreef op maandag 01 augustus 2005 @ 16:51:
[...]

Nee hoor, er zijn er slechts 25! (faculteit dus)

ok, dat sheelt al heet wat, maar 't blijven toch heel wat berekeningen

[Dido]

sjroorda schreef op maandag 01 augustus 2005 @ 16:51:
[...]

Nee hoor, er zijn er slechts 25! (faculteit dus)

Sterker nog, je kunt maar 20 getallen invullen (5 zijn er gegeven), dus zijn het er 20!
Scheelt toch een factor 6375600

Maar goed, als je bijvoorbeeld eens begint met de onderste regel: daar zijn 20*19*18 mogelijkheden voor, waarvan de allermeeste afvallen (geen 195 als horizontale som). Effectief kune je voor iedere mogelijkheid van drie getallen die daar niet kan staan 17! mogelijkheden wegstrepen (immers, de 17! mogelijkheden voor de overige vier rijen hoef je niet meer te checken: als de onderste rij niet klopt klopt je hele vierkant al niet.)

[ Voor 43% gewijzigd door Dido op 01-08-2005 16:59 ]

[Janoz]

Verschil tussen de 'alles bij langs gaan ' en de 'random wat proberen' oplossing is, aangenomen dat er 1 juiste is, dat bij de eerste optie de kans op een juiste steeds groter wordt todat deze gevonden is, terwijl hij voor de tweede optie altijd 1/(20!) blijft.

Om alle mogelijke volgordes van die 20 cijfers te krijgen kun je kijken naar permutaties.

[.oisyn]

Nee, je hebt niet 25^25 maar 20! mogelijkheden (geen oplossingen ) om je getalletjes te plaatsen, maar dat zou betekenen dat je eerst alle getallen gaat zetten en daarna pas gaat kijken of iets klopt. Het is handiger om je probleem op te delen in deelproblemen. Een enkele rij hoeft immers maar 195 op te tellen, je zou dus kunnen beginnen met de eerste rij en een nog volle lijst van getallen waar je uit kunt kiezen. Dan initialiseer je 3 pointers naar elementen uit de lijst voor de 3 getallen die je kiest; 1 weet je er al en de laatste is impliciet. De 3 pointers mogen uiteraard niet naar hetzelfde element wijzen. Je begint gewoon met de eerste 3 elementen in de lijst, en je verschuift de 3e pointer steeds naar achteren. Als hij niet verder kan zet je de 2e één verder, en de 3e één na de 2e, en ga je weer verder met verschuiven van de 3e. Als de 2e nu ook achteraan is (oftewel de een-na-laaste, omdat de 3e al achteraan staat) ga je de 1e verschuiven.

Dit doe je tot je voor één rij een mogelijke oplossing hebt. Nu kopieer je de lijst en haal je de al gebruikte getallen weg, en doe je hetzelfde voor de 2e rij. Weer kopieren en verwijderen van de gebruikte getallen, en verder met de 3e. Dit tot je ze alle 5 hebt gehad, en dan kun je de rest van de constraints testen (horizontaal en diagonaal controleren). Net zo lang tot je een oplossing hebt. Bedenk dat als je bij een willekeurige rij geen 195 meer kunt maken, je voor de vorige rij een nieuwe oplossing moet zoeken en dus meteen kunt stoppen met de huidige en degenen die erna komen.

Dit is een basis brute force algoritme wat je gegarandeerd een oplossing zal geven als die bestaat, hij zal alleen nog niet zo heel snel gaan. Door je getallen slim te kiezen kun je ervoor zorgen dat je begint met mogelijk goede oplossingen, en met wat verdere aannames kun je al snel bepalen dat de huidige poging niet tot het juiste resultaat zal leiden waardoor je hem vroegtijdig af kunt breken. Hoe dat te implementeren laat in aan jouw fantasie over

[Daos]

Je kan nooit een oplossing vinden. Het moet namelijk geen 74 maar 75 zijn.

[Pooh]

Met backtracking kom je er ook wel. Zoveel mogelijkheden zijn 't nou ook niet, en je kunt tijdens 't opbouwen continu controleren of je op de goede weg zit.

In pseudocode:

code:

bool correct(vierkant) {
    for every column and row
         if (filled and sum != 195) return false;
         else return true;
}

bool solve(array vierkant, array getallen) {
     if (not correct(vierkant)) return false;

     find first empty spot;
     if (no empty spot) solution = vierkant; //solution found!

     for (every number in getallen) {
          insert number in vierkant;
          extract number from getallen;
          if solve(vierkant, getallen) return true;
          remove number from vierkant; //mark spot empty again;
     }

     return false; //no solution at all
}

[ Voor 26% gewijzigd door Pooh op 01-08-2005 17:33 ]

[Daos]

Bij de oneven vierkanten (die ik ken) zit er een simpel partoon in:

a	b	c	d	e
e	a	b	c	d
d	e	a	b	c
c	d	e	a	b
b	c	d	e	a

Bij elke letter komt {1,2,3,4,5} of {6,7,8,9,10} of {11,..,15}. Volgorde staat vast. Het begin en de richting van de getallen niet. De richting is bij alle letters hetzelfde. Het begin is in dezelfde rij, kolom of diagonaal.

[edit]
Hmmm... Bij het vierkant in dit topic is dit niet zo. 63 (3 * 21) en 69 (3 * 23) staan niet bij elkaar zoals boven beschreven.

[edit2]
Ik ken ook geen vierkanten waarvan de gebroken diagonaal constant is. Waar heb je dat vierkant vandaan?

[edit3]
Ik denk dat dit vierkant bedoeld wordt. Alleen rijen en kolommen constant (69 staat ergens anders):

72	51	45	24	3
54	33	27	6	75
36	30	9	63	57
18	12	66	60	39
15	69	48	42	21

[ Voor 57% gewijzigd door Daos op 01-08-2005 18:25 ]

[AtlonXP1800]

Janoz schreef op maandag 01 augustus 2005 @ 16:57:
Om alle mogelijke volgordes van die 20 cijfers te krijgen kun je kijken naar permutaties.

Gisteravond eens even bezig geweest, toch weer tegen een probleem op gelopen.
Met een stuk java code is het mogelijk om van een reeks getallen alle permutaties te genereren.
Probleem is alleen dat dit met een getallenreeks van 20 getallen 2,432,902,008,176,640,000. uitkomsten zal geven. maw, alleen het genereren van die verschillende reeksen zal al zeer lang gaan duren (mijn computer was er na 3 uur nog niet klaar mee)

Ik heb het idee dat ik toch eerder moet gaan denken aan een oplossing zoals die van daos. (je had inderdaad gelijk dat er een 75 in moest zitten ipv 74, typfout, mijn excuses)

[Daos]

Je kan ook lineaire algebra gebruiken om het probleem te vereenvoudigen.

Voorbeeldje: Een 3x3 magisch vierkant met constante rij, kolom en diagonaal. Getalletjes van 1 tot en met 9.
De coordinaten van dit vierkant noem ik voor het gemak zo:

code:

x11 x12 x13
x21 x22 x23
x31 x32 x33

Per rij komt er (1 + 2 ... + 9) / 3 = 15 uit. De vergelijkingen worden:

code:

x11 + x12 + x13 =  15
x21 + x22 + x23 =  15
x31 + x32 + x33 =  15

x11 + x21 + x31 =  15
x12 + x22 + x32 =  15
x13 + x23 + x33 =  15

x11 + x22 + x33 =  15
x13 + x22 + x31 =  15

In een matrix ziet het er zo uit:

code:

  1   1   1                         |  15
              1   1   1             |  15
                          1   1   1 |  15
  1           1           1         |  15
      1           1           1     |  15
          1           1           1 |  15
  1               1               1 |  15
          1       1       1         |  15

Door een veelvoud van een rij bij een andere op te tellen kan je zo'n figuurtje maken (linkje):

code:

  1                               1 |  10
      1                       1     |  10
          1                  -1  -1 | - 5
              1              -1  -2 | -10
                  1                 |   5
                      1       1   2 |  20
                          1   1   1 |  15
                                    |   0

Uit dat figuur krijg je deze vergelijkingen:

code:

x11 =  10 +          -1*x33
x12 =  10 + -1*x32         
x13 = - 5 +  1*x32 +  1*x33
x21 = -10 +  1*x32 +  2*x33
x22 =   5
x23 =  20 + -1*x32 + -2*x33
x31 =  15 + -1*x32 + -1*x33
x32 =        1*x32
x33 =                 1*x33

Er zijn dus twee variabelen vrij te kiezen. Dat geeft 9 * 8 = 72 keer proberen en je krijgt elk magisch 3x3 vierkant. Dat is een stuk beter dan de 9! = 362880.

Bij 5x5 heb je voor een normaal magisch vierkant 12 vergelijkingen en 25 variabelen. Er zijn dus 13 (of meer) variabelen vrij te kiezen. Dit geeft in het gunstigste geval 25! / 12! = 3.2 * 10¹⁶ mogelijkheden die je moet proberen om elk vierkant te vinden.
Als er al 5 getallen gegeven zijn, dan zijn er nog maar 25! / 17! = 4.4 * 10¹⁰ mogelijkheden over. Het vierkant in dit topic heeft waarschijnlijk alleen constante rijen en kolommen. Dat geeft 25! / 15! = 1.2 * 10¹³ keer proberen in het gunstigste geval.


Het aantal mogelijkheden zal groter worden als een deel van de vergelijkingen geschreven kan worden als lineaire combinatie van andere vergelijkingen.

[ Voor 4% gewijzigd door Daos op 02-08-2005 11:03 ]

[Pooh]

AtlonXP1800 schreef op dinsdag 02 augustus 2005 @ 09:40:
[...]
Ik heb het idee dat ik toch eerder moet gaan denken aan een oplossing zoals die van daos. (je had inderdaad gelijk dat er een 75 in moest zitten ipv 74, typfout, mijn excuses)

Je moet ze ook niet eerst genereren, maar gewoon 1 voor 1 aflopen. Zie mijn backtracking oplossing. (Dus deeloplossingen creeren, en dan zo vroeg mogelijk wegstrepen)

(Mijn slordige 5-minuten implementatie genereerde in 3 seconden een antwoord, en had daar 28 miljoen stappen voor nodig.)

Edit: excuus, dat was meer geluk dan wijsheid. Werkt alleen als je rechtsonderin begint. Linksboven beginnen duurt een stuk langer. (Dik een kwartier. Levert overigens een andere oplossing. 3 miljard stappen)

[ Voor 24% gewijzigd door Pooh op 02-08-2005 14:28 ]

[Daos]

Een implementatie van mijn laatste idee hierboven beschreven. n is het aantal rijen of kolommen. o is een array met constanten. Het algoritme maakt vergelijkingen voor rijen, kolommen en de twee diagonalen. De waarden die in het vierkant komen te staan zijn uit {1,2,3,..,2*n}.

Java:

public class MagicSolver {
  public static void main(String[] args) {
    boolean br = true;

    int n = 5;

    int o[][] = {
      // {r, c, v}
      {1, 2, 17},
      {3, 4, 21},
      {4, 5, 13},
      {5, 1, 5},
      {5, 3, 23}
    };

    int c = o.length;
    int n2 = n * n;

    int e;
    if (br)
      e = 4 * n + c;
    else
      e = 2 * n + 2 + c;

    int t = n * (n2 + 1) / 2;

    int z[] = new int[e];
    for (int i = 0; i < e; i++)
      z[i] = t;

    int a[][] = new int[e][n2];
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        a[i][n * i + j] = 1;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        a[i + n][i + n * j] = 1;

    for (int i = 0; i < c; i++) {
      a[2 * n + i][o[i][0] * n + o[i][1] - n - 1] = 1;
      z[2 * n + i] = o[i][2];
    }

    if (br) {
      for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
          a[2 * n + c + i][j * n + (i + j) % n] = 1;
      for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
          a[3 * n + c + i][j * n + n - 1 - (i + j) % n] = 1;
    }
    else {
      for (int i = 0; i < n; i++)
        a[2 * n + c][(n + 1) * i] = 1;
      for (int i = 0; i < n; i++)
        a[2 * n + c + 1][(n - 1) * (i + 1)] = 1;
    }


    int totVerg = e;
    int totVar = n2;
    double[][] stelsel = new double[totVerg + 1][totVar + 1];
    for (int i = totVerg; i > 0; i--) {
      for (int j = totVar; j > 0; j--)
        stelsel[i][j] = a[i - 1][j - 1];
      stelsel[i][0] = z[i - 1];
    }

    Vegen.echelon(stelsel, totVerg, totVar);
    Vegen.geredEchelon(stelsel, totVerg, totVar);


    int q = 0;
    //d = column, f = row
    for (int d = 1, f = 1; d <= n2 && f <= e; d++, f++)
      while (d <= n2 && stelsel[f][d] != 1.0) {
        q++;
        d++;
      }
    int y = q;

    System.out.println(y + " variabele(n) vrij te kiezen...");

    double b[] = new double[n2];
    for (int i = 0; i < e && i < n2; i++)
      b[i] = stelsel[i + 1][0];

    double s[][] = new double[y][n2];

    q = 0;
    for (int d = 1, f = 1; d <= n2 && f <= e; d++, f++)
      while (d <= n2 && stelsel[f][d] != 1.0) {
        for (int i = 0; i < e && i < n2; i++)
          s[q][i] = -(int)Math.round(stelsel[i + 1][d]);
        q++;
        d++;
      }

    q = 0;
    for (int d = 1, f = 1; d <= n2 && f <= e; d++, f++)
      while (d <= n2 && stelsel[f][d] != 1.0) {
        for (int i = 0 ; i < y; i++) {
          for (int j = n2 - 1 ; j > d - 1; j--)
            s[i][j] = s[i][j - 1];
          if (i == q)
            s[i][d - 1] = 1;
          else
            s[i][d - 1] = 0;
        }
        for (int i = n2 - 1 ; i > d - 1; i--)
          b[i] = b[i - 1];
        b[d - 1] = 0;
        q++;
        d++;
      }

    int v[] = new int[y];
    for (int i = 0; i < y; i++)
      v[i] = 1;

    double r[] = new double[n2];

    boolean u[];

    while (true) {
      int h = y - 1;
      boolean i = true;
      while(i) {
        v[h]++;
        if (v[h] > n2) {
          v[h] = 1;
          h--;
          if (h < 0) break;
        }
        else {
          u = new boolean[n2];
          for (int j = 0; j < c; j++)
            u[o[j][2] - 1] = true;

          i = false;
          for (int j = 0; j < y; j++)
            if (u[v[j] - 1]) {
              i = true;
              h = j;
            }
            else
              u[v[j] - 1] = true;
        }
      }
      if (h < 0) break;

      for (int j = 0; j < n2; j++)
        r[j] = b[j];

      for (int j = 0; j < y; j++)
        for (int k = 0; k < n2; k++)
          r[k] += s[j][k] * v[j];

      u = new boolean[n2];
      boolean p = true;
      for (int j = 0; j < n2 && p; j++) {
        int w = (int)Math.round(r[j]);
        if (w < 1 || w > n2 || u[w - 1])
          p = false;
        else
          u[w - 1] = true;
      }

      if (p) {
        for (int j = 0; j < n2; j++) {
          if (j % n == 0)
            System.out.println();
          System.out.print((int)Math.round(r[j]) + "\t");
        }
        System.out.println();
      }
    }
  }
}

Java:

class Vegen {
  static boolean isNul(double a) {
    return Math.abs(a) < 1E-10;
  }

  static void echelon(double[][] stelsel, int totVerg, int totVar) {
    int verg1 = 1;
    for (int var1 = 1; var1 <= totVar && verg1 <= totVerg; var1++) {
      if (isNul(stelsel[verg1][var1]))
        for (int verg2 = verg1 + 1; verg2 <= totVerg; verg2++)
          if (!isNul(stelsel[verg2][var1])) {
            for (int var2 = 0; var2 <= totVar; var2++) {
              stelsel[0][var2] = stelsel[verg1][var2];        //rijtjes wisselen
              stelsel[verg1][var2] = stelsel[verg2][var2];
              stelsel[verg2][var2] = stelsel[0][var2];
            }
            break;
          }
      if (!isNul(stelsel[verg1][var1])) {
        for (int verg2 = verg1 + 1; verg2 <= totVerg; verg2++) {
            double factor = -stelsel[verg2][var1] / stelsel[verg1][var1];
            for (int var2 = 0; var2 <= totVar; var2++)
              stelsel[verg2][var2] += factor * stelsel[verg1][var2];     //vegen
        }
        verg1++;
      }
    }
  }

  static void geredEchelon(double[][] stelsel, int totVerg, int totVar) {
    for (int verg1 = totVerg; verg1 >= 1; verg1--)
      for (int var1 = 1; var1 <= totVar; var1++) {
        if (!isNul(stelsel[verg1][var1])) {
          double factor = 1 / stelsel[verg1][var1];
          for (int var2 = 0; var2 <= totVar; var2++)
            stelsel[verg1][var2] = factor * stelsel[verg1][var2];//pivot 1 maken

          for (int verg2 = 1; verg2 < verg1; verg2++) {
              factor = -stelsel[verg2][var1];
              for (int var2 = 0; var2 <= totVar; var2++)
                stelsel[verg2][var2] += factor * stelsel[verg1][var2];   //vegen
          }
          break;
        }
      }
  }
}

Met het algoritme kan ik snel een aantal 3x3 en 4x4 magische vierkanten vinden. Bij 5x5 heb ik na een uur nog niets gevonden (14 vrije variabelen). Er zit misschien nog ergens een fout of het komt doordat mijn PC aan vervanging toe is.

[ Voor 33% gewijzigd door Daos op 04-08-2005 15:41 . Reden: bugs verholpen + gebroken diagonalen toegevoegd ]

[zwippie]

@Daos: omdat je volgens je sig over een P200 beschikt heb ik je code ook maar even gedraaid, maar na een klein uurtje stomen heeft mijn XP1800 ook nog geen antwoorden gevonden.

Ik heb alleen n veranderd naar 5, hij maakte er zelf 13 variabelen vrij te kiezen van.

[ Voor 21% gewijzigd door zwippie op 03-08-2005 17:58 ]

[sjroorda]

Houd je er rekening mee dat de topicstarter het over de gebroken diagonalen heeft? Misschien zijn er zelfs geen oplossingen voor 'gewone' diagonalen hier?

[Pooh]

sjroorda schreef op donderdag 04 augustus 2005 @ 08:31:
Houd je er rekening mee dat de topicstarter het over de gebroken diagonalen heeft? Misschien zijn er zelfs geen oplossingen voor 'gewone' diagonalen hier?

Hmm, daar had ik eerst ook overheen gelezen.

Mijn oplossing (helaas voor de TS geen Java)

Die vond na ruim een halfuur op mijn P4 2GHz de volgende oplossing:

code:

24 51  3 45 72
33 75 27 54  6
57  9 36 63 30
66 18 60 12 39
15 42 69 21 48

Na ongeveer 30% van alle mogelijkheden geprobeerd te hebben. 8 miljard, dus interpolatie geeft het totaal aantal te controleren mogelijkheden ongeveer 2.4 * 10¹⁰

C++:

bool correct(int magic[5][5]);

bool solve(int magic[5][5], int seeds[20])
{

//  return when incorrect node
    if(!correct(magic)) return false;

//  try find next empty cell
    int row = -1, col = -1;

    for(int i=0;i<5;i++) {
        for(int j=0;j<5;j++) {
            if (magic[i][j] == 0) {
                row = i;
                col = j;
                break;
            }
        }   
        if (row != -1 && col != -1) break;
    }

//  if no empty cell, solution is found
    if (row == -1 && col == -1) {
        printf("Solution:\n\n");
        for(int i=0;i<5;i++) {
            for(int j=0;j<5;j++) {
                printf("%2d ",magic[i][j]);
            }
            printf("\n");
        }   
        return true;
    }


//  try next number
    for(int q=0;q<20;q++) { 
        
        if (seeds[q] == 0) continue;

        int seed = seeds[q];
        magic[row][col] = seed;
        seeds[q] = 0;

        if (solve(magic,seeds)) return true;
          
        // reset
        magic[row][col] = 0;
        seeds[q] = seed;        
    }

  return false;

} 


bool correct(int magic[5][5])
{
    //rows
    for(int i=0;i<5;i++)
        if ( (magic[0][i] != 0) && 
             (magic[1][i] != 0) &&
             (magic[2][i] != 0) &&
             (magic[3][i] != 0) &&
             (magic[4][i] != 0) &&
             (magic[0][i] + magic[1][i] + magic[2][i] + magic[3][i] + magic[4][i] != 195) ) return false;
//colums
    for(i=0;i<5;i++)
        if ( (magic[i][0] != 0) && 
             (magic[i][1] != 0) &&
             (magic[i][2] != 0) &&
             (magic[i][3] != 0) &&
             (magic[i][4] != 0) &&
             (magic[i][0] + magic[i][1] + magic[i][2] + magic[i][3] + magic[i][4] != 195) ) return false;
    
    int sum = 0;
    bool empty = false;
    int j;

    //broken diagonals 1
    for(i=0;i<5;i++) {
        sum = 0;
        empty = false;
        for(j=0;j<5;j++) {
            if (magic[j][(i+j) % 5] == 0) empty = true;
            else sum += magic[j][(i+j) % 5];            
        }
        if (!empty &&  sum != 195) return false;
    }

    //broken diagonals 2
    for(i=0;i<5;i++) {
        sum = 0;
        empty = false;
        for(j=0;j<5;j++) {
            if (magic[j][4 - ((i+j) % 5)] == 0) empty = true;
            else sum += magic[j][4 - ((i+j) % 5)];          
        }
        if (!empty &&  sum != 195) return false;
    }
    return true;
}


int main(int argc, char* argv[])
{
    int magic[5][5] =   {   { 0,51,0,0,0 } ,
                            { 0,0,0,0,0 } ,
                            { 0,0,0,63,0 } ,
                            { 0,0,0,0,39 } ,
                            { 15,0,69,0,0 } };

    int seeds[20] = {3,6,9,12,18,21,24,27,30,33,36,42,45,48,54,57,60,66,72,75 };

    solve(magic, seeds);

    return 0;
}

[ Voor 4% gewijzigd door Pooh op 04-08-2005 11:12 ]

[.oisyn]

Een diagonaal is toch een subset van de gebroken diagonalen? Of begrijp ik de term gebroken diagonaal verkeerd? Dat is toch gewoon diagonaal met de bekende "wrap-around" die je altijd ziet in spellen; je gaat er aan de linkerkant uit en je komt er aan de rechterkant weer in? Of om het wiskundig te omschrijven: het vierkant is de oppervlakte van een torus (donut)

[Pooh]

.oisyn schreef op donderdag 04 augustus 2005 @ 11:16:
Een diagonaal is toch een subset van de gebroken diagonalen? Of begrijp ik de term gebroken diagonaal verkeerd? Dat is toch gewoon diagonaal met de bekende "wrap-around" die je altijd ziet in spellen; je gaat er aan de linkerkant uit en je komt er aan de rechterkant weer in? Of om het wiskundig te omschrijven: het vierkant is de oppervlakte van een torus (donut)

Hangt een beetje van je definitie af. Sommigen beschouwen gewone diagonalen wellicht niet als 'gebroken'. Gelukkig noemt de TS ze allebei, dus daar kan geen verwarring over bestaan. (Maar je torus-model klopt)

edit: Overigens geeft dat een mooie optimalisatiemogelijkheid. Er zijn immers 25 'verschoven' oplossingen, als je de ingevullen getallen negeert. Eerst de gegeven getallen negeren, en zodra je een oplossing vindt die controleren op de 25 'verschoven' versies van de opgave zou wel eens veel sneller kunnen zijn.

[ Voor 26% gewijzigd door Pooh op 04-08-2005 11:22 ]

[.oisyn]

Pooh: die optimalisatie zou opgaan als je hele vierkant leeg was. Nu zijn er al een aantal getallen ingevuld en valt er dus weinig te schuiven met je mogelijkheden

.edit: ah ok

[ Voor 5% gewijzigd door .oisyn op 04-08-2005 11:41 ]

[Pooh]

.oisyn schreef op donderdag 04 augustus 2005 @ 11:25:
Pooh: die optimalisatie zou opgaan als je hele vierkant leeg was. Nu zijn er al een aantal getallen ingevuld en valt er dus weinig te schuiven met je mogelijkheden

Dat bedoelde ik ook. Je genereert oplossingen in een leeg veld, en verschuift 'm daarna 25 keer om te kijken of hij past op de opgave.

Maar 't is niet efficient, heb ik al wel door. De 5 extra getallen geven meer dan 25 keer zoveel mogelijkheden om te controleren. (Bij benadering: 2.4 * 10¹⁰ voor 20 mogelijkheden, is 2.4 * 10¹⁰ ^ (1/20) = 3.30 zoveel mogelijkheden per getal. 3.30⁵ > 25 )

[ Voor 6% gewijzigd door Pooh op 04-08-2005 11:41 ]

[Daos]

Ik heb bij mijn algoritme (zie eerder bericht) ook de gebroken diagonalen toegevoegd. Samen met de vijf gegeven waarden blijven er maar 3 variabelen over. Na ongeveer 7 duizend iteraties is de oplossing gevonden.

Het vinden van de oplossing kan volgens mij nog veel sneller. De uitkomsten van de eerste twee iteraties zijn:

code:

-10  17 -20  36  42
 11  46   9   5  -6
 24 -18  25  21  13
 35 -12  28   1  13
  5  32  23   2   3

code:

 -9  17 -19  35  41
 11  45   9   6  -6
 24 -17  24  21  13
 34 -11  28   1  13
  5  31  23   2   4

Veel getallen vallen buiten de 1 tot en met 25 en veranderen niet zo snel. Volgens mij kan je wel voorspellen wanneer alles tussen de 1 en 25 komt. Er hoeft dan alleen nog gekeken te worden of er niets dubbel is.
Ik ga dat een keer proberen te implementeren als ik wat meer tijd heb. Ik hoop dat ik dan nog weet wat mijn algoritme doet, want het is niet bepaald het mooiste wat ik ooit geproduceerd heb.

[Pooh]

Daos schreef op donderdag 04 augustus 2005 @ 16:51:
Veel getallen vallen buiten de 1 tot en met 25 en veranderen niet zo snel. Volgens mij kan je wel voorspellen wanneer alles tussen de 1 en 25 komt. Er hoeft dan alleen nog gekeken te worden of er niets dubbel is.

De getallen moeten niet tussen de 1 en 25 liggen, maar zoals in de topicstart staat: Het oplossen moet gebeuren door getallen in te voeren uit de volgende getallenreeks: 3,6,9,12,18,21,24,27,30,33,36,42,45,48,54,57,60,66,72,74

Overigens is een leuke extra eigenschap van de oplossing dat de som van een cel met zijn directe buren (links,rechts,boven,onder) ook 195 is, net als de som van een cel met zijn diagonaal-aangrenzende cellen.

[ Voor 33% gewijzigd door Pooh op 04-08-2005 18:05 ]

[Daos]

Pooh schreef op donderdag 04 augustus 2005 @ 17:56:
[...]


De getallen moeten niet tussen de 1 en 25 liggen, maar zoals in de topicstart staat: Het oplossen moet gebeuren door getallen in te voeren uit de volgende getallenreeks: 3,6,9,12,18,21,24,27,30,33,36,42,45,48,54,57,60,66,72,74

Die 74 moet 75 worden. je krijgt dan 3 * (1,2,3,4,6,7,8,9 .. 24, 25). De vijf gegeven waarden heb ik moeten delen door 3. 51 / 3 = 17, 63 / 3 = 21 etc..

Overigens is een leuke extra eigenschap van de oplossing dat de som van een cel met zijn directe buren (links,rechts,boven,onder) ook 195 is, net als de som van een cel met zijn diagonaal-aangrenzende cellen.

Misschien alleen bij oneven vierkanten.

code:

3   16  9   6   
10  5   4   15  
8   11  14  1   
13  2   7   12

[edit]
Bij die 4x4 is het weer zo dat elk 2x2 vierkantje ook 34 is.

[ Voor 4% gewijzigd door Daos op 04-08-2005 19:03 ]

[Tomatoman]

In Delphi heb ik eens een programma geschreven dat een vrijwel identiek probleem oplost. Het probleem was in mijn geval een n x n matrix, waarbij n meestal 5 was, waarin de getallen 0 t/m 9 moesten worden ingevuld. Per rij en kolom mocht een getal hooguit één keer voorkomen. De totalen van alle rijen, kolommen en de beide diagonalen was al ingevuld, evenals een paar getallen.

In principe is dit hetzelfde probleem, zij het dat de in te vullen getallen niet 0 t/m 9 zijn, maar een rijtje andere getallen. Ook mag een getal maar één keer voorkomen in de gehele matrix.

De oplossing die ik heb gebruikt en die prima werkte was een iteratieve benadering, gevolgd door brute force.

1. Per matrixcel wordt een array bijgehouden van alle toegestane waarden voor die cel. In het begin zijn dat natuurlijk alle in te vullen waarden voor de hele array. Op basis van logica zijn er vervolgens voor iedere cel een aantal mogelijkheden uit de array te schrappen. Wordt bijvoorbeeld het getal 33 in een bepaalde cel ingevuld, dan wordt de array voor die cel beperkt tot één waarde (namelijk 33) en wordt in alle andere cellen de waarde 33 uit de array geschrapt (want deze mogelijkheid is nu uitgesloten voor alle andere cellen). Niet vergeten: bij matrixcel (x, y) is x de kolomwaarde en y de rijwaarde, dus niet andersom.
2. Als eerste vul je voor iedere cel de matrix met mogelijkheden m alle getallen, in jouw geval 3,6,9,12,18,21,24,27,30,33,36,42,45,48,54,57,60,66,72,74. Uitzonderingen zijn de cellen waarvan het getal al ingevuld is, daar vul je de array met maar één getal, namelijk de vooraf ingevulde waarde.
3. Als tweede vul je voor alle rijen, kolommen en diagonalen het totaal in.
4. Nu het idee achter het iteratieve proces. De bedoeling is om zo veel mogelijk waarden per cel uit te sluiten, zodat er zo min mogelijk mogelijkheden overblijven. Stel dat er in cel (x, y) n_{x, y} mogelijkheden overblijven. Het totale aantal mogelijkheden is dan:
   n_0,0 · n_1,0 · ... · n_{kolommen-1,rijen-1}. In theorie is het aantal mogelijkheden zelfs na de iteratiestappen dusdanig groot dat brute force geen zin heeft. In de praktijk zijn de magische vierkanten altijd dusdanig ingericht dat na de iteratiestappen meestal slechts enige miljoenen tot miljarden mogelijkheden overblijven, want anders zijn ze door een mens niet op te lossen. Met brute force ben je dan heel snel klaar.
5. Dan het iteratieve proces zelf.
   
   Voor cel (0, 0) zijn de aanvankelijke mogelijkheden: 3,6,9,12,18,21,24,27,30,33,36,42,45,48,54,57,60,66,72,74. De minimale waarde is wellicht echter groter dan 3. Het totaal van de eerste rij moet 195 zijn. De waarde van cel (1,0) is 51 en de waarden voor cel (2,0), (3, 0) en (4, 0) zijn maximaal 74, 72 en 66 – dat is voor de cellen de hoogste waarde in hun array met mogelijkheden. Dat betekent dat de minimale waarde voor cel (0, 0) is: 195 - 51 - 74 - 72 - 66 = -68. Helaas, dat sluit nog steeds geen mogelijkheden uit.
   
   
   
   Nu de maximale waarde voor cel (0, 0). De minimale waardes voor de andere cellen in de eerste rij zijn: 51, 3, 6 en 9. Dat betekent dat de maximale waarde voor (0, 0) is: 195 - 51 - 3 - 6 - 9 = 126. Helaas, deze waarde sluit nog steeds geen mogelijkheden uit.
   
   
   
   Het zal echter blijken dat er rijen, kolommen of diagonalen zijn waarbij er wel degelijk mogelijkheden worden uitgesloten. Daartoe ga je consequent voor iedere cel de bijbehorende rij, kolom en diagonaal af en sluit je zo veel mogelijk waarden voor die cel uit. Als er voor een cel mogelijkheden afvallen, zullen er ook andere cellen waarvoor het aantal mogelijkheden kan wijzigen. Daarom moet je als je alle cellen doorlopen hebt het hele proces herhalen, net zolang tot er geen enkele cel meer wijzigt (vandaar dat het iteratief is).
6. Nu je het aantal mogelijkheden voor iedere cel hebt gereduceerd, kun je verder. Ga met brute force alle combinaties van celwaarden af, net zolang tot je een oplossing hebt gevonden.

Er zijn op deze aanpak nog wat verfijningen mogelijk. Zo zijn er nog meer mogelijkheden om mogelijke waarden voor cellen uit te sluiten, bijvoorbeeld door te kijken of een celwaarde even of oneven moet zijn. Ook kun je telkens als er een celwaarde is gevonden het iteratieve deel opnieuw doorlopen, dat versnelt het zoeken.