八皇后拼圖邏輯錯誤

Question

我正在編寫一個遞歸解決八皇后拼圖的程序，但是我很難把我的腦袋想象成我的程序「迴歸」來解決問題。我的Solve（）方法和我的isOpen（）方法可能都是錯誤的，但我無法弄清楚我做錯了什麼。我有我的代碼在下面（和驅動程序）。對不起，這是很長的，但我會很感激，如果我能得到幾個提示。

注*圖像圖標只是Freddie Mercury的

import java.io.*; 
import java.util.Formatter; 
import javax.swing.*; 

import java.awt.*; 

public class EightQueens extends JFrame { 

// declare class constants as needed 
final int BOARD_DIMENSION = 8; 
final boolean[][] BOARD = new boolean[8][8]; 
// declare instance variables 
PrintWriter output; 
int backtrack; 
int comparison; 
File file; 
// gui components 
JPanel chessPanel; 
JPanel square[]; 
Icon queenIcon; 
JLabel imageLabel; 

// constructor method 
public EightQueens() throws FileNotFoundException { 

    // gui stuff 
    setTitle("8 Queens: Freddie Style"); 
    setPreferredSize(new Dimension(800, 800)); 
    chessPanel = new JPanel(new GridLayout(8, 8)); 
    chessPanel.setPreferredSize(new Dimension(100, 100)); 
    chessPanel.setBackground(Color.BLACK); 
    square = new JPanel[64]; 
    queenIcon = new ImageIcon(getClass().getResource(
      "/resource/mercury.jpg")); 
    JLabel imageLabel = new JLabel("", queenIcon, JLabel.CENTER); 

    // CREATE AND INITIALIZE THE OUTPUT FILE 
    file = new File("TraceQueens.txt"); 
    output = new PrintWriter(file); 

    // CREATE AND INITIALIZE BOARD 
    for (int i = 0; i < 8; i++) 
     for (int j = 0; j < 8; j++) 
      BOARD[i][j] = false; 

    // add the squares to the chess panel 
    for (int i = 0; i < square.length; i++)// adds chess squares to the 
              // board 
    { 
     square[i] = new JPanel(new BorderLayout()); 
     square[i].setBackground(Color.BLACK); 
     chessPanel.add(square[i]); 
    } 
    // this will make the squares the correct colors 
    for (int i = 0; i < BOARD_DIMENSION; i = i + 2) 
     square[i].setBackground(Color.WHITE); 
    for (int i = BOARD_DIMENSION + 1; i < (2 * BOARD_DIMENSION) 
      && i > BOARD_DIMENSION; i = i + 2) 
     square[i].setBackground(Color.WHITE); 
    for (int i = (2 * BOARD_DIMENSION); i < (3 * BOARD_DIMENSION) 
      && i >= (2 * BOARD_DIMENSION); i = i + 2) 
     square[i].setBackground(Color.WHITE); 
    for (int i = (3 * BOARD_DIMENSION) + 1; i < (4 * BOARD_DIMENSION) 
      && i > (3 * BOARD_DIMENSION); i = i + 2) 
     square[i].setBackground(Color.WHITE); 
    for (int i = (4 * BOARD_DIMENSION); i < (5 * BOARD_DIMENSION) 
      && i >= (4 * BOARD_DIMENSION); i = i + 2) 
     square[i].setBackground(Color.WHITE); 
    for (int i = (5 * BOARD_DIMENSION) + 1; i < (6 * BOARD_DIMENSION) 
      && i > (5 * BOARD_DIMENSION); i = i + 2) 
     square[i].setBackground(Color.WHITE); 
    for (int i = (6 * BOARD_DIMENSION); i < (7 * BOARD_DIMENSION) 
      && i >= (6 * BOARD_DIMENSION); i = i + 2) 
     square[i].setBackground(Color.WHITE); 
    for (int i = (7 * BOARD_DIMENSION) + 1; i < (8 * BOARD_DIMENSION) 
      && i > (7 * BOARD_DIMENSION); i = i + 2) 
     square[i].setBackground(Color.WHITE); 

    // puts the chess panel on the EightQueens frame 
    add(chessPanel); 

} // end constructor 

// user interface method used to wrap the parameter representing the first 
// column 
public boolean solve() { 
    return solve(0); 
} 

// recursive method solve 

public boolean solve(int column) { 

    // The Queen has been placed on the board in column 
    int row = 0; 
    BOARD[row][column] = true; 
    output.println("The queen has been placed at [0][" + column + "]"); 

    // if column is beyond the last column, then the problem is solved 
    // base case 
    for(int r = 0; r < BOARD_DIMENSION; r++); 
    if (column == BOARD_DIMENSION) { 
     output.println("The problem has been solved"); 
     output.println("The program backtracked " + backtrack 
       + " times and made " + comparison + " comparisons"); 

     // CLOSE FILE 
     output.close(); 
     // RETURN TRUE 
     return true; 
    } else // attempt a solution from column 
    { 
     output.println("Attempting solution from column " + column); 
     for (int i = 0; i < BOARD_DIMENSION; i++) { 

      if (isOpen(i, column)) { 
       BOARD[i][column] = true; 
       comparison++; 

       // solve the "rest of the board" 
       if (solve(column + 1)) { 
        output.println("The queen has beel placed at [" + i 
          + "] + [" + column + "]"); 
        square[((i * 2) + column)].add(imageLabel, 
          BorderLayout.CENTER);// this converts the 2-d 
                // array location into a 
                // single value to 
                // make it compatible with the gui representation of the 
                // board 
        return true; 
       } 

       else { 

        BOARD[i][column] = false; 
        output.println("the queen has been removed from ["+i+"]["+column+"]"); 
       } 
      } else 
       output.println("The queen cannot be placed at [" + i 
         + "][" + column + "]"); 
     } 
     backtrack++; 
     //output.close(); //This is for testing only 
     return false; 

     // return false to Backtrack to previous column since no squares in 
     // current row will solve problem 
    } 
} 

// Method to verify that the square is open. 
public boolean isOpen(int row, int column) { 
    { 
     for (int i = 0; i < BOARD_DIMENSION; i++)// tests for the same row 
     { 
      if (BOARD[row][i] == true) 
       return false; 
     } 

     for (int i = 0; i < BOARD_DIMENSION; i++)// test for the same column 
     { 
      if (BOARD[i][column] == true) 
       return false; 
     } 

     for (int i = 0; i < BOARD_DIMENSION; i++) 
      // test for diagonal down to the left 
      while (row - 1 >= 0 && column - 1 >= 0) { 
       if (BOARD[row - 1][column - 1] == true) 
        return false; 
      } 

     for (int i = 0; i < BOARD_DIMENSION; i++) 
      // test for diagonal up to the left 
      while (row + 1 < BOARD_DIMENSION && column - 1 >= 0) 
       if (BOARD[row + 1][column - 1] == true) 
        return false; 
    } 
    return true; 
} 

// output the board 
public void printBoard()// this is probably wrong, but 
         // I want to find my mistakes in 
         // the rest of the code before fixing it 
{ 
    for (int i = 0; i < BOARD_DIMENSION; i++) 
     for (int j = 0; j < BOARD_DIMENSION; j++) { 
      if (BOARD[i][j] == false) { 
       System.out.print("*"); 
       if (i == BOARD_DIMENSION - 1) 
        System.out.print("\n"); 
      } 

      else 
       System.out.print("Q"); 
     } 

} 

} // end class EightQueens 

駕駛員的照片：

import javax.swing.*; 
import java.io.*; 
import java.util.*; 

public class EightQueensGame { 
public static void main(String args[]) throws FileNotFoundException { 
    EightQueens eightQueens = new EightQueens(); 

    eightQueens.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 
    eightQueens.pack(); 

    eightQueens.setVisible(true);//just for testing 
    if (eightQueens.solve()) 
    { 
     eightQueens.setVisible(true); 
     eightQueens.printBoard(); 


    } 

    else 
     System.out.println("Sorry, there is no solution"); 
} 
} 

Answer 1

你是在思考這個問題。我必須刪除許多代碼，因爲它是多餘的，可以用更有效的方式實現。檢查這個谷歌代碼庫：https://code.google.com/p/8queens/除了回溯以外的更多方法。順便說一下，您違反了MVC規則。你應該已經實現瞭解算器，然後是用戶界面，這樣你就可以決定改變你的視圖。

EightQueensSolver.java

public class EightQueensSolver { 

    final boolean[][] board ; 
    final int[] queensPositions; 

    public EightQueensSolver(int boardSize) { 
     if(boardSize<4){ 
      throw new RuntimeException("Can not solve boards of size < 4"); 
     } 
     board = new boolean[boardSize][boardSize]; 
     queensPositions = new int[boardSize]; 
    } 

    boolean solve(){ 
     return solve(0); 
    } 

    boolean solve(int row){ 
     for(int col=0;col<board.length;col++){ 

      if(isSafe(row, col)){ 
       //place the queen for now in this spot 
       board[row][col]=true; 
       queensPositions[row] = col; 
       //if we have finished the board, done. 
       if(row==board.length-1) return true; 
       //otherwise keep placing queens on next rows 
       if(solve(row+1)){ 
        //if placing the next queen will make the board solved, OK 
        return true; 
       }else{ 
        //otherwise backtrack and try other move 
        board[row][col]=false; 
       } 
      } 

     } 
     return false; 
    } 

    boolean isSafe(int row,int col){ 
     //no need to test if on the same row, because we 
     //place a single queen on each row. 
     //we only need to check if two queens are on 
     //same column or same diagonal 
     for(int r=0;r<row;r++){ 
      for(int c=0;c<board.length;c++){ 
       if(board[r][c] && (c==col || Math.abs(c-col)==Math.abs(r-row))) 
        return false; 
      } 
     } 
     return true; 
    } 


    void printBoard(){ 
     System.out.println(Arrays.deepToString(board) 
       .replace('[', '\n').replace("]", "") 
       .replace("true", "Q").replace("false", " ") 
     ); 
    } 

    int getQueenColumnPosition(int row){ 
     return queensPositions[row]; 
    } 
} 

EightQueensUI.java

public class EightQueensUI extends JFrame { 

    // gui components 
    Icon queenIcon; 
    JLabel imageLabel; 
    EightQueensSolver solver; 

    // constructor method 
    public EightQueensUI(int boardSize) { 
     super("8 Queens: Freddie Style"); 
     setPreferredSize(new Dimension(800, 800)); 
     getContentPane().setLayout(new GridLayout(boardSize, boardSize)); 
     queenIcon = new ImageIcon(getClass().getResource("circle.png")); 
     solver = new EightQueensSolver(boardSize); 

     solver.solve(); 

     for(int row=0;row<boardSize;row++){ 
      for(int col=0;col<boardSize;col++){ 
       JPanel panel = new JPanel(new BorderLayout()); 
       panel.setBackground((col-row)%2 == 0 ? Color.BLACK : Color.WHITE); 
       if(solver.getQueenColumnPosition(row)==col){ 
        panel.add(new JLabel(queenIcon)); 
       } 
       getContentPane().add(panel); 
      } 
     } 

    } // end constructor 

} // end class EightQueensUI 

EightQueensGame.java

public class EightQueensGame { 
    public static void main(String[] args) throws FileNotFoundException { 
     EightQueensUI eightQueens = new EightQueensUI(8); 

     eightQueens.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 
     eightQueens.pack(); 

     eightQueens.setVisible(true);//just for testing 
     eightQueens.solver.printBoard(); 
    } 
} 

輸出是

Q, , , , , , , , 
, , , , Q, , , , 
, , , , , , , Q, 
, , , , , Q, , , 
, , Q, , , , , , 
, , , , , , Q, , 
, Q, , , , , , , 
, , , Q, , , , 

編輯

我以一個列表，而不是一個矩陣，從而提高計算時間的大電路板尺寸稍微做了一些修改到EightQueensSolver讓它多一點效率。

public class EightQueensSolver { 

    final int[] queensPositions; 

    public EightQueensSolver(int boardSize) { 
     if(boardSize<4){ 
      throw new RuntimeException("Can not solve boards of size < 4"); 
     } 
     queensPositions = new int[boardSize]; 
     Arrays.fill(queensPositions, -1); 
    } 

    boolean solve(){ 
     return solve(0); 
    } 

    boolean solve(int row){ 
     for(int col=0;col<queensPositions.length;col++){ 

      if(isSafe(row, col)){ 
       //place the queen for now in this spot 
       queensPositions[row] = col; 
       //if we have finished the board, done. 
       if(row==queensPositions.length-1) return true; 
       //otherwise keep placing queens on next rows 
       if(solve(row+1)){ 
        //if placing the next queen will make the board solved, OK 
        return true; 
       }else{ 
        //otherwise backtrack and try other move 
        queensPositions[row]=-1; 
       } 
      } 

     } 
     return false; 
    } 

    boolean isSafe(int row,int col){ 
     //no need to test if on the same row, because we 
     //place a single queen on each row. 
     //we only need to check if two queens are on 
     //same column or same diagonal 
     for(int r=0;r<row;r++){ 
      int c = queensPositions[r]; 
      if(c==col || Math.abs(c-col)==Math.abs(r-row)) 
       return false; 
     } 
     return true; 
    } 


    void printBoard(){ 
     for(int row=0;row<queensPositions.length;row++){ 
      for(int col=0;col<queensPositions.length;col++){ 
       if(queensPositions[row]==col) System.out.print("Q,"); 
       else System.out.print(" ,"); 
      } 
      System.out.println(); 
     } 
    } 

    int getQueenColumnPosition(int row){ 
     return queensPositions[row]; 
    } 
} 

Answer 2

我做了一個比已經給出和接受的答案稍微OO的實現。我並不認爲它效率更高，但代碼實際上非常乾淨且易於閱讀。最重要的部分是branch（）方法。但是，它並沒有以任何方式進行優化，它是蠻力的，創建對象等等，使得它不是最好的實現。看看branch（）方法，我認爲這是一種實現回溯的非常乾淨的方法。

import java.util.ArrayList; 
import java.util.List; 


public class EightQueens { 

    public static final int DIMENSION = 20; 
    private Board board; 

    public EightQueens() { 
     board = new Board(); 
    } 

    public void solve() { 
     boolean result = branch(0); 
     System.out.println(result); 
     print(); 
    } 

    private boolean branch(int level) { 
     Queen queen = new Queen(level, 0); 
     for (int y = 0; y < DIMENSION; y++) { 
      queen.setY(y); 
      if (board.add(queen)) { // true: adding succeeded. valid position 
       if (board.getCount() == DIMENSION || branch(level + 1)) { 
        // cond1: we added the last queen at a valid position, so we're done here. 
        // cond2: not adding the last queen => check if there exists subsolution 
        return true; 
       } else { 
        // branch with (level + 1) failed, so remove the queen and go further 
        board.remove(queen); 
       } 
      } 
     } 

     return false; 
    } 

    private void print() { 

     for (int y = 0; y < DIMENSION; y++) { 
      for (int x = 0; x < DIMENSION; x++) { 
       System.out.print(board.queenOn(x, y) ? "x" : "-"); 
      } 
      System.out.print("\n"); 
     } 
    } 

    public static void main(String[] args) { 
     EightQueens queens = new EightQueens(); 
     queens.solve(); 
    } 

    // helper objects: Board and Queen 
    private class Board { 

     private final List<Queen> queens; 

     public Board() { 
      queens = new ArrayList<Queen>(); 
     } 

     public int getCount() { 
      return queens.size(); 
     } 

     public boolean add(Queen queen) { 
      for (Queen q : queens) { 
       // same row 
       if (q.getX() == queen.getX()) 
        return false; 
       // same column 
       if (q.getY() == queen.getY()) 
        return false; 
       // same diagonal 
       if (Math.abs(q.getY() - queen.getY()) == Math.abs(q.getX() - queen.getX())) 
        return false; 
      } 
      queens.add(queen); 
      return true; 
     } 

     public boolean queenOn(int x, int y) { 
      for (Queen queen : queens) { 
       if (queen.x == x && queen.y == y) { 
        return true; 
       } 
      } 
      return false; 
     } 

     public void remove(Queen queen) { 
      queens.remove(queen); 
     } 
    } 

    private class Queen { 
     private int x, y; 

     public Queen(int x, int y) { 
      this.x = x; 
      this.y = y; 
     } 

     public int getX() { 
      return x; 
     } 

     public int getY() { 
      return y; 
     } 

     public void setX(int x) { 
      this.x = x; 
     } 

     public void setY(int y) { 
      this.y = y; 
     } 
    } 
} 

備註＃1：運行此程序與尺寸等於2或3將打印「假」，並且給定尺寸的空板。正確的行爲，因爲這些維度不存在解決方案。

備註＃2：這個程序只找到第一個解決方案，不會繼續尋找更多的解決方案。但這當然不是這個答案的重點。