Backtracking

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

  • du meinst Beispiele für den Backtracking Algorithmus.

    Also ich hab mittels Backtracking noch zusätzlich Sudoku und das Nikolaushaus implementiert

    Wikipedia hat diese Beispiele:
    Damenproblem
    Gegeben ist ein Schachbrett mit n*n Feldern (je n Spalten und Reihen). Man positioniere nun n Damen so, dass sie sich nicht gegenseitig schlagen können.

    Springerproblem
    Gegeben ist ein „Schachbrett“ mit m\times n Feldern. Ein Springer kann von einer bestimmten Position aus N = 8 verschiedene Sprünge ausführen, falls diese nicht über den Rand des Brettes hinausführen. Gesucht ist ein Weg, bei dem alle Felder genau einmal besucht werden (Springerweg). Mit Hilfe von Backtracking können alle möglichen Wege systematisch durchprobiert werden. Ein Zug ist dabei gültig, wenn das neue Feld innerhalb des Spielfeldes liegt und noch unbesucht ist. Es gibt jedoch weitaus effizientere Verfahren für die Lösung dieses Problems. Siehe Programmbeispiel (Java-Applet) weiter unten.

    Rucksackproblem
    Gegeben ist ein Rucksack mit der Tragfähigkeit B. Weiterhin sind N Gegenstände mit Werten und Gewichten gegeben. Nun sollen Gegenstände so ausgewählt werden, die in der Summe einen maximalen Wert ergeben, aber deren Gesamtgewicht die Tragfähigkeit des Rucksacks nicht überschreitet.

    Färbe-/ Kartenproblem
    Gegeben ist eine Landkarte mit B Ländern, welche mit N verschiedenen Farben eingefärbt werden sollen. Gesucht ist eine Farbkombination, bei welcher alle Länder, die eine gemeinsame Grenze besitzen, unterschiedlich eingefärbt sind.

    Lösungen des Solitär-Brettspiels
    Die Lösungen des bekannten alten Brettspiels können gut mit Backtracking ermittelt werden. Zu Beginn stehen 32 Steine (Stifte oder Kugeln) auf dem Brett; davon werden in 31 Zügen je einer entfernt, indem man ihn mit einem anderen Stein überspringt.

    Wegsuche von A nach B in einem Graph
    Backtracking wird auch eingesetzt für die Wegsuche von A nach B in einem Graph, z.B. für die Suche nach Verbindungen in einem Fahrplan oder zum bestimmen einer Route in einem Routenplaner oder eines Weges durch ein Labyrinth.

  • Ja super vielen Dank

    Dame Springer und Rucksack habe ich fertig ich sitze jetzt seit 2 Tagen in Sudoku und
    möchte mir halt alle möglichen Lösungen ausgeben lassen beid er Dame war das ja nicht das Problem nur hier sehe ich kein Land
    vielleicht habt ihr eine Idee

    Gruß T

    Quellcode

    1. public class Sudo {
    4. public Sudo(int size){
    5. this.size = size;
    6. feld = new int [size][size];
    7. }
    11. public boolean check(int i, int j, int[][] cells){
    13. if (i == 9) {
    14. i = 0;
    15. j++;
    16. if (j == 9){
    17. writeMatrix();
    18. reset();
    19. return true;
    20. }
    22. }
    23. if (cells[i][j] != 0){
    24. return check(i+1,j,cells);
    25. }
    26. int val = 1;
    27. for (val = 1; val <= 9; ++val) {
    28. if (legal(i,j,val,cells)) {
    29. cells[i][j] = val;
    30. if (check(i+1,j,cells)){
    31. return true;
    33. }
    34. }
    35. }
    36. cells[i][j] = 0;
    37. return false;
    39. }
    41. private boolean legal(int i,int j,int val,int[][]cells){
    43. //check ob Wert schon vorhanden ist in der Reihe
    44. for (int k = 0; k < size; ++k)
    45. if (val == cells[k][j])
    46. return false;
    48. //check ob Wert schon vorhanden ist in der Spalte
    49. for (int k = 0; k < 9; ++k)
    50. if (val == cells[i][k])
    51. return false;
    53. int boxRowOffset = (i / 3)*3;
    54. int boxColOffset = (j / 3)*3;
    55. for (int k = 0; k < 3; ++k) // box
    56. for (int m = 0; m < 3; ++m)
    57. if (val == cells[boxRowOffset+k][boxColOffset+m])
    58. return false;
    60. return true; // no violations, so it's legal
    62. }
    64. static void writeMatrix() {
    66. for (int i = 0; i < feld.length; i++) {
    67. if(i%3==0){
    68. System.out.println("-------------------------");
    69. }
    70. for (int j = 0; j < feld.length; j++) {
    71. if(j%3==0){
    72. System.out.print("| ");
    73. }
    74. System.out.print(feld[i][j]+" ");
    75. }
    76. System.out.print("|");
    77. System.out.println();
    78. }
    79. System.out.println("-------------------------");
    81. }
    83. void reset() {
    84. for(int y=0;y<feld.length;y++)
    85. for(int x=0;x<feld.length;x++)
    86. feld[x][y]=0;
    88. }
    90. private static int[][]feld;
    91. private int size;
    93. public static void main(String[] args) {
    94. Sudo s = new Sudo(9);
    95. while(s.check(0,0,s.feld)){
    96. }
    97. }
    99. }
    Alles anzeigen