我正在研究 n-queens 问题，并且正在测试我目前所拥有的东西，看看我的逻辑是否正确。我的循环停止输出并在调整第二个皇后块后进入无限循环，以免发生冲突。
我不认为我的逻辑会陷入无限循环，基本上是：Push (1,1)
检查冲突
如果冲突，调整顶部皇后，如果无法调整，弹出，调整新顶部
如果没有冲突并且大小 < 8，则 push (size+1, 1) -这显然是一个冲突
检查冲突等
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 ) {
System.out.println("No problems");
return false;
}
}
else if (temp.getRow() ==temp.getNext().getRow() || temp.getColumn() == temp.getNext().getColumn() ||
diagonal(temp, temp.getNext())){
System.out.println("There's a conflict");
return true;
}
}
return false;
}
public static void playChess() {
System.out.println("Playing chess");
if (conflictCheck()) {
if (head.getColumn() == 8) {
queens.pop();
}
if (!queens.isEmpty()) {
System.out.println("Adjusting head");
head.setColumn(head.getColumn()+1);
System.out.println("Head is now " + head.getRow() + ", " + head.getColumn());
playChess();
}
}
else if (!conflictCheck() && queens.size() < 8) {
System.out.println("Stack isn't full yet");
queens.push(queens.size()+1,1);
playChess();
}
else {
success= true;
System.out.println("Success");
queens.viewPieces();
return;
}
}
public static void main(String[] args) {
queens.push(1, 1);
queens.viewPieces();
success = false;
playChess();
}
}
我的输出是：
The stack
1, 1
End of stack
Playing chess
No next node
No problems
No next node
No problems
Stack isn't full yet
Playing chess
There's a conflict
Adjusting head
Head is now 2, 2
Playing chess
problem
There's a conflict
Adjusting head
Head is now 2, 3
Playing chess