2010-07-09 7 views
6

Ich arbeite an einem N Queens-Programm, mit dem der Benutzer eine Königin-Konfiguration als String eingeben kann. Zum Beispiel: Wenn Sie dazu aufgefordert werden, könnte der Benutzer etwas wie Q .... Q ..... Q..Q eingeben. die, wenn sie angezeigt, wie ein Brett aussehen würde:Brauchen Sie Hilfe mit N Queens Programm (Überprüfung von Diagonalen)

Q . . . 
. Q . . 
. . . Q 
. . Q . 
Is not a solution! 

Dieses Programm ist einfach, dass sie davon ausgeht, dass der Benutzer gültige Informationen eingeben werden. Ich möchte den Hauptteil des Programms arbeiten lassen, bevor ich zurückgehe und die Fehlerbehandlung hinzufüge.

Für diejenigen, die nicht mit dem N Queens Puzzle vertraut sind, haben Sie grundsätzlich N Queens auf einem N x N Board. Du hast eine Königin pro Reihe. Ein bestücktes Board ist eine Lösung, wenn keine zwei Queens die gleiche Zeile, Spalte oder Diagonale teilen.

Ich habe erfolgreich Prüfungen für die Zeilen und Spalten implementiert. Allerdings bin ich ratlos, wie ich alle Diagonalen überprüfen kann. Ich weiß, wie man die zwei Hauptdiagonalen überprüft, wie im Tic Tac Toe, aber ich kann wirklich nicht visualisieren, wie ich alle möglichen Diagonalen überprüfen kann?

Kann jemand Hilfe anbieten?

Hier ist mein Code:

import java.util.Scanner; 
public class NQueens { 


    public static void main(String[] args) { 

     Scanner sc = new Scanner(System.in); 
     int qCount; 
     boolean solution = true; 


     System.out.println("Enter the String to test:"); 
     board = sc.nextLine(); 

     int boardLen = board.length(); 
     int maxDim = (int) Math.sqrt(boardLen); 
     char[][] gameBoard = new char[maxDim][maxDim]; 


     int counter = 0; 
     for (int i = 0; i < maxDim; i++) 
     { 
      for (int j = 0; j < maxDim; j++) 
      { 
       gameBoard[ i ][ j ] = board.charAt(counter); 
       counter++; 
      } 

     } 


     System.out.println(""); 
     System.out.println(""); 




    //check rows  

    for (int i = 0; i < maxDim; i++) 
    { 
     int queenCount = 0; 

     for (int j = 0; j < maxDim; j++) 
     { 
      if (gameBoard[ i ][ j ] == 'Q') 
      { 
       queenCount++; 


       if (queenCount > 1) 
       { 
        solution = false; 
        break; 

       } 


      } 


     } 

    } 


    // check columns 

    for (int i = 0; i < maxDim; i++) 
    { 
     int queenCount = 0; 

     for (int j = 0; j < maxDim; j++) 
     { 
      if (gameBoard[ j ][ i ] == 'Q') 
      { 
       queenCount++; 

       if (queenCount > 1) 
       { 
        solution = false; 
        break; 
       } 
      } 
     } 
    } 


    // print the board 

    for(int i = 0; i < maxDim; i++) 
    { 
     for (int j = 0; j < maxDim; j++) 
     { 
      System.out.print(gameBoard[ i ][ j ] + " "); 
     } 

     System.out.println(); 

    } 

    // print whether or not the placement of queens is a solution 
    if (solution) 
    { 
     System.out.println("Is a solution!"); 

    } 

    else 
    { 
     System.out.println("Is not a solution!"); 

    } 

    }//end main 

}//end class 

Dank Lesen Sie mehr: Brauchen Sie Hilfe mit N Queens Programm

Antwort

19

Ich glaube nicht, Sie alle Diagonalen überprüfen möchten, aber Sie können alle überprüfen die Königinnen stattdessen. Sie können überprüfen, ob sich zwei Königinnen auf derselben Diagonale befinden, indem Sie die Unterschiede zwischen den Zeilen und Spalten der beiden Qs überprüfen. Wenn die Unterschiede gleich sind, sind sie auf der gleichen Diagonale. (Im Allgemeinen, wenn die Steigung der Linie zwischen den beiden Königinnen + -1 ist, sind sie auf der gleichen Diagonale.)

Zum Beispiel, sagen Sie, Sie haben zwei Königinnen Q1 und Q2. Berechnen Sie den absoluten Wert der Unterschiede in ihren Zeilen und Spalten.

deltaRow = abs(Q1 row - Q2 row) 
deltaCol = abs(Q1 col - Q2 col) 

Wenn deltaRow == deltaCol sind die Königinnen auf der gleichen Diagonalen.

Tun Sie das nur für alle N Königinnen.

+1

Also im Grunde, was Sie sagen, ist, dass ich den x- und y-Wert jeder Königin in einem anderen 2d-Array speichern und dann die Überprüfung durchführen kann, die Sie illustriert haben? – Codebug

+1

@Will: Ja, speichern Sie einfach die x und y für jede Dame und machen Sie die Überprüfung für jedes Paar. –

+2

Brauchen Sie hier keinen absoluten Wert? – shinzou

1

Diagonalen können in Form von y = x + c oder y = c - x ausgedrückt werden. Ihre 4x4-Platine hat insgesamt 10 Diagonalen, 5 für jede Gleichung. Berechnen Sie die cs (sie variieren abhängig von der Boardgröße) und loopen Sie sich auf x, berechnen Sie die y's.

Sie müssen nach Koordinaten suchen, die kleiner als Null sind, die oberen Grenzen können vermieden werden, indem das Brett 2x so groß (in jede Richtung) wie nötig gemacht wird - die anderen Quadrate sind immer leer, so dass sie geprüft werden keinen Schaden.

Ich habe sogar das N Königinnen-Problem ohne Brett überhaupt - verfolgen Sie die Zeilen, Spalten und Diagonalen. Zu der Zeit war das schneller, weil die Addition viel schneller war als die Multiplikation, aber das ist nicht mehr der Fall.

2

Wir können sagen, dass die Königinnen auf der gleichen Diagonale sind, wenn die Steigung der Linie, die die 2 Königinnen verbindet, entweder 1 oder -1 ist.

Lassen q1 und q2 Datenstrukturen sein, die x- und y-Positionen der einzelnen Königin hält:

xDistance = q1.x - q2.x

yDistance = q1.y - q2.y

slope = xDistance/yDistance

So if (slope.abs() == 1) dann sie auf der gleichen Diagonalen sind.

+0

Dies ist ein wenig gefährlich, wenn Sie ganze Zahlen teilen, erhalten Sie eine 1 von 3/2. – shinzou