N Queens All Solutions, Derzeit zeigt 1

Question

Ich schrieb dieses Programm nach einem Monat Debuggen und ich habe es endlich zur Arbeit, aber es druckt nur 1 Lösung für die Königin Problem, weiß jemand, was ich tun kann, um es zu machen alle Lösungen ausdrucken? Code wird hilfreich sein, aber wenn Sie nur darauf hinweisen können, was zu ändern oder was hinzuzufügen, kann ich damit arbeiten.

import java.util.Scanner; 
    public class Queens 
    { 
    // squares per row or column 
    public static final int BOARD_SIZE = 8; 

    // used to indicate an empty square 
    public static final int EMPTY = 0; 

    // used to indicate square contains a queen 
    public static final int QUEEN = 1; 

    private int board[][]; // chess board 

    public Queens() { 
     // ------------------------------------------------- 
     // Constructor: Creates an empty square board. 
     // ------------------------------------------------- 
     board = new int[BOARD_SIZE][BOARD_SIZE]; 
    } // end constructor   

    public void clearBoard() { 
     // ------------------------------------------------- 
     // Clears the board. 
     // Precondition: None. 
     // Postcondition: Sets all squares to EMPTY. 
     // ------------------------------------------------- 
     for(int j = 1; j < 8; j++) 
     { 
      for(int k = 1; k < 8; k++) //Sets every column in this row to 0 
      { 
       board[j][k] = 0; 
      } 
      //moves on to next row and repeats 
     } 
    } // end clearBoard 

    public void displayBoard() { 
     // ------------------------------------------------- 
     // Displays the board. 
     // Precondition: None. 
     // Postcondition: Board is written to standard 
     // output; zero is an EMPTY square, one is a square 
     // containing a queen (QUEEN). 
     // ------------------------------------------------- 
     placeQueens(1); 
     int N = board.length; 
     for (int i = 0; i < N; i++) { 
      for (int j = 0; j < N; j++) { 
       if (board[i][j] == 1) 
       { 
        System.out.print("Q "); 
       } 
       else 
       { 
        System.out.print("_|"); 
       } 
      } 
      System.out.println(); 
     } 
    } // end displayBoard 

    public boolean placeQueens(int column) { 
     // ------------------------------------------------- 
     // Places queens in columns of the board beginning 
     // at the column specified. 
     // Precondition: Queens are placed correctly in 
     // columns 1 through column-1. 
     // Postcondition: If a solution is found, each 
     // column of the board contains one queen and method 
     // returns true; otherwise, returns false (no 
     // solution exists for a queen anywhere in column 
     // specified). 
     // ------------------------------------------------- 
     if (column > BOARD_SIZE) { 
      return true; // base case 
     } 
     else { 
      boolean queenPlaced = false; 
      int row = 1; // number of square in column 

      while (!queenPlaced && (row <= BOARD_SIZE)) { 
       // if square can be attacked 
       if (isUnderAttack(row, column)) { 
        ++row; // consider next square in column 
       } // end if 
       else { // place queen and consider next column 
        setQueen(row, column); 
        queenPlaced = placeQueens(column+1); 
        // if no queen is possible in next column, 
        if (!queenPlaced) { 
         // backtrack: remove queen placed earlier 
         // and try next square in column 
         removeQueen(row, column); 
         ++row; 
        } // end if 
       } // end if 
      } // end while 
      return queenPlaced; 
     } // end if 
    } // end placeQueens 

    private void setQueen(int row, int column) { 
     // -------------------------------------------------- 
     // Sets a queen at square indicated by row and 
     // column. 
     // Precondition: None. 
     // Postcondition: Sets the square on the board in a 
     // given row and column to QUEEN. 
     // -------------------------------------------------- 
     row = index(row); 
     column = index(column); 
     board[row][column] = 1; //Queen placed on square 
    } // end setQueen 

    private void removeQueen(int row, int column) { 
     // -------------------------------------------------- 
     // Removes a queen at square indicated by row and 
     // column. 
     // Precondition: None. 
     // Postcondition: Sets the square on the board in a 
     // given row and column to EMPTY. 
     // -------------------------------------------------- 
     column = index(column); 
     for(int x = 0; x < 8 ; x++) 
     { 
      if(board[x][column] == 1) 
      { 
       board[x][column] = 0; 
       x = 8;  
      } 
     } 

    } // end removeQueen 

    private boolean isUnderAttack(int row, int column) { 
     // -------------------------------------------------- 
     // Determines whether the square on the board at a 
     // given row and column is under attack by any queens 
     // in the columns 1 through column-1. 
     // Precondition: Each column between 1 and column-1 
     // has a queen placed in a square at a specific row. 
     // None of these queens can be attacked by any other 
     // queen. 
     // Postcondition: If the designated square is under 
     // attack, returns true; otherwise, returns false. 
     // -------------------------------------------------- 

     //Taking 1-8 & returning 0-7 to suite array 
     row = index(row); 
     column = index(column); 

     //Checks the rows & columns 
     //Rows 
     for(int i = 0; i < column && i < 8 && row < 8; i++) 
     { 
      //If there's a queen in that row, the queen is under attack 
      if(board[row][i] == 1) 
      { 
       return true; 
      } 
     } 
     //Column 

     for(int j = 0; j < row && j < 8 && column < 8; j++) 
     { 
      //If there's a queen in that column, the queen is under attack 
      if(board[j][column] == 1) 
      { 
       return true; 
      } 
     } 

     //Check diagonals 
     for(int i = row, j = column; i >= 0 && j >= 0 && i < 8 && j < 8; i--, j--) 
     { 
      //checks upper diagonal 
      if(board[i][j] == 1) 
      { 
       return true; 
      } 
     } 

     for(int i = row, j = column; i < board.length && j >= 0 && i < 8 && j < 8; i++, j--) 
     { 
      //checks lower diagonal 
      if(board[i][j] == 1) 
      { 
       return true; 
      } 
     } 
     //At this point the Queen is not being attacked 
     return false; 
    } // end isUnderAttack 

    private int index(int number) { 
     // -------------------------------------------------- 
     // Returns the array index that corresponds to 
     // a row or column number. 
     // Precondition: 1 <= number <= BOARD_SIZE. 
     // Postcondition: Returns adjusted index value. 
     // -------------------------------------------------- 
     return number - 1; 
    }// end index 

    public static void main(String[] args) 
    { 
     Queens eight = new Queens(); 
     eight.displayBoard(); 
    } 
} // end Queens 

Answer 1

Anzeigetafel ist Ihre Fahrroutine; Anstatt es nach dem Anzeigen einer Lösung anhalten zu lassen, wickeln Sie es in eine Schleife ein, die so lange dauert, wie placeQueensneue Lösungen finden können.

Dies bedeutet, dass Sie placeQueens anpassen müssen, um vom vorherigen Board-Zustand fortzufahren. Das tut es bereits in hohem Maße; Sie müssen nur den Fall behandeln, in dem es die letzte Spalte getroffen hat. Zum Beispiel, ziehe die 8. Dame auf ein Feld und gehe von dort weiter, wo du aufgehört hast - oder zurück zur nächsten legalen Position für die 7. Dame (da du weißt, dass es keinen anderen legalen Punkt für den 8. gibt).

Während Sie dies tun, müssen Sie die Schnittstelle zwischen diesen beiden Routinen etwas ändern, so dass placeQueens nicht nur jede Lösung, sondern eine Bedingung zurückgeben kann. Dies teilt displayBoard mit, um aus der Schleife auszubrechen (der neue Wrapper, den Sie hinzugefügt haben).

Ist das genug Beschreibung, um Sie entlang zu bewegen?

---

EDIT nach "Nicht wirklich" Kommentar ...

Vielleicht ist der einfachste Wrapper in Anzeigetafel wäre zu schreiben. An der Spitze, wo Sie placeQueens haben (1), stattdessen verwenden

col = 1 
while(placeQueens(col)) { 
    ... print the board as usual 
    ... remove 8th queen; mark its position as unusable (say, with a value of -1) 
    col = 8 
} 

placeQueens anpassen, so dass es von abholt, wo er aufgehört hat: es wird wollen, dass 8. Königin an der gleichen Stelle setzen. Wenn festgestellt wird, dass der Spot als unbrauchbar markiert wurde, setze die Markierung zurück und gehe zurück zur 7. Dame. Mit dieser Operation können Sie fortfahren und alle Lösungen finden.

Es gibt sauberere Möglichkeiten, dies zu tun, aber ich denke, dass dieses Ihre vorhandene Organisation ausreichend bewahrt. Idealerweise haben Sie ein Treiberprogramm, das den Place-and-Print-Prozess durchläuft, aber dies ist hauptsächlich eine Frage der Benennung und Organisation auf höherer Ebene.

Tut diese Sie bewegen sich gut genug?