8 Damen problem

[ripper]

Hey leute, ich habe mich mal in java mit dem 8 Damen problem beschäftigt aber komme einfach nicht weiter. Ich habe auch gehört dass man das rekursiv programmieren soll naja soweit bin ich bis jetzt ich hoffe dass ihr mir helfen könnt oder Denkanstöße geben könnt:

public class damen {

  public static void main(String[] args) {
    int [][] brett=new int [8][8];
    damen(brett);
    for(int i=0;i<brett.length;i++){
    System.out.println("\n");
      for(int n=0;n<brett[0].length;n++){
        System.out.print(brett[i][n] +"  ");
      }
    }
  }
  //0=Frei, 1=Dame, 2= Besetzt
  public static int [][] damen(int [][]a) {
    for(int l=0;l<a.length;l++){
      for(int m=0;m<a.length;m++){
       if(a[l][m]==0){
        a[l][m]=1;
         for(int i=1;i<a.length;i++){
           a[i][0]=2;
         }
         for(int n=1;n<a.length;n++){
           a[0][n]=2;
         }
         for(int k=0;k<a.length-1;k++){
           a[k+1][k+1]=2;
         }

       }

      }
    }
    return a;
  }
}

Bis jetzt kann er die erste Dame oben links setzen und alle Felder, die dadurch betroffen sind markieren, mit einer "2". Die "0" ist unbesetzt und die "1" soll die Dame darstellen.

LG,
ripper

 

[Marco13]

Wenn man das brute froce rekursiv löst, nennt man das "Backtracking". Das ist schreeeecklich ineffizient, aber vergleichsweise einfach zu programmieren. Man braucht eigentlich nur 2 1/2 Dinge:
1. Man muss einen Zug machen können (bzw. eine Dame setzen)
2. Man muss alle möglichen Züge auflisten können (bzw. alle Felder bestimmen, auf die eine Dame geetzt werden kann)
1b. Man muss einen Zug komplett rückgängig machen können.

Insebsondere der letzte Schritt ist wichtig. Das geht bei dir jetzt erstmal nicht, wegen der Markeirungen mit einem konstanten Wert: Wenn man einen Zug rückgängig machen will, kann man die 2er-Markierung auf den erreichbaren Feldern nicht einfach wegnehmen, weil es ja sein könnte, dass die Felder noch von einer anderen Dame bedroht werden. Aber mit einer kleinen Änderung an deinem aktuellen Programm wäre das kein Problem. Du könntest Felder, auf denen eine Dame steht, mit -1 markieren. Felder, die nich bedroht sind, haben standardmäßig den Wert 0, und andere Felder.... mal sehen, ob du selbst drauf kommst :wink:

Wenn man die drei oben genannten Operationen hat, ist das Durchsuchen im Pseudocode ungefähr so:

boolean findeLösung()
{
    List möglichkeiten = berechneAlleZugmöglichkeien();
    if (möglichkeiten.size() == 0) 
    {
        if (problem glöst) 
        {
            gibLösungAus();
            return true;
        }
        return false;
    }
    for (Möglichkeit m : möglichkeiten)
    {
        macheZug(m);
        boolean fertig = findeLösung();
        if (fertig) return true;
        macheZugRückgängig(m);
    }
    return false;
}

(Beachte, dass in dem Pseudocode kein einziges mal das Wort "Dame" oder "Spielfeld" vorkommt - also, wenn du mal irgendwan die 4-Färbung eines planaren Graphen mit Backtracking berechnen willst, oder ähnliches...: Einfach "berechneAlleZugmöglichkeien", "macheZug" und "macheZugRückgängig" neu implementieren, und fertig ist das Programm )

Bei 8 Damen wird das Programm aber u.U. schon eine ganze Weile brauchen. Ggf. erstmal mit einem 4x4-Feld und 4 Damen testen.