public static void placeQueens(int boardSize)
{
stack s = new stack();
boolean success = false;
// row = location within the stack, column = the element placed in the stack
s.push(1);
while (!success && s.top != null)
{
int x=0; // placeholder for when we pop values
boolean conflict = false;
// check for conflicts
for (int i=1; i<s.size(); i++)
{
int deltarows = s.size()-i;
//check if same column or same diagonal
// No need to check if it's on the same row, because we're actually moving row by row
if (s.getTop()==s.get(i) || s.getTop()==s.get(i)+deltarows || s.getTop()==s.get(i)-deltarows)
conflict = true;
}
if (conflict)
{
while (s.getTop()==boardSize)
x=s.pop();
if (s.top != null) // if the top is not null we push to the next spot after poping the previous queen
s.push(s.pop()+1);
else
s.push(x+1);
}
else if (!conflict && s.size()==boardSize)
{
// If there's no more conflict and the stack size is equal to the board size then we're done
success = true;
}
else
{
// new row, column 1
s.push(1);
}
}
s.showAll();
for (int x=1; x<=boardSize; x++)
for (int y=1; y<=boardSize; y++)
System.out.println("(" + x + ", " + y + "): " + s.get(x) + " == " + y + " -> " + (s.get(x) == y));
// print out the board with the queens
for (int x=1; x<=boardSize; x++)
{
for (int y=1; y<=boardSize; y++)
{
if (s.get(x)==y)
System.out.print("Q ");
else
System.out.print("* ");
}
System.out.println();
}
}
output:
please enter board size (n >= 4):
4
3 - 1 - 4 - 2
(1, 1): 2 == 1 -> false
(1, 2): 2 == 2 -> true
(1, 3): 2 == 3 -> false
(1, 4): 2 == 4 -> false
(2, 1): 4 == 1 -> false
(2, 2): 4 == 2 -> false
(2, 3): 4 == 3 -> false
(2, 4): 4 == 4 -> true
(3, 1): 1 == 1 -> true
(3, 2): 1 == 2 -> false
(3, 3): 1 == 3 -> false
(3, 4): 1 == 4 -> false
(4, 1): 3 == 1 -> false
(4, 2): 3 == 2 -> false
(4, 3): 3 == 3 -> true
(4, 4): 3 == 4 -> false
* Q * *
* * * Q
Q * * *
* * Q *
I didn't pay attention to my stack class, so i added this code to make sure where's the problem because i wasn't getting any Q placed, so my condition was always returning false.
for (int x=1; x<=boardSize; x++)
for (int y=1; y<=boardSize; y++)
System.out.println("(" + x + ", " + y + "): " + s.get(x) + " == " + y + " -> " + (s.get(x) == y));
The "get" function was always returning a 0, so i noticed it was from the stack class.
The n-queens exercise is about placing n queens on a n*n board, with no queens attacking each other.
About the algo, I was placing the queens column as the element in the stack and the row as the position in the stack.