Hallo
Ich habe momentan eine Übungsaufgabe zu bearbeiten, die Ich nächste Woche abgeben muss. Ich habe schon ein wenig Erfahrung in Java gesammelt, häng trotzdem bei dieser Aufgabe.
Ich freue mich über Lösungsvorschläge. Im voraus Vielen Dank :toll:
Eine Variante von Sudoku heißt Kendoku. Sie besteht aus einer (n n)-Matrix, deren Felder durch
dickere Umrandung zu unterschiedlichen Partitionen Pi zusammengefasst werden. Jedem Pi
ist eine
Operation Oi 2 f+; ; ; =; ’ ’g und deren Endergebnis Ri zugeordnet. Das Kendoku ist gelöst,
wenn in jeder Spalte bzw. jeder Zeile jeweils alle Zahlen von 1 bis n genau einmal so vorkommen,
dass sich bei Anwenden von Oi auf alle Zahlen in Pi das angegebene Ri ergibt.
int[][][] kenken
Jede der im Folgenden zu entwickelnden Methoden wird mit
einem dreidimensionalen int-Array aufgerufen, das ein Kendoku-Problem repräsentieren soll. Eine korrekte Datenstruktur hat exemplarisch nebenstehenden Aufbau: Jeder Eintrag
enthält die Daten einer Partition als zweidimensionales intArray. Der erste Eintrag jeder Partition Pi enthält wiederum
ein eindimensionales int-Array der Länge 2 mit dem (Ri
, Oi)-
Paar. Alle weiteren Einträge von Pi sind ebenfalls eindimensionale int-Arrays der Länge 2 und enthalten die Koordinaten
des zu Pi gehörenden Feldes in der Form (Zeile, Spalte). Das
Feld „oben/links“ im Kendoku hat die Koordinaten (0; 0).
Laden Sie die vorgegebene Datei Kendoku.java von der AuD-Seite herunter und implementieren
Sie darin die einzelnen Methoden gemäß ihrer API wie folgt:
a) Ergänzen Sie zunächst die Methode checkIntegrity(). Sie soll überprüfen, ob das übergebene 3D-Array strukturell als Kendoku-Problem (wie oben beschrieben und im Beispiel-Bild
gezeigt) interpretiert werden kann.
b) Implementieren Sie nun die Methode checkValidity(). Sie soll überprüfen, ob das übergebene 3D-Array semantisch als Kendoku-Problem interpretiert werden kann, d.h. ob die Partitionen überlappungsfrei sind und insgesamt genau ein quadratisches Kendoku abdecken (die
Partitionen selbst müssen dabei nicht zwangsweise zusammenhängend sein).
c) Programmieren Sie schließlich ein rekursives Verfahren zur Lösung eines Kendoku-Problems
in solve(). Falls es mindestens eine Lösung gibt, dann soll solve() eine beliebige davon
als quadratisches Array zurückgeben.
Ich habe momentan eine Übungsaufgabe zu bearbeiten, die Ich nächste Woche abgeben muss. Ich habe schon ein wenig Erfahrung in Java gesammelt, häng trotzdem bei dieser Aufgabe.
Ich freue mich über Lösungsvorschläge. Im voraus Vielen Dank :toll:
Eine Variante von Sudoku heißt Kendoku. Sie besteht aus einer (n n)-Matrix, deren Felder durch
dickere Umrandung zu unterschiedlichen Partitionen Pi zusammengefasst werden. Jedem Pi
ist eine
Operation Oi 2 f+; ; ; =; ’ ’g und deren Endergebnis Ri zugeordnet. Das Kendoku ist gelöst,
wenn in jeder Spalte bzw. jeder Zeile jeweils alle Zahlen von 1 bis n genau einmal so vorkommen,
dass sich bei Anwenden von Oi auf alle Zahlen in Pi das angegebene Ri ergibt.
int[][][] kenken
Jede der im Folgenden zu entwickelnden Methoden wird mit
einem dreidimensionalen int-Array aufgerufen, das ein Kendoku-Problem repräsentieren soll. Eine korrekte Datenstruktur hat exemplarisch nebenstehenden Aufbau: Jeder Eintrag
enthält die Daten einer Partition als zweidimensionales intArray. Der erste Eintrag jeder Partition Pi enthält wiederum
ein eindimensionales int-Array der Länge 2 mit dem (Ri
, Oi)-
Paar. Alle weiteren Einträge von Pi sind ebenfalls eindimensionale int-Arrays der Länge 2 und enthalten die Koordinaten
des zu Pi gehörenden Feldes in der Form (Zeile, Spalte). Das
Feld „oben/links“ im Kendoku hat die Koordinaten (0; 0).
Laden Sie die vorgegebene Datei Kendoku.java von der AuD-Seite herunter und implementieren
Sie darin die einzelnen Methoden gemäß ihrer API wie folgt:
a) Ergänzen Sie zunächst die Methode checkIntegrity(). Sie soll überprüfen, ob das übergebene 3D-Array strukturell als Kendoku-Problem (wie oben beschrieben und im Beispiel-Bild
gezeigt) interpretiert werden kann.
b) Implementieren Sie nun die Methode checkValidity(). Sie soll überprüfen, ob das übergebene 3D-Array semantisch als Kendoku-Problem interpretiert werden kann, d.h. ob die Partitionen überlappungsfrei sind und insgesamt genau ein quadratisches Kendoku abdecken (die
Partitionen selbst müssen dabei nicht zwangsweise zusammenhängend sein).
c) Programmieren Sie schließlich ein rekursives Verfahren zur Lösung eines Kendoku-Problems
in solve(). Falls es mindestens eine Lösung gibt, dann soll solve() eine beliebige davon
als quadratisches Array zurückgeben.
Java:
public class Kendoku {
public static void main(String[] args) {
int[][][] kenken = {
{{ 11, '+'}, {0, 0}, {1, 0}},
{{ 2, '/'}, {0, 1}, {0, 2}},
{{ 20, '*'}, {0, 3}, {1, 3}},
{{ 6, '*'}, {0, 4}, {0, 5}, {1, 5}, {2, 5}},
{{ 3, '-'}, {1, 1}, {1, 2}},
{{ 3, '/'}, {1, 4}, {2, 4}},
{{240, '*'}, {2, 0}, {2, 1}, {3, 0}, {3, 1}},
{{ 6, '*'}, {2, 2}, {2, 3}},
{{ 6, '*'}, {3, 2}, {4, 2}},
{{ 7, '+'}, {3, 3}, {4, 3}, {4, 4}},
{{ 30, '*'}, {3, 4}, {3, 5}},
{{ 6, '*'}, {4, 0}, {4, 1}},
{{ 9, '+'}, {4, 5}, {5, 5}},
{{ 8, '+'}, {5, 0}, {5, 1}, {5, 2}},
{{ 2, '/'}, {5, 3}, {5, 4}}
};
System.out.println("Integrity check : " + (checkIntegrity(kenken) ? "PASSED" : "FAILED"));
System.out.println("Validity check : " + (checkValidity(kenken) ? "PASSED" : "FAILED"));
int[][] solution = solve(kenken);
System.out.println("Solution check : " + (solution != null ? "PASSED" : "FAILED"));
if (solution != null) {
printArray(solution);
}
}
public static boolean checkIntegrity(int[][][] kenken) {
// TODO
return true;
}
public static boolean checkValidity(int[][][] kenken) {
// TODO
return true;
}
public static int[][] solve(int[][][] kenken) {
// TODO
return null;
}
protected static void printArray(int[][] array) {
for (int[] subArray : array) {
for (int val : subArray)
System.out.printf("%1$5d", val);
System.out.println();
}
}
}
