Java: 八皇后问题矩阵不会显示正确的棋盘

Question

抱歉，如果这个 post 不是很清楚，我现在想不通。

我一直在为这个八皇后分配而苦苦挣扎，似乎无法理解为什么两个测试 BoardState 对象显示相同的板，但冲突计数不同，只有一个显示正确董事会有适量的冲突。

下面是 Main class 和 BoardState class（后者用于跟踪给定板的数据）。

如有任何帮助，我们将不胜感激。

棋盘状态Class

package com.company;

import java.util.ArrayList;
import java.util.stream.IntStream;

public class BoardState {
    int[][] board;
    int[][] boardReverse;
    int conflictCount;
    
    public BoardState(int[][]arr){
        this.boardReverse=new int[arr[0].length][arr[0].length];
        this.board=arr.clone();

        for(int i=0;i<arr[0].length;i++){
            for(int j=0; j< arr[0].length; j++){
                this.boardReverse[i][j]=this.board[arr[0].length-1-i][j];
            }
        }
        this.conflictCount=updateConflictCount();
    }
    
    public int updateConflictCount(){
        int count=0;
        for(int i=0;i<board[0].length;i++){
            int rowCount=0;
            //horizontal conflict summing
            for(int j=0; j<board[0].length; j++){
                rowCount+=this.board[i][j];
            }
            count+=((rowCount*(rowCount-1))/2);
            //front diagonal conflict summing
        }
        count+=diagonalCount();
        return count;
    }
    
    //adds each sum of the diagonal to an int array
    public int diagonalCount(){
        int count=0;
        int tempSum=0;
        int j=0;
        int k;
        int i=0;
        //back diagonals

        for(i=0; i< board[0].length; i++){
            k=i;
            j=i;
            i=0;
            while(j>=0){
                tempSum+=this.board[j][i];
                j--;
                i++;
            }
            count+=(tempSum*(tempSum-1))/2;
            tempSum=0;
            i=k;
        }

        for(i=1; i< board[0].length; i++){
            k=i;
            j=board[0].length-1;
            while(i<=board[0].length-1){
                tempSum+=this.board[j][i];
                j--;
                i++;
            }
            count+=(tempSum*(tempSum-1))/2;
            tempSum=0;
            i=k;
        }

        //front diagonals
        for(i=0; i< board[0].length; i++){
            k=i;
            j=i;
            i=0;
            while(j>=0){
                tempSum+=this.boardReverse[j][i];
                j--;
                i++;
            }
            count+=(tempSum*(tempSum-1))/2;
            tempSum=0;
            i=k;
        }

        for(i=1; i< board[0].length; i++){
            k=i;
            j=board[0].length-1;
            while(i<=board[0].length-1){
                tempSum+=this.boardReverse[j][i];
                j--;
                i++;
            }
            count+=(tempSum*(tempSum-1))/2;
            tempSum=0;
            i=k;
        }

        return count;
    }

    public int[][] getBoard() {
        return board;
    }

    public void setBoard(int[][] board) {
        this.board = board;
    }

    public int[][] getBoardReverse() {
        return boardReverse;
    }

    public void setBoardReverse(int[][] boardReverse) {
        this.boardReverse = boardReverse;
    }

    public int getConflictCount() {
        this.setConflictCount(0);
        this.setConflictCount(this.updateConflictCount());
        return conflictCount;
    }

    public void setConflictCount(int conflictCount) {
        this.conflictCount = conflictCount;
    }
    
    public int[][] copyBoard(int[][] arr){
        int[][] copy=new int[arr[0].length][arr[0].length];
        for(int i=0;i<arr[0].length; i++){
            for(int j=0; j<arr[0].length; j++){
                copy[i][j]=arr[i][j];
            }
        }
        return copy;
    }

    public ArrayList<BoardState> getMoves(){
        //get possible moves in each column
        ArrayList<BoardState> prospectives= new ArrayList<BoardState>();
        prospectives.clear();
        int k;
        BoardState temp= new BoardState(this.getBoard().clone());
        for(int i=0; i<board[0].length; i++){
            temp.setBoard(this.copyBoard(this.board));
            temp.setConflictCount(this.getConflictCount());
            for(k=0; k<board[0].length; k++){
                if(board[k][i]==1){
                    temp.board[k][i]=0;
                    break;
                }
            }
            for(int j=0; j<board[0].length; j++){
                temp.board[j][i]=1;
                if(temp.getConflictCount()<this.getConflictCount()){
                    prospectives.add(new BoardState(temp.getBoard()));
                }
                temp.board[j][i]=0;
            }
            temp.board[k][i]=1;
        }
        return prospectives;
    }
}

主要Class

package com.company;

import java.util.Random;
import java.util.ArrayList;

public class Main {
    int restarts = 0;
    int stateChanges = 0;

    static ArrayList<BoardState> NeighborList = new ArrayList<BoardState>();

    public void DisplayBoard(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                System.out.print(arr[i][j] + "  ");
            }
            System.out.println();
        }
    }

    public static void initQueens(int[][] arr) {
        Random rand = new Random();
        for (int i = 0; i < arr[0].length; i++) {
            arr[rand.nextInt(8)][i] = 1;
        }
    }

    public static BoardState initBoard(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                arr[i][j] = 0;
            }
        }

        initQueens(arr);
        return new BoardState(arr);
    }

    public static BoardState findMaxima(BoardState state) {
        BoardState using = state;
        while (true) {
            ArrayList<BoardState> temp = new ArrayList<BoardState>(using.getMoves());
            if (temp.size() == 0) {
                //send to solution testing
                return new BoardState(using.board);
            }

            System.out.println(using.getConflictCount());
            for (int i = 0; i < temp.size(); i++) {
                if (temp.get(i).getConflictCount() < using.getConflictCount()) {
                    using = temp.get(i);
                }
            }
        }
    }

    public static void main(String[] args) {
        // write your code here
        Main testObj = new Main();

        int[][] board = new int[8][8];
        BoardState current = initBoard(board);
        BoardState current2 = initBoard(board);
        BoardState test = new BoardState(board);
        testObj.DisplayBoard(current.board);
        System.out.println("Conflicts: " + current.updateConflictCount());
        System.out.println();
        testObj.DisplayBoard(current2.board);
        System.out.println("Conflicts: " + current2.updateConflictCount());

        /* non-debugging code
        BoardState finalState;
        while (true) {
             finalState=findMaxima(current);
            if (finalState.getConflictCount()==0) {
                break;
            }
            testObj.restarts++;
            System.out.println(testObj.restarts);
            current=testObj.initBoard(board);
        }

        testObj.DisplayBoard(finalState.board);
        System.out.println(testObj.stateChanges);
         */
    }
}

Answer 1

问题是current和current2使用了同一个数组（board）。在 initBoard() 中，您随机设置皇后。所以你首先创建电路板，计算你的冲突计数，然后你覆盖电路板并计算另一个不同的冲突计数，然后你打印电路板两次。但是由于当前的原始板被覆盖了，所以你必须使用相同的板和不同的冲突计数。

Java: 八皇后问题矩阵不会显示正确的棋盘

Java: Eight-Queen problem matrix won't display the right board

java

arrays

matrix