8 Damen Problem

[ven000m]

Hallo,

hat jemand vielleicht eine Lösung zum 8. Damen Problem, ich hab selber schon gesucht, finde aber immer nur JAVA Swing Anwendungen, keine Konsolenausgabe oder halt eine leichtere Ausgabe, die sich mehr auf das Problem statt der grafischen Anwendung hinwendet.

Hat da jemand was?

 

[Johanness]

Guckst Du hier:
http://en.wikipedia.org/wiki/Eight_queens_puzzle


Johannes

 

[ven000m]

zzzzZZZzzzz

 

[ven000m]

so ich hab mich mal rangesetzt und eine gute Lösung gefunden die ich bis auf Kleinigkeiten auch verstehe..

import java.io.*;

class AchtDamenProblem
{ 
	static int       damen=8; // damenanzahl
	static boolean[] zeileFrei;
	static boolean[] steigDiagFrei;
	static boolean[] fallDiagFrei;
	static int[]     posInSpalte; // merken, wo man ist
	static int       loesungsAnzahl=0;

  static void initArrays()
  { zeileFrei     = new boolean[damen+1];
    steigDiagFrei = [b]new boolean[2*damen];[/b]
    fallDiagFrei  =[b] new boolean[2*damen+1];[/b]
    posInSpalte   = new int[damen+1];
    
    // Erst mal alles auf true, d.h. alles frei
    for (int i=1; i<=damen; i++)     zeileFrei[i]     = true;
    for (int i=1; i<=[b]2*damen-1;[/b] i++) steigDiagFrei[i] = true;
    for (int i=2; i<=2*damen; i++)   fallDiagFrei[i]  = true;
    for (int i=1; i<=damen; i++)     posInSpalte[i]   = 0;
  } // initArrays

  static void loesungAusgeben()
  {  for (int spalte=1; spalte<=damen; spalte++)
          	//System.out.print(posInSpalte[spalte]);
  			//System.out.print(" ");
     loesungsAnzahl++;
  } // loesungAusgeben

  // TEILE WURDEN ENTFERNT DAS ES ÜBERSICHTLICHER IST!!



  static boolean nichtBedroht(int x, int y)
  { return (zeileFrei[y] &&steigDiagFrei[damen+y-x] &&fallDiagFrei[x+y]);
  } // nichtBedroht

  

  public static void main(String[] arg)throws IOException
  { System.out.println("Das Programm bestimmt alle Loesungen des N-Damen-Problems.");
    System.out.print("Wie viele Damen sollen gesetzt werden? ");
    damen = io.readInteger();
    initArrays();
    probiereDameZuSetzen(1); // 1. Dame in 1. Spalte setzen
    System.out.println();
    System.out.println("Es ergaben sich "+loesungsAnzahl+" Loesungen.");
  } // main
} // class Damen

Weiß jemand wofür das *2 ist?
Die diagonalen Felder sind doch auch nur max. 8 bei einem 8x8 Schachbrett?

Diese -1 bedeutet, ich bin immer eine Zeile oder Spalte daneben, was dann diese Diagonale erzeugt?

Gruß

 

[norman]

zeig doch bitte deine probiereDameZuSetzen()


zu deiner Frage: 2*damen-1 ergibt die anzahl aller steigenden oder fallenden diagonalen. hast du ein feld mit 3x3 feldern, ist die längste diagonale 3 felder lang, richtig. aber insgesamt gibt es in dem feld 5 diagonalen (obwohl 2 davon (die ecken) keine wirklichen diagonalen sind). und diese 5 wird mit 2*3-1 errechnet. du kannst das ja mal an einem kariertem blatt papier nachvollziehen.
jedenfalls muss zu beginn ja JEDE reihe und JEDE spalte und JEDE diagonale (sowohl steigend als auch fallend) auf FREI gesetzt werden, auch wenn hier die felder alle in mehreren arrays vorkommen.

grüße