Backtracking effizienter machen?

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Backtracking effizienter machen?

    Hallo,
    ich habe versucht mithilfe von Backtracking ein Magisches Quadrat der Größe n zu erstellen.
    Bei n=3 funktioniert das auch wunderbar, nur für größere n ergeben sich riesige Laufzeiten.
    Kann man die Funktion noch effizienter machen oder mache ich einen grundsätzlichen Denkfehler?

    Hier mal die Kernfunktion meines Programms:

    Quellcode

    1. void findeLoesung (int Stufe,int* Feld,int* Wahl)
    2. {
    3. int i=0;
    4. while(Fertig==0)
    5. {
    6. Feld[Stufe]=Wahl[i];
    7. if (Gueltig(Feld)==1)
    8. {
    9. if (Stufe+1==Groesse*Groesse)
    10. {
    11. if (Gueltig2(Feld)==1)
    12. {
    13. Fertig=1;
    14. printf("QQÖÖQ\n");
    15. return;
    16. }
    17. else
    18. {
    19. Feld[Stufe]=0;
    20. }
    21. }
    22. else
    23. {
    24. findeLoesung(Stufe+1,Feld,Wahl);
    25. }
    26. }
    27. else
    28. {
    29. Feld[Stufe]=0;
    30. }
    31. if (i<Groesse*Groesse-1)
    32. {
    33. i++;
    34. }
    35. else
    36. {
    37. return;
    38. }
    39. }
    40. }
    Alles anzeigen