M
Michael789
Gast
HI
Es geht darum dass ich ein 5x5 Array hab mit diesem Rätsel "Es gibt 5 häuser in 5 verschiedenne farben, in jedem wohnt einer mit unterschiedlicher Nationalität, hat ein unetrschiedliches Haustier uswusw.
Das soll mit Bcktracking rekursiv gelöst werden, sollte auch soweit passen.
ABER: Ich verwende oft die Methode isEmpty().
Muss die nicht implementiert werden? Oder kann ich allgemein abfragen ob ein Array null ist mit arr[y][x].isEmpty(); geht das?
Jedenfalls sagt er mir beim Ausführen in Z115: null pointer Exception?! Woran liegt das?
Danke schon mal.
Es geht darum dass ich ein 5x5 Array hab mit diesem Rätsel "Es gibt 5 häuser in 5 verschiedenne farben, in jedem wohnt einer mit unterschiedlicher Nationalität, hat ein unetrschiedliches Haustier uswusw.
Das soll mit Bcktracking rekursiv gelöst werden, sollte auch soweit passen.
ABER: Ich verwende oft die Methode isEmpty().
Muss die nicht implementiert werden? Oder kann ich allgemein abfragen ob ein Array null ist mit arr[y][x].isEmpty(); geht das?
Jedenfalls sagt er mir beim Ausführen in Z115: null pointer Exception?! Woran liegt das?
Danke schon mal.
Java:
public class Einstein
{
/**Spalten Inex der Eigenschaften*/
private static final int NATION = 0;
private static final int HOUSE_COLOR = 1;
private static final int PET = 2;
private static final int DRINK = 3;
private static final int CIGARETTE = 4;
/**Mögliche Werte der Spalten*/
private static String[] nations = {"dane", "swede", "german", "norway", "briton"};
private static String[] houseColors = {"red", "yellow", "green", "white", "blue"};
private static String[] pets = {"cat", "dog", "fish", "bird", "horse"};
private static String[] drinks = {"coffee", "milk", "beer", "water", "tee"};
private static String[] cigarettes = {"pall mall", "dunhill", "marlboro", "winfield", "rothmanns"};
/**Array aller möglichen Attribute*/
private static String[][] properties = {nations, houseColors, pets, drinks, cigarettes};
/**Lösungstabelle*/
private static String[][] table = new String[5][5];
/**Main Methode*/
public static void main (String[] arg)
{
solve(); /**Rekursiv lösen*/
if((pruefeGueltigkeit()==true)&&(pruefeVollstaendigkeit()==true))
{
System.out.println("Einstein geloest");
}
else
{
System.out.println("Keine Loesung moeglich!");
}
}
private static void solve(){
// Falls keine gueltige Loesung entstanden ist, Aufruf abbrechen
if(!pruefeGueltigkeit())
return;
//nächstes freies Feld holen
int[] index = getNextEmpty();
//pruefen ob Tabelle vollstaendig ausgefuellt. Falls ja, Rekursion abbrechen
if(pruefeVollstaendigkeit())
return;
//prüfen aus welcher Spalte das leere feld kommt um zu wissen welche Werte (woerter) ausprobeirt werden muessen
if(index[1]==0){
for(int i=0;i<table[0].length;i++){
table[index[0]][index[1]]=nations[i];
solve();
if(pruefeGueltigkeit()&&pruefeVollstaendigkeit())
return;
}
table[index[0]][index[1]]=null;
}
if(index[1]==1){
for(int i=0;i<table[0].length;i++){
table[index[0]][index[1]]=houseColors[i];
solve();
if(pruefeGueltigkeit()&&pruefeVollstaendigkeit())
return;
}
table[index[0]][index[1]]=null;
}
if(index[1]==2){
for(int i=0;i<table[0].length;i++){
table[index[0]][index[1]]=pets[i];
solve();
if(pruefeGueltigkeit()&&pruefeVollstaendigkeit())
return;
}
table[index[0]][index[1]]=null;
}
if(index[1]==3){
for(int i=0;i<table[0].length;i++){
table[index[0]][index[1]]=drinks[i];
solve();
if(pruefeGueltigkeit()&&pruefeVollstaendigkeit())
return;
}
table[index[0]][index[1]]=null;
}
if(index[1]==4){
for(int i=0;i<table[0].length;i++){
table[index[0]][index[1]]=cigarettes[i];
solve();
if(pruefeGueltigkeit()&&pruefeVollstaendigkeit())
return;
}
table[index[0]][index[1]]=null;
}
}
private static boolean pruefeVollstaendigkeit()
{
for(int i=0;i<table.length;i++)
{
for(int j=0;j<table[0].length;j++)
{
if(table[j][i]==null)
return false;
}
}
return true;
}
public static boolean pruefeGueltigkeit()
{
/**Ueberprueft ob ein Eintrag doppelt vorkommt.
In keine Spalte darf ein Eintrag doppelt vorkommen. Regeln 1-4*/
for(int propertyIdx=0; propertyIdx < table[0].length; propertyIdx++)
{
for(int houseIdx1=0; houseIdx1 < table.length-1; houseIdx1++)
{
for(int houseIdx2=houseIdx1+1; houseIdx2 < table.length; houseIdx2++)
{
if(table[houseIdx1][propertyIdx].isEmpty())
{
continue;
}
/**Wenn ein Eintrag doppelt vorkommt*/
if(table[houseIdx1][propertyIdx].equals(table[houseIdx2][propertyIdx]))
{
return false;
}
}
}
}
/**Ueberpruefen der Regeln fuer jede Zeile, eine Zeile entspricht einem Haus
* Wenn eine Regel verletzt wird wird false zurückgegeben*/
for(int houseIdx=0; houseIdx < table.length; houseIdx++)
{
/**Regel 5; Der Norweger wohnt im ersten Haus, houseIdx ==0 => erstes Haus*/
if(houseIdx==0)
{
if(!table[houseIdx][NATION].isEmpty()&&!table[houseIdx][NATION].equals("norway"))
{
return false;
}
}
if(!table[houseIdx][NATION].isEmpty()&&table[houseIdx][NATION].equals("briton")&&table[houseIdx][PET].equals("cat"))
return false;
if(!table[houseIdx][NATION].isEmpty()&&table[houseIdx][NATION].equals("german")&&table[houseIdx][CIGARETTE].equals("rothmanns")&&!table[houseIdx][DRINK].equals("coffee"))
return false;
if(houseIdx==0&&table[houseIdx][HOUSE_COLOR].equals("white"))
return false;
else if(houseIdx==4&&table[houseIdx][HOUSE_COLOR].equals("green"))
return false;
else if(houseIdx!=4&&table[houseIdx][HOUSE_COLOR].equals("green")&&!table[houseIdx][HOUSE_COLOR+1].isEmpty()&&!table[houseIdx][HOUSE_COLOR+1].equals("white"))
return false;
if(!table[houseIdx][CIGARETTE].equals("pall mall")&&!table[houseIdx][PET].isEmpty()&&!table[houseIdx][PET].equals("bird"))
return false;
}
/**keine Regel verletzt*/
return true;
}
/**Diese Methode liefert ein zweidimensionales Array mit den Koordinaten des naechsten freien Feldes*/
public static int[] getNextEmpty()
{
int[] a1 = new int[2];
a1[0]=-1;
a1[1]=-1;
for(int i=0;i<table[0].length;i++)
{
for(int j=0;j<table.length;j++)
{
if(table[i][j]==null)
{
a1[0]=i;
a1[1]=j;
return a1;
}
}
}
return a1;
}
}
