2016-05-03 13 views
0

Ich versuche eine Lösung für das Problem der Acht Königinnen zu finden, unabhängig vom Ausgangspunkt. Unten ist meine Solver-Klasse, aber es funktioniert aus irgendeinem Grund nicht, wenn ich die Königin in eine andere Reihe als die erste stelle.Acht-König-Algorithmus für verschiedene Startpunkte

import java.util.*; 
public class Queens { 
    private static int x; 
    private static int y; 
    private static ArrayList<Integer> rows = new ArrayList<Integer>(); 
    public Queens(int index, int row, int pos) { 

    for (int i = 0; i<index; i++) 
     rows.add(i); 
    rows.remove(row); 
    x = pos; 
    y = row; 
    } 

public static boolean solve(int row, int[][] board, int N, int pos) { 
    board[y][x] = 1; 
    System.out.println("row: " + row); 
    for(int i = 0; i < 8; i++) { 
     for(int j = 0; j < 8; j++) { 
     if(board[i][j]==1) System.out.print("Q "); 
     else System.out.print("* "); 
     } 
     System.out.println(); 
    } 
    System.out.println();  
    if(row>=N-1) return true; 
    for(int position = pos; position < N; position++) { 
     if(isValid(board, rows.get(row), position, N)) { 
     board[rows.get(row)][position] = 1; 
     if(!solve(row+1, board, N, 0)) { 
      board[rows.get(row)][position] = 0; 
     } else 
      return true; 
     } 
    } 
    return false; 
    } 

    public static boolean isValid(int[][] board, int y, int x, int N) { 
    int i, j; 
    for(i = 0; i < y; i++) 
     if(board[i][x]==1) 
     return false; 
    i = y - 1; 
    j = x - 1; 
    while((i>=0)&&(j>=0)) 
     if(board[i--][j--]==1) return false; 
    i = y - 1; 
    j = x + 1; 
    while((i>=0)&&(j<N)) 
     if(board[i--][j++]==1) return false; 
    return true; 
    } 
} 

Zum Beispiel, wenn ich die anfängliche Königin an Bord legen [2] [2], das ist die Lösung, die ich erhalte:

Q * * * * * * * 
* * Q * * * * * 
* * Q * * * * * 
* * * * * Q * * 
* * * * * * * Q 
* Q * * * * * * 
* * * Q * * * * 
* * * * * * Q * 

Was mit dem Code falsch? Warum ignoriert es das ursprüngliche Stück? Danke im Voraus.

+0

Wo ist Ihr Debugging-Versuch? Fügen Sie Druckanweisungen an strategischen Orten ein, um den Kontroll- und Datenfluss zu verfolgen. Grabe nach einem bestimmten Problem. Beschreibe es und poste die detaillierte Ausgabe hier. – Prune

Antwort

1

Was sind die Grenzen für die for-Schleife in isValid? Verhindern sie, dass du eine Königin in eine Spalte legst, in der sich eine andere Königin befindet?

Eine ähnliche Frage gilt auch für die While-Schleifen - können sie erkennen, dass es eine Dame auf der Diagonale gibt, aber unter die Sie jetzt platzieren?

+0

Ja, ich erkannte das untenstehende Problem und löste es, aber vergessen zu aktualisieren. Im Grunde brauchte ich noch zwei weitere Bedingungen, die die unteren Diagonalen abtasteten. Trotzdem danke. – paniks