N-Queens, Java using LinkedList Stack
-
26-05-2021 - |
Question
Working on the N-queens problem. Having some difficult filling up the stack correctly. Was hoping anyone could give me any pointers.
Right now my output is strange..There are only 7 nodes, but my 'success' boolean needs 8 for it to be true. And the head node is 2,1 when I thought it should be 1,2 since I'd be increasing the column.
I know I need to check for the diagonal also, but I'm taking it step by step.
The first thing I need to work out if my conflictCheck method. It never return true (for, yes there is a conflict). I'll update shortly if I figure something out.
Hurray
8, 1
7, 1
6, 1
5, 1
4, 1
3, 1
2, 1
EDIT:
I've made some changes to the code for a more recursive attempt. My new output is this:
The stack
1, 1
End of stack
Pushing next node
The stack
2, 1
1, 1
End of stack
Moving over one column
The stack
2, 2
1, 1
End of stack
problem
Moving over one column
The stack
2, 3
1, 1
End of stack
This is part of the code/work in progress. Right now, it's running into an eternal loop, most likely from that while (conflictCheck)
public static boolean conflictCheck() {
QueenNode temp = head;
//walk through stack and check for conflicts
while(temp!=null) {
//if there is no next node, there is no conflict with it
if (temp.getNext() == null){
System.out.println("No next node");
if (queens.size() < 8 ) {
return false;
}
}
else if (temp.getRow() ==temp.getNext().getRow() || temp.getColumn() == temp.getNext().getColumn() ||
diagonal(temp, temp.getNext())){
return true;
}
}
return false;
}
public static void mover(QueenNode n) {
System.out.println("Moving over one column");
n.setColumn(n.getColumn()+1);
queens.viewPieces();
}
public static void playChess(int k, int total) {
QueenNode temp= head;
while (temp != null) {
System.out.println("Pushing next node");
queens.push(k,1);
queens.viewPieces();
//success
if(k == 8){
System.out.println("Hurray");
success = true;
return;
}
//conflict between pieces, loops through entire board
while (conflictCheck()) {
if (head.getColumn() != 8) {
mover(head);
}
else {
queens.pop();
mover(head);
}
}
playChess(k+1, total);
}
}
public static void main(String[] args) {
queens.push(1, 1);
queens.viewPieces();
success = false;
playChess(2, total);
}
}
Solution
temp != null && temp.getNext()!= null
- for 8th queen the value temp.getNext() is null and it is not printed. Change to:
while (temp != null ) {
System.out.println(temp.getRow() + ", " + temp.getColumn());
temp = temp.getNext();
}
Edit
Change || to &&:
if (temp.getRow() != temp.getNext().getRow() &&
temp.getColumn() != temp.getNext().getColumn()) {
return false;
}
In code queens.push(queens.size()+1, 1);
you always assign 1 as second argument. You should check all possibilities.