Backtracking kann nicht mit Kreuzungen umgehen
-
Das hier ist keine Hausaufgabe, sondern ein Problem aus der Mittagspause.
Folgende Aufgabe war gestellt: 4 Leute sollen sich ein Land teilen. Jeder soll auf seinem Stück Land ein Haus und ein Brunnen haben. Außerdem sollen die Länder jeweils kongruent sein, also die gleiche Form haben. Die Brunnen und Häuser sind folgendermaßen verteilt:Brun = Brunnen +------+------+------+------+------+------+ | Leer | Leer | Haus | Haus | Leer | Leer | +------+------+------+------+------+------+ | Leer | Leer | Leer | Leer | Brun | Leer | +------+------+------+------+------+------+ | Leer | Leer | Haus | Leer | Brun | Leer | +------+------+------+------+------+------+ | Leer | Leer | Leer | Leer | Leer | Leer | +------+------+------+------+------+------+ | Leer | Leer | Leer | Leer | Leer | Leer | +------+------+------+------+------+------+ | Leer | Brun | Leer | Leer | Brun | Haus | +------+------+------+------+------+------+Jetzt habe ich ein Programm geschrieben, was das Problem löst und das Land aufteilt. Das Problem ist jedoch, daß es nicht mit Kreuzungen umgehen kann, sondern eine unverzweigte Lösung sucht. Die Lösung des Problems hat aber leider eine Kreuzung in der Aufteilung. So muß ich in meinem Lösungsarray die Kreuzung manuell eintragen, damit er die Lösung findet. Ich hab im Moment keine Ahnung, wie ich das Problem ohne das manuelle Eintragen der Kreuzung lösen kann.
Wäre also nett, wenn ihr mir ein Hinweis gebt, wie ich Kreuzungen in meinen Algorithmus kriege. Alternativ könnt ihr natürlich auch komplett andere Lösungsansätze posten.
Hier das Programm: (die Kreuzungen sind jeweils eingetragen in solution[1][1], solution[1][4], solution[4][1] und solution[4][4]. Es soll die Lösung finden auch wenn in diesen Zellen 0 eingetragen ist.)
#include <stdio.h> #include <conio.h> #define LEER '0' #define HAUS 'H' #define BRUNNEN 'B' static char spielfeld[6][6] = { {'0', '0', 'H', 'H', '0', '0'}, {'0', '0', '0', '0', 'B', '0'}, {'0', '0', 'H', '0', 'B', '0'}, {'0', '0', '0', '0', '0', '0'}, {'0', '0', '0', '0', '0', '0'}, {'0', 'B', '0', '0', 'B', 'H'} }; static int solution[6][6] = { // Solution array {0, 0, 0, 0, 0, 0}, // records the steps taken {0, 9, 0, 0,-1, 0}, // and the order of the steps {0, 0, 1,-1, 0, 0}, // by numbers from 1 - 9 {0, 0,-3,-2, 0, 0}, // 1 marks the starting sport {0,-3, 0, 0,-2, 0}, // -1..-3 marks the land of the {0, 0, 0, 0, 0, 0} // "others" }; static int stepX[4] = { 0, 1, 0,-1}; // First search up, then right, static int stepY[4] = {-1, 0, 1, 0}; // then down and then left void PrintSolution(void) { int i, j; for(i = 0; i < 6; i++) { for(j = 0; j < 6; j++) { printf(" %2d", solution[i][j]); } printf("\n"); } } int isSolution(int who) { int i, j; int hasBrunnen = 0, hasHaus = 0; if(who > 0) { for(i = 0; i < 6; i++) for(j = 0; j < 6; j++) if(spielfeld[i][j] == BRUNNEN && solution[i][j] > 0) return 1; } else { for(i = 0; i < 6; i++) for(j = 0; j < 6; j++) { if(spielfeld[i][j] == BRUNNEN && solution[i][j] == who) hasBrunnen = 1; else if(spielfeld[i][j] == HAUS && solution[i][j] == who) hasHaus = 1; if(hasBrunnen && hasHaus) return 1; } } return 0; } int FindSolution(int index, int iX, int iY) { int step = -1; int newX = 0, newY = 0; int isOk = 1; while(step < 4) // There are still directions left { step++; newX = iX + stepX[step]; // New x direction newY = iY + stepY[step]; // New y direction isOk = 1; if(newX < 0 || newX > 5) isOk = 0; // Out of bounds if(newY < 0 || newY > 5) isOk = 0; // Out of bounds if(index > 9) isOk = 0; // Max is 9 steps if(spielfeld[newY][newX] == HAUS) isOk = 0; // Blocked? if(solution[newY][newX] != 0) isOk = 0; // Blocked? if(solution[newX][5-newY] != 0) isOk = 0; // Blocked? if(solution[5-newY][5-newX] != 0) isOk = 0; // Blocked? if(solution[5-newX][newY] != 0) isOk = 0; // Blocked? if(isOk) { solution[newY][newX] = index; solution[newX][5-newY] = -1; // Rotate 90° and set occupied solution[5-newY][5-newX] = -2; // Rotate 180° and set occupied solution[5-newX][newY] = -3; // Rotate 270° and set occupied PrintSolution(); // For debugging only printf("\n"); // For debugging only if(!isSolution(index) || !isSolution(-1) || !isSolution(-2) || !isSolution(-3)) { if(FindSolution(index + 1, newX, newY)) { return 1; // Found a solution } else { solution[newY][newX] = 0; // Take back move solution[newX][5-newY] = 0; // Rotate 90° and set unoccupied solution[5-newY][5-newX] = 0; // Rotate 180° and set unoccupied solution[5-newX][newY] = 0; // Rotate 270° and set unoccupied } } else { return 1; // Found a solution } } } return 0; } int main(void) { // Start at the house at spielfeld[2][2]. The starting spot is // already set, so begin with index 2. FindSolution(2, 2, 2); PrintSolution(); getch(); return 0; }Danke!
-
Ich befürchte mal, daß dir das keiner wird lösen können.
-
^^frag' doch mal im mathe-forum.
-
Javaner schrieb:
Ich befürchte mal, daß dir das keiner wird lösen können.
du meinst wohl eher, es wird keiner lust haben sich mit son sch... die zeit um die ohren zu schlagen.
-
LOL!!
Naja, wenn du es so deutlich schreibst!
-
Passt schon. Keine Hilfe mehr nötig ...