'Java: Eight-Queen problem matrix won't display the right board
Sorry if this post isn't very clear, I'm not think straight right now.
I have been struggling with this Eight Queens assignment and can't seem to understand why the two test BoardState objects display the same board, but differ in conflict count, with only one of them showing the right board with the right amount of conflicts.
Below is the Main class and the BoardState class(the latter being used to keep track of data about a given board).
Any help would be much appreciated.
BoardState 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;
}
}
Main 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);
*/
}
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
