0

我正在编写一个程序来递归地解决八皇后难题，但是我很难弄清楚我应该如何让我的程序“回溯”来解决问题。我的 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");
}
}
4

2 回答 2

1

你想多了这个问题。我不得不删除您的许多代码，因为它是多余的并且可以通过更有效的方式来实现。检查此 google 代码存储库：https ://code.google.com/p/8queens/了解除回溯之外的更多方法。顺便说一句，您在这里违反了 MVC 规则。你应该已经实现了求解器然后是用户界面，这样你就可以决定改变你的视图。

八皇后求解器.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];
    }
}

八皇后UI.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

八皇后游戏.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];
    }
}
于 2012-10-01T06:04:50.797 回答
0

我做了一个比已经给出和接受的答案更面向对象的实现。我并没有声称它更有效，但代码实际上非常干净且易于阅读。最重要的部分是 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：在 DIMENSION 等于 2 或 3 的情况下运行此程序将打印“false”，以及给定尺寸的空板。正确的行为，因为这些维度不存在解决方案。

备注#2：这个程序只找到第一个解决方案，而不是继续寻找更多的解决方案。但这当然不是这个答案的重点。

于 2012-10-17T13:58:28.400 回答